相似性得分 - 列文施泰因

java levenshtein-distance similarity

2022-09-01 12:42:11

我在Java中实现了Levenshtein算法，现在得到了该算法所做的更正，即成本。这确实有一点帮助，但不是很多，因为我希望结果是百分比。

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

我也想知道你们是怎么做到的，为什么。

答案 1

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

因此，Levenshtein 距离为 0 表示：两个字符串相等
Levenshtein 的最大距离（所有字符都不同）为 max（string1.length， string2.length）

因此，如果您需要百分比，则必须使用此百分比来缩放。例如：

“Hallo”，“Hello” -> 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));

答案 2

您可以下载Apache Commons StringUtils并研究（并可能使用）他们的Levenshtein距离算法的实现。