创建一个“拼写检查”，用合理的运行时检查数据库
我不是要求实现拼写检查算法本身。 我有一个包含数十万条记录的数据库。 我要做的是检查用户输入针对所有这些记录的表格中的某个列，并返回任何具有一定汉明距离的匹配（同样，这个问题不是关于确定汉明距离等）。 当然，目的是创建一个“你是说”的function，用户搜索名称，如果在数据库中找不到直接匹配，则返回可能匹配的列表。
我试图想出一种方法，在最合理的运行时间内完成所有这些检查。 如何以最有效的方式检查用户对所有这些记录的输入？
该function目前已实现，但运行时速度非常慢。 它现在的工作方式是将所有记录从用户指定的表（或多个表）加载到内存中 ，然后执行检查。
为了它的价值，我正在使用NHibernate进行数据访问。
如果我能做到这一点或我的选择是什么，我将不胜感激。
计算Levenshtein距离不必像您想象的那样昂贵。 Norvig文章中的代码可以被认为是伪代码，以帮助读者理解算法。 一个更有效的实现（在我的情况下，在20,000个术语数据集上快约300倍）就是走一条路。 性能差异主要归因于为了进行字典查找而无需分配数百万个字符串，在GC中花费的时间少得多，并且您还获得了更好的引用局部性，因此CPU缓存未命中率更低。 通过这种方法，我可以在我的Web服务器上大约2ms进行查找。 另一个好处是能够轻松返回以提供的字符串开头的所有结果。
缺点是创建trie很慢（可能需要一秒左右），因此如果源数据定期更改，那么您需要决定是重建整个事物还是应用增量。 无论如何，您希望在构建后尽可能多地重用结构。
正如达卡拉所说，BK树是一个很好的第一次采取。 它们很容易实现。 通过Google可以轻松找到几种免费实现，但可以在此处找到更好的算法介绍： http ： //blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees 。
不幸的是，计算Levenshtein距离是非常昂贵的，如果你使用带有大字典的BK树，你会做很多事情。 为了获得更好的性能，您可以考虑使用Levenshtein Automata。 更难实现，但也更有效，它们可用于解决您的问题。 同样令人敬畏的博客有详细信息： http ： //blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata 。 本文可能也很有趣： http ： //citeseerx.ist.psu.edu/viewdoc/summary？doi = 10.1.1.16.652 。
我猜Levenshtein距离比汉明距离更有用。
让我们举一个例子：我们采用单词example并将自己限制在Levenshtein距离1.然后我们可以列举所有可能存在的拼写错误：
- 1次插入（208）
- aexample
- bexample
- cexample
- …
- examplex
- exampley
- examplez
- 1删除（7）
- xample
- eample
- exmple
- …
- 为例
- 1个替换（182）
- axample
- bxample
- cxample
- …
- examplz
您可以将每个拼写错误存储在数据库中，并将其链接到正确的拼写， example 。 这工作并且会很快，但会创建一个庞大的数据库。
注意通过使用不同的字符执行相同的操作会发生大多数拼写错误：
- 1次插入（8）
- ？例
- 例
- 例
- 例
- 例
- 例
- 例
- 例？
- 1删除（7）
- xample
- eample
- exmple
- 的exaple
- examle
- exampe
- 为例
- 1个替换（7）
- ？xample
- è？充裕
- 恩？mple
- EXA？PLE
- 考试？乐
- examp？è
- 为例？
这看起来很容易管理。 您可以为每个单词生成所有这些“提示”并将它们存储在数据库中。 当用户输入单词时，从中生成所有“提示”并查询数据库。
示例：用户输入exaple （通知缺少m ）。
SELECT DISTINCT word FROM dictionary WHERE hint = '?exaple' OR hint = 'e?xaple' OR hint = 'ex?aple' OR hint = 'exa?ple' OR hint = 'exap?le' OR hint = 'exapl?e' OR hint = 'exaple?' OR hint = 'xaple' OR hint = 'eaple' OR hint = 'exple' OR hint = 'exale' OR hint = 'exape' OR hint = 'exapl' OR hint = '?xaple' OR hint = 'e?aple' OR hint = 'ex?ple' OR hint = 'exa?le' OR hint = 'exap?e' OR hint = 'exapl?'
exaple with 1 insertion == exa?ple == example with 1 substitution
另请参阅： Google“你的意思是什么？”算法是如何工作的？
它将用户指定的一个或多个表中的所有记录加载到内存中，然后执行检查
不要那样做
或
- 匹配匹配在后端，只返回您需要的结果。
要么
- 在获取工作集命中之前将记录缓存到内存中，并在需要时进行检查。
您需要以不同于数据库的方式构建数据。 在客户端上构建自定义搜索树，其中包含所需的所有字典数据。 虽然如果字典非常大，内存可能会成为问题，但搜索本身会非常快。 O（nlogn）如果我没记错的话。
看看BK-Trees
此外，考虑Levenshtein距离 ，而不是使用汉明距离
你标记为正确的答案..
Note: when i say dictionary.. in this post, i mean hash map .. map.. basically i mean a python dictionary
另一种方法是通过创建倒置的单词索引来提高其性能。
因此，不是根据整个数据库计算编辑距离，而是创建26个字典..每个字母都有一个键。 所以英语有26个字母..所以键是“a”，“b”..“z”
所以假设你的数据库中有“苹果”
所以在“a”字典中：你添加“apple”这个词
在“p”字典中：你添加“苹果”这个词
在“l”字典中：你添加“苹果”这个词
在“e”字典中：你添加“苹果”这个词
所以，对字典中的所有单词执行此操作。
现在输入拼写错误的单词时..
让我们说aplse
你从“a”开始，然后检索“a”中的所有单词
然后你从“p”开始，找到“a”和“p”之间的单词的交集
然后你从“l”开始，找到“a”，“p”和“l”之间的单词的交集
你为所有的字母表做了这个。
最后你会得到一堆由字母“a”，“p”，“l”，“s”，“e”组成的单词
在下一步中，您将计算输入字与上述步骤返回的一串字之间的编辑距离。从而大大减少您的运行时间。
现在可能会出现无法返回任何内容的情况。
所以像“aklse”这样的东西……很有可能没有单词由这些字母组成。在这种情况下，你必须开始将上面的步骤反转到你有一定数量的单词的阶段剩下。
所以有点喜欢以* klse开头（单词k，l，s，e之间的交集）num（wordsreturned）= k1
然后a * lse（单词a，l，s，e之间的交叉点）…… numwords = k2
选择那些返回的单词数量较多的那个..在这种情况下，实际上没有一个答案..因为很多单词可能有相同的编辑距离…你可以说如果editdistance更大比“k”那么没有好的比赛……
在此基础上构建了许多复杂的算法。
喜欢在这些步骤之后，使用统计推断（当输入是“aplse”时，这个词是“苹果”的概率等等）然后你去机器学习方式:)