3 ms·

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

• Sniffnoy 14y ago
  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.
  • malkia 14y ago
    Thanks, Sniffnoy!