Trie和Radix Trie数据结构有什么区别？

Question

Trie和Radix Trie数据结构有什么区别？

algorithmdata-structurestreepatricia-trieradix-tree

131

trie 和 radix trie 是相同的数据结构吗？

如果它们不同，那么 radix trie（也称为 Patricia trie）的含义是什么？

- Aryak Sengupta

7

我是唯一一个觉得标签应该是radix-trie而不是radix-tree有点烦人吗？而且已经有相当多的问题使用了这个标签。 - errantlinguist

3

维基百科将“radix trie”一词翻译为“Radix tree”。此外，“Radix tree”这个术语在文献中被广泛使用。如果非要称Trie为“prefix trees”，这对我来说更有意义。毕竟，它们都是树形数据结构。 - Amelio Vazquez-Reina

1

此外：“radix trie（又称为Patricia trie）的含义是什么？”这假设基数树和PATRICIA树是同一物，但它们并不相同（例如，请参见此答案）。PATRICIA树是通过运行PATRICIA算法得到的树（顺便说一下，PATRICIA是一个缩写，代表“Practical Algorithm To Retrieve Information Coded in Alphanumeric”）。所得到的树可以理解为具有radix = 2的基数树，这意味着您需要每次查找输入字符串的log2(radix)=1位来遍历该树。 - Amelio Vazquez-Reina

4个回答

86

我的问题是Trie数据结构和Radix Trie是否相同？

简而言之，不是。Radix Trie类别描述了特定类型的Trie，但这并不意味着所有tries都是Radix tries。

如果它们不同，那Radix trie（又名Patricia Trie）的意义是什么？

我假设您在问题中想要写"aren't"，因此我进行了更正。

同样地，PATRICIA表示一种特定类型的Radix trie，但并不是所有Radix tries都是PATRICIA tries。

什么是Trie？

"Trie"是一种树形数据结构，适用于用作关联数组，其中分支或边缘对应于键的部分。这里“部分”的定义相当模糊，因为tries的不同实现使用不同的比特长度来对应于边缘。例如，二进制trie每个节点有两个对应于0或1的边缘，而16路trie每个节点有十六个对应于四位（或十六进制数字：0x0到0xf）的边缘。

从维基百科检索到的以下图表似乎描述了至少插入了'A'、'to'、'tea'、'ted'、'ten'、'i'、'in'和'inn'这些键的trie：

如果此trie要存储键't'或'te'的项目，则需要在每个节点上存在额外信息（图表中的数字）以区分空节点和具有实际值的节点。

什么是Radix trie？

"Radix trie"似乎描述了一种压缩公共前缀部分的trie形式，就像Ivaylo Strandjev在他的答案中所描述的那样。考虑使用以下静态分配索引键"smile"、"smiled"、"smiles"和"smiling"的256路trie：

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;

每个下标都可以访问内部节点。也就是说，要检索 smile_item，需要访问七个节点。八个节点访问对应于 smiled_item 和 smiles_item，九个节点对应于 smiling_item。对于这四个项，总共有十四个节点。然而，它们都有相同的前四个字节（对应于前四个节点）。通过将这四个字节压缩以创建一个与 ['s']['m']['i']['l'] 相对应的 root，优化了四个节点访问。这意味着更少的内存和更少的节点访问，这是一个非常好的迹象。可以递归地应用这种优化，以减少访问不必要的后缀字节的需要。最终，您会到达一个只比较搜索键和由 trie 索引的键在位置上的差异的点。这就是基数 trie。

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

为了检索项，每个节点都需要一个位置。使用搜索关键字“smiles”和root.position为4，我们访问root["smiles"[4]]，这恰好是root['e']。我们将其存储在名为current的变量中。current.position为5，这是"smiled"和"smiles"之间差异的位置，因此下一个访问将是root["smiles"[5]]。这将带我们到smiles_item，并结束了我们的字符串。我们的搜索已终止，并且已经检索到该项，只需进行三次节点访问，而不是八次。

什么是PATRICIA trie？

