这是对相当令人难以置信的 SymSpell 算法以及我们如何在 lnx 中实现它的一个相当普遍的看法。
我在开发 lnx 时遇到的最酷的功能之一是一种称为 SymSpell 的算法：https://github.com/lnx-search/lnx
每当您希望搜索引擎解决用户的输入错误时，您都必须计算应用到某个单词所需的更改以获得目标单词。
例如，如果我要纠正Beer到Bree我们必须应用两词取代过程，两个步骤分解为：
- - Beer -> Brer+1 替换e为r.
- - Brer -> Bree +1 替换r为e.
现在，这是一个相对简单的过程，当您有数百万个单词要搜索并与整个句子进行比较时，问题就来了。突然间，您发现自己进行了数百万次迭代来实现这种错字容忍度。当查看更大的索引时，尤其是当您有很多用户要搜索请求时，这就是事情开始变得非常缓慢、非常快的地方。
现在，大多数情况下，搜索引擎都采用根据字长计算最大编辑距离的策略，这有助于通过不过度宽容匹配相似词来提高相关性，而且还有助于提高性能，因为大多数词的编辑距离为 0或 1 比允许每个单词的最大编辑距离为 2 节省大量计算。这同样是一种权衡，然而，即使一个非常常见的错误是 helo 或类似的错误，像 hello 这样的词只会被赋予 0 的编辑距离，与纯全文搜索相比，它仍然相当慢。
当我们增长到更大的索引（在本例中为 20GB 的文本）时，当在我的本地机器上以相当高的 5GHz 时钟速度和 NVMe 随时仅运行 1 个并发客户端时，我们的驱动器延迟会猛增。
因此，在这种情况下，我们只剩下三个选项：
- 增加单机或分片搜索请求的计算能力。
- 删除可搜索文本的数量。
- 摒弃错别字容忍度。
。。。。
什么是 SymSpell
SymSpell 分解为对称删除拼写校正算法：
从每个字典术语生成具有编辑距离（仅删除）的术语，并将它们与原始术语一起添加到字典中。这必须在预计算步骤中仅执行一次。生成与输入术语具有编辑距离（仅删除）的术语并在字典中搜索它们。对于长度为 n 的单词、字母大小为 a、编辑距离为 1 的单词，将只有 n 个删除，在搜索时总共有 n 个术语。 - 有关更多信息，请查看Wolf Garbe 的博客。
总的来说，这使得更正的成本大大降低，代价是一些预先计算和内存使用（预先计算的字典保存在内存中）但是，这使得它很难在搜索引擎中使用，并且需要这样做许多尝试和设计迭代使其在 lnx 中工作。
更多点击标题