Edit Distance

Put your strings in the text boxes and submit the form. You may have the strings normalised first (they will be converted to lowercase and stripped of spaces). The edit distance between the two strings will be computed (using Levenshtein's algorithm) and displayed, along with the similarity (1 minus the edit distance as a fraction of the length of the longer string).

String A
String B
Normalise?

Use this version if you also want a representation of the differences between the strings.

String A
String B
Normalise?

You can read the source code to the plain or deluxe (which relies on a separate library file) versions if you like. Note that the code doesn't implement Levenshtein's algorithm as it is usually written; rather, it turns it inside out and uses a more functionally-oriented form which the author thinks is easier to understand. The 'distance' function is memoised (its results are cached) to allow reuse of computations and so save time. A version without memoisation would be simpler, but would run extremely slowly. Instead of a dictionary, memo could be a matrix; this would be faster, and more convenient in languages like C and Java. In fact, if memo was a matrix, it would end up with exactly the same values as the matrix in the conventional algorithm!