基于双数组Trie树的中文分词词典算法优化研究
【出 处】:
【作 者】:
杨文川
[1] ;
刘健
[1] ;
于淼
[1]
【摘 要】
摘要:基于双数组Trie树的中文分词词典具有较高的查找效率,但其插入时间复杂度较高。为此提出了一种基于5iX数组Trie树结构的改进算法iDAT,在原始词典初始化时优先处理分支多的节点,并在初始化之后对base数纽中的空序列的下标值做Hash,Hash表中存放空序列之前的所有空序列个数之和,而后运用iDAT算法进行插入。本算法借鉴了单模式匹配的Sunday算法中的跳跃思想,在适当增加空间开销的基础上,降低了Trie树在动态插入过程中的平均时间复杂度,在实际操作过程中有着良好的性能。
相关热词搜索: 双数组 Trie树 时间复杂度 分词词典 double-array ~ Trie-tree ~ time complexity ~ word segmentation dictionary
上一篇:Web服务个性化推荐研究综述
下一篇:基于几何规划的布尔可满足问题求解方法