问题标签 [levenshtein-distance]

我本着回答您自己的问题的精神发布此消息。

我的问题是：如何在 Delphi 中实现 Levenshtein 算法来计算两个字符串之间的编辑距离，如此处所述？

只是关于性能的说明：这东西非常快。在我的台式机（2.33 Ghz 双核、2GB 内存、WinXP）上，我可以在不到一秒的时间内运行 100K 字符串数组。

我正在为我的网站自定义 404 页面。我希望它包括一个“你的意思是......？” 我需要弄清楚如何做到这一点。

到目前为止，我正在做的事情是：我列出了用户可能正在寻找的文件的广泛列表，然后使用 levenshtein() 将每个可能的文件名与输入错误的文件名进行比较。“您的意思是”选择了差异最小的那些。

我也考虑过使用 metaphone()，但我认为这可能是过度的。

对于“您的意思是……？”，您有什么建议？脚本？

我正在使用 levenshtein 算法来满足这些要求：

当找到一个包含 N 个字符的单词时，在我的字典数据库中建议作为更正的单词是：

与找到的单词有1个字符差异的每个N个字符的字典单词。示例：找到的单词：bearn，字典单词：bears

每个 N+1 个字符的字典单词，其中 N 个字符等于找到的单词。示例：找到的单词：bear，字典单词：bears

每个包含 N-1 个字符的字典单词，其中 N-1 个字符等于找到的单词。示例：找到的词：熊，字典词：熊

我在 C++ 中使用这个 Levenshtein 算法的实现来查找单词的 Levenshtein 编号何时为 1（这是所有三种情况的 Levenshtein 编号），但是我该如何选择要建议的单词呢？我读过有关 Boyer-Moore-Horspool 和 Knuth-Morris-Pratt 的文章，但我不确定它们中的任何一个有什么帮助。

我对 T-SQL 计算 Levenshtein 距离的算法感兴趣。

我需要将来自不同来源的产品名称（相机、笔记本电脑、电视等）自动匹配到数据库中的规范名称。

例如"Canon PowerShot a20IS"、"NEW powershot A20 IS from Canon"和"Digital Camera Canon PS A20IS" 应该都匹配"Canon PowerShot A20 IS"。我已经通过一些额外的启发式（删除明显的常用词，为数字更改分配更高的成本等）来处理 levenshtein 距离，这在某种程度上有效，但不幸的是还不够好。

主要问题是，即使是相关关键字的单个字母变化也会产生巨大的差异，但要检测哪些是相关关键字并不容易。以三个产品名称为例：
Lenovo T400
Lenovo R400
New Lenovo T-400, Core 2 Duo
前两个在任何标准上都是非常相似的字符串（好吧，soundex 在这种情况下可能有助于区分 T 和 R，但名称可能还有400T和400R），第一和第三作为琴弦相距很远，但是是同一个产品。

显然，匹配算法不可能 100% 精确，我的目标是自动匹配大约 80% 的名称，并且置信度很高。

非常感谢任何想法或参考

我希望能够在如下表中搜索 smith 以获得它在 1 个方差内的所有内容。

数据：

我已经研究过使用 Levenshtein distance 有人知道如何用它来实现吗？

分析显示这是我编写的一个小文字游戏代码中最慢的部分：

笔记：

• distance()被调用超过 500 万次，其中大部分来自 getchildren，它应该获取单词列表中与word恰好相差 1 个字母的所有单词。
• wordlist 被预先过滤为仅包含包含相同数量字母的单词，word因此可以保证word1并且word2具有相同数量的字符。
• 我对 Python 相当陌生（3 天前开始学习它），所以对命名约定或其他样式的评论也很感激。
• 对于单词表，使用“2+2lemma.txt”文件获取12dict 单词表

结果：

谢谢大家，结合不同的建议，我现在让程序运行速度提高了两倍（除了我在询问之前自己进行的优化，所以速度比我最初的实现提高了大约 4 倍）

我用两组输入进行了测试，我将它们称为 A 和 B

优化 1：迭代 word1,2 的索引... from

迭代字母对使用zip(word1, word2)

输入 A 的执行时间从 11.92 到 9.18，输入 B 的执行时间从 79.30 到 74.59

优化 2：除了距离方法（我在其他地方仍然需要 A* 启发式）之外，还添加了一种单独的方法

输入 A 的执行时间从 9.18 到 8.83，输入 B 的执行时间从 74.59 到 70.14

优化3：这里的大赢家是使用izip而不是zip

输入 A 的执行时间从 8.83 到 5.02，输入 B 的执行时间从 70.14 到 41.69

我可能会更好地用较低级别的语言编写它，但我现在对此感到满意。谢谢大家！

再次编辑：更多结果使用 Mark 的方法检查第一个字母不匹配的情况使其从 5.02 -> 3.59 和 41.69 -> 29.82 下降

