本文对双数组Trie树(Double-Array Trie)算法提出了一种优化策略,即在采用Trie树构造数组的过程中,优先处理分支结点数更多的结点。这种优化策略可以在保证该算法数据查找效率不变的同时,进一步减少数据稀疏,提高空间利用率。我们基于该优化算法实现了一个词典管理程序,并与利用其他索引机制的词典进行了实验对比。实验结果表明,利用优化的双数组Trie树算法的词典不仅在查询速度上优于用其他索引机制的词典,而且存储数据的空间占用也比较小。
Abstract
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树 /
词典 /
分词
{{custom_keyword}} /
Key words
computer application /
Chinese information processing /
Double-Array /
TRIE /
lexicon /
word segmentation
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] 殷人昆,陶永雷,谢若阳,盛绚华. 数据结构(用面向对象方法与C++描述) [M]. 北京:清华大学出版社 1999.
[2] Douglas C. Schmidt. GPERF: A Perfect Hash Function Generator[Z]. 1999.
[3] Theppitak Karoonboonyanan. An Implementation of Double-Array Trie[Z] , http://linux.thai.net/～thep/datrie/datrie.html, 2003.
[4] Jun-Ichi Aoe, Katsushi Morimoto, Takashi Sato, An Efficient Implementation of Trie Structures [J]. Software-Practice and Experience. 1992, 22 (9) : 695-721.
[5] Aoe, J. An Efficient Digital Search Algorithm by Using a Double-Array Structure [J]. IEEE Transactions on Software Engineering. 1989, 15 (9) : 1066-1077.
[6] 孙茂松,左正平,黄昌宁. 汉语自动分词词典机制的实验研究[J]. 中文信息学报, 2000, 14 (1) : 1 - 6.
[7] 杨文峰,陈光英,李星. 基于PATRICIA tree的汉语自动分词词典机制[J]. 中文信息学报, 2001, 15 (3) : 44 - 49.
[8] 马哲,姚敏. 一种改进的基于PATRICIA树的汉语自动分词词典机制[J]. 华南理工大学学报(自然科学版) , 2004. 32 (增刊) : 28 - 31.
[9] 路志英,林孔元,郭祺,段广玉. 中文切分词典的最大匹配索引法[J]. 天津大学学报, 1999, 32 (5) : 599 - 603.
[10] 李庆虎,陈玉健,孙家广. 一种中文分词词典新机制——双字哈希机制[J]. 中文信息学报, 2003, 17 (4) : 13 - 18.
[11] 刘群,张华平,俞鸿魁,程学旗. 基于层次隐马模型的汉语语法分析[J]. 计算机研究与发展, 2004. 8.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家973项目资助(2004CB318109);国家242信息安全计划资助课题成果(2005C36);中国科学院计算所知识创新工程资助(20056550)
{{custom_fund}}
PDF(322 KB)
