

This post is confusingly written. As the author points out, the issue is not with Damerau-Levenshtein distance, which certainly does obey the triangle inequality; rather the issue is with the incorrect algorithm used to compute it. Nonetheless, after the initial introduction he usually refers to it as "Damerau-Levenshtein" when in fact it's an incorrect version of Damerau-Levenshtein.

The difference he's pointing out isn't that Levenshtein obeys the triangle inequality but Damerau-Levenshtein doesn't; it's that a naive algorithm to compute Levenshtein works, but a naive algorithm to compute Damerau-Levenshtein doesn't -- and that the measure it does compute does not obey the triangle inequality.

While it's clear that the author recognizes this, he should really be more explicit and avoid conflating terms like this; this sort of thing is going to confuse people.

according to wikipedia Damerau-Levenshtein does not obey the triangle inequality - http://en.wikipedia.org/wiki/Damerau–Levenshtein_distance#Ap...


Read more closely -- it's the "restricted edit distance" which does not obey the triangle inequality, which, if you read the "Algorithm" section, is not actually the same thing as Damerau-Levenshtein distance. (Notice also how the section you point to makes sure to differentiate between restricted edit distance and real edit distance, i.e. Damerau-Levenshtein distance.)

That Damerau-Levenshtein distance obeys the triangle inequality follows trivially from the definition, since it's just distance in an appropriate graph.


Thanks, Sniffnoy!

