Trie 和基 Trie 数据结构之间的区别是什么？

小开

最佳答案

基数树是 trie 的压缩版本。在 Trie 中，在每个边上写一个字母，而在 PATRICIA 树(或基数树)中存储整个单词。

现在，假设你有单词 hello，hat和 have。要将它们存储在 trie中，它看起来像:

    e - l - l - o
/
h - a - t
\
v - e

你需要9个节点，我把字母放在节点里，但实际上它们标记了边。

在一棵根茎树上，你会看到:

            *
/
(ello)
/
* - h - * -(a) - * - (t) - *
\
(ve)
\
*

你只需要五个节点。在图片上面的节点是星号。

因此，总的来说，基数树需要 更少的记忆，但是实现起来更加困难。否则，两者的用例几乎是相同的。

小开

我的问题是 Trie的数据结构和 基地组织是否是一回事？

简而言之，没有。类别 基地组织描述了试试的一个特定类别，但是这并不意味着所有的尝试都是基本的尝试。

如果它们是[不]相同的，那么 Radix Trie (又名 Patricia Trie)的含义是什么？

我猜你是想在你的问题中写没有，所以我更正一下。

类似地，PATRICIA 表示特定类型的基数尝试，但并非所有基数尝试都是 PATRICIA 尝试。

什么是尝试？

“ Trie”描述了一种适合用作关联数组的树型数据结构，其中分支或边缘对应于键的零件。这里，零件的定义相当模糊，因为不同的 try 实现使用不同的位长度来对应边。例如，一个二进制尝试每个节点有两条边，对应于0或1，而一个16路尝试每个节点有16条边，对应于4位(或十六进制数字: 0x0到0xf)。

This diagram, retrieved from Wikipedia, seems to depict a trie with (at least) the keys 'A', 'to', 'tea', 'ted', 'ten', 'i', 'in' and 'inn' inserted:

Basic trie

If this trie were to store items for the keys 't' or 'te' there would need to be extra information (the numbers in the diagram) present at each node to distinguish between nullary nodes and nodes with actual values.

基数试验是什么？

正如 Ivaylo Strandjev 在他的回答中所描述的那样，“基本试验”似乎描述了一种压缩了常见前缀部分的试验形式。考虑一个256路的尝试，使用下面的静态分配对“微笑”、“微笑”、“微笑”和“微笑”这几个键进行索引:

root['s']['m']['i']['l']['e']['\0'] = smile_item;
root['s']['m']['i']['l']['e']['d']['\0'] = smiled_item;
root['s']['m']['i']['l']['e']['s']['\0'] = smiles_item;
root['s']['m']['i']['l']['i']['n']['g']['\0'] = smiling_item;

Each subscript accesses an internal node. That means to retrieve smile_item, you must access seven nodes. Eight node accesses correspond to smiled_item and smiles_item, and nine to smiling_item. For these four items, there are fourteen nodes in total. They all have the first four bytes (corresponding to the first four nodes) in common, however. By condensing those four bytes to create a root that corresponds to ['s']['m']['i']['l'], four node accesses have been optimised away. That means less memory and less node accesses, which is a very good indication. The optimisation can be applied recursively to reduce the need to access unnecessary suffix bytes. Eventually, you get to a point where you're only comparing 在尝试索引的位置，搜索键和索引键之间的差异. This is a radix trie.

root = smil_dummy;
root['e'] = smile_item;
root['e']['d'] = smiled_item;
root['e']['s'] = smiles_item;
root['i'] = smiling_item;

要检索项，每个节点都需要一个位置。通过一个搜索关键字“微笑”和一个4的 root.position，我们访问 root["smiles"[4]]，这碰巧是 root['e']。我们将其存储在一个名为 current的变量中。current.position是5，这是 "smiled"和 "smiles"之间差异的位置，因此下一个访问将是 root["smiles"[5]]。这将我们带到 smiles_item，以及我们的字符串的结束。我们的搜索已经结束，项目已经被检索，只有三个节点访问，而不是八个。

什么是 PATRICIA 试验？

PATRICIA 尝试是基数尝试的一种变体，对于基数尝试，应该只有 n节点用于包含 n项。在我们上面粗略演示的基三伪码中，总共有五个节点: root(一个空节点; 它不包含实际值)、 root['e']、 root['e']['d']、 root['e']['s']和 root['i']。在 PATRICIA 的审判中，应该只有四个人。由于 PATRICIA 是一种二进制算法，让我们通过查看二进制前缀来看看这些前缀之间的区别。

smile:   0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0000 0000  0000 0000
smiled:  0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0110 0100  0000 0000
smiles:  0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0111 0011  0000 0000
smiling: 0111 0011  0110 1101  0110 1001  0110 1100  0110 1001  0110 1110  0110 0111 ...

