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

Improved Wu-Manber multiple patterns matching algorithm

作　　者：杨东红[1] 徐恪[1] 崔勇[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《清华大学学报（自然科学版）》2006年第4期555-558,共4页Journal of Tsinghua University(Science and Technology)

基　　金：国家自然科学基金资助项目(60473082);国家"九七三"基础研究项目(2003CB314801)

摘　　要：为提高串匹配算法在实际应用中的运算性能，对Wu-Manber算法进行了改进。吸收了QS（Quick Search）算法的思想，并利用匹配过程中匹配失败的信息，达到最大跳跃距离，实现了快速的多模式匹配算法。对改进后的算法和Wu-Manber算法进行对比实验，当最小模式长度较大时，改进后的算法性能与原算法基本相同；而当模式最小长度较小时（〈9），改进后的算法比原算法有显著提高，用于英文文本时比原算法的所用时间平均减少了8％～20％，用于中文文本时平均减少了15％～30％。The performance of the string match algorithm is improved using a modified Wu-Manber algorithm, which is a multiple pattern matching algorithm from the Boyer Moore pattern matching algorithm family. The modified algorithm uses methods from the QS （quick search） algorithm and mismatch indicators from the pattern matching to calculate a maximum shift distance. Tests on small and large pattern lengths showed that the improved algorithm requires 8%- 20% less time than the Wu-Manber algorithm in English and 15%- 30% less time than the Wu-Manber algorithm in Chinese.

关 键 词：多模式串匹配 字符串匹配 WU-MANBER算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]