Levenshtein Distance vs Damerau Levenstein vs Optimal String Alignment Distance

Question

Could anyone explain in simple words (and maybe with an example) what the difference between the Levenshtein Distance, Damerau Levenstein, and Optimal String Alignment Distance? When would one use one over the other distance algorithm?

And the Math behind calculating distance between the strings

Links to other resources are also appreciated.

Answer 1

For two strings, a and b:

1. Levenshtein Distance: The minimal number of insertions, deletions, and symbol substitutions required to transform a into b.
2. Damerau Levenstein: Like the Levenstein Distance, but you can also use transpositions (swapping of adjacent symbols).
3. Optimal String Alignment Distance: Like Damerau Levenstein, but you are not allowed to apply multiple transformations on a same substring (e.g. first transpose two symbols, then insert a third between them).

The distances can all be computed using dynamic programming.

In my opinion, the Wikipedia page explains it quite well.

If you are interested in books, you can try Gusfield's "Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology" (and others your online book shop might recommend to you after you search for the above).

Answer 2

I presume you understand the general purpose behind the algorithms. I.e. compute the 'distance' in respect to how many 'edits' it would take to transform string A so that it equals string B. The algorithms for this (in general) are constrained by 'types' of edits it can handle when evaluating.

The Levenshtein computes the distance taking three possible ways into account, insertions, deletions or substitutions, of single characters. The Wikipedia article covers the details beyond what would make sense to attempt here, https://en.wikipedia.org/wiki/Levenshtein_distance.

The Damerau-Levenshtein variant adds a fourth way, the ability to account for transposition of two adjacent characters, as a possible step. Again, Wikipedia coverage is extensive and comparative to the other methods, https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance.

The Optimal String Alignment adds a similar fourth way. Though it is similar, it's not the same as the 'true' Damerau-Levenshtein algorithm above. OSA is covered in the D-L article above.

Attempting to explain in short, the algorithms keeps a matrix of minimum costs at the character intersects based on the 3/4 ways of comparing edit costs when iterating through the two strings.

Examine the two example matrices in the Levenshtein article above, to understand how the matrix forms.

Here's an article that explains it: https://people.cs.pitt.edu/~kirk/cs1501/Pruhs/Spring2006/assignments/editdistance/Levenshtein%20Distance.htm,

There is also a third article on 'edit distance' in general: https://en.wikipedia.org/wiki/Edit_distance

Other than these articles, you can search the Internet because there are lots of information out there. The main thing is not to drown in lingo. The algorithms are actually simple (i.e. elegant) which sometimes makes people think too much.