双数组Trie树算法优化及其应用研究  

Research of Optimization on Double-Array Trie and its Application

作　　者：王思力[1] 张华平[1] 王斌[1] 

机构地区：[1]中国科学院计算技术研究所

出　　处：《中文信息学报》2006年第5期24-30,共7页Journal of Chinese Information Processing

基　　金：国家973项目资助(2004CB318109);国家242信息安全计划资助课题成果(2005C36);中国科学院计算所知识创新工程资助(20056550)

摘　　要：本文对双数组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.

关 键 词：计算机应用 中文信息处理 双数组 TRIE树 词典 分词 

分 类 号：TP391.1[自动化与计算机技术—计算机应用技术]