压缩的实施？

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 

然后他说这个函数用在try的高度优化的实现中。有人碰巧知道他指的是哪个确切的实施？

Answer 1

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

在这种情况下，他显然是在做一个按位的trie，所以它存储了一个位的前缀 - 也就是说，这些位在项的开始处共有一个节点，然后有两个分支节点，一个节点的下一个位为0，另一个为下一个位1.假定这些节点也将被压缩，所以它们不会只存储下一个单一位，而是存储一个到目前为止插入到特里的项目中全部匹配的比特数。

实际上，给定节点之后的下一个位可能根本不存储在以下节点中。该位可以隐含在所遵循的链接中，所以下一个节点仅在那之后存储位。

Answer 2

如果您正在寻找高度优化的按位压缩树（即基树）。 BSD routing table在它的实现中使用了一个。代码是不是虽然容易阅读。

Answer 3

他在谈论简洁尝试，tries其中每个节点只需要两位来存储（理论最小值）。

Steve Hanov在Succinct Tries here上写了一篇非常平易近人的博客文章。您还可以阅读Guy Jacobson （最近编写为1989年）的原始文件，其中介绍了他们here。