字符串-Trie


背景

Trie字典树是一种常见的数据结构,在UC实习时同组的同学曾使用Trie进行词频统计。当然Trie还能用于快速检索(前缀匹配)。下面将探讨Trie的若干问题

中文字符如何构建Trie

1、GBK编码 汉字的GBK编码使用2字节编码,即2的16次。此种构建方式消耗的空间较大。 2、自建编码 由于方案一造成的浪费,由于常用汉字的数量远小于全部汉字,可以使用为出现的汉字分配唯一ID,进而使用该ID构建字典树。

Trie的优化

根据以上方法可以完成字典树的构建,但是仍然存在明显的问题,Trie结构消耗空间过大。Trie的本质是一个确定的有限自动机,Aoe.J提出了用两个线性数组来表示Trie树的方法,即Double Array Trie,具体的原理可以参考引用资料2。另,附录3、4为双数组Trie的Java和C++实现。

待续

好吧,资料越查越多,后续沿着附录5继续吧。

引用资料

1.http://sc.snu.ac.kr/~xuan/spe777ja.pdf 2.http://wenku.baidu.com/view/b5cdbd0490c69ec3d5bb7574.html 3.https://github.com/komiya-atsushi/darts-java 4.http://chasen.org/~taku/software/darts/ 5.http://blog.csdn.net/v_JULY_v/article/details/6897097