2

由于某种原因，我对尝试的了解越多，我就越感到困惑。
现在让我感到困惑的是：
我已经阅读了大约 2 种类型的实现。

  1. 使用数组来表示字符（不存储字符本身），并且在每个节点中还存储实际单词的索引（如果我们找到一个单词）。
  2. 使用一个Collection存储字符的节点，并在每个节点的末尾使用一个布尔值来确定我们是否在这条路径上找到了一个单词

在第一种情况下，它没有被提及，但似乎我们实际上必须保留所有字典单词（因为我们间接引用它们）。所以我们有array_size*numberOfNodes*lengthOfword + size of dictionary processed

在后一种情况下，我们不需要字典，因为字符直接存储在树中。所以在我看来，第二种实现更节省空间。但我不确定多少。
我对实现的理解是否正确，是否有特定的理由来选择另一种？另外，我们如何计算第二种情况的空间需求？

4

1 回答 1

3

尝试不会将原始单词存储在任何地方，而是隐式存储它们。trie 的基本结构如下： trie 中的每个节点存储

  • 确定到达节点的路径是否形成一个单词的单个位，以及
  • 指向由字符标记的子节点的指针集合。

要确定一个单词是否在 trie 中，请从根开始，然后按照适当标记的指针一次一个。如果您到达标记为单词的节点，则该单词存在于 trie 中。如果你到达一个没有标记的节点或者你从树上掉下来，这个词就不存在了。

您上面列出的两个结构之间的区别在于子指针的存储方式。在第一个版本中，子指针存储为字母表中每个符号一个指针的数组，这使得跟随子指针非常快，但空间效率极低。在第二个版本中，您显式存储某种类型的集合，其中仅包含您需要的标记指针。这速度较慢，但​​对于稀疏尝试而言更节省空间。

trie 的空间使用取决于节点的数量（称为 n）、字母表的大小（称为 k）以及子指针的表示方式。如果存储一个固定大小的指针数组，那么空间使用量约为 kn 个指针（n 个节点，每个节点有 k 个指针），加上每个节点处的标记的 n 位。例如，如果您有一个按排序顺序存储的动态指针数组，则开销将是 n 个子指针总数，加上 n 位，再加上存储单个集合所需空间量的 n 倍。

第一种方法的优点是速度和简单，在密集尝试上具有非常好的性能。对于稀疏尝试，第二个速度较慢但内存效率更高。

这些不是唯一可能的空间优化。Patricia 尝试将只有一个子节点的节点压缩在一起，并且非常节省空间。DAWG 尝试将尽可能多的节点合并在一起，但不支持高效插入。

希望这可以帮助！

于 2013-01-21T19:10:03.847 回答