module Edits::RestrictedEdit
Overview
Implements Restricted Damerau-Levenshtein distance (Optimal Alignment) algorithm.
Determines distance between two strings by counting edits, identifying:
- Insertion
- Deletion
- Substitution
- Adjacent transposition
This variant is restricted by the condition that no sub-string is edited more than once.
Extended Modules
Defined in:
edits/restricted_edit.crClass Method Summary
-
.distance(str1, str2, max : Int)
Calculate the Restricted Damerau-Levenshtein distance (Optimal Alignment) of two sequences, bounded by a maximum value.
-
.distance(str1, str2)
Calculate the Restricted Damerau-Levenshtein distance (Optimal Alignment) of two sequences.
Class Method Detail
def self.distance(str1, str2, max : Int)
#
Calculate the Restricted Damerau-Levenshtein distance (Optimal Alignment) of two sequences, bounded by a maximum value.
Edits::RestrictedEdit.distance("cloud", "crayon") # => 5
Edits::RestrictedEdit.distance("cloud", "crayon", 2) # => 2
def self.distance(str1, str2)
#
Calculate the Restricted Damerau-Levenshtein distance (Optimal Alignment) of two sequences.
Note: Not a true distance metric, fails to satisfy triangle inequality.
RestrictedEdit.distance("iota", "atom") # => 3