基于后缀WM匹配算法的改进算法  

An Improved Algorithm Based on the Suffix WM Matching Algorithm

作　　者：蒋晓鸽[1] 武小年[1,2] 张昭[1] 

机构地区：[1]桂林电子科技大学信息与通信学院,桂林541004 [2]保密通信重点实验室,成都610041

出　　处：《计算机与数字工程》2013年第4期608-610,共3页Computer & Digital Engineering

基　　金：保密通信重点实验室基金(编号:9140C110404110C1106);广西自然科学基金(编号:2012GXNSFAA053224);广西研究生教育创新计划(编号:2010105950810M18);广西教育厅基金(编号:201010LX156;CD10066X)资助

摘　　要：针对基于后缀WM匹配算法中的字符重复匹配问题,给出了相应的改进算法。该算法针对扫描阶段确定的与模式串前缀、后缀和前m个字符的后缀都相同的文本串字符块,在匹配阶段跳过文本串字符块中已经确定的字符块,避免了对已经确定的字符块的重复匹配,减少匹配开销。实验结果表明,相对于原始算法,改进算法降低了系统匹配的运行时间,提高了系统运行的效率。With regard to the problem of the repeated matching in WM algorithm based on suffix matching, an improved algorithm is proposed in this paper. When the algorithm detects that the text string has the same prefix, suffix, and suffix of the former m character as the pattern string, during the matching stage, the algorithm would skip the located blocks which have been confirmed in the scanning. Which avoid repeatedly matching the confirmed blocks, reducing the matching overhead. The tested results show that, compared with the original algorithm, the improved algorithm reduces the matching time, and improves the efficiency of the system.

关 键 词：多模式匹配 WM算法 前缀 后缀 

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