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

Question

我正在使用 Daitch-Mokotoff 算法和 Damerau-Levenshtein 算法来判断用户输入和应用程序中的值是否“相同”。

Levenshtein 距离是否应该被用作绝对值？如果一个单词有 20 个字母，距离为 4 就不算太糟糕。但如果这个单词只有 4 个字母……

我现在所做的是将距离 / 长度以获得更好地反映单词已被修改的百分比的距离。

这是一个有效/可行的方法吗？还是说它很愚蠢？

- Joseph Tura

---

这不是一个非常愚蠢的方法，它以前已经被使用过并取得了一些成功。不过还有更好的措施。 - Fred Foo

你认为那些是什么？ - Joseph Tura

Answer 1

Levenshtein距离是否应该被用作绝对值？看起来这取决于您的要求。（澄清一下：Levenshtein距离是一个绝对值，但正如OP指出的那样，原始值可能不如考虑单词长度的度量对于给定应用程序更有用。这是因为我们真正关心的是相似性而不是距离本身。） 我同时使用Daitch-Mokotoff声音编码和Damerau-Levenshtein来确定用户输入和应用程序中的值是否“相同”。 听起来你正在尝试确定用户是否打算使他们的输入与给定的数据值相同？ 你在做拼写检查吗？还是将无效的输入符合到已知值集合中？ 你的优先事项是什么？

• 尽量减少误报（尝试确保所有建议的单词非常“相似”，并且建议列表很短）
• 尽量减少漏报（尝试确保用户所想要的字符串在建议列表中，即使这使列表变长）
• 最大化平均匹配精度

您可能需要使用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.

- LarsH

---

由于我想找出两个单词有多相似（速度不是问题），Jaro Winkler 算法似乎是一个不错的建议。 - Joseph Tura

@Joseph：这似乎是一个使用Jaro-Winkler算法的好应用，因为它具有很好的特性，可以从0（无相似度）到1（完全匹配）之间进行评估，您可以说，例如任何超过0.9相似度的内容都足够相似。然后，您可以基于用户测试来调整该阈值。 - LarsH

Answer 2

Levenshtein距离是两个单词之间的相对值。将LD与长度进行比较是不相关的，例如：

猫 -> 斯卡特 = 1（相似度75％？？）

差异 -> 差异 = 1（相似度90％？？）

这两个单词的Lev距离都为1，即它们只有一个字符的区别，但与它们的长度相比，第二组单词似乎更“相似”。

我使用Soundex排列具有相同Lev距离的单词，例如：

猫和肥相对于卡特都有LD为1，但在使用Soundex时，该单词更可能是kat而不是fat（假设该单词拼写错误，而不是打字错误！）

因此，简短的答案就是只需使用Lev距离来确定相似性。

- James Westgate

---

我不明白你的例子如何证明你的观点：“将LD与长度进行比较是不相关的。”即使它们具有相同的LD，“cat”和“scat”之间的差异也比“difference”和“differences”更大。 - Davy8

我认为在我的情况下确实有所不同。特别是因为我使用了soundexing（请参见下面对LarsH答案的评论）。 - Joseph Tura