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

Question

假设我有一个很大的单词列表。 (大约 4-5 千，并且还在增加)。有人搜索了一个字符串。不幸的是，在单词列表中找不到该字符串。现在找到与输入字符串相似的单词的最佳和优化方法是什么？我首先想到的是计算词表的每个条目与输入字符串之间的 Levenshtein 距离。但这是做到这一点的优化方法吗？

(请注意，这不是特定于语言的问题)

Answer 1

编辑:新解决方案

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

Fast and Easy Levenshtein distance using a Trie

它依赖于 Levenshtein 距离的动态规划查找表在不同调用中具有公共(public)行，即 levenshtein(kate,cat) 和 levenshtein(凯特，猫)。

使用 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 上，这是无关紧要的，因为它只需要完成一次并存储在内存中。

唯一的小缺点是尝试会占用大量内存(可以使用 DAWG 减少内存，但会牺牲一些速度)。

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

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

我们的想法是构建可能的单词编辑，然后选择最有可能对该单词进行拼写更正。