-4

根据libstdc++ 文档的第 3 点和第 4 点，PATRICIA 尝试有两种类型的节点：

(PATRICIA) trie 类似于树，但有以下区别：

  1. 它明确地将键视为一系列元素。例如，trie 可以将字符串视为字符序列；trie 可以将数字视为位序列。

  2. 它不是（必然）二进制。每个节点都有 n + 1 个扇出，其中 n 是不同元素的数量。

  3. 它仅在叶节点存储值。

  4. 内部节点具有以下属性：A）每个都至少有两个子节点，B）每个节点都与其任何后代共享相同的前缀。

我一直在阅读的书（Algorithms in C, Parts 1-4 by Robert Sedgewick）似乎描述了一个 PATRICIA trie，它只使用 n 个节点存储 n 个值，使用内部节点来存储值：

与 DST 一样，patricia 尝试允许在只有 N 个节点的树中搜索 N 个键。...我们通过另一个简单的设备避免外部节点：我们将数据存储在内部节点中，并将指向外部节点的链接替换为指向树中正确内部节点的链接

这里似乎有两个信仰阵营：

  1. 一方面，我们有一个严格、具体的定义（即 Sedgewick、Knuth、Morrison，他们似乎都将 PATRICIA 专门描述为一棵消除了单向分支的前缀压缩二叉树）；和
  2. 然后我们有一些人认为该术语形成了一个松散、模糊的定义，这似乎更像是他们的意思是使用像“map”、“dictionary”或“trie”这样的词（这些实际上都是松散定义的，即 libcs​​td++ 文档）。

我想我担心我的资源的准确性。据我了解，由于常见前缀引入的问题，不可能在不将其呈现为二叉树的情况下表示只有 N 个节点的树（这似乎违反了 libcs​​td++ 文档的第 2 点，以及处理变量时的第 4 点-width 键），并且不失严格单向分支的概念（违反第 3 点和第 4 点，使“叶节点”和“子节点”的概念有些无效）。这两个功能协同工作以消除“内部节点”的困境，这将导致此类树使用超过 N 个节点（回想一下：N 个项目与 N 个节点）。

这两组参考文献不可能都正确；有太多的相互排斥。如果一个参考说 PATRICIA 是二元的，另一个说它可能不是，它们不能都被认为是事实正确的，这只是我在这里看到的不一致的一个例子。这些引用中哪些是正确的？

4

2 回答 2

5

我继续从过去有信誉的来源中寻找一个具体的定义来证实我的怀疑，我写信是为了提供我的发现。也许最重要的是定义 PATRICIA 的官方论文，该论文由 Morrison 博士在 1968 年 10 月的“Journal of the ACM”中发表：

PATRICIA 由“A Library Automaton”[3] 等研究演变而来。... 在这一演变的早期，人们决定将字母表限制为二进制。一个对这个决定产生强烈影响的定理是一个在另一种形式中归因于欧拉的定理。该定理指出，如果字母表是二进制的，则分支数正好比端数少一。推论指出，随着图书馆的发展，每一个新的末端都会带着一个新的分支进入图书馆，而每个分支恰好有两个出口。这些事实在为索引分配存储时非常有用。它们暗示所需的总存储空间完全由端数决定，并且所有所需的存储空间都将实际使用。

这肯定与 libstdc++ 参考的第 2 点和第 3 点相矛盾。本文中还有进一步的证据，例如具体的算法细节，但上面的引用就足够了。

然而，似乎与 Sedgewick 报价中的官方描述没有任何偏差。基于此，libstdc++ 资源肯定不如 Sedgewick 资源有效。

于 2013-04-09T14:17:22.383 回答
1

虽然这两个定义似乎都是正确的，但第一个更详细，对我来说似乎更好。也看看这个答案，我试图描述帕特里夏和普通特里之间的区别。

于 2013-04-09T08:02:42.073 回答