基于遗传算法和舍伍德思想的双数组Trie树改进

• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 双数组索引 舍伍德随机思想 遗传算法 变异
• 年，卷（期）: 2009,（29）
• 所属期刊栏目: 数据库、信号与信息处理
• 页码范围: 128-130,152
• 页数: 4页
• 分类号: TP311
• 字数: 4576字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2009.29.038

摘要

对汉语信息处理中常常要涉及汉语词典查询,当所涉及的词典规模较为庞大时如何快速访问词典以获取词语知识便成为了一个需重点解决的问题.将阐述一种简单快捷的基于双数组Trie(Double-Array Trie)原理的词典查询机制.该算法的查询时间为O(n)的线性时间(n为查询词条的长度),由此可见双数组算法在时间上存在着明显优势,但在空间耗费上却存在着浪费现象.前人提出了一些解决方案,其中主要的有:在构造双数组时采用一种启发式排序策略,即每一次都先处理当前分支节点最多的活动节点.考虑到这种启发式思想为确定性算法,容易陷入局部最优陷阱之中,因此在这种思想的基础上引入了舍伍德随机思想和遗传算法中常常运用到的变异思想,在改进算法空间利用率的同时也使得算法跳出了局部最优解的陷阱.