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

• 作者: 张华平 王思力 王斌
• 来源期刊: 中文信息学报
• 学科: 工学
• 关键词: 计算机应用 中文信息处理 双数组 Trie树 词典 分词
• 年，卷（期）: 2006,（5）
• 页码范围: 24-30
• 页数: 7页
• 分类号: TP391.1
• 字数: 5007字
• 语种: 中文
• DOI: 10.3969/j.issn.1003-0077.2006.05.004

摘要

本文对双数组Trie树(Double-Array Trie)算法提出了一种优化策略,即在采用Trie树构造数组的过程中,优先处理分支结点数更多的结点.这种优化策略可以在保证该算法数据查找效率不变的同时,进一步减少数据稀疏,提高空间利用率.我们基于该优化算法实现了一个词典管理程序,并与利用其他索引机制的词典进行了实验对比.实验结果表明,利用优化的双数组Trie树算法的词典不仅在查询速度上优于用其他索引机制的词典,而且存储数据的空间占用也比较小.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王斌	中国科学院计算技术研究所	325	6645	42.0	69.0