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

An Improved Multi-Pattern String Matching Algorithm

作　　者：代六玲[1] 黄河燕[2] 陈肇雄[2] 

机构地区：[1]北京理工大学软件学院,北京100081 [2]中国科学院计算机语言信息工程研究中心,北京100083

出　　处：《模式识别与人工智能》2006年第1期47-51,共5页Pattern Recognition and Artificial Intelligence

基　　金：国家自然科学基金(No.60272088)

摘　　要：在对著名的 SunWu 多模式串匹配算法进行分析之后,结合 QS 算法的优点,设计了一种较高效的多模式串匹配算法 QMS.该算法使用散列技术和前缀表减少发生部分匹配时实际进行的模式串比较次数.在计算跳跃距离时,充分考虑当前窗口紧邻的下一个字符带来的信息,使用更加精确的跳跃距离计算方法以获得更大的平均跳跃距离,从而获得更高的扫描效率和空间利用率.在真实文本上的对比实验表明,在通常应用环境中,该算法缩短了扫描时间,取得了较好的效果.A new algorithm for matching multiple strings at the same time is suggested . The new algorithm is based on the ideas of QS and SunWu algorithm, named as QMS （Quick Multi-pattern Searching） algorithm in this paper. QMS uses hashing and PREFIX table to decrease the number of comparisons . During the computation of the shift distance , the character closely after the current window is considered . Because the shift distance is computed with more accurate technique, larger average shift distance is acquired. More characters can be skipped when the text is scanned , so the algorithm becomes very efficient . Tests on an actual corpus show that QMS algorithm is much more efficient than SunWu algorithm under common circumstances.

关 键 词：多模式串匹配 BOYER-MOORE算法 Quick Search算法 SunWu算法 

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