algorithm - 存储字典（单词）以优化搜索时间的良好数据结构是什么？

Question

提供有效单词列表和搜索词，我想查找搜索词是否是有效词 ALLOWING 2 个错字字符。

什么是存储单词字典（假设它包含一百万个单词）和查找单词是否存在于字典中的算法（允许 2 个错字字符）的良好数据结构。

如果不允许出现拼写错误，那么 Trie 将是存储单词的好方法，但不确定在允许拼写错误时它是否仍然是存储字典的最佳方式。不确定回溯算法（在 Trie 中搜索允许 2 个拼写错误的单词）的复杂性是多少。有什么想法吗？

标签： algorithmsearchfuzzy-search

Answer 1

如果不需要同时存储所有输入错误的单词，我会考虑使用两步法来解决这个问题。

1. 构建一个包含所有有效单词（不包括拼写错误）的哈希值的集合。所以可能我们在这里谈论的是大约 10.000 个条目，它们仍然应该允许使用二进制搜索进行相当快速的查找。如果在集合中找到一个单词的哈希，则它是正确输入的。

2. 如果在集合中未找到单词哈希，则该单词可能是输入错误的。因此，计算单词和所有已知单词之间的 Damerau-Levenshtein 距离，以找出用户可能的意思。为了在此处获得一些性能，请修改 DL 算法以在距离大于允许的 2 个错别字的阈值时中止计算。