Yukang's Page

高效的Crit-bit Tree

2013-05-18

最近了解到有这么一种数据结构,想拿来在工作中做一些事情,结果效果不好。原来我的理解有一些不对。在这里记录一下。

Crit-bit tree是一种特别的树结构,一般用于存放字符串。Critbit tree是一种BitWise tries,其树的深度为O(longest-length),有点像二叉树,不过对于字符串做分支检测的时候代价很小。

Crit-bit快速高效的支持下面的一些操作:

  • 插入一个字符串
  • 测试一个字符串是否在树里
  • 删除一个字符串
  • 查找出树中所有以某个字符串开始的所有字符串

和hash有点像,不过hash对于第四点没这么方便。
我做了一些性能对比,测试数据是/usr/share/dict/words里面的所有单词,同时做插入和查询的操作。具体测试代码看这里,结果是:

critbit 11.6MB 23.34
set 21.6 MB 45.85s
trie 332.3 MB 17.84s

从中可以看到trie树的内存消耗是比较大的,但是查找速度最好。critbit的内存消耗真的非常小,如果只是把这里所有的单词存下来都要4MB的内存,其查找的速度虽然和trie树比起来差一些,但还是相当不错。

好好的研读了crit-bit的实现和这篇文章,里面技巧挺多的。
critbit的结构很简单:

typedef struct{
void* child[2];
uint32 byte;
uint8 otherbits;
}critbit0_node;
typedef struct{
void* root;
}critbit0_tree;

其中child是void*指针,对于树的内部节点其指向的是子节点,对于叶子节点其指向的是字符串。
byte用来表示当前节点匹配的长度,otherbits是一个mask,可以用来快速的取得不同最高位,在查询的过程中用这个来做branch。

具体的代码分析这里比较少,最复杂的函数是critbit0_insert。在插入过程中需要记录下来byte和otherbits,
并且更新前面的父节点。

critbit

然后再继续插入后的结构变化是:
critbit

下面记录一下其中的几个技巧。

align指针最后一位用来做标志

树的结构需要一个标志变量来表示是否是内部节点或者是叶子节点。这个变量如何能省掉?
看上面的void root和void child, 都是即可以用来指向字符串又可以指向节点,一般申请过来的指针变量都是align好的,所以最低位为0,这是可以拿来用的。因此对于内部节点我们可以在这个位上设置为1,只是要注意在通过这个指针取值的时候需要减回去。

a = (posix_memalign((void**)&x, sizeof(void*), ulen+1))

posix_memalign在这里用的是sizeof(void*),其实就和malloc一样了,因为一般Linux上编译器和C库已经处理了对齐问题。

因此在查找的这段代码里是这样的:

int critbit0_contains(critbit0_tree*t, const char* u) {
const uint8* ubytes= (void*)u;
const size_t ulen= strlen(u);
uint8* p= t->root;
if(!p) return 0;
while( 1 & (intptr_t)p ){ //内部节点?
critbit0_node* q = (void*)(p-1); //取得真正的指针
uint8 c = 0;
if(q->byte < ulen) c = ubytes[q->byte];
const int direction= (1+(q->otherbits|c))>>8;
p = q->child[direction];
}
//叶子节点
return 0 == strcmp(u, (const char*)p);
}

取最高位的非0bit

在插入过程中计算最高位的不同位。

newotherbits = p[newbyte]^ubytes[newbyte];

其实也可以用一个for循环来计算,不过这里是这样实现的:

newotherbits |= newotherbits>>1;
newotherbits |= newotherbits>>2;
newotherbits |= newotherbits>>4;

这相当于是计算不小于它的2的整数次幂,对于32bit的代码可以看看这里next_pow_of_2


文章和代码,其中那篇文章有详细分析。

我的测试代码,trie/set等

使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章