让我们假设节点是按照上面提供的顺序添加的。smile_item是这棵树的根。差异，粗体，使它稍微更容易发现，是在 "smile"的最后一个字节，在位36。到目前为止，我们所有的节点都有一样前缀。smiled_node属于 smile_node[0]。"smiled"和 "smiles"之间的差异出现在位43，其中 "smiles"有一个“1”位，因此 smiled_node[1]是 smiles_node。

而不是使用 NULL作为分支和/或额外的内部信息来表示搜索何时结束，分支链接回 up树的某个地方，所以搜索在偏移量结束时测试减少而不是增加。下面是这样一个简单的 tree图(尽管 PATRICIA 实际上更像是一个循环图，而不是树，如你所见) ，它包含在塞奇威克的书中如下:

Simple PATRICIA diagram

一个更复杂的 PATRICIA 算法涉及变长键是可能的，尽管 PATRICIA 的一些技术特性在这个过程中丢失了(即任何节点都包含与之前的节点共同的前缀) :

Complex PATRICIA diagram

通过这样的分支，有许多好处: 每个节点都包含一个值。包括根。因此，代码的长度和复杂性变得更短，实际上可能更快一些。至少有一个分支，最多有 k分支(其中 k是搜索键中的位数)用于定位项。这些节点是很小，因为它们每个只存储两个分支，这使得它们非常适合于缓存本地优化。这些属性使得 PATRICIA 成为目前为止我最喜欢的算法..。

为了减轻我即将到来的关节炎的严重程度，我将在这里简短地描述一下，但是如果你想了解更多关于 PATRICIA 的知识，你可以参考一些书籍，比如 Donald Knuth 的《计算机编程的艺术，第3卷》，或者 Sedgewick 的《你最喜欢的语言的算法，第1-4部分》。

小开

TRIE:
We can have a search scheme where instead of comparing a whole search key with all existing keys (such as a hash scheme), we could also compare each character of the search key. Following this idea, we can build a structure (as shown below) which has three existing keys – “爸爸”, “Dab”, and ”出租车”.

         [root]
...// | \\...
|  \
c   d
|    \
[*]    [*]
...//|\.  ./|\\...        Fig-I
a       a
/       /
[*]      [*]
...//|\..  ../|\\...
/        /   \
B        b     d
/        /       \
[]       []       []


(cab)   (dab)     (dad)

这实质上是一个 M 元树，内部节点表示为[ * ] ，叶子节点表示为[]。这种结构称为  trie 。每个节点上的分支决策可以保持等于字母表中唯一符号的数量，例如 R。对于小写英文字母 a-z，R = 26; 对于扩展 ASCII 字母，R = 256; 对于二进制数字/字符串，R = 2。

紧凑型试验:
通常， trie 中的节点使用 size = R 的数组，因此当每个节点的边较少时，会造成内存浪费。为了回避记忆的问题，人们提出了各种建议。基于这些变化， trie 也被命名为“ 小规模试验”和“ 压缩试验”。虽然一致的命名法很少见，但紧凑型  trie 的最常见版本是在节点具有单边时对所有边进行分组。使用这个概念，上面(图 -I)  trie 与键“爸爸”，“拍”和“驾驶室”可以采取以下形式。

         [root]
...// | \\...
|  \
cab  da
|    \
[ ]   [*]                Fig-II
./|\\...
|  \
b   d
|    \
[]    []

请注意，‘ c’、‘ a’和‘ b’中的每一个都是其对应的父节点的唯一边，因此，它们被合并成一个单一的边“ cabi”。类似地，‘ d’和‘ a’被合并为标记为“ da”的单边。

基地试验:
术语基，在数学中，意味着一个数字系统的基础，它本质上表示代表该系统中任何数字所需的唯一符号的数目。例如，十进制系统是基数十，二进制系统是基数二。使用类似的概念，当我们有兴趣通过底层表示系统的唯一符号数来描述一个数据结构或算法时，我们用术语“基”标记这个概念。例如，某些排序算法的“基数排序”。在同样的逻辑中，trie的所有变体的特征(例如深度、内存需求、搜索错过/命中运行时等)都依赖于底层字母表的基数，我们可以称它们为基数“ trie’s”。例如，当使用字母 a-z 时，一个未压缩的以及压缩的 trie，我们可以称它为基数26 trie。任何只使用两个符号(传统上是‘0’和‘1’)的尝试都可以称为基数2trie。然而，不知何故，许多文献限制使用术语“根试验”只为压缩 trie。

