（计算机软件与理论专业论文）串匹配算法优化技术研究.pdf

摘要 摘要 串匹配是计算机研究领域的一个经典问题，是众多网络安全系统中的关键 技术之一。随着互联网的普及和发展，海量信息的处理和新的应用需求对串匹 配技术提出了新的挑战。 本文主要对大规模精确串匹配技术和动态串匹配技术进行研究。在大规模 精确串匹配方面，本文分别从压缩存储空间和改善数据结构局部性这两方面出 发，提出了基丁存储压缩的串匹配算法和对串匹配自动机进行内存布局优化的 策略。在动态串匹配方面，本文对经舆的串匹配算法进行了扩展，提供动态增 删关键词的能力。 具体来说，本文取得的土要成果如下： 1 串匹配算法性能分析：通过实验和理论分析，本文得出串匹配算法的执 行时间和二级c a c h em i s s 之间的线性关系，并对经典算法的时间复杂度进 行了分析，提出了从压缩存储空间和改善数据结构局部性这两方面来优化 串匹配算法的途径。 2 ，基于存储压缩的串匹配算法：从压缩存储空间以改善c a c h e 命中率的思想 出发，本文提出了一种对经典s b o m 算法进行空间压缩的策略，并从理论 上证明了该方法具有线性的空间复杂度。这种改进策略有效地压缩了自动 机的存储空间，大幅度地提高了算法的匹配速度。 3 串匹配算法的内存布局优化：从改善数据结构局部性的思想出发，本文 对内存布局优化问题进行了形式化和建模，并提出了利用线性规划方法进 行求解的策略该方法在理论和实际中都具有一定的指导意义 4 经典算法在动态匹配上的扩展：本文对经典的串匹配算法进行了扩展， 动态地维护和更新已经建立的数据结构，提供增加和删除关键词的操作。 并保证近似线性的时间复杂度 5 通用串匹配算法库：基于前人的研究成果和本文的部分工作，本文构建 了一个通用串匹配算法库。该算法库具有多线程安全和通用的特点，可以 为不同的项目提供二次开发支持。 。 关键词：字符串匹配，精确串匹配，动态串匹配，压缩存储，内存布局优化 r_二 a b s t r a c t r e s e a r c ho fs t r i n gm a t c h i n ga l g o r i t h mo p t i m i z a t i o n l i uy a n - b i n gi n s t i t u t eo fc o m p u t i n gt e c h n o l o g y , c h i n e s ea c a d e m yo fs c i - e n c e s d i r e c t e db yg u ol i a b s t r a c t s t r i n gm a t c h i n gi sac l a s s i cr e s e a r c ha r e ai nc o m p u t e rs c i e n c ea n dp l a y sa l li m - p o r t a n tr o l ei nd i f f e r e n tk i n d so f n e t w o r ks e c u r i t ys y s t e m s n o w a d a y s t h ec l a s s i cs t r i n g m a t c h i n ga l g o r i t h m sh a v e b e e nf a c e dw i t hg r e a tc h a l l e n g e sb e c a u s eo f t h er a p i d l yg r o w - i n go f i n f o r m a t i o na n dt h ee m e r g e n c eo f n e wa p p l i c a t i o nr e q u i r e m e n t si ne n g i n e e r i n g t h i st h e s i sw a sd e d i c a t e dt ot h er e s e a r c ho f l a r g es c a l ee x a c ts t r i n gm a t c h i n ga n d d y n a m i cs t r i n gm a t c h i n g w i t l lr e s p e c tt ol a r g e0 t a l ee x a c ts t r i n gm a t c h i n g t w oo f - t i m i z a t i o ns t r a t e g i e sw e r ep r o p o s e d ：c o m p r e s s i n gt h em e m o r ys p a c eo fa u t o m a t at o a c h i e v eab e t t e rc a c h ep e r f o r m a n c ea n dr e a r r a n g i n gt h es t a t e so fa u t o m a t at oi m p r o v e i t sl o c a l i t y w i t hr e s p e c tt od y n a m i cs t r i n gm a t c h i n g , c l a s s i ca l g o r i t h m sa r ee x t e n d e d t op r o v i d et h ea b i l i t yo f i n s e r t i n ga n dd e l e t i n gak e y w o r d h lt l l i st h e s i s t h ef o l l o w i n gr e s u l t sh a v eb e e na c h i e v e d ： 1 p e r f o r m a n c ea n a l y s i so fs t r i n gm a t c h i n ga l g o r i t h m ：t h r o u g he x p e r i m e n t a l a n dt h e o r e t i c a la n a l y s i s , t h ei i n c a rc o r r e l a t i o nb e t w e e nt h ee x e c u t i 蚰t i m ea n d l e v e l2c a c h em i s s e so f a l g o r i t h mw a si l l u s t r a t e d t h i st h e s i sa n a l y z e dt h et i m e c o m p l e x i t yo f t h ec l a s s i ca l g o r i t h m ( c g a c , w u - m a n b c r , s b o m ) a n dp r o p o s e d t w oo p t i m i z a t i o ns t r a t e g i e s ：c o m p r e s s i n gt h es t r i n gm a t c h i n ga u t o m a t a sm e m o r y s p a c ea n di m p r o v i n gi t sl o c a l i t y 2 as t r i n gm a t c h i n ga l g o r i t h mb a s e do nm e m o r ys p a c ec o m p r e s s i o n ：b a s e d 0 nt h ei d e ao fc o m p r e s s i n ga u t o m a t a sm e m o r ys p a c e ，t h i st h e s i sp r o p o s e da s t r a t e g yt oc o m p r e s ss b o m sm e m o r ys p a c e ，a n dp r o v e dt h a tt h ei m p r o v e da l g o r i t h m i so ( m r l o g 阎m r ) i ns p a c ec o m p l e x i t y e x p e r h n e n t ss h o w e dt h a tt h i s i m p r o v e m e n tn o to n l ye f f e c t i v e l yc o m p r e s s e dt h ea u t o m a t a sm e m o r ys p a c e ，b u t a l s og r e a t l yi m p r o v e dt h es e a r c h i n gs p 正 一n 一 、fl， l1ll? 3 m e m o r yl a y o u to p t i m i z a t i o no f s t r i n gm a t c h i n ga u t o m a t a ：b a s e do nt h ei d e a o f i m p r o v i n ga u t o m a t a sl o c a l i t y , f i r s t l y , t h i st h e s i sf o r m u l a t e dt h em e m o r yl a y - o u tp r o b l e mi n t oam a t h e m a t i c a lo p t i m i z a t i o np r o b l e m a n dt h e n , l i n e a rp r o - g r a m m i n gm e t h o dw a se m p l o y e dt os o l v ei t m e m o r yl a y o u to p t i m i z a t i o ni s i n s t r u c t i v eb o t l i i np r a c t i c ea n dt h e o r y 4 e x t e n s i o no fc l a s s i ca l g o r i t h m s ：t h i st h e s i se x t e n d e dt h ec l a s s i ca l g o r i t h m s ， p r o v i d et h ea b i l i t yo f i n s e r t i n ga n dd e l e t i n gak e y w o r d w i t h o u tr e c o n s t r u c t i n gt h e w h o l ea u t o m a t a t h ei n s e r t i n ga n dd e l e t i n go p e r a t i o ni sa p p r o x i m a t e l yl i n e a ri n t i m ec o m p l e x i t y ，“5 u n i v e r s a ls t r i n gm a t c h i n gl i b r a r y ：b a s e do nt h er e s e a r c ho f p i o n e e r sa n dt h e w o r ko ft h i st h e s i s ，au n i v e r s a ls t r i n gm a t c h i n gl i b r a r yw a sb u i l d t h el i b r a r yi s t h r e a d - s a f e t ya n dp r o v i d ec o n t i n u o u ss t r e a ms e a r c h i n g rc a nb eu s e di nd i f f e r e n t p r o j e c t sf o rf l l r t h e rd e v e l o p m e n t k e yw o r d s ：p a t t e r nm a t c h i n g , e x a c tp a t t e r nm a t c h i n g ，d y n a m i cp a t t e mm a t c h i n g , s p a c ec o m p r e s s i o n , m e m o r yl a y o u to p t i m i z a t i o n i 一 鞋譬t i i，j hi_ ，_，i， 插网 插图 1 i1 9 9 9 1 - - 2 0 0 6 i 我国国际出口带宽里指数增长 3 1 2 三种经典串匹配算法的匹配速度与天键词规模的关系4 2 1 p = 她的，b 鼬 对应的a c 自动机8 2 2a c 自动机搜索文木= b a b a b a b 的过程1 5 2 3w u m a n b e r 的跳跃过程：块b 出现在模式串中1 6 2 4w u - m a n b e r 的跳跃过程：块b 没有出现在模式中1 6 2 5 w u - m a n b e r 的跳跃过程：块b ； j 现在模式中并r s b l = 0 1 7 2 6 p = 口凡加u n c e ，a n n u a l ，a n n u a l l y 对应的f a c t o ro r a c l e 自动机1 7 2 7f a c t o r o r a c l e 完全识别匹配窗口1 8 2 8f a c t o r o r a c l e 部分识别匹配窗口。1 8 3 1 三种经典串匹配算法的匹配速度与关键词规模的关系1 9 3 2 三种经典算法的匹配时问2 l 3 3 三种经典算法的二级c a c h e m i s s 次数2 2 3 4f a c t o r o r a c l e 自动机结点的出度统计2 5 3 5f a c t o r o r a c l e 自动机结点被访问的频率2 6 4 1 d o u b l e a r r a y t r i e 示意图2 9 4 21 0 0 0 5 0 0 0 0 个关键词的匹配速度比较( 2 5 6 - 7 符集，关键词长度 为6 ) 3 6 4 3 1 0 0 0 - 5 0 0 0 0 个关键词的匹配速度比较( 3 2 字符集，关键词长度 为6 ) 3 7 4 a1 0 0 0 - 5 0 0 0 0 个关键词的匹配速度比较( 4 字符集，关键词长度 为2 0 ) ：3 8 4 51 4 8 2 个s n o r t 关键词时的匹配速度比较3 9 4 61 0 0 0 5 0 0 0 0 个关键词的存储空间比较( 2 5 6 - 字符集，关键词长度 为6 ) 4 0 4 7 1 0 0 0 - 5 0 0 0 0 4 关键词的存储空间比较( 3 2 字符集，关键词长度 为6 ) 4 l v l i 插图 4 8 1 0 0 0 - 5 0 0 0 0 个关键词的存储空问比较( 4 字符集，关键词长度 为2 0 ) 4 2 4 91 4 8 2 个s n o r t 关键词时的存储空问比较4 2 4 1 01 0 0 0 - 5 0 0 0 0 个关键词平均跳跃距离比较( 2 5 6 字符集，关键词长 度为6 ) ，4 3 4 “1 0 0 0 - 5 0 0 0 0 个关键词平均跳跃距离比较( 3 2 字符集，关键词k 度 为6 ) 4 3 4 1 21 0 0 0 5 0 0 0 0 个关键词平均跳跃距离比较( 4 字符集，关键词长度 为2 0 ) “ 4 1 3 访问内存次数与关键词个数的关系，4 4 4 1 4 访问内存次数与二级c a c h e 人小的之间的关系4 5 5 1 不同的内存布局下发生一次c a c h em i s s 的概率4 6 5 2 原始b o m 和状态重排r e a r r a n g e b o m 的二级c a c h em i s s l t 较5 0 6 1 动态更新a c 自动机的过程5 3 6 2 扩展的w m 跳跃距离表5 5 6 3 批量增加5 0 0 关键训时闻代价比较( a c 和a d a p t a c ) 5 7 6 4 批量增加5 0 0 关键词时间代价比较( w m 幕i a d a p t _ w m ) 5 8 6 5 批量增加5 0 0 关键词时间代价比较( b o m 和a d a p t _ b o m )5 9 6 6 匹配速度比较( a c 和a d a p t _ a c ) 5 9 6 7 匹配速度比较( w m 和a d a p l w m ) 6 0 6 8 匹配速度比较( b o m 和a d a p t b o m ) 6 0 7 i 通用串匹配算法库框架6 l 7 2a p i 接口的使用流程6 3 一v l 一 、- l i i f l j ， f 声明尸明 本人声明所呈交的论文足我个人在导师指导下进行的研究t 作及取得的研 究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中不包龠其 他人已经发表或撰写过的研究成果。与我一同t 作的同志对本研究所做的任何 贡献均己在论文中作了明确的说明并表示了谢意。 作者签名：立1 3 煎豆 日 期：z 鲤正g 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件，允 许论文被查阅和借阅：并可以公布论文的全部或部分内容可以采用影 印、缩印或其它复制手段保存该论文。 名：边名：翠趔憧 第一章引j 第一章引言 1 1 串匹配技术研究的目的和意义 搜索问题足计算机科学中最基本的问题，串匹配就是在一个符号序列中查 找另一个( 或一些) 符号序列的搜索问题。在现实生活中，串匹配技术的应用 十分广泛，其主要应用领域包括：入侵检测、病毒检测、信息检索、信息过 滤、计算生物学等等串匹配技术的研究与发展是与现实应用息息相关的，近 年来，新的应用需求对串匹配技术提出了新的要求和挑战。 1 1 1 串匹配技术的广泛应用 二十一世纪足互联网的时代。网络的普及和发展，使我们的计算机日益紧 密地联系起来，并且从根本上改变了传统的“计算机”的概念，即从单一孤立 的个人计算机转变为接入互联网这个庞大的分布知识库的网络终端机，万维 网、新闻组、电子邮件、点对点软件以及正在发展的网格等各种应用服务也随 之而来网络在为我们带来了无限的共享和机会的同时。也使得我们遭到恶意 攻击的危险同等地增加如何才能在享用网络发展带来的丰富知识和服务的同 时，保护用户信息不被窃取、计算机系统不被破坏、网络高速公路不被蓄意破 坏堵塞，已经成为一个受到个人、公司、研究机构和政府机关等广泛关注的问 题。 入侵检测技术是网络安全问题的一个主要研究方向入侵检测技术的目的 是建立一种计算机系统的安全保护机制，防止在未授权的情况下操作计算机系 统和访问系统内存储的数据资源入侵检测最常用的技术是。数据监听”，即 通过监听系统日志中记录的关于用户活动的详细信息来搜集用户对系统进行非 法入侵的“证据”，从而判断用户的行为是否合法入侵检测系统针对各种入 侵行为的特点建立了一组入侵行为的特征模式集，同时加入针对各种行为入 侵检测系统应该采取的措施，构成系统的安全规则所以一个入侵检测系统 的主要工作就足在监听剑的数据中匹配系统的安全规则，根据发现的入侵情 况采取相应的措施在入侵检测系统中，精确模式串匹配技术不仅得到了广 泛应用【1 1 【2 】【3 】，而且成为影响系统性能的决定性因素【4 】。开源入侵检测系 统s n o r t 【5 】采用了b o y e 卜m o o 串匹配算法。这是一种精确的单模式串匹配算 第一章引青 法m i k ef i s k 和g e o r g ev a r g h e s e 使用了s b m h 多模式串算法代替s n o r t 原来的 匹配算法，使s n o r t 系统的平均性能提高了5 0 0 6 ，在处理网络数据包的追踪问 题上更足得到了5 倍的性能提升【3 】。 病毒检测也是串匹配算法的重要应用领域之一病毒检测系统有一个庞大 的病毒特征库，病毒检测就是在每一个文件中搜索可疑的病毒特征的过程。据 统计，剑2 0 0 5 年，网络病毒已接近1 0 万种【6 】。在商用的病毒软件系统中，病毒1 序也是每天更新。面对如此庞大的病毒库，没有有效的串匹配算法足不可相象 的。 在网络信息以指数级速度增长的今天，信息的良莠不齐也足一个严重困扰 人们的问题。大量黄色信息、反动言论和国家机密在网络上蔓延和传播，给社 会稳定和国家安全造成了严重威胁，如何对这些不良信息进行网络监管是网络 “， 内容过滤系统的重要任务在这些系统中，使用串匹配算法对有害信息进行匹 配足基本的手段之一。这些系统通常运行在骨干网结点上，单位时问内需要处 理的数据量非常之大，实时性要求非常之高。作为检测引擎的核心，串匹配算 法性能的好坏是影响系统性能的决定因素之一 随着生命科学的发展，人们对生命物质的微观结构有了越来越清晰的认 识目前，人类基因组序列的绘制工作已经完成，p r o s i t e 、g e n b a n k 等大型序列 库也已经建立【7 】。计算生物学的一个基本问题是：寻找一个或一组基因片断在 一个基因序列中的出现位置【8 】，以比较基因的相似性和遗传关系：或者根据已 知的蛋白质样本去匹配未知的蛋白质序列【9 】，来确定这种未知的蛋白质序列所 属的蛋白质种类和功能由于蛋白质和基因都可以用建立在一定字符集上的符 号序列来表示，所以传统的模式串匹配技术又有了新的用武之地 综上所述，串匹配技术在在众多的领域中发挥着基础的核心作用。对串匹 配算法作进一步的研究和改进，对于提高应用系统的性能、节约硬件成本有着 重要的现实意义 1 1 2 串匹配技术面临的新挑战 近年来，随着网络技术的普及和发展。网络带宽和流量呈指数级的速度增 长( 图i i ) ，我国互联网的规模正以前所未有的速度扩张根据中国互联网络 信息中心( c n n i c ) 的。中国互联网络发展状况统计报告”【l o 】调查显示，截 止到2 0 0 5 年1 2 j 目3 1 日，我国国际出口带宽的总容量为1 3 6 1 0 6 m ，与一年前的调 一2 一 第一章引言 查结果相比增加- f 6 t ，6 7 7 m ，增长率为8 2 9 ；l p v 4 地址数已达7 4 ，3 9 1 , 2 9 6 个，与 一年前的调查相比增加了1 4 , 4 4 5 , 5 6 8 个，增长率g j 2 4 1 面对日益增长的庞大 网络流量，安全系统中需要处理的数据量也越来越大。现有的串匹配算法的处 理能力越来越不敷应用 图1 11 9 9 9 1 2 0 0 6 i 我国国际出1 ：3 带宽呈指数增长 另一方面，应用系统中需要关注的特征的规模也越来越大，早已达到几千 和上万的规模例如： 开源入侵检测系统s n o r t 的规则库基本是按照线性速度飞快增长的【l l 】； 开源病毒检测系统c l a m a v 0 8 3 【1 2 】病毒库中的病毒签名片断也高 达2 6 ，6 5 3 条； 在现实工程中已经提出了5 1 0 万特征串过滤的需求 随着模式串规模的不断扩大，经典算法的性能急剧下降。从图1 2 中我们可以看 出，现有的串匹配算法仅适合于中等规模( 1 万以内) 的模式串集合，对于更大 规模( 1 万1 0 万) 的模式串集合，这些算法的性能下降幅度很大，已经不能很 好地满足实际应用的要求因此，如何解决大规模串匹配的性能瓶颈，是我们 面临的一个巨大挑战。 一3 一 宣：一；，0 第一节引j 网10 2互种经典串匹配算法的匹配速度与关键词规模的关系 动态串匹配也是许多现实系统中的重要需求。经典的多模式串匹配算法利 用关键词集合相对稳定的特点。先对关键词集合进行预处理，建立可快速访问 的索引结构，然后对文本进行扫描。但是在一些实时的网络监测系统中，待扫 描的关键词的规模常常高达几千至几万，并且更新非常频繁，系统要求关键词 匹配算法具备快速地更新关键词集合的能力但是，经典的多关键词匹配算法 不具备动态地、实时地增删关键词的能力，每增加或删除一个关键词，都需要 对关键词集合重新进行预处理，建立新的数据结构。对于关键词集合规模很大 并且更新非常频繁的实时系统来说，这种完全重构的方法代价巨大。根本无法 满足实时性的要求。因此，对动态串匹配算法的研究也是非常有必要的 1 2 本文的研究内容与安排 本文主要对大规模精确串匹配技术和动态串匹配技术进行研究。在大规模 精确串匹配方面，我们致力于解决大规模关键词环境下经典算法的性能大幅度 下降的问题在动态串匹配方面，我们试图解决经典算法不易于扩展到动态匹 一4 一 j ； ? 。 i i ； 3 ： ， 2 ； 第一章引青 配上来的问题 本文后续内容组织如下：第二章总结了精确串匹配算法和动态串匹配算法 的研究现状；第三章对精确串匹配算法进行性能分析，提出了改进经典算法的 两种可行途径；沿着这两条途径展丁f 。第四章、第五章分别提出了基于存储压 缩的串匹配算法和基于内存布局优化的串匹配自动机优化策略；第六章对经典 的串匹配算法进行了扩展，以满足动态匹配的需求。第七章介绍了本文构建的 通用串匹配算法库的框架和接口。第八章是本文的总结和展望。 一5 一 第j 章串匹配算法的研究现状 第二章串匹配算法的研究现状 2 1 串匹配的定义 所谓串匹配( s t r i n g m a t c h i n g , o r p a t t e r n m a t c h i n g ) ，就是给定一组特定的 字符串集合p ，对于任意的一个字符串t ，找出尸中的字符串在t 中的所有出现 位置。我们称p 为模式串集合，称p 中的元素为模式串( 或关键词) ，称t 为文 本。字符串中的字符部取自一个有限的符号集合e ，简称字母表或字符集。 按照文献【1 3 1 的分类方式，串匹配可以分为四类：精确串匹配( e x a c t s t r i n gm a t c h i n g ) 、扩展串匹配( e x t e n d e ds t r i n gm a t c h i n g ) 、近似串匹配 ( a p p r o x i m a t es t r i n gm a t c h i n g ) 和正则表达式匹配( r e g u l a re x p r e s s i o nm a t c h - i n g ) 精确串匹配要求文本中被匹配的字符串与模式串严格相等。近似串匹配 允许被匹配的字符串和模式串之间有一定的误差( e r r o r ) ；两个字符串之阃的 误差可以用距离来度量，常用的距离有：编辑距离( e d i td i s t a n c e ) 、汉明距离 ( h a m m i n gd i s t a n c e ) 等在正则表达式匹配中，待匹配的不是简单的字符串， 而足正则表达式，这使得正则表达式匹配比精确串匹配要困难的多扩展串匹 配介于精确串匹配和正则表达式匹配之间，它的模式串通常是一些特殊的正则 表达式，因而常常可以通过特殊的手段解决。 按照模式串集合是否固定，串匹配又可以分为两大类：静态串匹配 ( s t a t i cs t r i n gm a t c h i n g ，o rf i x e ds t r i n gm a t c h i n g ) 和动态串匹配( d y n a m i cs t r i n g m a t c h i n g ) 静态串匹配的模式串集合p 是静态和固定不变的，这样可以在匹 配之前对模式串集合进行预处理，建立模式串的索引结构，以提高匹配时的速 度动态串匹配的模式串集合p 是动态的，随着时间的变化，可以在p 中添加或 删除一个模式串。因此，动态串匹配要求算法能够动态地维护数据结构，提供 快速地插入和删除一个模式串的操作 本课题只研究精确串匹配和动态串匹配，下面给出它们的严格定义： 精确串匹配 已知：有限字符集合e ：模式串集合p ：( 坳p ) ( p + ) ；文本：t + 求解：o c c u r ( p , t ) = ( p ， z ) i ( 了z ) ( 劫) ( t = 印9 ) ，p p ，即模式串集合 中的模式串在文本中的所有出现位置 一6 一 第一：市串匹配算法的研究现状 动态串匹配 已知：有限字符集合e ；模式串的集台p ；文本t 。 求解：删r ( p ，t ) 同时要求提供插入和删除一个模式串的操 作：i 札s e n ( p ) ，d e l e t e p ) 扫尸) 我们对本文中出现的常用符号作如下约定： e ：字符集； p ：模式串集合： 。p ：p d p 的模式串； r ：模式串集合的规模i p b m ：p 中最短模式串的长度，i l p m i n p i ip p ) 。 2 2 精确串匹配算法的研究现状 目前国内外研究者提出的串匹配算法总共有几百种【1 4 】，算法的思想和使 用的技巧非常丰富。下面我们选取其中使用最广泛、效率最高的一些算法加以 介绍和分析其中有些是单模式串匹配算法( 即j p j = 1 ) ，有些是多模式串匹 配算法由于大部分单模式串匹配算法都能很容易地推广到多模式串的情形， 所以我们不作明显的区分 2 2 1 基于前缀的算法 k m ea c 基于前缀的算法一般需要逐个扫描文本字符，与模式串的前缀进行匹配。 它们不具备跳跃能力，所以具有o ( n ) 的时间复杂度k m p 【1 5 和a c 【1 6 算法 是其中的代表。 k m p 算法由m o r r i s 、p r a t t 和k n u t h 提出它的原理是：在当前文本窗口内 从左向右开始匹配，如果在识别到模式串的第j + 1 个字符p j + l 时发现不匹 配，则说明莉个字符p l 砘p j 与已经扫描的文本是相等的如果我们知 道p l p 2 以( osk j ) 是m m 胁的后缀，并i e i p l p 2 m 是满足这个条件的 最长前缀串，那么匹配窗1 ：3 就可以安全地向右移奶一k 个字符，同时从新 的匹配窗口的第七+ 1 个字符开始比较。定义僦矗忉= m a x ki ( p i p 2 p k ； 一 一 第：幸书地配算法的研究现状 n 一l p j ) a ( p j m ) ) ，那么在位置j + 1 不匹配时，匹配窗口可以安全地移 动j n e z t j 1 个字符。 a h o - c o r a s i c k ( 以下简称a c ) 算法足k m p 算法向多模式串情形的自然扩 展a c 算法使用t r i e 数据结构来组织所有的模式串，然后从t i l e 的根结点丌始 层次遍历- 构造结点问的后缀链( s u p p l yl i n k ) 【1 3 1 在匹配时，当当前状态无 法继续识别字符时，就沿着后缀链向上回溯，直到找到一个能够识别该字符的 状态为止a d v a n c e da c 算法足在a c 算法的基础上，将后缀链进行修改，直接 指向当前状态的后继状态，构成的一个完全循环自动机。这样，在匹配时无需 沿着后缀链回溯，而是直接跳转到它的后继状态因此a d v a n c e da c 比a c 快得 多。 “下面我柄瘤过图亲来展示a c 算鑫的运行机制。” 图2 1 足模式串集合p = k 6 6 ，曲6 对应的a c 自动机。黑色实线表示状态 转移，蓝色虚线表示后缀链，方框表示的是在该状态有哪些模式串被匹配。 ，”。、 图2 1 p = 6 0 6 6 ，口6 口6 ，对应的a c 自动机 图2 2 是a c 自动机搜索文本t = b a b a b a b 的过程。 从本质上来看，k m p 和a c 都是对识别模式串最长前缀的的确定型自动机的 模拟而我们后面将要介绍的s h i t t - o r 【1 7 1 算法则可以看作是对相应的非确定型 自动机的模拟 a c 算法不受模式串长度和文本特征的影响，具有抗攻击的优点，是工程应 用中的首选算法之一 一窖一 第：二章串匹配算法的研究现状 2 2 2 基于后缀的算法【b m ，h o r s p 0 0 1 w u m a n b e q b mf 1 8 算法足最早的跳跃型算法它的特点足在窗e l 内部从右向左逆向匹 配，通过两种启发式方法( “良好后缀转移”和“不良字符转移”) 来决定下 一次匹配窗口的开始位置。b m 算法具有较好的跳跃能力，但它的预处理过程比 较复杂。在单模式串匹配领域，它不足最快的算法。c o m m c n t z - w a l t c r 【1 9 】算法 是b m 算法向多模式串情形的推广 h o 硌p o o l 【2 0 算法对b m 做了简化，它根据匹配窗口的最后一个字符在模式 串中的出现位置来决定跳跃距离。它的跳跃距离表示为： s p 】= m m a x j 1 0 = 0 ) v 0 t o , a 盯= 岛) l ( 仃e ) h o 俗p o o l 的优点在于只要维护一个大小为的表，就可以用o ( 1 ) 的时间计算出 跳跃距离，因而是一种非常快速的单模式串匹配算法。s e t - h o r s p o o l 【1 3 】算法 是h o r s p o o l 算法向多模式串情形的自然推广s e t - h o r s p 0 0 1 只适合较小规模的模 式串集合，这是因为随着模式串规模的扩大，单个字符在模式串中的最右出现 位置越来越靠近模式串的尾部，因而跳跃能力非常有限。可以证明，在随机情 况下，s e t - h o r s p o o l 的平均跳跃距离为m ( 1 一暑旨) w u - m a n b e r 2 1 1 算法克服t s e t - h o r s p o o l 的缺点。它用多个字符组成的 块b 来代替单个字符，这就降低了块在模式串中出现的概率，改善了跳跃 能力。w u - m a n b e x 的跳跃距离可以表示为： 8 e l = t i t , 一m a x ，i u = b 一1 ) v ( b = 巧l p j ) ) ( b e 6 ) 用字符块代替单个字符的方法，固然改善- f g t 跃距离，但它它需要维护一个i e r 大小的表，带来了存储空问的暴涨w u - m a n b c r 算法通过散列解决了这个问 题由于采用哈希和查表的方法，w u - m a n b e r 计算跳跃距离的代价为d ( 1 ) ，因 而是一种效率非常高的多模式串匹配算法 下面我们通过图示来展示w u - m a n b e r 算法的跳跃过程。 情形l ：块口出现在模式串中，这时模式串向右滑动s b 1 = m j 个字 符为该块在模式中的最右出现位置如图2 3 所示。 一9 一 第一章串匹配算法的研究现状 情形2 ：块b 没有出现在模式中，这时模式串向右滑动s l 明；m b + 1 个字 符，6 为块的大小如图2 4 所示 情形3 ：5 f 口l = 0 ，即块出现在模式串中并且与模式串右端对齐，这时需要 对文本和模式串进行验证，看是否出现一个匹配然后模式串向右滑动1 个字 符如图2 5 所示 【2 2 中使用。精确错误块字符转移”和“弱化良好后缀转移”这两种方法 进一步改进了w u - m a n b e r 算法的跳跃距离 2 2 3 基于因子的算法 b d m 。b o m 】 。，b d m 【2 3 】、b o m 【2 4 】都是基于因子( 即子串) 的跳跃型算法。它们的跳跃 方式完全相同，都从右向左逆向扫描匹配窗口，识别能够和模式串的子串相匹 配的最长字符串t ，如果l u l + 于匹配窗1 3 的长度m ，那么匹配窗口可以安全地向 右滑动r r t , 一i u l 个字符；否则，需要检查模式串和当前位置的文本是否相等，并 报告可能的匹配，然后匹配窗口滑动一个字符。 b d m 和b o m 的主要区别在于它们识别模式串因子的数据结构不 同。b d m 用来识别模式串因子的数据结构是d a w g ，d a w g 是识别模式串因 子的最小自动机，构造它的时间复杂度和空间复杂度都是o ( r a ) b o m 用来 识别模式串因子的数据结构是f a c t o r o r a c l e ，f a c t o r o r a c l e 具有弱因子识别的功 能，由于子串识别的不精确性，b o m 相比于b d m 的跳跃能力稍弱；但f a c t o r o r a c l e 的结点数日比d a w g 要少f a c t o r o r a c l e 构建的时间复杂度和空间复杂度 也都是d ( m ) 下面我们通过图示来展示b o m 算法的运行机制。 图2 6 是模式串集合p = a n n o u n c e ，a n n u a l ，a n n u a l l y 对应的f a c t o ro m c l e 自动机 在使用f a c t o ro r a c l e 自动机扫描文本时。有两种可能的情况：完全识别匹配 窗口内的字符串和部分识别匹配窗口内的字符串 图2 7 是完全识别的情况：窗口( 卿，p o s + m i 内的字母全部被识别，到达状 态1 2 。这时需要将字符串a n n o u n c e 与匹配窗口左端对齐，验证是否匹配：然后 匹配窗口向右滑动1 个字符 所谓弱冈了识别是指：f a c t o r o r a c l e 识别的字符串集台是模式串了串集含的超集。凡是模 式串的于串都能被它所接受伊它所接受的字符串有可能不是模式串的了：串 一l o 第：章串匹配算法的研究现状 闰2 8 足部分识别的情况：窗口( 删，p o s + m 1 内的字母部分被识别，到达状 态8 ，无法继续识别字母o ，于足匹配窗口移到字母o 之后。 在一般情况下，跳跃型算法具有弧线性的时间复杂度，这优于非跳跃型算 法的线性时间复杂度，但是跳跃型算法在最坏情况下的时问复杂度为d ( 啪) 随着模式串和文本特征的不同，算法的性能差别可能非常大必须针对具体的 应用环境选择合适的算法 2 2 4 位并行算法 s h i f t - a nd s h i f t - o r b n d m 】 位并行的主要思想足利用位操作的并行特性来提高算法的速度。在精确模 式串匹配算法中，s h i f t - a n d 、s h i f t o r 【1 7 和b n d m 【2 5 足运用位并行最为成 功的范例。 s h i f t - a n d 算法用m 位的向量且p l ( 盯) 表示字符盯在模式串中可能出现 的位置，即： 蹴： f p j ， t o o t h e r w i s e b p 】可以在预处理阶段计算。用m 位的向量d 记录与当前位置文本的后缀相匹 配的模式串前缀的位置，即： f f p l 乃= 岛一，+ l t i ， o t h e r w i s e d t i l j = o i i l 】j 一1 ( 岛= 功) ( 1 j m ) d i h = ( t i = p 1 ) ， 它可以统一表示为： d l i 】= ( ( d p 一1 l 1 ) 1 0 m - 1 1 ) b 陋d 在匹配时，只需逐个扫描文本字符并更新位置向量d m 即可在文本位置设b 匹 配成功的条件是：n l i l s a o 一1 0 ” 1 o ，_-(1l = 刚 有史 定的d据根 筇一：章串匹配算法的研究现状 s h i f t - o r 使用负逻辑，简化了d f 】的更新操作； d i j = ( d i l 】 1 ) ( u ) b i o 意义与前面相同当d m & l o ”q 0 m 时，模式串匹配成功；否则，匹配 窗口可以安全地移动m m 个字符。 s h i f t - o r 和b n d m 算法都可以推广到多模式串的情形。由于利用了位操作 速度快的特点，位并行算法效率都很高但所有模式串的长度之和不能超过机 器的字长，因而位并行只适合于小规模模式串的场合 2 2 5 近年来的进展 近几年来，在串匹配领域又取得了一些新的进展，具体如下： 【2 6 1 提出了一种基于分组的串匹配算法。文中证明了最优分组定理并提 、 出了基于最短路