创建一个“拼写检查”，用合理的运行时间检查数据库
我不是在问关于实现拼写检查算法本身的问题。我有一个包含数十万条记录的数据库。我要做的是根据表中的特定列检查用户输入的所有这些记录，并返回具有特定hamming距离的任何匹配(同样，这个问题不是关于确定hamming距离等)。当然，这样做的目的是创建一个“你的意思是不是”特性，用户在其中搜索一个名字，如果在数据库中没有找到直接匹配，则返回一个可能匹配的列表。
我正在试图想出一种方法，在尽可能合理的运行时间内完成所有这些检查。我如何才能以最有效的方式对照所有这些记录检查用户的输入？
该功能目前已实现，但运行时非常慢。它现在的工作方式是将用户指定的一个(或多个)表中的所有记录加载到内存中，然后执行检查。
无论如何，我正在使用NHibernate进行数据访问。
我非常感谢任何关于我如何做到这一点或我的选择是什么的反馈。
回答 4
Stack Overflow用户
发布于 2011-01-30 00:00:19
计算Levenshtein距离并不一定像你想象的那样昂贵。Norvig article中的代码可以看作是帮助读者理解算法的伪代码。一个更有效的实现(在我的例子中，在20,000个术语数据集上大约快300倍)是遍历trie。性能差异主要归因于消除了为执行字典查找而分配数百万个字符串的需要，在GC中花费的时间要少得多，而且您还可以获得更好的引用局部性，从而减少CPU缓存未命中。使用这种方法，我可以在我的web服务器上进行大约2毫秒的查找。一个额外的好处是能够很容易地返回所有以提供的字符串开头的结果。
缺点是创建trie很慢(可能需要一秒钟左右)，所以如果源数据定期更改，那么您需要决定是重建整个数据还是应用增量。无论如何，一旦构建好了这个结构，您就希望尽可能多地重用它。
Stack Overflow用户
发布于 2011-01-29 14:08:05
正如Darcara所说，BK-Tree是一个很好的第一步。它们很容易实现。通过谷歌可以很容易地找到几个免费的实现，但可以在这里找到更好的算法介绍：http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees。
不幸的是，计算Levenshtein距离是相当昂贵的，如果你使用BK-Tree和一个大字典，你会做很多事情。为了获得更好的性能，您可以考虑使用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。
Stack Overflow用户
发布于 2011-01-29 07:37:28
您需要以与数据库不同的方式组织数据。在客户端构建自定义搜索树，其中包含所需的所有字典数据。虽然如果字典非常大，内存可能会成为一个问题，但搜索本身将非常快。O(nlogn)如果我没记错的话。
看一看BK-Trees
此外，不使用汉明距离，而是考虑Levenshtein distance
https://stackoverflow.com/questions/4833769
复制相似问题
腾讯云开发者
