计算相对Levenshtein距离 - 有意义吗？

Question

我正在使用Daitch-Mokotoff soundexing和Damerau-Levenshtein来查明用户条目和应用程序中的值是否"相同".

Levenshtein距离应该被用作绝对值吗？如果我有一个20个字母的单词,那么4的距离就不那么糟了.如果这个单词有4个字母......

我现在正在做的是取距离/长度来获得更好地反映单词的百分比变化的距离.

这是一种有效/经证实的方法吗？还是愚蠢的？

Answer 1

Levenshtein距离应该被用作绝对值吗？

这似乎取决于您的要求.(澄清一下:Levenshtein距离是一个绝对值,但正如OP指出的那样,原始值可能不如给定应用程序那么有用,因为它会考虑到单词的长度.这是因为我们真的对距离本身的相似性更感兴趣.)

我正在使用Daitch-Mokotoff soundexing和Damerau-Levenshtein来查明用户条目和应用程序中的值是否"相同".

听起来你正在试图确定用户是否希望他们的条目与给定的数据值相同？

你在做拼写检查吗？或者将无效输入符合一组已知值？你的首要任务是什么？

• 最大限度地减少误报(尽量确保所有建议的单词都非常"相似",建议清单很短)
• 最大限度地减少漏报(尝试确保用户想要的字符串在建议列表中,即使它使列表变长)
• 最大化平均匹配精度

您最终可能会以一种方式使用Levenshtein距离来确定是否应在建议列表中提供单词; 以及确定如何订购建议清单的另一种方法.

在我看来,如果我正确地推断出你的目的,那么你想要测量的核心东西是相似性而不是两个字符串之间的差异.因此,您可以使用Jaro或Jaro-Winkler距离,它考虑了字符串的长度和共同的字符数:

两个给定字符串s1和s2的Jaro距离dj是

(m / |s1| + m / |s2| + (m - t) / m) / 3

哪里:

• m是匹配字符的数量
• t是换位次数

Jaro-Winkler距离使用前缀标度p,它对从设置前缀长度l的开头匹配的字符串给出更有利的评级.