我应该使用哪种数据结构来查找相似的字符串？

Question

我应该使用哪种数据结构来查找相似的字符串？例如，当您查询谷歌搜索字符串“hapyp brithdya”时，谷歌会问您是否是“happy birthday”，这是一个非常类似于先前拼写错误的字符串“hapyp brithdya”的字符串。

哪种数据结构在空间和时间上执行此类操作最有效？

请帮忙。非常感谢您的时间。

- Daniel Johnson

---

在您的示例中，您仅显示了由字母排列不同而产生的单词。您是否还想查找那些实际上包含不同字母但又“相似”的单词（例如，“happy”和“hbppy”）？ - Francois G

是的，没错。我也想得到像“快乐”或“开心”的单词。 - Daniel Johnson

Answer 1

如果你需要一种数据结构，我会推荐 Levenshtein自动机。

这可以扩展到概率变量，返回字符串的最可能（根据语料库统计）的更正。参见Google的Peter Norvig的文章 "如何编写拼写纠正器"，了解基本思路；将其与Levenshtein自动机相结合需要一些有限状态转换器的知识。有关详细信息，请参阅Hassan，Noeman和Hassan。

- Fred Foo

Answer 2

Google使用的一种学习机制是搜索历史记录。例如，我搜索了“hapyp brithdya”，然后意识到拼写错误，因此没有选择任何链接。我的下一个搜索将是“happy birthday”正确的拼写。从这个搜索序列中，Google可以推断出“hapyp brithdya”实际上意味着“happy birthday”。

另一个基于相同线路的评分机制，帮助Google提供更可接受的拼写纠正，是当用户点击(由Google搜索建议的)包含“happy birthday”的链接时对“hapyp brithdya”的接近程度增加了。“nappy birthday”在用户没有访问的链接中出现，与“hapyp brithdya”的接近程度相比较低。

- Akhil