如何使用SymSpell将模糊搜索速度提高五倍以上 - lnx

21-11-25 banq

这是对相当令人难以置信的 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 中工作。

更多点击标题

 

猜你喜欢