Trie树遍历如何加速？_西西软件资讯

类型：FTP 工具大小：106KB语言：中文评分：5.0
标签：

立即下载

　Trie树用来给字符串排序的时候有一个好处：边读边排序，但是读完之后要输出的时候麻烦来了。经过测试，用26W个word建立的Trie中，空白位是使用位的20倍左右，那么在Trie比较大的时候当然也就比较慢了。这篇文章讨论的优化主要是去避免访问这些空白位，实现方式无关（数组或指针？）。

　　首先想到的一个方法是：在insert的时候顺便标记这个节点有哪些子节点。因为总共只有26种可能性，那么自然也就想到了用一个int作为flag，如果0位置1则表示有‘a’这个子节点。

　　第一步（记录）完成了，下面我们来看如何来使用该记录？熟悉位移的同学可能已经想到：可以使用x&-x来计算出最低位为1的数。但是遗憾的是这个并不是我们想要的结果，因为得到的是2^N，我们想要的是这个N。好的，最笨的一种方法出来了：

　　int t[] = new int[1<<26];

　　t[1<<0] = 0.....

非常遗憾的是我们申请不了这么大的空间。那么，问题就是将一些离散的数通过数组建立映射关系，很自然地就会联想到Hash。怎么使用Hash呢？我尝试了一下，从2^0到2^26对29取余数为：

　　1.2.4.8.16.3.6.12.24.19.9.18.7.14.28.27.25.21.13.26.23.17.5.10.20.11

没有看错，没有一个是相同的！这样的话就可以仅仅使用一个大小不到30的数组就可以搞定。同样遗憾的时候，这里用到了取余数的操作，要知道这个还算比较大的，可能一不小心就把我们辛辛苦苦省下来的时间又葬送掉了。那么有没有其他的方法呢？还是回到最笨的方法的思路上：

　　如果我们申请不了int[1<<26]，那申请int[1<<13]总是可以的吧？

为什么这么做呢？因为申请不了这么大的空间！这时候就把这个问题换成两半了，比如在节点I出的标志位flag：

　　int lowHalf = flag&((1<<14)-1);

　　int highHalf = (flag>>13)&((1<<14)-1);

　　while(lowHalf > 0){

　　　　int i = lowHalf&-lowHalf;

　　　　int j = t[i];

　　　　// do someting

　　}

　　while(highHalf > 0){

　　　　int i = highHalf&-highHalf;

　　　　int j = t[i]+13;

　　　　// do someting

　　}

和最笨的那种方法相比，只是多了一次操作而已。

　　好了现在来看最后一种方法，就不多写了：

　　switch(flag&-flag){

　　case 1<<0:

　　case 1<<1:

　　case 1<<2:

　　.....

　　}

PS：直接用一个整数来表示：
没有子节点为:0
a节点为:1 << 0
b节点为：1 << 1
......
z节点为: 1 << 25

最后还需一位来表示是否单词 1 << 26,当然，如果没有子节点，自然是单词了。

判断是否有z节点只要 &(1<<25)就好

如果遍历，可以先 | 0 一下减少是最终节点的操作