字符串-Trie


  1. 背景
  2. 中文字符如何构建Trie
  3. Trie的优化
  4. 待续
  5. 引用资料

背景

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