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

Question

是特里和基数特里数据结构是一回事吗？

如果它们相同,那么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类别,但这并不意味着所有尝试都是基数尝试.

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

我认为你打算写的不是你的问题,因此我的纠正.

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

什么是特里？

"Trie"描述了适合用作关联阵列的树数据结构,其中分支或边缘对应于键的部分.这里,部分的定义相当模糊,因为尝试的不同实现使用不同的比特长度来对应边缘.例如,二进制trie每个节点有两个边对应于0或1,而16路trie每个节点有16个边对应4位(或十六进制数:0x0到0xf).

从维基百科中检索到的这个图表似乎描绘了一个带有(至少)键'A','to','tea','ted','ten'和'inn'的插件:

如果这个特里要存储密钥't','te','i'或'in'的项目,则需要在每个节点上存在额外的信息,以区分具有实际值的nullary节点和节点.

什么是基数特里？

正如Ivaylo Strandjev在他的回答中所描述的那样,"Radix trie"似乎描述了一种融合常见前缀部分的特里结构形式.考虑一个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.对于这四个项目,总共有十四个节点.但是,它们都具有共同的前四个字节(对应于前四个节点).通过压缩这四个字节来创建root对应的四个字节,['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;

要检索项目,每个节点都需要一个位置.使用"微笑"和root.position4 的搜索键,我们可以访问root["smiles"[4]],这恰好是root['e'].我们将它存储在一个名为的变量中current.current.position是5,这是"smiled"和之间的区别的位置"smiles",所以下一次访问将是root["smiles"[5]].这带给我们smiles_item,并结束我们的字符串.我们的搜索已终止,并且已检索到该项目,只有三个节点访问而不是八个.

什么是PATRICIA特里？

PATRICIA trie是基数尝试的变体,其中应该只有n用于包含n项目的节点.在我们的粗略表明基数线索上述伪代码中,总共有五个节点:root(这是一个无参节点;它不包含任何实际值), ,,root['e'] 和.在PATRICIA特里,应该只有四个.让我们看看这些前缀如何通过二进制查看它们可能会有所不同,因为PATRICIA是一个二进制算法.root['e']['d']root['e']['s']root['i']

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-favorite-language},1-4部分中的算法".

Answer 3

TRIE:
我们可以有一个搜索方案,而不是将整个搜索关键字与所有现有关键字(例如哈希方案)进行比较,我们也可以比较搜索关键字的每个字符.按照这个想法,我们可以构建一个结构(如下所示),它有三个现有的键 - " dad "," dab "和" 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也被命名为" compact trie "和" compressed trie ".虽然一致的命名法很少见,但是当节点具有单个边缘时,通过对所有边缘进行分组来形成紧凑型线索的最常见版本.使用这个概念,上面的(图1)trie带有键"dad","dab"和"cab"可以采用下面的形式.

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

注意,'c','a'和'b'中的每一个都是其相应父节点的唯一边缘,因此,它们聚集成单个边缘"cab".类似地,'d'和''合并为标记为"da"的单边.

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

PATRICIA Tree/Trie的前奏:
有趣的是,即使字符串作为键也可以使用二进制字母表示.如果我们假设ASCII编码,则可以通过编写每个字符的二进制表示顺序写成二进制形式的密钥"dad",通过编写"d","a"的二进制形式来表示为" 01100100 01100001 01100100 ", 'd'顺序.使用这个概念,可以形成一个trie(带有Radix Two).下面我们使用简化的假设来描述这个概念,即字母'a','b','c'和''来自较小的字母而不是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:
如果我们使用单边压缩来压缩上面的二进制trie(图-III),它将比上面显示的节点少得多,但是,节点仍然会超过3,它包含的键数. 唐纳德·R·莫里森(1968年)发现了一种创新的方法,即使用二元trie仅使用N个节点来描绘N个键,并将这个数据结构命名为PATRICIA.他的trie结构基本上摆脱了单边(单向分支); 在这样做的同时,他还摆脱了两种节点的概念 - 内部节点(不描绘任何键)和叶节点(描绘键).与上面解释的压缩逻辑不同,他的线索使用不同的概念,其中每个节点包括指示要跳过多少位的密钥以进行分支决策.他的PATRICIA trie的另一个特点是它不存储密钥 - 这意味着这样的数据结构不适合回答问题,例如列出与给定前缀匹配的所有密钥,但是有助于查找密钥是否存在或不是在特里.尽管如此,从那时起,Patricia Tree或Patricia Trie这个术语已被用于许多不同但相似的意义上,例如,表示一个紧凑的trie [NIST],或表示基数为2的两基数[如微妙所示]在WIKI的方式]等等.

Trie可能不是Radix Trie:
三元搜索Trie(又名三元搜索树)通常缩写为TST是一种数据结构(由J. Bentley和R. Sedgewick提出),看起来非常类似于具有三向分支的trie.对于这样的树,每个节点具有特征字母'x',使得分支决定由键的字符是否小于,等于或大于'x'来驱动.由于这种固定的3路分支功能,它为trie提供了一种节省内存的替代方案,特别是当R(基数)非常大时,例如Unicode字母表.有趣的是,与(R-way)trie不同,TST 不具有受R影响的特征.例如,TST的搜索未命中是ln(N),而R-way Trie的对数_R(N).TST的存储器要求,不同于R-方式线索是NOT R的函数,以及.所以我们应该小心地将TST称为基数.我个人认为我们不应该把它称为基数,因为没有(据我所知)其特征受其基础字母的基数R的影响.

Answer 4

\n

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

\n

\n

\n

\n

基数尝试（又名基数树、帕特里夏树）基于我们可以以某种方式压缩路径的想法，例如在“中间 t 节点”之后，我们可以在一个节点中包含“hem”，或“idote”在\n个节点中。

\n

\n

下面是比较 trie 和 radix trie 的图表：

\n

\n

\n

原始 trie 有 9 个节点和 8 个边，如果我们假设一条边有 9 个字节\n，每个节点有 4 个字节的开销，这意味着

\n

\n

       9 * 4 + 8 * 9 = 108 bytes.\n

\n

\n

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

\n

\n

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

\n

对于这个简单的 trie，压缩版本需要的内存减少了 30%\n。

\n

参考

\n