相似度得分 - Levenshtein

Question

我在Java中实现了Levenshtein算法,现在我正在通过算法进行校正,即成本.这确实有点帮助,但不多,因为我希望结果为百分比.

所以我想知道如何计算这些相似点.

我也想知道你们这样做的原因以及原因.

Answer 1

两个字符串之间的Levenshtein距离定义为将一个字符串转换为另一个字符串所需的最小编辑数,允许的编辑操作是单个字符的插入,删除或替换.(维基百科)

• 所以Levenshtein距离为0意味着:两个弦都相等
• 最大Levenshtein距离(所有字符都不同)是max(string1.length,string2.length)

因此,如果您需要一个百分比,您必须使用它来指向比例.例如:

"你好","你好" - > Levenstein距离1这两个字符串的Max Levenstein距离是:5.所以20%的字符不匹配.

String s1 = "Hallo";
String s2 = "Hello";
int lfd = calculateLevensteinDistance(s1, s2);
double ratio = ((double) lfd) / (Math.max(s1.length, s2.length));

Answer 2

您可以下载Apache Commons StringUtils并调查(并可能使用)他们的Levenshtein距离算法的实现.