创建一个"拼写检查",用合理的运行时检查数据库

Question

我不是要求实现拼写检查算法本身.我有一个包含数十万条记录的数据库.我要做的是针对所有这些记录检查表格中某个列的用户输入,并返回具有某个汉明距离的任何匹配(同样,这个问题不是关于确定汉明距离等).当然,目的是创建一个"你是说"的功能,用户搜索名称,如果在数据库中找不到直接匹配,则返回可能匹配的列表.

我试图想出一种方法,在最合理的运行时间内完成所有这些检查.如何以最有效的方式检查用户对所有这些记录的输入？

该功能目前已实现,但运行时速度非常慢.它现在的工作方式是将所有记录从用户指定的表(或多个表)加载到内存中,然后执行检查.

对于它的价值,我使用NHibernate进行数据访问.

如果我能做到这一点或我的选择是什么,我将不胜感激.

Answer 1

计算Levenshtein距离不必像您想象的那样昂贵.Norvig文章中的代码可以被认为是伪代码,以帮助读者理解算法.一个更有效的实现(在我的情况下,大约300倍20000项数据集更快)是步行一个线索.性能差异主要归因于无需分配数百万个字符串以进行字典查找,在GC中花费的时间更少,并且您还可以获得更好的引用局部性,从而减少CPU缓存未命中率.通过这种方法,我可以在我的Web服务器上大约2ms进行查找.另一个好处是能够轻松返回以提供的字符串开头的所有结果.

缺点是创建trie很慢(可能需要一秒左右),所以如果源数据定期更改,那么您需要决定是重建整个事物还是应用增量.无论如何,您希望在构建后尽可能多地重用结构.