基于双数组Trie树的中文分词词典算法优化研究

• 作者: 于淼 刘健 杨文川
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 双数组 Trie树 时间复杂度 分词词典
• 年，卷（期）: 2013,（9）
• 所属期刊栏目: 数据挖掘
• 页码范围: 127-131
• 页数: 5页
• 分类号: TP391.3
• 字数: 3645字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2013.09.021

摘要

基于双数组Trie树的中文分词词典具有较高的查找效率,但其插入时间复杂度较高.为此提出了一种基于双数组Trie树结构的改进算法iDAT,在原始词典初始化时优先处理分支多的节点,并在初始化之后对base数组中的空序列的下标值做Hash,Hash表中存放空序列之前的所有空序列个数之和,而后运用iDAT算法进行插入.本算法借鉴了单模式匹配的Sunday算法中的跳跃思想,在适当增加空间开销的基础上,降低了Trie树在动态插入过程中的平均时间复杂度,在实际操作过程中有着良好的性能.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	于淼	北京邮电大学计算机学院	2	19	2.0	2.0
2	杨文川	北京邮电大学计算机学院	10	39	4.0	6.0
3	刘健	北京邮电大学计算机学院	1	15	1.0	1.0