Dan*_*son 3 language-agnostic string algorithm matching data-structures
我应该使用什么数据结构来查找类似的字符串？例如,当您向Google查询字符串"hapyp brithdya"时,Google会问您"生日快乐",这是一个非常类似于之前拼写错误的字符串"hapyp brithdya"的字符串.
什么样的数据结构在空间和时间上进行这种操作最有效？
请帮忙.非常感谢您的时间.
既然你要求数据结构,我将推荐Levenshtein自动机.
这些可以扩展到概率变量,该变量返回最可能(根据语料库统计)字符串的校正.请参阅Google的Peter Norvig 撰写的文章"如何编写拼写校正器"的基本概念; 将其与Levenshtein自动机结合起来需要一些有限状态传感器的知识.有关详细信息,请参阅Hassan,Noeman和Hassan.