News for hackers. Stuff that matters.

A comment on Levenshtein Distance. Parent comment

Re:Levenshtein Distance by mceachen on Thursday August 22, 2019 @06:50PM (#20773089)
I may be misunderstanding you, but an orderless sum of characters in a string won't be an effective prefilter for any string similarity algo.

Think "atc" and "cat". Same sum.

[ Parent | on HN ]
Re:Levenshtein Distance by msvan on Thursday August 22, 2019 @08:14PM (#20773574)
The sum forms a necessary but not sufficient condition for being within a certain Levenshtein distance. In your example, the inequality I gave above does not apply since |c1-c2| = 0. You would have to calculate the Levenshtein distance. In cases where the inequality is satisfied, you do not have to calculate the Levenshtein distance at all.

The idea is that any edit operation on a string will at most change the letter sum by |A|.

[ Parent | on HN ]