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

An improved Wu-Manber multiple patterns matching algorithm

作　　者：马伟华[1] 刘玉梅[1] 叶飞[1] 杨旭东 

机构地区：[1]哈尔滨工程大学信息与通信工程学院 [2]65316部队司令部18分队

出　　处：《应用科技》2007年第10期32-34,38,共4页Applied Science and Technology

摘　　要：在分析Wu—Manber算法的基础上，结合QS算法思想，设计了一种改进的多模式串匹配算法：QWM（quick Wu—Manber）．算法充分利用紧邻当前窗口之后的B字符块，使算法的最大移动距离由原来的（m—B＋1）增大至（m＋B），平均移动距离也得到很大提高．同时对QWM算法和Wu-Manber算法进行了实验对比，无论模式串数量和最小长度怎么变化，性能都有较大提升．实验表明，改进的算法在对英文文本进行扫描时有4％～13％的提高．Based on the analysis of Wu-Manber algorithm and the idea of QS algorithm, an improved multiple patterns matching algorithm was presented, named QWM（Quick Wu-Manber）. Considering the information of the B- gram nexted to the current window, the maximum shift distance of the algorithm reached m ＋ B from m - B ＋ 1. And larger average shift distance was acquired. QWM and Wu-Manber algorithm were compared in experiments. With the change of the number and the minimum length of the patterns, the improvement of the performance was large. The results of experiments show that the improvs algorithm performs 4% - 13% better than Wu-Manber algorithm when scanming English text.

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

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