levenshteinDistance<E> function

int levenshteinDistance<E>(
  1. List<E> source,
  2. List<E> target, {
  3. DualEqualityTest<E, E>? test,
})

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

Parameters

  • source and target are two list of items.
  • test is an optional equality matcher.

Details

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

The Levenshtein distance allows three types of operations:

  • insertions: insert a single item anywhere in the source list
  • deletions: delete a single item from the source
  • substitutions: replace one item with another 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 and m is the length of target,
Complexity: Time O(nm) | Space O(n)

Implementation

int levenshteinDistance<E>(
  List<E> source,
  List<E> target, {
  DualEqualityTest<E, E>? test,
}) {
  if (source.length > target.length) {
    // since this is symmetric, we can swap them to optimize the inner loop
    List<E> t = target;
    target = source;
    source = t;
  }
  if (test == null) {
    return levenshteinDistanceDefault(source, target);
  }
  return levenshteinDistanceCustom(source, target, test);
}