改进的Sunday模式匹配算法的设计与实现_巫喜红

（ 1． 嘉应学院 计算机学院，广东 梅州 514015 ； 2． 广东工业大学 计算机学院，广东 广州 510006 ）
研究了它的改进算法 I － Sunday 算法． 依据模 要： 针对 Sunday 模式匹配算法低效率问题， I － Sunday 算法在遇到坏字符时， 式匹配算法的跳跃思想， 不但考虑当前匹配窗口的下一位字符， 而 且也考虑了下一位字符之后长度为模式串长度的那个字符 ， 这就跳跃了更大的距离． 另外， 匹配时 摘 采用双向并行方式进行匹配． 为了验证 I － Sunday 算法的性能， 在同等条件下， 在匹配次数和比较的 字符个数两方面对 I － Sunday 算法进行实验． 实验结果表明， 由于 I － Sunday 算法能够跳 过 大 量 的坏 字符， 大大地减少匹配次数和字符的比较， 从而缩短匹配时间， 有效地提高模式匹配速度． 关键词： Sunday 算法; Sunday 算法改进; 双向并行; 模式匹配 中图分类号： TP391. 9 文献标志码： A 文章编号： 1007－ 2683 （ 2013 ） 06－ 0052－ 06
Design and Ｒealization of the Improved Sunday Pattern Matching Algorithm
2 WU Xihong1 ， LING Jie1，
（ 1． Department of Computer Science and Technology ，Jiaying University，Meizhou 514015 ，China； 2． Computer College，Guangdong University of Technology，Guangzhou 510090 ，China）
1
几种经典算法
定义 n 为文本串的长 文本串 T = T0 … T n － 1 ，
m 为模式串的长度， （n 度； 模式串 P = P0 … P m － 1 ， m） ； T 和 P 都建立在有限字符集上， 大小为 σ． 对于文本串 T 和模式串 P ， 在 T 中寻找等于 P 的子串， 如果在 T 中存在等于 P 的子串， 则称匹配
下一轮判断 T ［ 15］= ‘ h’， 故右移 BM_Bc ［ h］=5。 下一轮判断 T ［ 20］= ‘ n’， 故右移 BM_Bc ［ n］=5。
匹配成功，且 T 串无可比较字符，匹配结束。
结果
比较次数是 6，比较的字符个数是 18.
1. 2
Sunday 算法 Sunday 算法是 Daniel M． Sunday 于 1990 年提出
收稿日期： 2013 － 03 － 04 基金项目： 国家十二五科技支撑计划项目（ 2012BAH27F05 ） ； 广东省自然科学基金（ S2012020011071 ） ； 广东省战略性新兴产业核心技术攻 关项目（ 2012A010701004 ） ． Email： wxhtuogao@ 126． com； 作者简介： 巫喜红（ 1975 —） ， 女， 副教授， 凌 捷（ 1964 —） ， 教授． 男， 博士，
表2
过程 轮数
字符集 C 和 BM － Bc 函数值
acghimnrstw 31555455525
BM 算法匹配过程
说明
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 串T s t r i n g n a t e h w a t c h n t c h n m a t c h
下一轮判断T ［ 4］= ‘ n’，故右移 BM_Bc ［ n］=5。
第1轮 ···· h 第2轮 第3轮 第4轮 第5轮 第6轮
···· h
m
［ 9］= ‘ c’，故右移 BM_Bc ［ c］=1。 下一轮判断T
下一轮判断 T ［ 10］= ‘ h’，故右移 BM_Bc ［ h］=5。
a t c h m a t c h · · · · h m a t c h
P 与 T 的比较时， 可以从左向右或从右向左进行比 较， 它在发现不匹配时， 算法能跳过尽可能多的字符 以进行下一步的匹配， 从而提高了匹配效率． Sunday 算法所跳过的字符数与 BM 算法相似， 当 匹配失败时， 考虑的是当前匹配窗口中 T 的下一位字
的一种比 BM 算法搜索速度更快的算法． 其核心思 想是： 采用 BM 算法中的坏字符启发规则， 开始时 P 的最左边与 T 的最左边对齐， 模式匹配过程中进行
54
哈
尔ห้องสมุดไป่ตู้
滨
理
工
大
学
学
报
第 18 卷
0． ． m － 1］ i． ． i + m － 1］ 符， 也就是当 P［ 与 T［ 对齐进 i + m］ 行匹配， 如果匹配失败， 则分析 T［ 这个字符， 来 0． ． m － 1］ i + m］ 决定 P［ 右移的距离， 如果 T［ 没有在 匹配串中出现则直接跳过， 即移动步长 = 匹配串长度 + 1； 否则， 同 BM 算法一样其移动步长 = 匹配串中最 右端的该字符到末尾的距离 + 1． Sunday 右移距离的 ［ 10 － 11 ］ i + m］ 计算公式 如式 （ 2 ） 所示， 即： 若 T［ 不在 P 中出现， 则右移距离为公式（ 2） 中的第 1 种情况； 若 T ［ i + m］ 在 P 中出现， 则右移距离为式（ 2 ） 中的第 2 种 情况． 具体的右移情况示意图如图 1 所示． m + 1 ； C≠P［j］． 即 C 不在 P 中出； （ 第 1 种情况） Sunday － Bc［C］= min｛ j | P［j］= C， 1 ≤j≤m 且 T［m － j］= C｝ ， 即 C 在 P 中出现（ 第 2 种情况） ． （ 2） 正文串为“stringnatch例如： 在前面的例子中， watchntchnmatch” ， ， 模 式 串 为“match ” 按 照 Sunday 算法， 字符集 C 和 Sunday － Bc 函数值如表 3 所示． 具
表1
C BM － Bc［ C］
［6 ］ －［9 ］
计算机的广泛应用， 使得其成为人们日常生活 中不可缺少的一部分． 各行各业的人们在享受计算 机网络带给人们无限便利的同时， 网络安全也不断 引起人们的关注， 而模式匹配算法作为入侵检测系 统的关键技术之一也日益成为人们研究的热点 ， 其 性能的优劣直接关系着入侵检测系统的效率 ， 因此， 研究更高效的模式匹配算法已变得越来越重要 ． 对 于模式匹配算法已有不少的研究成果 ， 比如： 典型的 单模式算法主要有 Knuth － Morris － Pratt （ KMP ） 算 ［1 ］ Byoer － Moore （ BM） 算法［2］及 BM 算法的一些 法 、 ［3 ］ 多模式算法主要有 Aho － 变种算法 Sunday 算法 ， Corasick（ AC ） 算法［4］、 Wu － Mander 算法［5］． 本文通 过实例对 Sunday 算法进行分析， 并在其基础上从跳 跃距 离、 匹 配 方 式 两 方 面 进 行 改 进， 称改进后的 Sunday 算法为 Improved － Sunday 算法， 简称 I － Sunday 算法．
第6 期
巫喜红等： 改进的 Sunday 模式匹配算法的设计与实现
53
0
引
言
成功， 函数值返回为 P 中第一个字符相等的字符在 主串 T 中的序号， 否则称为匹配失败， 函数值返回 为 0， 这个搜索过程就是模式匹配． 1. 1 BM 算法 BM 算法是效率较高的一种单模式匹配算法 ， BM 算法因其跳过了 这是因为在模式匹配过程中， 很多无用的字符， 被大多数入侵检测系统所应用， 其 基本思想是： 开始时 P 的最左边与 T 的最左边对 齐， 模式匹配过程中， 从右向左的把 P 同 T 进行比 较， 当某趟匹配失败时， 采用坏字符启发规则和好后 缀规则 计算 P 的右移距离， 并取两者最大值 ， 来决定模式串的右移量 移动尽可能远的距离， 直到 文本串匹配结束． BM 算法的右移距离公式如式（ 1） ． （ 1 ≤ j≤ m） ． m； C≠P［j］ （ 第 1 种情况） 即 C 不在 P 中出现或 C = P［m］ BM － Bc ［C］ = min｛ j | P［j］ = C， 1 ≤j≤m － 1 且 T［m － 1 － j］ = C｝ ， 即 C 在 P 中出现（ 第 2 种情况） （ 1） 模 例如： 正文串为“stringnatchwatchntchnmatch ” “match” ， 式串为 按照 BM 算法， 字符集 C 和 BM － Bc 函数值如表 1 所示， 具体的匹配的过程如表 2 所示 （ 表示不用比较的字符， 下划线粗体的字符表示比 较过的字符） ．
Abstract： In order to improve the efficiency of Sunday pattern matching algorithm ，this paper studies an improved Sunday （ I － Sunday ） algorithm． According to the thought of jumping ，when encountering bad characters， the I － Sunday algorithm not only considers the next character of the current matching window ，but the character whose length equals the pattern strings’after the next character of the current matching window． All these decide that I － Sunday algorithm can jump a greater distance． In addition ，when matching the I － Sunday algorithm，we use the mode of bidirectional parallel matching． In order to verify the performance of the I － Sunday algorithm，in the same condition ，some experiments are done from two aspects which are matching times and compared characters ’ numbers． The experimental results show that the I － Sunday algorithm is more efficient than the Sunday algorithm because it can jump over a large number of bad character and greatly reduce the match number times and the character comparison so as to shorten the matching time． The I － Sunday algorithm effectively improves the speed of pattern matching． Key words： Sunday algorithm； improved Sunday algorithm； bidirectional parallel； pattern matching