c# - 创建一个 "spell check"以合理的运行时间检查数据库

Question

我不是在询问实现拼写检查算法本身。我有一个包含数十万条记录的数据库。我想要做的是针对所有这些记录检查表中特定列的用户输入，并返回具有特定汉明距离的任何匹配项(同样，这个问题与确定汉明距离等无关)。当然，目的是创建一个“您是不是要找”功能，用户可以在其中搜索姓名，如果在数据库中未找到直接匹配项，则返回可能匹配项的列表。

我正在尝试想出一种方法，以尽可能在最合理的运行时执行所有这些检查。我如何才能以最有效的方式检查用户的输入是否符合所有这些记录？

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

为了它的值(value)，我使用 NHibernate 进行数据访问。

对于我如何执行此操作或我有哪些选择的任何反馈，我将不胜感激。

Answer 1

计算 Levenshtein 距离并不一定像您想象的那么昂贵。 Norvig article中的代码可以将其视为帮助读者理解算法的伪代码。一个更有效的实现(在我的例子中，在 20,000 个术语数据集上快大约 300 倍)是走 trie .性能差异主要归因于消除了为进行字典查找而分配数百万个字符串的需要，在 GC 中花费的时间大大减少，并且您还获得了更好的引用位置，从而减少了 CPU 缓存未命中。通过这种方法，我可以在 2 毫秒左右的时间内在我的 Web 服务器上进行查找。一个额外的好处是能够轻松返回以提供的字符串开头的所有结果。

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