PATRICIA trie是基数树的一种变体，其中应仅使用n个节点来包含n个项目。在我们上面简单演示的基数树伪代码中，总共有五个节点：root（它是一个零元节点；它不包含任何实际值），root['e']，root['e']['d']，root['e']['s']和root['i']。在PATRICIA trie中，应该只有四个。让我们通过以二进制形式查看这些前缀的不同之处来了解它们的区别，因为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`作为分支和/或额外的内部信息来表示搜索何时终止，不如将分支链接回树的某个位置，因此当要测试的偏移量减少而不是增加时，搜索就会终止。下面是这样一棵简单的图（尽管PATRICIA实际上更像是一个循环图，而不是一棵树，正如您将看到的那样），它包含在下面提到的Sedgewick的书中：

简单的PATRICIA图

可以使用长度不同的键来创建更复杂的PATRICIA算法，但是在这个过程中会失去一些PATRICIA的技术特性（即任何节点都与其前一个节点具有公共前缀）。

通过这种方式进行分支，有许多好处：每个节点都包含一个值。这包括根节点。因此，代码的长度和复杂性变得更短，实际上可能更快。要查找一个项，至少需要跟踪一个分支，最多需要跟踪k个分支（其中k是搜索键中的位数）。节点很小，因为它们只存储两个分支，这使它们非常适合于缓存局部性优化。这些特性使PATRICIA成为我目前最喜欢的算法之一...

为了减轻即将到来的关节炎的严重程度，我要在这里简短地描述一下，但是如果您想了解有关PATRICIA的更多信息，可以参考Donald Knuth的《计算机编程艺术，第3卷》或Sedgewick的《{your-favourite-language}算法，第1-4部分》等书籍。

- autistic

@BuckCherry 我很想回复你，但是请理解我的电脑被盗了，我无法投入足够的精力来做出一个恰当的回应。 - autistic

这张从维基百科获取的图似乎描绘了一个Trie树，至少插入了键'A'、'to'、'tea'、'ted'、'ten'和'inn'。虽然不想挑剔，但实际上这里的数字是值，因此还有'i'和'in'。 - Ervadac

@autistic如果我现在想插入一个以1011 0011开头的键，会发生什么？ - Daniel

@Daniel 我感觉你在我写“如果你想了解更多关于PATRICIA的信息，可以查阅诸如……”之前就停止阅读了。这些书详细介绍了所有明显问题的答案，精确地回答了这些问题，因此我们不必在互联网上重复它们（可能出现错误），从而提高了您的教育质量和速度。尽管如此，对于PATRICIA的插入过程始于搜索位的第一个差异，同时遍历树进行搜索。如果第一个差异发生在位0上，就像你的例子一样，那么新节点很可能成为根节点。‍♂️ - autistic

塞奇威克的一本书实际上是我来到这里的原因。在此期间，我已经理解了它，但是塞奇威克的阅读令人痛苦。他在30页前说过一些实际上解释了一切的话，但之后再也没有提到过，所以如果我恰好跳过了那部分而进入这本书，我将会缺少一些至关重要的细节，这些细节可能很难理解。 - Daniel

显示剩余3条评论

28

Trie（字典树）:
可以使用一种搜索方案，其中不是将整个搜索关键字与所有现有关键字进行比较（例如哈希方案），而是可以逐个字符地比较搜索关键字。按照这个想法，我们可以构建一个结构（如下所示），其中有三个现有的关键字 -“dad”、“dab”和“cab”。

         [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:
通常，trie 中的一个节点使用大小为 R 的数组，因此当每个节点具有较少的边缘时会造成内存浪费。为了解决内存问题，提出了各种建议。基于这些变化，trie 也被命名为“compact trie”和“compressed trie”。尽管一致的命名方法很少见，但最常见的紧凑 trie 版本是在节点只有单个边缘时将所有边缘分组。使用此概念，以上（图-I）包含关键字“dad”、“dab”和“cab”的trie 可以采用以下形式。

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

注意，每个“c”、“a”和“b”都是其相应父节点的唯一边缘，因此它们被合并成一个单一的边缘“cab”。同样，‘d’和‘a’被合并为标记为“da”的单一边缘。基数 Trie: 在数学中，“基数”意味着数字系统的基础，它实际上表示表示该系统中任何数字所需的唯一符号的数量。例如，十进制系统是基数十，二进制系统是基数二。使用类似的概念，当我们有兴趣通过底层表示系统的唯一符号数来表征数据结构或算法时，我们会将该概念标记为“基数”。例如，用于某些排序算法的“基数排序”。在同样的逻辑线上，所有依赖于基数的字母表的特征（如深度、内存需求、搜索未命中/命中运行时间等）的trie的变体，我们可以称之为基数“trie”。例如，当使用字母a-z时，未压缩的trie以及压缩的trie，我们可以称之为基数26 trie。只使用两个符号（传统上为“0”和“1”）的任何trie都可以称为基数2 trie。然而，一些文献仅限制使用术语“基数Trie”仅用于压缩的trie。 PATRICIA树/trie 的前奏: 有趣的是，甚至字符串键也可以使用二进制字母表表示。如果我们假设ASCII编码，则将密钥“dad”写成二进制形式可以通过按顺序写入每个字符的二进制表示来完成，例如“01100100 01100001 01100100”即写二进制形式的‘d’、‘a’和‘d’。使用这个概念，可以形成一个基数为二的trie。下面我们使用一个简化的假设来描述这个概念，即字母’a’、’b’、’c’和’d’来自一个较小的字母表而不是ASCII。注意Fig-III：如上所述，为了使描绘容易，让我们假设只有4个字母{a，b，c，d}和它们对应的二进制表示分别为“00”，“01”，“10”和“11”。有了这个，我们的字符串键“dad”、“dab”和“cab”变成了“110011”，“110001”和“100001”。对应的trie如图III所示（位从左到右读取，就像字符串从左到右读取一样）。

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

PATRICIA Trie/Tree:
PATRICIA 树（称为“可扩展字母缩写树”）是一种数据结构，它是由 Donald R. Morrison 在 1968 年提出的。通过去除单向边（即仅有一个子节点的分支），他既消除了内部节点和叶子节点的区别，也极大地减少了节点数量。相比之下，上图中的二进制 trie 经过单边压缩后，其节点数量仍然大于包含键数的 3 个节点。PATRICIA 树的每个节点包含一个值，用于指示需要跳过多少位以进行分支决策。不同于其他压缩逻辑，它不存储键本身，因此无法用于列出与给定前缀匹配的所有键，但可用于查找某个键是否存在于 trie 中。值得注意的是，“Patricia Tree” 或 “Patricia Trie” 这个术语已被广泛应用于许多类似但不完全相同的概念，例如表示紧凑的 trie（NIST），或者表示基数为二的基数 trie（如维基百科中微妙的表述）等。

Trie that may not be a Radix Trie:
三叉搜索树(Ternary Search Trie，又称Ternary Search Tree)是一种数据结构(由 J. Bentley 和 R. Sedgewick 提出)，看起来非常类似于具有三向分支的 trie 树。对于此类树，每个节点都有一个特征字母'x'，以便通过键的字符是小于、等于还是大于'x'来进行分支决策。由于它具有固定的3向分支特性，因此在R（基数）很大时，如Unicode字母表中，它提供了一种内存占用更少的替代trie的方法。与(R路)trie不同，TST的特征没有受到R的影响。例如，TST的搜索未命中时间复杂度为ln(N)，而R-way Trie的为log_R(N)。此外，TST的内存需求也不是R的函数。因此，在称呼TST为基数trie时要小心谨慎。我个人认为我们不应该将其称为基数trie，因为我所知道的其特征都不受其底层字母表的基数R的影响。

- KGhatak

4

作为一个按照Morrison、Sedgewick和Knuth的方法实现了PATRICIA的人，我可以告诉你，你在这里描述的算法（我也试图在我的答案中描述）仍然非常适合回答类似“列出所有与给定前缀匹配的键”的问题。顺便说一句，很高兴看到其他人也对那个问题有所关注 :) 我喜欢那个解释。 - autistic

“不适合回答类似于列出所有与给定前缀匹配的键”的问题，真的吗？” - Pacerier

@Pacerier 当然可以！经典的PATRICIA存储一个整数，你可以将其用作数组的索引。将字符串放入数组中。将基于0的数组索引放入trie中。使搜索、比较和位提取函数操作与整数对应的字符串，而不是整数。如果你的插入函数基于其他函数（因为那里有很多重复的逻辑），那么你就会走得更远。你也可以使用uintptr_t作为你的整数，因为这种类型似乎通常被期望存在（尽管不是必需的）。 - autistic

@autistic 如果我想插入0011...，但它与其他字符串没有共同前缀，那么会发生什么？ - Daniel

请问作者或查阅教材。我建议您在提问前先做一些研究，不要再问这样的问题了。替换操作是指将字符串中所有匹配某一模式的字符替换成另一个指定的字符串。 - autistic

显示剩余5条评论

9

在Trie树中，大多数节点不存储键，只是连接键和其扩展的节点路径上的跳跃点。这些跳跃点大部分是必要的，但当我们存储长单词时，它们往往会产生一长串只有一个子节点的内部节点链。这是Trie树需要太多空间的主要原因，有时比二叉搜索树还多。

基数树（也称为基数树，即 Patricia 树）的思想是我们可以压缩路径，例如在“中间t节点”之后，我们可以在一个节点中具有“hem”，或者在一个节点中具有“idote”。

以下是比较 Trie 和 Radix Trie 的图表：

原始Trie树有9个节点和8条边，假设每条边占用9个字节，每个节点占用4个字节的开销，那么就意味着：

       9 * 4 + 8 * 9 = 108 bytes.

右侧的压缩字典树有6个节点和5条边，但在这种情况下，每条边携带一个字符串而不仅仅是一个字符。但是，我们可以通过单独考虑边引用和字符串标签来简化操作。这样，我们仍然会计算每条边9个字节的成本（因为我们将包括边缘成本中的字符串终止字节），但我们可以将字符串长度的总和添加到最终表达式的第三个术语中；需要的总字节数由以下公式给出：

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

对于这个简单的 Trie 数据结构，压缩版本需要比原始版本少30% 的内存。

参考链接：https://freecontent.manning.com/marcello-la-rocca-advanced-algorithms-and-data-structures/

- Yilmaz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ivaylo Strandjev · Accepted Answer

基数树是字典树的一种压缩形式。在字典树中，每个边上只写一个字母，而在PATRICIA树（或基数树）中，您存储整个单词。

现在，假设您有单词hello、hat和have。要将它们存储在字典树中，它会像这样：

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

你需要九个节点。我已经将字母放在节点上，但实际上它们标记的是边缘。

在基数树中，您将拥有：

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

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

因此，总体而言，基数树占用的内存较少，但实现起来更困难。否则，两者的用例几乎相同。