词的Damerau-Levenshtein距离

Question

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

我正在寻找一个使用SQL Server的实现，但算法的名称将足够好。

Answer 1

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

Answer 2

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

如果您需要在重新排列单词时查找拼写错误，我发现将空格最少的单词放回重新排列成不同顺序的相同单词的字符串中，然后对新单词和第二个短语运行Levenshtein非常有效！

哈沃德医学院(2个空间，6个排列)哈沃德医学院(3个空间，24个排列) Levenshtein距离- 17比“斯坦福医学院”(Levenshtein距离5)

哈沃德医学院vs.哈沃德医学院的LD为6。仍然允许斯坦福大学犯一个错误，但排名更接近，所以你可以增加一些东西，比如丢弃单词(在这种情况下，去掉" of“的LD只有3)。

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

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