algorithm - 如何使用后缀数组进行文本更正？

Question

我们使用后缀数组来实现关键字搜索，例如考虑一个短语:

白色浴室瓷砖

我们插入后缀:

1) 白色浴室瓷砖

2)浴室瓷砖

3)瓷砖

现在，如果用户输入“white”、“bathroom”或“tile”等词，就可以找到短语“white bathroom tile”。

但是，现在有一个问题，一个人可以输入“tyle”，但什么也找不到。

所以，我想问一下如何为此实现某种快速模糊搜索。基本上我希望这个算法能够纠正用户并仍然找到“tile”。

我考虑过应用 levenstein 距离，但我的尝试失败了。我们的想法是，我们可以找到以“t”开头的一组单词，并为每个单词计算 levenstein 距离，然后返回 levenstein 距离最小的结果。

这失败了，因为用户可以键入的是“iile”而不是“tile”，现在没有任何单词，我的算法将 levenstein 距离应用于“i”组中的单词。

有什么好的方法可以解决这个问题？

Answer 1

您可以使用 Edit distance algorithm算法找到与搜索词具有最小编辑距离的词列表。

例如，对于单词tyle和ile，搜索到的单词tile的编辑距离将为1。对于单词iile，tile和iile之间的编辑距离也为1。

更新

如果遍历后缀数组上的所有单词计算编辑距离比较慢(即编辑距离的时间复杂度为O(^2))，我建议构建一个前缀树(trie) 加上句子的所有后缀。然后在查找的时候，比如对于单词tyle，尝试这样遍历前缀树:

• 如果前缀树中有当前字符的节点，则遍历该节点
• 如果当前字符没有节点，则递归遍历所有节点并跳过该字符。
• 在查找过程中，计算您跳过的字符数。您跳过的字符数越少，这个词就越适合。