背景
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
本文作者 ： cyningsun
本文地址 ： https://www.cyningsun.com/03-21-2016/trie.html
版权声明 ：本博客所有文章除特别声明外，均采用 CC BY-NC-ND 3.0 CN 许可协议。转载请注明出处！