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

Question

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

我想创建一个对学校名称列表执行模糊搜索的算法。

这是我目前看到的内容:

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

• 编辑距离
• Damerau-Levenshtein 距离
• Needleman–Wunsch 算法

然而，这只是给出了 2 个字符串的相似程度的分数。我能想到的将其实现为搜索算法的唯一方法是执行线性搜索并为每个字符串执行字符串度量算法，并返回得分高于特定阈值的字符串。 (最初我将我的字符串存储在一个特里树中，但这显然对我没有帮助!)

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

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

我需要什么？

谁能给我推荐一个高效的模糊搜索算法。与:

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

我明白所有的算法都有其优点和缺点，没有最好的算法。

Answer 1

考虑到您正在尝试对学校名称列表进行模糊搜索，我认为您不希望使用 Levenshtein 距离等传统字符串相似性。我的假设是您正在接受用户的输入(键盘输入或通过电话语音输入)，并且您希望快速找到匹配的学校。

距离度量告诉您两个字符串基于替换、删除和插入的相似程度。但是这些算法并没有真正告诉您字符串与人类语言中的单词有多相似。

例如，考虑单词“smith”、“smythe”和“smote”。我可以分两步从“smythe”到“smith”:

smythe -> smithe -> smith

从“smote”到“smith”分两步:

smote -> smite -> smith

所以这两者与strings 具有相同的距离，但作为words，它们有显着的不同。如果有人告诉你(口头语言)他正在寻找“Symthe College”，你几乎肯定会说，“哦，我想你是说史密斯。”但是，如果有人说“Smote College”，您就不会知道他在说什么。

您需要的是 phonetic algorithm喜欢Soundex或 Metaphone .基本上，这些算法将单词分解为音素，并创建该单词在口语中的发音方式的表示。然后，您可以将结果与已知的单词列表进行比较以找到匹配项。

这样的系统会比使用距离度量多快。考虑使用距离度量，您需要将用户的输入与列表中的每个单词进行比较以获得距离。这在计算上是昂贵的，而且结果，正如我用“smith”和“smote”所展示的那样，可能会很糟糕。

使用语音算法，您可以创建每个已知单词的音素表示并将其放入字典( HashMap 或可能是 trie)中。这是一次性的启动成本。然后，每当用户输入搜索词时，您就创建他输入的音素表示并在字典中查找。这要快得多，而且会产生更好的结果。

还请考虑一下，当人们拼错专有名称时，他们几乎总是能正确拼出第一个字母，而且通常拼错的发音听起来就像他们试图拼写的实际单词一样。如果是这样的话，那么语音算法绝对是可行的方法。