string - 压缩的 trie 实现？

Question

我正在学习 Udacity 课程，并且在其中一堂课（https://www.youtube.com/watch?v=gPQ-g8xkIAQ&feature=player_embedded）中，教授给出的功能high_common_bits（从讲座中逐字提取）看起来像这在伪代码中：

function high_common_bits(a,b):
   return:
     - high order bits that a+b in common
     - highest differing bit set
     - all remaining bits clear

举个例子：

a = 10101
b = 10011
high_common_bits(a,b) => 10100

然后他说这个函数用于高度优化的尝试实现。有谁碰巧知道他指的是哪个确切的实现？

score 5 · Accepted Answer

如果您正在寻找高度优化的按位压缩树（又名基数树）。BSD 路由表在其实现中使用一个。虽然代码不容易阅读。

score 1 · Accepted Answer

他说的是简洁尝试，每个节点只需要存储两个位（理论上的最小值）的尝试。

Steve Hanov 在这里写了一篇关于简洁尝试的非常平易近人的博客文章。您还可以阅读 Guy Jacobson 的原始论文（写于 1989 年），这里介绍了它们。

score 0 · Accepted Answer

压缩的 trie 将前缀存储在一个节点中，然后从该节点分支到已看到的以该前缀开头的每个可能项。

在这种情况下，他显然是在进行逐位尝试，因此它存储了位前缀——即，项目共同的开头位进入一个节点，然后从该节点有两个分支，一个到下一位的节点为 0，下一位的节点为 1。据推测，这些节点也会被压缩，因此它们不会只存储下一位，而是存储一些位到目前为止，在插入到 trie 中的项目中都匹配。

事实上，给定节点之后的下一位可能根本不会存储在后续节点中。该位可以隐含在后面的链接中，因此下一个节点仅存储之后的位。

3 回答 3