基于双字符序检测的BM模式匹配改进算法

J4 ›› 2012, Vol. 34 ›› Issue (3): 113-117.

基于双字符序检测的BM模式匹配改进算法

王浩，张霖，张庆

（安徽建筑工业学院信息网络中心，安徽合肥 230022）

收稿日期:2011-10-17 修回日期:2011-12-25 出版日期:2012-03-26 发布日期:2012-03-25
基金资助:
安徽高校省级自然科学研究重点项目(KJ2009A61);安徽高校省级自然科学研究一般项目(KJ2010B041)

An Improved BM Pattern Matching Algorithm Based on Double Character Sequence Checking

WANG Hao,ZHANG Lin,ZHANG Qing

(Information and Network Center,Anhui Institute of Architecture and Industry,Hefei 230022,China)

Received:2011-10-17 Revised:2011-12-25 Online:2012-03-26 Published:2012-03-25

摘要/Abstract

摘要：

BM算法是一类效率较高的单模式匹配算法，通常改进的BM算法往往从提高字符首次不匹配概率和匹配窗口的最大移动距离入手，但为实现此目的所带来的高访存开销使算法实际效率受到影响。DCSBM算法以适当减小关键步长为代价，在利用双字符序检测提高首次匹配失败概率的同时，对匹配窗口移动关键步长字符距离所需的查表次数和访存次数进行优化。经测试，DCSBM算法显著提高了匹配窗口的平均移动距离。在文本或模式串相对较长情况下，该算法实际测试效率优于BM、BMHS、BMN等算法。

关键词: 模式匹配, 双字符序, BM算法, BMHS算法

Abstract:

The BM algorithm is a more efficient single pattern matching algorithm. The common method of improving the BM algorithm is to start with increasing the probability of the first failure character matching and the maximal moving distance of the matching window. At the same time, the higher cost of accessing memory counteracts the actual efficiency of the new algorithm. Optimizing the number of the lookup table and the times of accessing memory when it moves the key distance of the matching window, and DCSBM makes good use of the double character’s first failure matching probability at the cost of reducing the key steps properly. It is tested that DCSBM obviously increases the average moving distance of the matching window. In larger length of the text or pattern, the real efficiency of DCSBM is higher than BM, BMHS, or BMN algorithm.

Key words: pattern matching;double character sequence;BM algorithm;BMHS algorithm

王浩，张霖，张庆. 基于双字符序检测的BM模式匹配改进算法[J]. J4, 2012, 34(3): 113-117.

WANG Hao,ZHANG Lin,ZHANG Qing. An Improved BM Pattern Matching Algorithm Based on Double Character Sequence Checking[J]. J4, 2012, 34(3): 113-117.

参考文献［8］

［1］	Knuth D E, Morris J H, Pratt V R. Fast Pattern Matching in String［J］ . SIAM Journal on Computing, 1977, 20(6):323350.
［2］	Karp R M,Rabin M O. Eficient Randomized Pattern—Matching Algorithm［J］．IBM J Res Develop, 1987, 31(2):249260.
［3］	Boyer R S, Moore J S. A Fast String Searching Algorithm［J］ . Communications of the ACM, 1977,20:762772.
［4］	Horspool R N. Practical Fast Searching in Srtings［J］. Software Practice & Experience,1980, 10(6):501506.
［5］	Sunday D M.A Very Fast Substring Search Algorithm［J］. Communication of the ACM,1990, 33(8):132142.
［6］	张娜,侯整风.一种快速的BM模式匹配改进算法［J］.合肥工业大学学报（自然科学版）, 2006,29(7):834838.
［7］	万晓榆,杨波,樊自甫.改进的Sunday模式匹配算法［J］.计算机工程, 2009,35(7):125126.
［8］	何畏,汪荣贵,查全民.一种新的快速移动单模式匹配算法［J］.合肥工业大学学报（自然科学版）, 2010,33(5):665669.

[1]	崔莹. 基于相似义原和依存句法的政外领域事件抽取方法[J]. 计算机工程与科学, 2020, 42(09): 1632-1639.
[2]	武优西,王博,高雪冬. 无重叠条件模式匹配的在线求解算法[J]. 计算机工程与科学, 2019, 41(12): 2239-2246.
[3]	郁伟生1，邓伟1，张瑶2，李蜀瑜1,2. 基于时间序列的音乐流行趋势预测研究[J]. 计算机工程与科学, 2018, 40(09): 1703-1709.
[4]	姜文超1,林德熙1，孙傲冰2，伍小强2. 一种新的基于相似度过滤的大数据保序匹配与检索算法[J]. 计算机工程与科学, 2017, 39(07): 1249-1256.
[5]	高冠东1,2,王晶1,刘菲1,段庆1,朱杰1. 一种基于极坐标变换的点模式匹配算法[J]. J4, 2016, 38(02): 331-337.
[6]	唐湘滟, 程杰仁, 殷建平, 龚德良. 基于NP模式的报文检测方法[J]. 计算机工程与科学, 2014, 36(11): 2128-2131.
[7]	李贯峰，陈冬梅. 基于证据理论的不确定模式匹配方法[J]. J4, 2014, 36(06): 1108-1113.
[8]	李东[1] 古宁[1] 林育蓓[2]. 一种用于多模式匹配的高效二叉检索树[J]. J4, 2008, 30(8): 69-71.
[9]	王建国[1] 郑家恒[2]. BM串匹配算法的一个改进算法[J]. J4, 2007, 29(5): 94-95.
[10]	王聪刘国华苑迎张凌宇. 一种基于子串运算的模式匹配方法[J]. J4, 2007, 29(10): 57-60.
[11]	钱颖. 发掘数据库模式间的复杂匹配[J]. J4, 2007, 29(10): 61-62.
[12]	陈祥松邓苏黄宏斌. 基于GLAV集成中的模式匹配方法研究[J]. J4, 2006, 28(6): 86-89.
[13]	王天江刘芳卢正鼎. 基于聚类汇总的记录匹配算法[J]. J4, 2004, 26(9): 62-63.
[14]	任晓峰董占球. 基于网络的入侵检测系统弱点分析[J]. J4, 2002, 24(6): 20-22.
[15]	陈海涛胡华平等. 网络入侵检测中高效散列模式树算法的研究[J]. J4, 2002, 24(5): 34-38.