algorithm - trie 和 radix trie 数据结构有什么区别？

Question

trie和radix trie数据结构是否相同？

如果它们不一样，那么基数特里（AKA Patricia trie）的含义是什么？

Answer 1

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

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

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

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

在基数树中，您将拥有：

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

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

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

Answer 2

我的问题是Trie数据结构和Radix Trie是否是一回事？

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

如果它们 [n't] 相同，那么 Radix trie（又名 Patricia Trie）的含义是什么？

我假设您打算写的不在您的问题中，因此我进行了更正。

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

---

什么是特里？

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

这张从 Wikipedia 检索到的图表似乎描绘了一个带有（至少）键“A”、“to”、“tea”、“ted”、“ten”、“i”、“in”和“inn”的树插入：

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

---

什么是基数？

正如 Ivaylo Strandjev 在他的回答中所描述的那样，“基数特里树”似乎描述了一种压缩常见前缀部分的特里树形式。考虑一个 256 路的 trie，它使用以下静态分配索引键“smile”、“smiled”、“smiles”和“smiling”：

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。对于这四个项目，总共有十四个节点。但是，它们都有前四个字节（对应于前四个节点）。通过压缩这四个字节以创建root对应于的 a ['s']['m']['i']['l']，四个节点访问已被优化掉。这意味着更少的内存和更少的节点访问，这是一个很好的指示。可以递归地应用优化以减少访问不必要的后缀字节的需要。最终，您只需要比较trie 索引位置的搜索键和索引键之间的差异. 这是一个基数树。

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

要检索项目，每个节点都需要一个位置。使用“smiles”的搜索键和root.position4 的 a，我们访问root["smiles"[4]]，恰好是root['e']。我们将其存储在一个名为 的变量中current。current.position是 5，也就是 和 之间的差的位置"smiled"，"smiles"所以接下来的访问将是root["smiles"[5]]。这将我们带到smiles_item, 和字符串的结尾。我们的搜索已终止，并且该项目已被检索，只有三个节点访问而不是八个。

---

什么是 PATRICIA 特里？

PATRICIA trie 是基数尝试的变体，它应该只存在n用于包含n项目的节点。在上面我们粗略演示的 radix trie 伪代码中，总共有五个节点：（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 的一些技术特性在此过程中丢失了（即任何节点都包含与它之前的节点相同的前缀）：

通过这样的分支，有很多好处： 每个节点都包含一个值。这包括根。结果，代码的长度和复杂性变得更短，实际上可能更快一些。遵循至少一个分支和最多k分支（其中k是搜索关键字中的位数）来定位项目。节点很小，因为它们每个只存储两个分支，这使得它们非常适合缓存局部性优化。这些属性使 PATRICIA 成为我迄今为止最喜欢的算法......

我将在这里缩短这个描述，以减少我即将发生的关节炎的严重程度，但如果你想了解更多关于 PATRICIA 的信息，你可以查阅 Donald Knuth 的“计算机编程艺术，第 3 卷”等书籍，或 Sedgewick 的任何“{your-favourite-language} 中的算法，第 1-4 部分”。

Answer 3

TRIE：
我们可以有一个搜索方案，而不是将整个搜索键与所有现有键（例如哈希方案）进行比较，我们还可以比较搜索键的每个字符。按照这个想法，我们可以构建一个结构（如下所示），它具有三个现有的键——“<em>dad”、“<em>dab”和“<em>cab”。

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

(cab)   (dab)     (dad)

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

Compact TRIE：
通常情况下，trie中的节点使用 size=R 的数组，因此当每个节点的边数较少时会导致内存浪费。为了规避内存问题，提出了各种建议。基于这些变化，trie也被命名为“<em>compact trie”和“<em>compressed trie”。虽然一致的命名法很少见，但紧凑型树的最常见版本是通过在节点具有单边时对所有边进行分组来形成的。使用这个概念，上面（图一）带有键“ dad ”、“dab”和“cab”的树可以采用以下形式。

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

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

Radix Trie：
术语radix在数学中表示数字系统的基础，它本质上表示表示该系统中任何数字所需的唯一符号的数量。例如，十进制系统是基数十，二进制系统是基数二。使用类似的概念，当我们对通过底层表示系统的唯一符号的数量来表征数据结构或算法感兴趣时，我们用术语“基数”来标记这个概念。例如，某些排序算法的“基数排序”。在同一条逻辑中，trie的所有变体其特征（如深度、内存需求、搜索未命中/命中运行时等）取决于底层字母的基数，我们可以称它们为基数“trie's”。例如，当使用字母 az 时，未压缩和压缩的trie ，我们可以将其称为 radix 26 trie。任何只使用两个符号（传统上是 '0' 和 '1'）的 trie 都可以称为 radix 2 trie。然而，不知何故，许多文献将术语“Radix Trie”限制为仅用于压缩的trie。

PATRICIA Tree/Trie 的前奏：
有趣的是，即使作为键的字符串也可以使用二进制字母表示。如果我们假设 ASCII 编码，那么键“dad”可以通过按顺序写入每个字符的二进制表示来以二进制形式写入，例如“<strong>01100100 01100001 01100100 ”通过写入二进制形式的 'd', 'a ', 和 'd' 顺序。使用这个概念，可以形成一个trie （带有基数 2）。下面我们使用简化的假设来描述这个概念，即字母“a”、“b”、“c”和“d”来自较小的字母表而不是 ASCII。

图 III 的注意事项：如前所述，为了便于描述，我们假设一个只有 4 个字母 {a,b,c,d} 的字母表，它们对应的二进制表示是“00”、“01”、“10”和“11”分别。这样，我们的字符串键“dad”、“dab”和“cab”分别变为“110011”、“110001”和“100001”。对此的尝试将如下图 III 所示（从左到右读取位，就像从左到右读取字符串一样）。

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

PATRICIA Trie/Tree：
如果我们使用单边压缩来压缩上面的二叉树（图 III），它的节点会比上面显示的少得多，但是节点仍然会多于 3，它包含的键的数量. Donald R. Morrison（在 1968 年）发现了一种创新的方法，使用二叉树来描述仅使用 N 个节点的 N 个键，他将这种数据结构命名为PATRICIA. 他的 trie 结构基本上摆脱了单边（单向分支）；在这样做的过程中，他还摆脱了两种节点的概念——内部节点（不描述任何键）和叶节点（描述键）。与上面解释的压缩逻辑不同，他的 trie 使用不同的概念，其中每个节点都包含一个指示，指示要跳过多少位密钥以做出分支决策。他的 PATRICIA trie 的另一个特点是它不存储键 - 这意味着这种数据结构不适合回答诸如列出与给定前缀匹配的所有键之类的问题，但对于查找键是否存在或不在特里. 尽管如此，从那时起，Patricia Tree 或 Patricia Trie 一词已被用于许多不同但相似的含义，例如，表示紧凑的 trie [NIST]，或表示具有基数 2 的基数树 [如微妙的方式在 WIKI] 等等。

可能不是 Radix Trie 的 Trie：
Ternary Search Trie（又名 Ternary Search Tree）通常缩写为TST是一种数据结构（由J. Bentley和R. Sedgewick提出），看起来非常类似于具有三向分支的 trie。对于这样的树，每个节点都有一个特征字母“x”，因此分支决策是由一个键的字符是否小于、等于或大于“x”来驱动的。由于这个固定的 3 路分支特性，它为 trie 提供了一种节省内存的替代方案，尤其是当 R（基数）非常大时，例如 Unicode 字母表。有趣的是，与 (R-way) trie不同，TST的特性不受 R 的影响。例如，TST 的搜索未命中是ln(N)与R-way Trie 的log _R (N)相反。TST 的内存要求，与 R-way trie不同，它也不是R的函数。所以我们应该小心地将 TST 称为 radix-trie。我个人认为我们不应该称它为 radix-trie，因为（据我所知）它的特征都不受其底层字母的基数 R 的影响。

Answer 4

在尝试中，大多数节点不存储密钥，而只是在密钥和扩展它的节点之间的路径上的跳跃。大多数这些跃点都是必要的，但是当我们存储长单词时，它们往往会产生长链的内部节点，每个节点只有一个子节点。这是尝试需要太多空间的主要原因，有时甚至超过 BST。

基数尝试（又名基数树，又名帕特里夏树）基于我们可以以某种方式压缩路径的想法，例如在“中间 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%。