帕特里夏树序曲/三:
It would be interesting to notice that even strings as keys can be represented using binary-alphabets. If we assume ASCII encoding, then a key “dad” can be written in binary form by writing the binary representation of each character in sequence, say as “011001000110000101100100” by writing binary forms of ‘d’, ‘a’, and ‘d’ sequentially. 使用这个概念，可以形成一个  trie (带有基数2)。下面我们使用一个简化的假设来描述这个概念，即字母‘ a’、‘ b’、‘ c’和‘ d’来自一个较小的字母表，而不是 ASCII。

图 III 注释: 如前所述，为了简化描述，让我们假设一个只有4个字母{ a，b，c，d }的字母表及其对应的二进制表示分别是“00”、“01”、“10”和“11”。这样，我们的字符串键“ dad”、“ dab”和“ cabi”分别变成“110011”、“110001”和“100001”。这方面的尝试如图三所示(位从左到右读取，就像字符串从左到右读取一样)。

          [root]
\1
\
[*]
0/ \1
/   \
[*]   [*]
0/     /
/     /0
[*]    [*]
0/      /
/      /0
[*]    [*]
0/     0/ \1                Fig-III
/      /   \
[*]   [*]   [*]
\1     \1    \1
\      \     \
[]     []    []
(cab)   (dab) (dad)

返回文章页面帕特丽夏译者:
如果我们使用单边压缩来压缩上面的二进制  trie (图 -III) ，它的节点将比上面显示的少得多，但是节点仍然比它包含的键数3多。Donald R. Morrison(1968年)发现了一种创新的方法，使用二进制  trie 来描述 N 键只使用 N 个节点，他命名这种数据结构 PATRICIA。他的 trie 结构基本上去掉了单边(单向分支) ; 在这样做的同时，他也去掉了两种节点的概念——内部节点(不描述任何键)和叶子节点(描述键)。与上面解释的压缩逻辑不同，他的尝试使用了一个不同的概念，其中每个节点都包含一个指示，说明为了做出分支决策，要跳过一个键的多少位。然而，他的 PATRICIA 尝试的另一个特点是它不存储密钥——这意味着这样的数据结构不适合回答诸如 列出所有匹配给定前缀的键之类的问题，但有利于查找 如果在尝试中存在或不存在密钥。尽管如此，术语 Patricia Tree 或 Patricia Trie 自那时以来已经在许多不同但相似的意义上使用，例如表示紧凑型试验[ NIST ] ，或表示基数为2的基数试验[如 WIKI 中以微妙的方式表示]等等。

可能不是基地组织的组织:
三元搜索 Trie (又名三元搜索树)通常缩写为 TST ，它是一种数据结构(由 J.Bentley和 R. Sedgewick提出) ，看起来非常类似于三向分支的 Trie。对于这种树，每个节点都有一个特征字母“ x”，因此分支决策是由键的一个字符是小于、等于还是大于“ x”来驱动的。由于这种固定的3路分支特性，它为 try 提供了一种高效的内存替代方案，特别是当 R (基数)非常大时，比如 Unicode 字母表。有趣的是，与(R-way)  trie 不同，TST 的特征不受 R 的影响。例如，TST 的搜索失误是 ln(N)，而 R-way Trie 的搜索失误是 Log R (N)。与 R 路  trie 不同，TST 的记忆需求 NOT也是 R 的函数。因此，我们应该小心地把 TST 称为基数试验。就我个人而言，我不认为我们应该把它称为基数-三元组，因为(就我所知)它的特征没有一个是受基数 R 的基本字母表的影响的。

小开

在 try 中，大多数节点不存储密钥，只是键和扩展键之间的路径。这些跳跃大多数是但是当我们存储长单词时，它们往往会产生长单词内部节点链，每个节点只有一个子节点 reason tries need too much space, sometimes more than BSTs.

基数试验(又名基数树，又名 Patricia 树)是基于我们可以通过某种方式压缩路径，例如 “中间 t 节点”，我们可以在一个节点中使用“ hem”，或者在一个节点。

下面是一个比较 trie 与基数 trie 的图表:

The original trie has 9 nodes and 8 edges, and if we assume 9 bytes 对于每个节点开销为4字节的边，这意味着

       9 * 4 + 8 * 9 = 108 bytes.

右边的压缩版本有6个节点和5条边，但是在这里 case each edge carries a string, not just a character; however, we can 通过计算边引用和字符串来简化操作标签分开。这样，我们仍然计算每边9字节 (因为我们将在边缘中包含字符串终止符字节 ) ，但是我们可以将字符串长度之和作为第三项添加到 the final expression; the total number of bytes needed is given by

    6 * 4 + 5 * 9 + 8 * 1 = 77 bytes.

对于这个简单的尝试，压缩版本要求减少30% 记忆。

参考文献