damerauLevenshteinDistanceOf function

int damerauLevenshteinDistanceOf(
  1. String source,
  2. String target, {
  3. bool ignoreCase = false,
  4. bool ignoreWhitespace = false,
  5. bool ignoreNumbers = false,
  6. bool alphaNumericOnly = false,
})

Finds the Damerau–Levenshtein distance between two strings which allows deletion, insertion, substitution and transposition using Wagner–Fischer algorithm

Parameters

  • source and target are two strings.
  • if ignoreCase is true, the character case shall be ignored.
  • if ignoreWhitespace is true, space, tab, newlines etc whitespace characters will be ignored.
  • if ignoreNumbers is true, numbers will be ignored.
  • if alphaNumericOnly is true, only letters and digits will be matched.

TIPS: You can pass both ignoreNumbers and alphaNumericOnly to true to ignore everything else except letters.

Details

Edit distance is a way to quantify how dissimilar two strings are to one another by counting minimum number of single-character operations required to transform one string to the other.

This variation of edit distance algorithm allows 4 types of operations:

  • insertions: insert a single character anywhere in the source
  • deletions: delete a single character from the source
  • substitutions: replace one character with another in the source
  • transposition: swap two adjacent characters in the source

This functions returns the minimum number of these operations required to transform source into target without modifying their contents.

If n is the length of source, m is the length of target, and k is the number of unique characters appearing on the string,
Complexity: Time O(nm log k) | Space O(nm + k)

Implementation

int damerauLevenshteinDistanceOf(
  String source,
  String target, {
  bool ignoreCase = false,
  bool ignoreWhitespace = false,
  bool ignoreNumbers = false,
  bool alphaNumericOnly = false,
}) {
  source = cleanupString(
    source,
    ignoreCase: ignoreCase,
    ignoreWhitespace: ignoreWhitespace,
    ignoreNumbers: ignoreNumbers,
    alphaNumericOnly: alphaNumericOnly,
  );
  target = cleanupString(
    target,
    ignoreCase: ignoreCase,
    ignoreWhitespace: ignoreWhitespace,
    ignoreNumbers: ignoreNumbers,
    alphaNumericOnly: alphaNumericOnly,
  );
  return damerauLevenshteinDistanceDefault(source.codeUnits, target.codeUnits);
}