基于TRIE索引树的结构在分词词典数據结构中普遍采用即便在改进的数据结构中其思想也都保持不变,本文以TRIE索引树来对分词词典进行一些分析
数据结构首先包含一个首芓的数组,每个数组的offset即某个汉字的编码转化为short整形的值(一个汉字2字节)gb2312编码表可以参见:。例如“啊”是编码表中的首个汉字,編码为45216则该数组(A)的啊所在的位置为A[45216];至少需要包括两个字段【该字开头的trie数的孩子数】【该字开头的trie树的location】,首字数组可以看作是樹根数组存放着全部树根。
其下的TRIE树在检索词汇的第二字第三字时进行匹配发挥作用,至少需要包含汉字编码(2字节)孩子数(2字節),location(4字节)当汉字编码为0表示已经到词汇的终结位置,【location】上存放的是该词的统计信息词频,查询频率等等
注意这样存储的词典是支持随机查找的,给定一个词汇可以认为在O(k)的时间复杂度下找到该词汇是否存在,以及其统计信息的位置
粗略算来TRIE树只比顺序存储增加了30%的存储代价,即获得了随机查询的能力
TRIE树很现在前缀相同的情况下大大节约了开销,但同时由于需要存储过多的location(链式存放的弊端)导致存储代价的提高,
有没有更好的方法来降低所需的内存消耗同时提高随机查询的速度呢?