查找相似字符串的优化方法

Question

假设我有一大串单词。(约有4-5千人，而且还在增加)。有人在找绳子。不幸的是，字列表中没有找到字符串。现在，找到与输入字符串相似的单词的最佳优化方法是什么？我想到的第一件事是计算单词列表的每个条目与输入字符串之间的Levenshtein距离。但这是最优的方法吗？

(请注意，这不是针对语言的问题)

Answer 1

编辑：新解决方案

是的，计算输入和单词列表之间的Levenshtein距离可能是一种合理的方法，但需要很长时间。BK-树木可以改善这一点，但随着Levenshtein距离的增大，它们很快就会变慢。我们似乎可以使用trie加速Levenshtein距离的计算，如这篇出色的博客文章所述：

使用Trie的快速和容易的Levenshtein距离

它依赖于这样一个事实: Levenshtein距离的动态规划查找表在不同的调用中具有公共行，即levenshtein(kate,cat)和levenshtein(kate,cats)。

使用TWL06字典运行该页面上的Python程序将给出如下结果：

> python dict_lev.py HACKING 1
Read 178691 words into 395185 nodes
('BACKING', 1)
('HACKING', 0)
('HACKLING', 1)
('HANKING', 1)
('HARKING', 1)
('HAWKING', 1)
('HOCKING', 1)
('JACKING', 1)
('LACKING', 1)
('PACKING', 1)
('SACKING', 1)
('SHACKING', 1)
('RACKING', 1)
('TACKING', 1)
('THACKING', 1)
('WHACKING', 1)
('YACKING', 1)
Search took 0.0189998 s

这是非常快的，而且在其他语言中会更快。大部分时间都花在构建trie上，这是不相关的，因为只需要完成一次并存储在内存中。

唯一的小缺点是，尝试占用大量内存(这可以减少一个道格，以一定的速度)。

另一种方法：Peter有一篇很棒的关于拼写更正的文章(有完整的源代码)。

http://norvig.com/spell-correct.html

这样做的目的是对单词进行可能的编辑，然后选择该单词最有可能的拼写更正。

Answer 2

我认为有比这更好的东西存在，但是BK树至少是来自蛮力的一个很好的优化。

它使用Levenshtein距离的属性是一个度量空间，因此，如果在您的d和dict中的任意字符串s之间得到一个Levenshtein距离，那么您的所有结果都必须在(d+n) to (d-n)到s之间。这里n是您想要输出的查询的最大Levenshtein距离。

详细说明如下：http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees