对于字符串的高效处理一般都是用字典树——Trie，或者ac自动机的。但是字典树对于大量数据的空间的开销相当大，特别我们的字典中不仅仅是26个字母组成的字符串时空间的损耗就会巨大无比。。。
三叉搜索树就是一种比较好的解决方法，我第一次看到的时候时在最近的《程序员》杂志上的一篇文章——《用三叉搜索树实现高效率的“自动完成”》，是一个.net大牛写的～于是我便对这个产生了兴趣，在折腾几天后，终于用java也写了一个很挫的三叉搜索树（见用三叉搜索树实现高效字符查找）。
其实所谓的三叉树就是舍去了Trie的多余的指针，而是把一个个树套在一起，每个节点压缩成三个方向。如果匹配的话就走中间方向的指针，如果不匹配，那么就走左或者右指针。选左选右则是这个数据结构优化的一个好地方，我用了字母顺序，文章作者说这个是最挫的方法。。。窘一个。。。好方法我还没有想到，因为不会写自平衡的树。。。杯具一个。。。
这里有一个例子，假如我们存入”AB”,”ABBA”.”ABCD”.”BCD”,这几个单词，那么三叉树就会出现如下的储存方式。。。
红线表示匹配的箭头～黄色的表示单词结尾
评论:9
参与评论