一种改进的Wu-Manber多关键字匹配算法  

An Improvement of Wu-Manber Multiple Patterns Matching Algorithm

作　　者：莫德敏[1] 刘耀军[2] 

机构地区：[1]太原科技大学计算机科学与技术学院,山西太原030024 [2]太原师范学院计算机系,山西太原030012

出　　处：《中文信息学报》2009年第1期30-34,共5页Journal of Chinese Information Processing

摘　　要：针对Wu-Manber算法在处理公共子后缀模式情况下的不足,该文提出了一种基于非空公共子后缀模式的处理算法。该算法把有非空公共子后缀的模式汇集在一起,进一步减小了next链表的平均长度。在匹配过程中减少了字符比较的次数,从而提高算法的运行效率。该文对搜狗实验室给出的相关文档进行全文检索实验,并和原Wu-Manber算法、孙晓山等提出的改进算法进行比较。实验结果表明,该文提出的改进算法有效地减少了匹配过程中字符比较的次数,从而提高匹配的速度和效率。This paper proposes a modified Wu-Manber algorithm based on the-free subsuffix for multiple patterns matching . The algorithm reduces the amount of string matching by collecting patterns with common subsuffix. The experiments based on documents provided by Sogou indicate that the suggested algorithm can significantly improve the efficiency of string matching compared with the original Wu-Manber algorithm and its modified version.

关 键 词：计算机应用 中文信息处理 Wu—Manber算法 多关键字匹配 模式匹配 字符串匹配 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]