模糊搜索算法(近似字符串匹配算法)

Question

我想创建一个模糊搜索算法.然而,经过数小时的研究,我真的很挣扎.

我想创建一个算法,在学校名称列表上执行模糊搜索.

这是我到目前为止所看到的:

我的大部分研究都指向Google和Stackoverflow上的" 字符串指标 ",例如:

• Levenshtein距离
• Damerau-Levenshtein距离
• Needleman-Wunsch算法

然而,这仅仅给出了两个字符串相似的分数.我可以想到将其实现为搜索算法的唯一方法是执行线性搜索并对每个字符串执行字符串度量算法,并返回分数高于某个阈值的字符串.(原来我把我的琴弦存放在一棵树上,但这显然不会帮助我!)

虽然这对于小型列表来说并不是一个坏主意,但对于名为100,000个名称的列表来说,这将是一个问题,并且用户执行了许多查询.

我看到的另一种算法是拼写检查方法,您只需搜索所有可能的拼写错误.然而,这也是非常低效的,因为对于长度为7的单词而言需要超过75,000个单词并且错误计数仅为2.

我需要的？

有人可以建议我一个很好的高效模糊搜索算法.有:

• 算法的名称
• 它是如何工作的或它是如何工作的链接
• Pro和cons以及何时最佳使用(可选)

我知道所有算法都有其优点和缺点,没有最好的算法.

Answer 1

考虑到你试图对学校名称列表进行模糊搜索,我认为你不想像Levenshtein距离那样寻找传统的字符串相似性.我的假设是你正在接受用户的输入(键盘输入或通过电话说话),并且你想快速找到匹配的学校.

距离指标告诉您两个字符串基于替换,删除和插入的相似程度.但是这些算法并没有真正告诉你任何关于字符串与人类语言中的单词有多相似的信息.

例如,考虑"smith","smythe"和"smote"这两个词.我可以分两步走出"smythe"到"smith":

smythe -> smithe -> smith

从两个步骤的"击打"到"史密斯":

smote -> smite -> smith

所以两者的距离与琴弦的距离相同,但作为单词,它们的差别很大.如果有人告诉你(口语)他正在寻找"Symthe学院",你几乎肯定会说,"哦,我认为你的意思是史密斯." 但如果有人说"斯莫特学院",你就不会知道他在说什么.

你需要的是像Soundex或Metaphone这样的语音算法.基本上,这些算法会将一个单词分解为音素,并创建一个表示单词如何在口语中发音的表示.然后,您可以将结果与已知的单词列表进行比较,以找到匹配项.

这样的系统将是很多比使用距离度量更快.考虑到使用距离度量,您需要将用户的输入与列表中的每个单词进行比较以获得距离.这在计算上是昂贵的,结果,正如我用"史密斯"和"击打"所证明的那样,可笑得很糟糕.

使用语音算法,您可以创建每个已知单词的音素表示,并将其放在字典中(哈希映射或可能是trie).这是一次性的启动成本.然后,只要用户输入搜索词,您就可以创建其输入的音素表示并在词典中查找.这样可以更快,并产生更好的结果.

还要考虑到,当人们拼错正确的名字时,他们几乎总能得到正确的第一个字母,并且通常会发出拼写错误的声音,就像他们试图拼写的实际单词一样.如果是这样的话,语音算法肯定是要走的路.

Answer 2

我写了一篇关于我如何实现模糊搜索的文章：

https://medium.com/@Srekel/implementing-a-fuzzy-search-algorithm-for-the-debuginator-cacc349e6c55

实现在 Github 中并且在公共领域，所以请随意查看。

https://github.com/Srekel/the-debuginator/blob/master/the_debuginator.h#L1856

它的基本原理是：将您要搜索的所有字符串拆分为多个部分。所以如果你有路径，那么“C:\documents\lol.txt”可能是“C”、“documents”、“lol”、“txt”。

确保将这些字符串小写以确保不区分大小写。（也许只有在搜索字符串全小写时才这样做）。

然后将您的搜索字符串与此匹配。在我的情况下，无论顺序如何，我都想匹配它，因此即使“lol”出现在“doc”之后，“loldoc”仍将匹配上述路径。

匹配需要有一些得分才能很好。我认为最重要的部分是连续匹配，所以一个接一个匹配的字符越多越好。所以“doc”比“dcm”好。

然后，您可能希望为部分开始时的比赛提供额外的分数。因此，“doc”比“ocu”获得更多积分。

在我的情况下，我也会为匹配零件的末端提供更多积分。

最后，您可能需要考虑为匹配最后一部分提供额外的分数。这使得匹配文件名/结尾的分数高于导致它的文件夹。

Answer 3

你将模糊搜索算法与实现混淆:对一个单词进行模糊搜索可能会返回Levenshtein距离为2的所有单词的400个结果.但是,对于用户,你必须只显示前5-10.

在实现方面,您将预处理字典中的所有单词并将结果保存到数据库中.流行的单词(及其模糊的单词)将保存到缓存层中 - 因此您不必为每个请求点击DB.

您可以添加一个AI层,它将添加最常见的拼写错误并将其添加到数据库中.等等.

Answer 4

“一种模糊搜索”的简单算法

老实说，在某些情况下，模糊搜索大多没有用，我认为更简单的算法可以改善搜索结果，同时提供我们仍在执行模糊搜索的感觉。

这是我的用例：使用 "Fuzzy search" 过滤国家/地区列表。

我正在处理的名单中有两个以 Z 开头的国家：赞比亚和津巴布韦。

我正在使用Fusejs。

在这种情况下，当输入针“zam”时，结果集有 19 个匹配项，并且与列表底部的任何人（赞比亚）最相关的匹配项。结果中的大多数其他国家甚至没有名字中的字母 z。

这是一个移动应用程序，您可以在其中从列表中选择一个国家/地区。这应该很像当您必须从手机的联系人中选择联系人时。您可以通过在搜索框中输入一些术语来过滤联系人列表。

恕我直言，这种有限的搜索内容不应该以人们问“这到底是什么？！？”的方式对待。

人们可能会建议按最相关的匹配进行排序。但在这种情况下这是不可能的，因为用户将始终必须在减少的列表中直观地找到“感兴趣的项目”。请记住，这应该是一个过滤工具，而不是“à la Google”的搜索引擎。所以结果应该以可预测的方式排序。在过滤之前，排序是按字母顺序排列的。所以过滤后的列表应该只是原始列表的按字母顺序排序的子集。

所以我想出了以下算法......

1. 抓住针......在这种情况下：zam
2. .*在针头和针尾插入花样
3. .*在针的每个字母之间插入图案
4. 使用现在的新针在大海捞针中执行正则表达式搜索 .*z.*a.*m.*

在这种情况下，通过查找字母 z、a 和 m 按此顺序出现的所有内容，用户将获得非常期望的结果。针中的所有字母都将以相同的顺序出现在比赛中。

这也将匹配像 Mo zam bique这样的国家名称......这是完美的。

我只是觉得有时候，我们不应该尝试用火箭筒杀死一只苍蝇。