假设我正在寻找一个可能在或不在 95k 单词的字典中的单词 - 我无法使用单词长度来促进搜索。我的问题是关于在不进行 O(n) 查找的情况下找到单词的最快方法。
以下是我的两个想法：
首先，将单词存储在一个 hast 表中，查找单词是 O(1)，这似乎是我认为最好的方案，但也有人建议使用 Trie 浏览不同的网站，我对此的问题是它是否实用有一个包含这么多单词的 Trie。 在这种情况下，查找将是 O(k)。
那么在大字典中查找单词的最佳方法是什么？
问问题
367 次
4 回答
1
最优性取决于您的用例——您关心查找时间还是空间？（另外，你关心插入新词吗？）。
您可以在时间上做的最好的事情是使用哈希表，但对于字典来说，它的空间效率很低。trie 压缩了空间要求，因为它存储前缀，而不是整个单词，但查找时间更长。因此，要回答您的问题，使用包含大量单词的 trie 比哈希表更节省空间。
于 2012-10-27T00:13:05.677 回答
1
如果您只是搜索一个单词，那么设置哈希表或树结构的成本将超过线性搜索。当这些结构的成本在（非常）许多用途中摊销时，这些结构变得（非常）有效。
如果字典已排序（为什么字典不排序？），那么您可以log(n)通过对文件进行二进制搜索及时查找单个单词，而无需额外的结构。
于 2012-10-27T01:56:01.097 回答
0
我认为在字典中查找单词的最佳方法是 B+ 树。让我解释一下原因。
假设您有一个由 10 个字符串组成的根块。块中的字符串已排序。这 10 个字符串后跟一个指向另一个 10 个字符串单元格的指针，然后就是一个。所以您唯一要做的就是字符串比较你的关键字从第一个开始，直到你找到一个比较小的单词（StringCompare）。
如果我们以每个字符串旁边都有一个指针为标准，该指针显示一个单元格中的单词比较小，那么您将需要 5 步和 5 次比较才能结束可能或可能的最终数据括号不包含您的关键字。
在 5 次比较 + 最后括号中的比较中，您正在搜索 10*10*10*10*10 单词的字典。
该算法是对数速度 Log 100000，以单元格中的字符串数为基础。如果每个单元格有 10 个单词，则需要 5 个步骤。
我必须提到，只有树的根必须存储在 RAM 内存中。所有其他块都可以存储在硬盘中，而不会因为几个步骤而显着降低性能。
希望我解释正确 :D 至少我试过了！玩得开心
于 2012-10-27T02:45:33.320 回答
0
Trie 更可取，因为这种数据结构可以比哈希表更快。哈希表O(1)仅在理想情况下，在现实世界的应用程序中可能会发生冲突。不同类型的 trie 数据结构不受此影响。
另一种情况是压缩。Trie 比哈希表更紧凑。哈希表需要一些空间来进行高效的插入操作。如果哈希表的负载因子接近 100%，则插入操作需要很长时间。
使用哈希表，您必须将您的密钥与字典中的至少一个密钥进行比较，在这种情况下，密钥比较需要O(k)密钥长度为 k。使用 trie 您正在做同样的事情，您的查找操作是O(k).
尝试允许有序遍历、哈希表——不要。
那里有许多类型的尝试，例如三元搜索尝试在这种特殊情况下非常好。与常规哈希表相比，数组映射的 trie 也非常快。
于 2012-10-28T08:17:17.927 回答