摘要
本文对双数组Trie树(Doub le-Array Trie)算法提出了一种优化策略,即在采用Trie树构造数组的过程中,优先处理分支结点数更多的结点。这种优化策略可以在保证该算法数据查找效率不变的同时,进一步减少数据稀疏,提高空间利用率。我们基于该优化算法实现了一个词典管理程序,并与利用其他索引机制的词典进行了实验对比。实验结果表明,利用优化的双数组Trie树算法的词典不仅在查询速度上优于用其他索引机制的词典,而且存储数据的空间占用也比较小。
This paper proposes an improved strategy for the algorithm of Double-Array Trie that is, the node with most child nodes is praessed firstly when constructing the array. This strategy can reduce the data sparseness and keep the search efficiency meanwhile. We implement a program for lexicon management base on the improved Double-Array Trie and compare it with other index mechanisms. The results clearly show that the improved Double-Array-Trie algorithm has a much higher search speed and needs a smaller space for data store than other index machanisms.
出处
《中文信息学报》
CSCD
北大核心
2006年第5期24-30,共7页
Journal of Chinese Information Processing
基金
国家973项目资助(2004CB318109)
国家242信息安全计划资助课题成果(2005C36)
中国科学院计算所知识创新工程资助(20056550)
关键词
计算机应用
中文信息处理
双数组
TRIE树
词典
分词
computer application
Chinese information processing
Double-Array
TRIE
lexicon
word segmentation
