我不是在询问如何实现拼写检查算法本身。我有一个包含数十万条记录的数据库。我想要做的是针对所有这些记录的表中的特定列检查用户输入，并返回具有特定汉明距离的任何匹配项（同样，这个问题不是关于确定汉明距离等）。当然，目的是创建一个“您的意思是”功能，用户在其中搜索名称，如果在数据库中找不到直接匹配项，则返回可能匹配项的列表。
我正在尝试想出一种方法来在尽可能合理的运行时间内完成所有这些检查。如何以最有效的方式根据所有这些记录检查用户的输入？
该功能目前已实现，但运行速度非常慢。它现在的工作方式是将用户指定的表（或多个表）中的所有记录加载到memory然后执行检查。
无论如何，我使用 NHibernate 进行数据访问。
如果您能提供有关我如何执行此操作或我的选择的反馈，我将不胜感激。
计算编辑距离并不一定像您想象的那么昂贵。中的代码诺维格文章 http://norvig.com/spell-correct.html可以被认为是伪代码，以帮助读者理解算法。一个更有效的实现（在我的例子中，在 20,000 个术语数据集上快大约 300 倍）是遍历trie http://en.wikipedia.org/wiki/Trie。性能差异主要归因于不需要分配数百万个字符串来进行字典查找，在 GC 上花费的时间少得多，并且您还可以获得更好的引用局部性，从而减少 CPU 缓存未命中。通过这种方法，我能够在大约 2 毫秒内在我的 Web 服务器上进行查找。额外的好处是能够轻松返回以提供的字符串开头的所有结果。
缺点是创建 trie 很慢（可能需要一秒钟左右），因此如果源数据定期更改，那么您需要决定是重建整个数据还是应用增量。无论如何，您希望在构建完成后尽可能地重复使用该结构。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
