sql-server - 单词的 Damerau-Levenshtein 距离

Question

我正在寻找这样一种算法，但它可以在单词之间而不是字母之间进行替换。有这样的算法吗？

我正在寻找 SQL Server 的实现，但算法的名称就足够了。

Answer 1

据我所知，没有理由不能只使用现有的 Levenshtein 算法 - 只需使用单词作为符号而不是字母。

Answer 2

1. 用空格分割两个字符串
2. 通过遍历两个字符串中的单词来创建一个单词哈希表（如果需要，可以将您从拆分操作中获得的数组连接成一个），每个新单词都会获得一个递增的新数字
3. 对 2 个结果数组使用 Levenshtein 算法（但不将它们转换回字符串，因为 11,12 -> "1112" -> 1,1,1,2

如果您需要在重新排列单词时找到拼写错误，我发现将空格最少的单词重新排列成以不同顺序重新排列的相同单词的字符串，然后在新单词和第二个短语上运行 Levenshtein 效果很好！

Harward Medical School（2 个空格，6 个排列） Harward School of Medicine（3 个空格，24 个排列） Levenshtein 距离 - 17 与“斯坦福医学院”（Levenshtein 距离 5）进行比较

Harward School Medical vs. Harward School of Medicine 的 LD 为 6。仍然允许斯坦福犯错误，但排名更接近，因此您可以构建诸如删除单词之类的内容（在这种情况下删除“of”只会获得 LD 3)

按空格排列单词的性能是 O(n!)，丢弃单词是 O(n+m)，其中 n,m 是每个短语中的单词数，除非你想丢弃多个单词，反之亦然，你可以只选择删除少于 4 个字母的单词，或介词/形容词列表中的单词等。

Levenshtein 的性能在其维基百科页面上进行了解释。