改进的Wu-Manber多模式串匹配算法

摘要：

为提高串匹配算法在实际应用中的运算性能,对Wu-Manber 算法进行了改进.吸收了QS(Quick Search)算法的思想, 并利用匹配过程中匹配失败的信息, 达到最大跳跃距离, 实现了快速的多模式匹配算法.对改进后的算法和Wu-Manber算法进行对比实验,当最小模式长度较大时,改进后的算法性能与原算法基本相同;而当模式最小长度较小时(<9), 改进后的算法比原算法有显著提高,用于英文文本时比原算法的所用时间平均减少了8%～20%, 用于中文文本时平均减少了15%～30%.

关键词：多模式串匹配、字符串匹配、Wu-Manber算法

所属期刊栏目：46

分类号：TP301.6(计算技术、计算机技术)

资助基金：中国科学院资助项目60473082;科技部科研项目2003CB314801

在线出版日期：2006-06-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：555-558