基于TRIE索引树的结构在分词词典数据结构中普遍采用,即便在改进的数据结构中其思想也都保持不变,本文以TRIE索引树来对分词词典进行一些分析。
数据结构首先包含一个首字的数组,每个数组的offset即某个汉字的编码转化为short整形的值(一个汉字2字节)。gb2312编码表可以参见:http://linux.chinaunix.net/techdoc/desktop/2009/03/12/1101139.shtml。例如,“啊”是编码表中的首个汉字,编码为45216,则该数组(A)的啊所在的位置为A[45216];至少需要包括两个字段【该字开头的trie数的孩子数】【该字开头的trie树的location】,首字数组可以看作是树根数组,存放着全部树根。
其下的TRIE树在检索词汇的第二字,第三字时进行匹配发挥作用,至少需要包含汉字编码(2字节),孩子数(2字节),location(4字节),当汉字编码为0表示已经到词汇的终结位置,【location】上存放的是该词的统计信息,词频,查询频率等等。
我们来大致估算一些这样做的代价。
假定我们基于以下信息来做出估算。
词典数量为10万个词汇,单字,2字词,3字词,4字词的比例约为3.6%,64% 16% 14%
首字的开销为:65536*6B = 390K
2字词的开销为:64k*8B = 512k
3字词的开销为:16k*8B = 128K
4字词的开销为:14k*8B = 112k
其余词的开销为:2.4k*8B = 19.2k
合计大小约为1 161.2K
注意这样存储的词典是支持随机查找的,给定一个词汇,可以认为在O(k)的时间复杂度下找到该词汇是否存在,以及其统计信息的位置。
如果词典是顺序存储的,每个单词后面加一个location域,这样需要的存储开销为
首字:3.6k*6 = 21.6k
2字: 64k*8 = 512k
3字: 16k*10 = 160k
4字: 14k*12 = 168k
其他: 2.4*14 = 33.6k
合计大小为:895.2K
粗略算来TRIE树只比顺序存储增加了30%的存储代价,即获得了随机查询的能力。
TRIE树很现在前缀相同的情况下大大节约了开销,但同时由于需要存储过多的location(链式存放的弊端),导致存储代价的提高,
有没有更好的方法来降低所需的内存消耗,同时提高随机查询的速度呢?
图片来源:http://www.docin.com/p-44568531.html