如何使用SymSpell将模糊搜索速度提高五倍以上 - lnx
source link: https://www.jdon.com/57755
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
这是对相当令人难以置信的 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 中工作。
更多点击标题
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK