我想创建一个模糊搜索算法。然而，经过数小时的研究，我真的很挣扎。
我想创建一个算法，在学校名称列表上执行模糊搜索。
这是我到目前为止所看到的：
我的大部分研究都指向Google和Stackoverflow上的“字符串指标”，例如：
然而，这仅仅给出了两个字符串相似的分数。我可以想到将其实现为搜索算法的唯一方法是执行线性搜索并对每个字符串执行字符串度量算法，并返回分数高于某个阈值的字符串。 （原来我把我的琴弦存放在一棵树上，但这显然不会帮助我！）
虽然这对于小型列表来说并不是一个坏主意，但对于名为100,000个名称的列表来说，这将是一个问题，并且用户执行了许多查询。
我看到的另一种算法是拼写检查方法，您只需搜索所有可能的拼写错误。然而，这也是非常低效的，因为对于长度为7的单词而言需要超过75,000个单词并且错误计数仅为2。
我需要的？
有人可以建议我一个很好的高效模糊搜索算法。有：
我知道所有算法都有其优点和缺点，没有最好的算法。
考虑到你试图对学校名称列表进行模糊搜索，我认为你不想像Levenshtein距离那样寻找传统的字符串相似性。我的假设是你正在接受用户的输入（键盘输入或通过电话说话），并且你想快速找到匹配的学校。
距离指标告诉您两个字符串基于替换，删除和插入的相似程度。但是这些算法并没有真正告诉你关于字符串与人类语言中的单词有多相似的信息。
例如，考虑“smith”，“smythe”和“smote”这两个词。我可以分两步走出“smythe”到“smith”：
smythe -> smithe -> smith
从两个步骤的“击打”到“史密斯”：
smote -> smite -> smith
所以两者的距离与琴弦的距离相同，但作为单词，它们的差别很大。如果有人告诉你（口语）他正在寻找“Symthe学院”，你几乎肯定会说，“哦，我认为你的意思是史密斯。”但如果有人说“斯莫特学院”，你就不会知道他在说什么。
你需要的是phonetic algorithm，如Soundex或Metaphone。基本上，这些算法会将一个单词分解为音素，并创建一个表示单词如何在口语中发音的表示。然后，您可以将结果与已知的单词列表进行比较，以找到匹配项。
这样的系统比使用距离度量快得多。考虑到使用距离度量，您需要将用户的输入与列表中的每个单词进行比较以获得距离。这在计算上是昂贵的，结果，正如我用“史密斯”和“击打”所证明的那样，可笑得很糟糕。
使用语音算法，您可以创建每个已知单词的音素表示，并将其放在字典中（哈希映射或可能是trie）。这是一次性的启动成本。然后，只要用户输入搜索词，您就可以创建其输入的音素表示并在词典中查找。这样可以更快，并产生更好的结果。
还要考虑到，当人们拼错正确的名字时，他们几乎总能得到正确的第一个字母，并且通常会发出拼写错误的声音，就像他们试图拼写的实际单词一样。如果是这样的话，语音算法肯定是要走的路。
你将模糊搜索算法与实现混淆：对一个单词进行模糊搜索可能会返回Levenshtein距离为2的所有单词的400个结果。但是，对于用户，你必须只显示前5-10。
在实现方面，您将预处理字典中的所有单词并将结果保存到数据库中。流行的单词（及其模糊的单词）将保存到缓存层中 - 因此您不必为每个请求点击DB。
您可以添加一个AI层，它将添加最常见的拼写错误并将其添加到数据库中。等等。
我写了一篇关于如何实现模糊搜索的文章：
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”。
确保小写这些字符串以确保它不区分大小写。 （也许只有在搜索字符串全为小写时才这样做）。
然后将您的搜索字符串与此匹配。在我的情况下，无论顺序如何，我都想匹配它，所以“loldoc”仍然会匹配上述路径，即使“lol”在“doc”之后。
匹配需要有一些得分才能好。我认为最重要的部分是连续匹配，所以越多的字符直接匹配，就越好。所以“doc”比“dcm”更好。
然后你可能想要为一个部分开头的比赛提供额外的分数。因此，您获得的“doc”比“ocu”更多。
在我的情况下，我还提供了更多的点来匹配零件的结尾。
最后，您可能需要考虑为匹配最后一个部分提供额外的分数。这使得匹配文件名/结尾分数高于导致它的文件夹。
一种简单的“一种模糊搜索”算法
说实话，在某些情况下，模糊搜索几乎是无用的，我认为更简单的算法可以改善搜索结果，同时提供我们仍在进行模糊搜索的感觉。
这是我的用例：使用“模糊搜索”过滤国家列表。
我与之合作的名单有两个国家，从Z开始：赞比亚和津巴布韦。
我在使用Fusejs。
在这种情况下，当输入针“zam”时，结果集有19个匹配，并且对于列表底部的任何人（赞比亚）最相关。结果中的大多数其他国家的名字中都没有字母z。
这是一个移动应用程序，您可以从列表中选择一个国家/地区。这应该很像你必须从手机的联系人中选择一个联系人。您可以通过在搜索框中输入一些术语来过滤联系人列表。
恕我直言，这种有限的搜索内容不应该以一种让人们问“到底是什么？！？”的方式来对待。
有人可能建议按最相关的匹配排序。但在这种情况下，这是不可能的，因为用户将始终必须在缩小列表中直观地找到“感兴趣的项目”。请记住，这应该是一个过滤工具，而不是搜索引擎“àlaGoogle”。因此，结果应以可预测的方式排序。在过滤之前，排序是按字母顺序排列的。因此，过滤后的列表应该只是原始列表的按字母顺序排序的子集。
所以我提出了以下算法......
.*图案.*图案.*z.*a.*m.*）在大海捞针中执行正则表达式搜索在这种情况下，用户将通过查找以此顺序出现字母z，a和m的某些内容而获得非常期望的结果。针中的所有字母将以相同的顺序出现在匹配中。
这也将匹配像莫桑比克这样的国家名称......这是完美的。
我只是觉得有时候，我们不应该试着用火箭筒杀死苍蝇。