| 双数组Trie树算法优化及其应用研究 |
| |
| 引用本文： | 王思力,张华平,王斌.双数组Trie树算法优化及其应用研究[J].中文信息学报,2006,20(5):26-32. |
| |
| 作者姓名： | 王思力 张华平 王斌 |
| |
| 作者单位： | 1.中国科学院计算技术研究所2.中国科学院研究生院 |
| |
| 基金项目： | 国家973项目资助(2004CB318109)，国家242信息安全计划资助课题成果(2005C36)，中国科学院计算所知识创新工程资助(20056550) |
| |
| 摘 要： | 本文对双数组Trie树(Double-Array Trie)算法提出了一种优化策略,即在采用Trie树构造数组的过程中,优先处理分支结点数更多的结点。这种优化策略可以在保证该算法数据查找效率不变的同时,进一步减少数据稀疏,提高空间利用率。我们基于该优化算法实现了一个词典管理程序,并与利用其他索引机制的词典进行了实验对比。实验结果表明,利用优化的双数组Trie树算法的词典不仅在查询速度上优于用其他索引机制的词典,而且存储数据的空间占用也比较小。
|
| 关 键 词： | 计算机应用 中文信息处理 双数组 Trie树 词典 分词 |
| 文章编号： | 1003-0077（2006）05-0024-07 |
| 收稿时间： | 2005-08-28 |
| 修稿时间： | 2006-07-11 |
Research of Optimization on Double-Array Trie and its Application |
| |
| WANG Si-li,ZHANG Hua-ping,WANG Bin.Research of Optimization on Double-Array Trie and its Application[J].Journal of Chinese Information Processing,2006,20(5):26-32. |
| |
| Authors: | WANG Si-li ZHANG Hua-ping WANG Bin |
| |
| Affiliation: | 1.Institution of Computing Technology , The Chinese Academy of Sciences2.Graduate School of the Chinese Academy of Sciences |
| |
| 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. |
| |
| Keywords: | computer application Chinese information processing Double-Array TRIE lexicon word segmentation |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《中文信息学报》浏览原始摘要信息 |
|
点击此处可从《中文信息学报》下载全文 |