在此基础上并合并izip而不是range，我最终得到了这个：

挤压得更多，使时间从 3.59 -> 3.38 和 29.82 -> 27.88

甚至更多的结果！

尝试 Sumudu 的建议，即我生成一个与“word”相差 1 个字母的所有字符串的列表，然后检查哪些字符串在 wordlist中，而不是 is_neighbor 函数，我最终得到了这个：

最终速度变慢了（3.38 -> 3.74 和 27.88 -> 34.40），但看起来很有希望。起初我认为我需要优化的部分是“one_letter_off_strings”，但分析显示并非如此，而且慢的部分实际上是

我想如果我切换“oneoff”和“wordlist”并在我正在寻找两个列表的交集时以另一种方式进行比较，是否会有任何区别。我用字母上的 set-intersection替换它：

砰！3.74 -> 0.23 和 34.40 -> 2.25

这真是令人惊讶，与我最初的幼稚实现的总速度差异：23.79 -> 0.23 和 180.07 -> 2.25，比原来的实现快大约 80 到 100 倍。

如果有人有兴趣，我会发表博客文章来描述程序并描述所做的优化，包括此处未提及的优化（因为它位于不同的代码部分中）。

大辩论：

好的，我和 Unknown 正在进行一场大辩论，您可以在他的回答的评论中阅读。他声称，如果将其移植到 C 中，使用原始方法（使用 is_neighbor 而不是使用集合）会更快。我尝试了 2 个小时来获得我编写的 C 模块来构建和可链接，但在尝试后没有太大成功按照这个和这个例子，看起来这个过程在Windows中有点不同？我不知道，但我放弃了。无论如何，这是程序的完整代码，文本文件来自12dict单词列表使用“2+2lemma.txt”文件。对不起，如果代码有点乱，这只是我一起破解的。此外，我忘记从单词列表中删除逗号，因此这实际上是一个错误，您可以保留它以进行相同的比较，或者通过在 cleanentries 的字符列表中添加逗号来修复它。

我留下了 is_neighbors 方法，即使它没有被使用。这是建议移植到 C 的方法。要使用它，只需将 getchildren 替换为：

至于让它作为 C 模块工作，我并没有那么远，但这就是我想出的：

我使用以下方法对此进行了分析：

python -m cProfile "Wordgame.py"

记录的时间是AStar方法调用的总时间。快速输入集是“诗歌诗人”，而长输入集是“诗人诗歌”。不同机器之间的时间显然会有所不同，因此如果有人最终尝试这样做，请按原样比较程序的结果，以及与 C 模块的比较。

我在使用 PHP levenshtein函数比较字符串方面取得了一些成功。

但是，对于包含交换位置的子字符串的两个字符串，算法将它们计为全新的子字符串。

例如：

被视为具有以下共同点：

我更喜欢一种算法，它看到前两个更相似。

我怎么能想出一个比较函数来识别已经切换位置的子字符串与编辑不同？

我想到的一种可能的方法是在比较之前将字符串中的所有单词按字母顺序排列。这将单词的原始顺序完全排除在比较之外。然而，这样做的一个缺点是，仅更改单词的第一个字母会造成比更改单个字母更大的干扰。

我想要实现的是比较关于人的两个作为自由文本字符串的事实，并确定这些事实表明相同事实的可能性有多大。事实可能是某人就读的学校，例如他们的雇主或出版商的名称。两个记录可能有相同的学校拼写不同，单词的顺序不同，多余的单词等，所以如果我们要很好地猜测它们指的是同一所学校，匹配必须有点模糊。到目前为止，它在拼写错误方面效果很好（我使用的是类似于变音位的语音算法），但如果你切换学校中常见的单词顺序，效果就很差：“xxx 学院”vs “xxx学院”。

1）为什么我们在这些行上加 1？

线

应该考虑删除/较低的字长，还是我错过了什么？

2）此外，评论状态删除和插入。我是否认为它正在检查两个单词中的已删除字符（整数 j/i 表示单词的长度），因为较低的值将表示已删除的字符。

使用的代码在这里（因为它是伪代码，我没有语言特定的问题，这个线程不属于任何语言类别）：

http://www.iterasi.net/openviewer.aspx?sqrlitid=z0cloj7xhk-ce0f72v4cjq

我将“块转置”放在引号中，因为我不知道技术术语是否或应该是什么。只知道该过程是否有技术术语将非常有帮助。

关于编辑距离的Wikipedia 文章为这个概念提供了一些很好的背景。

通过考虑“块转置”，我的意思是

应该匹配

比匹配更接近

即距离计算应该检测文本的子串何时在文本中简单地移动。常见的 Levenshtein 距离公式并非如此。

字符串最多只有几百个字符——它们是作者姓名或作者姓名列表，可以采用多种格式。我不做 DNA 测序（尽管我怀疑做过的人会对这个主题有所了解）。