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

Question

我同时使用 Daitch-Mokotoff soundexing 和 Damerau-Levenshtein 来确定用户条目和应用程序中的值是否“相同”。

Levenshtein 距离是否应该用作绝对值？如果我有一个 20 个字母的单词，距离 4 还不错。如果单词有 4 个字母...

我现在正在做的是取距离/长度来得到一个距离，以更好地反射(reflect)单词已更改的百分比。

这是一种有效/经过验证的方法吗？还是单纯的愚蠢？

Answer 1

Is Levenshtein distance supposed to be used as an absolute value?

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

I am using both Daitch-Mokotoff soundexing and Damerau-Levenshtein to find out if a user entry and a value in the application are "the same".

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

你在做拼写检查吗？或者使无效输入符合一组已知的值？
你的优先事项是什么？

尽量减少误报(尽量确保所有建议的单词都非常“相似”，并且建议列表很短)

尽量减少漏报(尽量确保用户想要的字符串在建议列表中，即使它使列表很长)

最大化平均匹配精度

您最终可能会以一种方式使用 Levenshtein 距离来确定是否应在建议列表中提供某个单词；以及另一种确定如何对建议列表进行排序的方法。

在我看来，如果我正确地推断出您的目的，那么您要衡量的核心内容是相似性而不是两个字符串之间的差异。因此，您可以使用 Jaro or Jaro-Winkler distance ，它考虑了字符串的长度和共同的字符数:

The Jaro distance dj of two given strings s1 and s2 is

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

where:

• m is the number of matching characters
• t is the number of transpositions

Jaro–Winkler distance uses a prefix scale p which gives more favourable ratings to strings that match from the beginning for a set prefix length l.