Hacker Timesnew | past | comments | ask | show | jobs | submitlogin

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!




Consider applying for YC's Summer 2026 batch! Applications are open till May 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: