QS快速单模式匹配的两种改进算法  

Two Improved Fast Single Pattern Matching Algorithms of QS

作　　者：周志平[1] 庄金莲[1] 陈佳丽[1] 

机构地区：[1]龙岩学院数学与计算机科学学院,福建龙岩364000

出　　处：《三明学院学报》2013年第4期30-33,46,共5页Journal of Sanming University

摘　　要：模式匹配算法已广泛应用于各个领域,针对如何减少匹配次数,提高算法效率,提出两种改进的QS快速匹配算法。第一种算法通过检测匹配窗口的末字符是否出现于模式串中,并依据情况滑动模式串。第二种算法通过构造BM及QS算法两个坏字符滑动表,经查表比较后确定每一次的滑动距离,使得模式串的滑动距离达到最大,从而大大减少了尝试的次数。实验结果表明,UCD与MSD算法的尝试匹配次数明显优于QS及其他算法,具有更高的效率。Pattern matching algorithms has been widely used in various fields. Aiming at how to reduce the number of attempts as well as improve the efficiency of the algorithm, two pattern matching algorithms are presented to improve the algo- rithm of quick search. The first algorithm matches the text window by checking whether the last character occurs in the pattern string, and then shifts the pattern string depending on the situation. The second algorithm constructs two bad character shift tables of BM and QS algorithms＇, then look up these two tables to determine the shift distance each time, making the pattern string reach the maximum shiR distance. This greatly reduces the number of attempts and increases the shig distance. The experimental results show that UCD and MSD algorithms＇ matching speed is significantly faster than QS and other algorithms.

关 键 词：QS算法 模式匹配 串搜索 字符串匹配 

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