data-structures - 尝试的缺点

Question

我一直在研究尝试并检查它们的优缺点。它们在字典、拼写检查器等许多实际应用中非常有用，因为它们具有恒定的 O(m) 查找(其中 m 是字符串的长度)和其他优点，例如提供字符串的有序检索和获取公共(public)前缀。所以，优势对我来说很清楚，但局限性有点令人困惑。

我正在关注这个链接:https://en.wikipedia.org/wiki/Trie

这里列出的缺点是:

在某些情况下，尝试查找数据的速度可能比哈希表慢，尤其是当数据直接在硬盘驱动器或其他随机访问时间比主存储器长的辅助存储设备上访问时。

跟进问题 - 为什么会有涉及二级存储的场景？不是尝试也应该存储在主内存中。如果它们存储在辅助存储中，那么无论如何使用 trie 是没有用的，因为磁盘访问总是会导致更长的时间。

有些尝试可能需要比哈希表更多的空间，因为可能会为搜索字符串中的每个字符分配内存，而不是像大多数哈希表那样为整个条目分配一 block 内存。

追问 :是不是因为尝试将包含更多用于将每个字符连接到下一个字符的引用/指针，并且与将其存储为整个字符串相比会消耗更多字节？ (我从这里的一个答案中得到了这个原因)。任何人都可以详细说明这一点吗？

我真的很感激这里的一些帮助。谢谢。

Answer 1

首先，“恒定的 O(m) 查找”是没有意义的。 trie 中的查找时间为 O(m):它取决于您正在查找的字符串的长度。

构造良好的哈希表(即良好的哈希函数和合理的负载因子)具有 O(1) 查找时间。

假设有能力的构造，在哈希表中查找字符串将比在 trie 中查找要快得多。

尝试和哈希表用于不同的事情。如果您想要的只是查找单词的能力，那么哈希表会更快。如果您想查找公共(public)前缀、有序检索或做类似的事情，那么您需要尝试一下。

哈希表可以非常快速地查找单个字符串。这就像一匹纯种赛马。这就是它所能做的。另一方面，特里是可以做很多事情的主力。它永远不会像哈希表那样快速查找，但它可以做很多哈希表不能做的事情。

例如，使用字典查找所有以“pre”开头的单词将花费 O(n) 时间，因为您必须搜索所有单词。使用 trie，需要三个探针才能找到包含所有这些单词的子树，然后您所要做的就是遍历该子树。当然，最坏的情况是 O(n)，但前提是你的 trie 中的所有单词都以“pre”开头。

确实，写入磁盘会比整个 trie 都在内存中要慢，但不能说基于磁盘的 trie 与替代方案相比没有优势。如果数据不适合内存，那么无论您使用什么数据结构，您都需要一些外部(即非内存)存储。当数据在磁盘上时访问速度较慢这一事实并没有从根本上改变 trie 与哈希表的优缺点。例如，在查找具有特定前缀的所有单词时，基于磁盘的 trie 仍然比基于磁盘的哈希表更快。

哈希表的开销通常是其包含的字数的恒定倍数。也就是说，除了存储字符串所需的内存之外，还有每个字符串的开销来存储哈希码和字符串之间的映射。

trie 的内存更复杂一些。在最坏的情况下，每个字符有一个节点。所有这些小节点分配开始加起来。想象一个包含 200,000 个单词的字典，平均单词长度为 5 个字符。那是一百万个节点的开销。

幸运的是，有一些方法可以大大压缩 trie，而不会损失太多(如果有的话)性能。生成的数据结构比简单构造的 trie 更小且对缓存更友好。