11

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

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

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

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

4

2 回答 2

7

Levenshtein 距离是否应该用作绝对值？

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

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

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

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

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

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

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

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

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

在哪里：

  • m 是匹配字符的数量
  • t 是转置的数量

Jaro-Winkler 距离使用前缀标度p，它为从开头匹配一组前缀长度l的字符串提供更有利的评级。

于 2010-10-06T20:44:04.603 回答
1

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

cat -> scat = 1（75% 相似？？）

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

这两个词的 lev 距离都是 1，即它们相差一个字符，但与它们的长度相比，第二组看起来“更”相似。

我使用 soundexing 对具有相同 lev 距离的单词进行排名，例如

cat并且fat两者相对于 的 LD 都为 1 kat，但是在使用 soundex 时，这个词更可能是 kat 而不是 fat（假设这个词拼写错误，而不是输入错误！）

所以简短的回答就是使用 lev 距离来确定相似度。

于 2010-10-06T20:14:39.627 回答