（计算机系统结构专业论文）快速精确字符串匹配算法研究.pdf

快速精确字符串匹配算法研究 摘要 字符串匹配算法是计算机应用、信息检索及计算生物学等的重要研究 内容，在日常生活及科学研究中有着广阔的应用。随着计算机技术和网络 技术的发展，新的应用对匹配实时性的要求不断提高。本文在对精确字符 串匹配问题的研究与现状及其各种方法进行深入探讨的基础上，针对单模 式精确字符串匹配及多模式字符串匹配中，被广泛使用的b m 和w m 两种 算法进行深入系统的研究，并提出相应的改进算法并通过实验验证了新算 法的优越性。全文主要内容如下： 1 分析了字符串匹配算法的国内外研究现状，详细讨论了精确字符串 匹配下的三种搜索方式，研究并实现了单模式字符串匹配及多模式字符串 匹配下的若干典型算法，包括s h i f t a n d 及s h i f t o r 算法、h o r s p o o l 算法、 b n d m 及b o m 算法、a c 算法、w m 算法、s b o m 算法。 2 传统的b m 算法在不匹配发生时，匹配窗口移动的最大距离较小并 且匹配窗口能够移动的最大安全距离也不够大。因此，字符串匹配速度仍 有提升空间。针对这种情况，本文提出了一种新的可以增加平均移动距离 的改进的b m 算法。该算法首先在预处理阶段使用任意的两个字符作为字 符块来计算移动距离，并设置最大移动距离为模式串长度加一；然后在查 找阶段通过比较连续的两个字符块来增加大距离移动的概率。实验结果表 明该算法相比于原算法在速度性能上提高明显。 3 传统的w m 算法在发生不匹配时安全移动距离明显较小，而当与 模式串匹配后的移动距离又较保守，并且存在单次匹配而整个模式串不匹 配的概率较大的情况。针对这些问题，本文提出了一种新的改进的w m 算 法，该算法首先对s h i f t 表进行改进，使得安全移动的距离有了较为明显 的提高；其次改进搜索查找算法，通过增加比较字符块使得单次匹配而整 个模式串不匹配的概率下降并使与模式串匹配后的移动距离不再为1 。实 验表明，本算法较原算法在匹配速度上具有较好的实验效果。 关键字：字符串匹配；模式串匹配；精确串匹配；b m 算法；w m 算法 t h er e s e a r c hf o rf a s te x a c ts t r i n gm a t c h i n ga l g o r i t h m a bs t r a c t s t r i n gm a t c h i n ga l g o r i t h mi st h ei m p o r t a n tr e s e a r c ht o p i ci nc o m p u t e r a p p l i c a t i o n ，i n f o r m a t i o nr e t r i e v a la n dc o m p u t a t i o n a lb i o l o g ya n ds oo n i th a s ab r o a da p p l i c a t i o ni nt h e d a i l yl i f e a n ds c i e n t i f i cr e s e a r c h w i t ht h e d e v e l o p m e n t o f c o m p u t e rt e c h n o l o g y a n d n e t w o r k t e c h n o l o g y ，n e w a p p l i c a t i o n sc o n t i n u et oi n c r e a s et h er e q u i r e m e n t so f r e a l - t i m eo ft h em a t c h i n g i n t h i sp a p e r ，o nt h eb a s e so fs t u d y i n gt h er e s e a r c ha n ds t a t u so ft h ee x a c t s t r i n gm a t c h i n gp r o b l e ma n di t sv a r i o u sm e t h o d s ，id e e p l ya n ds y s t e m a t i c l y s t u d yt h eb ma l g o r i t h ma n dw ma l g o r i t h m ，w h i c ha r ew i d e l yu s e di ne x a c t s t r i n gm a t c h i n gf o rs i n g l e m o d ea n dm u l t i - p a t t e r ns t r i n gm a t c h i n g ，a n d p r o p o s et h ec o r r e s p o n d i n gi m p r o v e da l g o r i t h m s ，w h o s es u p e r i o r i t i e s a r e e x p e r i m e n t a l l yv e r i f i e d t h em a i nc o n c e p t so ft h i sp a p e ra r ea sf o l l o w s ： 1 a n a l y s et h er e s e a r c hs i t u a t i o na th o m ea n da b r o a do fs t r i n g m a t c h i n g a l g o r i t h m ，d i s c u s st h et h r e ek i n d so fs e a r c hm e t h o d su n d e re x a c ts t r i n g m a t c h i n gi nd e t a i l ，s t u d ya n di m p l e m e n ts o m et y p i c a la l g o r i t h m su n d e r s i n g l e p a t t e r ns t r i n gm a t c h i n ga n dm u l t i p a t t e r ns t r i n gm a t c h i n g ，i n c l u d i n g s h i f t - a n da n ds h i f t o ra l g o r i t h m ，h o r s p o o la l g o r i t h m ，b n d ma n db o m a l g o r i t h m ，a ca l g o r i t h m ，w ma l g o r i t h m ，s b o ma l g o r i t h m 2 i nt h et r a d i t i o n a lb ma l g o r i t h m ，w h e nn om a t c h i n go c c u r s ，t h e m a x i m u md i s t a n c eo fm a t c h i n gw i n d o wm o v e di sm u c hs m a l l e ra n dt h e m a x i m u ms a f ed i s t a n c eo fm a t c h i n gw i n d o wm o v e di sa l s on o tb i ge n o u g h t h e r e f o r e ，t ot h es p e e do fs t r i n gm a t c h i n g ，t h e r ei ss t i l lr o o mf o ri m p r o v e m e n t i nv i e wo ft h i ss i t u a t i o n ，t h i sp a p e rp r e s e n t san e wi m p r o v e db ma l g o r i t h m ， w h i c hc a ni n c r e a s et h ea v e r a g em o v i n gd i s t a n c e f i r s t l y , i nt h ep r e p r o c e s s i n g s t a g e ，t h ea l g o r i t h mc a l c u l a t e st h em o v i n gd i s t a n c eu s i n ga n yt w oc h a r a c t e r s a st h ec h a r a c t e rb l o c k ，a n ds e t st h em a x i m u mm o v i n gd i s t a n c ea st h el e n g t ho f s t r i n gp l u s i n go n e ；t h e n ，i nt h es e a r c h i n gs t a g e ，i ti n c r e a s e st h el a r g ed i s t a n c e s m o v i n gp r o b a b i l i t yb yc o m p a r i n gt h et w oc o n s e c u t i v ec h a r a c t e rb l o c k s e x p e r i m e n t a l r e s u l t ss h o wt h a tt h e a l g o r i t h m c a ni m p r o v et h e s p e e d s i g n i f i c a n t l yc o m p a r i n gt ot h eo r i g i n a la l g o r i t h m s 3 w h e nn o tm a t c h i n g t h es a f em o v i n gd i s t a n c eo ft h et r a d i t i o n a lw m a l g o r i t h mi sc l e a rs m a l l ，a n dt h em o v i n gd i s t a n c ei sm o r ec o n s e r v a t i v ea f t e rt h e l i p a t t e r ns t r i n gm a t c h i n g ，w h a t sm o r e ，t h ep r o b a b i l i t yo fs i n g l em a t c h i n ga n dt h e w h o l ep a t t e r ns t r i n gn o tm a t c h i n gi sm u c h l a r g e r t os o l v et h e s ep r o b l e m s t h i s p a p e rp r e s e n t san e wi m p r o v e dw ma l g o r i t h m ，w h i c hf i r s t l yi m p r o v et h e s h i f t t a b l e ， s i g n i f i c a n t l yi m p r o v i n g t h es a f e m o v i n g d i s t a n c e ，s e c o n d l y ，i m p r o v es e a r c h i n ga l g o r i t h m ，m a k i n gt h e p r o b a b i l i t yo f s i n g l em a t c h i n ga n dt h ew h o l ep a t t e r ns t r i n gn o tm a t c h i n gd o w nb yi n c r e a s i n g t h ec o m p a r i n gc h a r a c t e rb l o c k ，a n dm a k i n gt h em o v i n gd i s t a n c ea f t e rp a t t e r n s t r i n gm a t c h i n gn o tb e e no n e e x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mi sb e t t e r t h a nt h eo r i g i n a la l g o r i t h mw i t hf a s t e rm a t c h i n gs p e e d k e y w o r d s ：s t r i n gm a t c h i n g ，p a t t e r ns t r i n gm a t c h i n g ，e x a c ts t r i n gm a t c h i n g ， b ma l g o r i t h m ，w ma l g o r i t h m i 插图清单 图2 1 用子串的方法进行搜索窗口的移动1 5 图3 1h o r s p o o l 算法工作原理一2 1 图3 2 子串搜索的位并行方法2 3 图3 3 “a n n o t u l c e ”的反转”e c n u o n n a 对于的f a c t o ro r a c l e 自动机2 5 图3 4 不同模式串长度的处理结果2 9 图3 5 不同文本串长度的处理结果3 0 图3 - 6 不同模式串长度的处理结果3 1 图4 1 模式串集合 h e ，s h e ，h i s ，h e r s 的g o t o 函数3 3 图4 2 模式串集合( b o o k ，d e s k 的f a c t o ro r a c l e 。3 9 图4 3 不同模式串个数的处理结果4 4 v 表格清单 表4 1 模式串集合 b o o k ，d e s k ，p e n 的s h i f t 表3 6 表4 2 模式串集合 b o o k ，d e s k ，p e n 的h a s h 表和p r e f i x 表3 7 表4 3 模式串集合 b o o k ，d e s k , p e n 新的s h i f t 表4 1 表4 - 4 不同模式串最小长度及个数下两种算法的比较次数4 2 v i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得 金壁王些太堂 或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签字： 俩覆 学位论文版权使用授权书 签字日期：o 毕、 本学位论文作者完全了解 金壁王些太堂 有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借 阅。本人授权 金胆王些太堂 可以将学位论文的全部或部分论文内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：n 乏 签字日期： w f o 七、诞 学位论文作者毕业后去向： 工作单位： 通讯地由e ： 导师签名： 签字日期： 电话： 邮编： ￥h 致谢 近三年的研究生生活即将结束，这三年的学习和生活虽然短暂，但却 紧张而充实，回顾自己一路走来，掂量一下得失，不由感到自己还是十分 的幸运，幸运自己一路并不孤单，拥有众多良师益友的帮助，拥有挚爱亲 人的支持，在此，我要衷心地对大家说一声：“谢谢了”。 首先，我要感谢我的导师汪荣贵教授，三年前，当我还是一个刚刚本 科毕业的“菜鸟”，怀着忐忑不安的情绪进入研究生阶段学习时，他的一番 热情洋溢的鼓励让我对自己充满了信心，同时也使我对网络安全产生了极 大的兴趣。三年来，从学士到硕士，他给予我无微不至的关怀，我不仅从 汪老师那里学到了专业知识，学到了分析问题解决问题的方法，更重要的 是学到了一种踏实做事，认真做人的人生态度，这些必将使我终生受益匪 浅。值此之际，谨向恩师致以最崇高的敬意和最诚挚的感激。 感谢计算机学院的胡敏老师、曹航老师等各位老师在日常学习生活中 提供的帮助。 感谢和我一起走过三年研究生生涯的张璇、查全民、杨万挺、吴昊同 学，他们才华横溢、充满青春活力，他们的思想和智慧给予我很大的启迪， 他们的执著和追求使我深受鼓舞，他们过人的毅力使我佩服不已，和他们 在一起的日子我永远难忘。 感谢朱静、李孟敏、张新龙、张勇、沈法琳、周良、傅剑锋、游生福 等一起努力奋斗过的师妹师弟们，感谢他们对我的信任和支持，同时他们 无私的帮助使我倍加珍惜同学情谊，祝福我们的友谊天长地久。 特别要感谢我的父母和姐姐，他们总是在背后默默地支持着我，关爱 我，他们无私的爱是鼓励我不断努力和前进的动力，他们的爱我将永远铭 记在心。 最后，对所有关心和帮助过我的老师、同学和朋友表示衷心的感谢! i v 第一章绪论 1 1 课题的背景和意义 串匹配问题是指从给定的符号序列中找出一个或若干个具有某种属 性的模式序列，而字符串匹配指的便是从给定的字符序列中找出一个或若 干个给定的字符串。字符串匹配算法是一个基础算法，它的解决以及在这 个过程中产生的方法对计算机的其他问题都产生了巨大的影响。在我们日 常使用计算机的过程中，使用字符串匹配技术的例子十分普遍，例如：入 侵检测、病毒检测、信息检索、信息过滤、计算生物学等等都包含了字符 串匹配技术。 在字符串匹配技术被广泛应用的同时，众多的科技人员也对其进行了 深入研究，字符串匹配问题现已经发展成一门相对独立的学科一字符串 学( s t r i n g o l o g y ) i l 】【2 】【3 】。字符串匹配技术最先被应用的领域是图书文献目 录摘要的查询系统和构建数据的全文检索系统。而后，随着网络安全技术 和生物技术的日益发展，在网络安全和生物计算等领域中字符串匹配技术 又获得了新的发展空间。 随着网络速度和流量的日益增加，基于网络的入侵检测【4 儿5 】系统面临 着严峻的挑战，它的处理、分析速度越来越难跟得上网络流量增加速度， 从而极易导致数据包的丢失。解决数据包丢失等问题，提高处理速度是关 键。另外对于基于误用的入侵检测系统而言，检测过程中最费时的部分便 是入侵特征匹配。以开源软件s n o r t 6 j 为例，通过对s n o r t 实际运行中各函 数被调用的时间比分析发现，约有3 1 的时间是对数据包负载中特征字符 串的匹配耗时，这也是耗时最多的一项。其次是匹配头结点，约占总时间 的1 5 2 ；而其它类型的匹配仅占5 8 ，此外在s n o r t 2 3 3 的规则集中有 内容匹配选项的规则数目达到总规则数的9 0 以上。由上述数字可以看出 对于基于误用的入侵检测，字符串匹配算法是至关重要的，它的性能将直 接影响到入侵检测系统的准确性和快速性。而随着网络带宽不断增高，千 兆以太网络现在己进入普及阶段，目前主干网络上带宽更高。在如此高带 宽的网络下进行入侵检测和病毒检测对字符串匹配算法性能提出了严峻 的挑战，因为目前在通用计算机上，进行精确字符串匹配的典型算法还无 法达到1 0 g b s 级别。如果不能提出更高速的精确串匹配算法，在高速网 络上，网络安全将成为一种空谈。 目前，信息资源的高速膨胀已成为一个全球普遍关注的现象。加利福 尼亚大学伯克利分校研究人员发现，仅从1 9 9 9 年至2 0 0 2 年全球新产生出 的信息量就翻了一番。伴随着信息膨胀，信息的良莠不齐的现象也是一个 严重困扰人们的问题。大量反动言论、黄色信息及国家机密在网络上蔓延 和传播，给国家安全和社会稳定造成了严重的威胁，如何对这些不良信息 进行网络监管是我们面临的一个严重问题。在信息过滤时，特别是在主干 网络上进行过滤与检索，对字符串匹配的实时性要求极高，字符串匹配性 能的优劣直接影响了过滤与检索系统的性能。在这些系统中，使用串匹配 算法对有害信息进行匹配是进行过滤的基本手段之一。这些系统通常运行 在骨干网结点上，单位时间内需要处理的数据量非常大，实时性要求也很 高。作为检测引擎的核心，字符串匹配算法性能的优劣是影响系统性能的 决定因素之一。 随着生命科学的发展，人们对生命物质的微观结构也有了越来越清晰 的认识。目前，人类基因组序列的绘制工作已经基本完成，p r o s i t e 等大型 蛋白质重要样本数据库也已建立【_ 7 1 。由于基因和蛋白质都可以用建立在一 定字符集上的符号序列来表示，因此字符串匹配技术便有了新的发展空 间。在计算生物学中，海量的基因组序列数据( 如每个人类基因的碱基数目 高达3 0 亿对) 和蛋白质序列数据中进行比对、分析、组合的基础是字符串 匹配技术。计算生物学中字符串匹配的特点是数据量巨大，字符集小，并 且存在大量的噪声信号等问题。原有字符串匹配算法很难适应这样的文 本，这也为字符串匹配算法研究提出了新的挑战与机遇。 综上所述，随着计算机技术和网络技术的发展，新的应用对匹配实时 性的要求不断提高，于此同时需要进行匹配的文本量也正成几何级数增 长。而字符串匹配技术的发展却明显滞后于信息总量和计算机硬件的发 展，现己成为制约串匹配类应用的瓶颈。因此发展字符串匹配算法对提高 相关应用系统的性能有着重要的现实意义。 1 2 串匹配问题简介 串匹配可以分为三类：精确串匹配( e x a c ts 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 n m a t c h i n g ) t 引。精确字符串匹配要求文本中被匹配的字符串与模式串严格相 等。近似匹配算法的功能是按照算法定义的相似程度度量标准，在数据序 列中找出所有和一个或一组特定的模试串的相似程度在定范围内的所 有子串的出现位置。文本串与模式串之间的误差可以用距离来度量，常用 的距离有：编辑距离( 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 ) 等。在正 则表达式匹配中，待匹配的不是简单的字符串，而是正则表达式，它是在 数据序列中找出能够被正则表达式接收的所有子串的出现位置。这三类算 法的产生都是与具体的应用领域的需求直接相关的，精确匹配算法主要应 用在文本检索和网络安全的入侵检测领域中，近似匹配算法主要应用在计 2 算生物学和信号处理等应用领域，正则表达式匹配算法主要用来处理简单 的序列匹配无法描述的问题，是精确匹配算法或近似匹配算法的增强模 式。 1 2 1 精确字符串匹配 精确字符串匹配算法分为单模式精确字符串匹配算法和多模式精确 字符串匹配算法，它们的区分在于与文本串比较的模式串的个数。 单模式精确字符串匹配，就是指在一个文本t = t l r ，。中找出某个特定 模式串p = p 。p ：p 肿的所有出现位置，其中r 和p 都是在有限字母表上 的字符序列，力和m 是自然数。设x , y 和z 为字符串，则称x 为砂的前缀， 称x 为胗的后缀。而多模式精确字符串匹配是指在文本t = t l f ，一，。中找出 模式串集合p = p 。p p p 。的所有模式串的所有出现位置。 根据在文本中搜索模式串方式的不同，单模式精确字符串匹配算法可 以归结为三种基本的方法。基于这三种方法的单模式精确字符串匹配算法 都能够扩展成多模式精确字符串匹配算法。 第一种方法是从文本中逐个读入字符，每读入一个字符就更新相应变 量，检查是否存在一个可能的匹配。k m p ( k n u t h m o r r i s p r a t t ) 算法1 9 j 就属 于这种方法，另外两种是更快的s h i f t o r 算法【lo j 和s h i f t a n d 算法【1 1 1 ，对 其进行扩展后可以支持对更复杂模式串的搜索。基于这种算法的多模式算 法包括著名的a c ( a h o c o r a s i c k ) 算法【l 引，如果用i 尸l 表示所有模式串的长度 之和，那么，当l 尸i 彳艮小的时候，可以使用m u l t i p l es h i f t a n d 算法i l l 】。 第二种方法基于滑动窗口。滑动窗口沿着文本t 滑动，对于任意位置 上的窗口，在窗e l 中从后向前搜索窗口中的文本和模式串p 的公共后缀。 b m ( b o y e r m o o r e ) 算法【l3 】就是用了这种方法。但在一般情况下， b o y e r m o o r e 算法比它的一个简化版本h o r s p o o l 算法【1 4 l 要慢。实际上，b m 系列算法中除了h o r s p o o l ，都要比使用其他方法的一些算法慢。基于这种 算法的有著名的c w ( c o m m e n t z w a l t e r ) 算法l l5 1 ，但其实际运行的效率不是 很高。h o r s p o o l 算法的扩展是s e th o r s p o o l 算法，当搜索一个很大字母表 上的一个较小的模式串集合时，其效率很高。w m ( w u m a n b e r ) t 1 6 】算法结 合了后缀搜索算法和散列方法，在实际应用中效率很高。 第三种方法出现的较晚，和第二种方法一样，第三种方法也使用了滑 动窗口，并在其中从后向前搜索。不同的是，它搜索的是窗口中文本的最 长后缀，并且这个最长后缀同时也是模式串p 的一个因子。最早使用这种 方法的算法是b d m ( b a c k w a r dd a w gm a t c h i n g ) 算法【l ，当p 足够短时， 可以将其改造成更简单、更有效的算法b n d m ( b a c k w a r dn o n d e t e r m i n i s t i c d a w gm a t c h i n g ) 【l 引。对于较长的模式串，一个称为b o m ( b a c k w a r do r a c l e 3 m a t c h i n g ) 【1 9 1 的新算法是最快的。由b o m 算法派生出了多模式匹配算法 s b o m ( s e tb a c k w a r do r a c l em a t c h i n g ) 算法2 0 1 。当模式串集合中的最小 模式串长度较大时，s b o m 算法的效率很高。与s h i f t o r 算法相似，当l p | 很小时，b n d m 派生出了m u l t i p l eb n d m 算法【2 1 儿2 2 1 。 1 2 2 近似字符串匹配 近似字符串匹配算法也可以叫做允许误差的模式串匹配，就是在文本 r 中查找模式串p ，并允许模式串p 和它在文本中的出现之间存在有限的k 个差异。目的是找到数据串中与模式串的差异度在一定范围内的所有子串 出现位置，所以近似模式串匹配算法的结果是与预先定义的两个符号串近 似度的计算方式相关的。近似模式串匹配算法的求解主要有四种途径【2 3 1 ： 动态规划法( d y n a m i cp r o g r a m m i n g ) t 2 4 】【2 5 儿2 6 2 7 】，基于自动机的方法 ( a l g o r i t h m sb a s e do l la u t o m a t a ) 2 5 】，位并行方法( b i t p a r a l l e l i s m ) t 2 8 】【2 9 】【3 0 1 和过 滤筛选法( f i l t e r i n ga l g o r i t h m ) | 2 8 】【2 9 】【3 1 】【32 1 。 现在有很多度量“差异”的模型，有些非常复杂，尤其是在计算生物领 域中，目前最为流行的是编辑距离模型，在编辑距离模型中，一个差异等 价于一个编辑操作：插入一个字符、删除一个字符，或者替换一个字符。 设x ，y 是两个字符串，他们之间的编辑距离e d ( x ，y ) 就是将x 转变为y ( 或者是将y 转变为x ) 所需的最少编辑操作次数，例如： e d ( a n n u a l , a n n e a l i n g ) = 4 。因此，近似字符串匹配也可以描述为：在文本r 中找出所有的子串p ，是的p d 仞，p ) = j j 。为了保证匹配过程的输出结果个 数是线性的，通常只返回p 出现的起始位置或者终止位置。要注意的是， 如果模式串的长度为聊，那么上面的k 值必须满足o k 第二种方法是维护一个集合，它包括了所有既是已读入文本的后缀 也是模式串p 的前缀的字符串，并且每读入一个文本字符时就更新 该集合。当模式串的长度足够短时，位并行方法可以有效地维护这 个集合。s h i f t a n d 算法和s h i f t o r 算法使用了此方法。 k m p 算法1 9 j 1 9 7 0 年，m o r r i s 和p r a t t 提出了k m p 算法的原型，而后由k n u t h 于1 9 7 7 通过改进它预处理过程中最长前缀的定义正式给出了k m p 算法。k m p 算 法主要基于以下思想：当程序在匹配窗口内从左向右开始匹配，在模式串 的第k + 1 个字符p 处发现不匹配，则说明前k 个字符p r p 。与当前文本 完全相等。如果知道对应匹配子串a 仇的所有后缀中含有的p ，p 。的最 长前缀p 1 p t ( o i k ) ，就可以将匹配窗1 3 安全的向右移动k i 位。 其中最长前缀定义为： d 绣妒对p r 彰鼠= m a ) ( j l 怄忿 v o i dk m p ( c h a r x ，i n t1 1 1 ，c h a r y ，i n tn ) i n t i , j ，n e x t x s i z e ； 预处理 p r e k m p ( x ，r n ，n e x t ) ； 搜索 i - - j = o ； w h i l e ( j - 1 & & x 【i 】! = y 【j 】) i = n e x t i ； i + + ； j + + ； i f ( i = m ) o u t p u t ( j - 1 ) ； i = n e x t i ； ) 9 算法实例： 设模式串p = a b c a a b c a c 文本串t = a d b a a c b c a a b c a a b c a c 我们首先对n e x t 数组进行预置，根据n e x t 数组的算法得到，如下 j 123 4567 89 n e x t i 】0 1l12 1 345 模式串 ab ca abc ac 再与文本串t 进行比较，所经过的步骤如下 j l234567891 01 11 2 1 3 1 4 1 51 61 718 目标tad b aacbcaabcaabcac 模式pab caabcac 垦 bcaabcac ab ca a bcac abc a abc ac abc a abc ac 量 bcaabcac abca abcac 垒 bca abcac a 鱼 caabcac abca abcac 针对k m p 算法国内外均有大量的改进算法，如s i m o n 算法， a p o s t o l i c o c r o e h e m o r e 算法等。k m p 算法虽然其时间复杂度不高，但是在 实际应用中性能并不优秀，经常比蛮力法还要慢，因此这些改进算法实际 效果也不够好。 2 4 基于后缀搜索的方法 虽然k m p 算法比b f 算法有了很大的进步，但速度并不是很快。因为 每次字符匹配不成功之后，模式串都是向前移动到一个合适的位置，而文 本串不变，无论什么情况，文本串都是从第一个字符开始，依次向右，直 到最后一个字符比较完毕。基于后缀搜索的方法很好的解决了这个问题， 它可以跳过更多的字符。 按后缀匹配机制指在滑动窗口中从后向前( 沿文本的反向) 逐个读入文 本字符，搜索窗口中文本和模式串的最长共同后缀。按后缀匹配算法均能 1 0 实现跳跃，跳过一些文本字符，从而拥有亚线性平均时间复杂度。一般来 说按后缀匹配算法在实际匹配中性能高于按前缀匹配的方法。 b m 算法【”1 ： b m 算法中，一但匹配失败，则有两种方法来确定模式串向右移动的 距离。这两种方法都给出了可以安全向右移动而不会错过任何匹配的距 离，我们取其中最大的距离来移动匹配窗口。这两种方法被称为：坏字符 规则和好后缀规则。 ( 1 ) 坏字符规则 根据后缀搜索的方法，当发生不匹配时，设t k 】p 【j 】，这以前的m - j 个字符都已匹配。这时，主要看t 【k 】是否在模式串p 中，分两种情况： ( a ) t k 】不在模式串p 中出现，这时，我们完全可以将模式串移动到 t 【k 】之后，因为t 【k 】不在p 中，不与任何一个p i 】( 1 i m ) 匹配，这样 移动完全是安全的。然后从p 【m 】与t 【k + m 】继续进行比较。 ( b ) t k 】在模式串p 中出现。t k l = p x 并且t k 】不在p x + l ，m 】中。 也就是说，能够在p 串中找到字符t k 】，设为p 【x 】，并且为p 串中最右出现 的字符。此时又分两种情况： 如果x 如果x j ，即p 【x 】在p j 】的右边，这时按理应将串p 向左移，这样做 明显是无用的，所以，此时应仅向右移动1 位，然后再从p 【m 】与 t k + m - j 1 】开始比较。 实际上坏字符规则就是计算b a d c h a r 数组的过程，它用来计算字符集 己中每个字符所对应的偏移量，如果某个字符在模式p 中出现了多次，则 从最右边的那次出现确定偏移量，对于乞中的每个字符a ，可表示为： b a d c h a r c 】= = i n “鲥硼一肿m + 玎钳薯著帅蝴 ( 2 ) 好后缀规则 在匹配过程中，会有一部分子串匹配成功。设t k 】p d 】，那么p j + l m 】 已经匹配，这时，我们可以在p 中从p d 】开始向前寻找与p j + i m 】相同的 子串。如果有这样的子串，将其移动到当前位置，进行匹配。 好后缀规则所要计算出的移动窗口右移的偏移量主要有两方面因素 决定： ( a ) 该后缀在模式中除去自身外，从最右端开始再次出现的位置； ( b ) 当除该后缀外不存在与其相同的字符串时，寻找既是该后缀的某 个后缀同时又是模式的前缀字符串的位置。 实际上好后缀规则就是计算s u f f i x 数组的过程，根据以上分析其值可 表示为： s u f f i x c = i - m a x jl p j + i2 b “ j i ，0 k m - i ) 当进行了上述两步预处理之后，便可对文本串进行匹配，查找阶段根 据后缀搜索方式进行匹配查找，当发生不匹配时选取b a d c h a r c $ 1 】s u f f i x c 】 中的最大值对匹配窗口进行右移。b m 算法的最坏时间复杂度为o ( m 奎n ) ， 最好的时间复杂度却是o ( n m ) 。实际比较次数只有文本串长度的 2 0 3 0 。我们可以把它的时间复杂度称为“亚线性”，因为它能够让模式 匹配算法的比较次数低于文本串的长度。在此之前的算法，虽然达到了线 性复杂度，但比较的次数总是不低于文本串长度。 伪代码如下： v o i dp r e b m b c ( c h a r 幸x ，i n tm ，i n tb m b c 【】) i n ti ； f o r ( i = o ；i g & & s u f f i + m 一1 一f 】 1 2 v i o dp r e b m g s ( c h a r x , i n tm ，i n tb m 3 s ) l i n ti , j ，s u r f x s i z e ； s u f f i x e s ( x ，m ，s u 田； f o r ( i = 0 ；i = 一1 ；一- i ) i f ( i - - - = 一1l i s u f f i l = = i + 1 ) f o r ( ；j 抵达了窗e l 的起始位置，这意味着整个模式串p 被成功匹配。于是 报告一个成功匹配，并像上述中那样移动窗口。 b d m 算法的最坏时间复杂度是o ( m n ) 。然而在文本的各个字符互相 独立并且等概率出现的条件下，该算法能够达到最优的平均时间复杂度 o ( n l o g l l m m ) 。 本算法使用了后缀自动机这种数据结构，虽然功能强大，但结构复杂。 鉴于以下两点本节不做过多讨论。 当模式串的长度不超过机器字长w 时，后缀自动机可以用位并行方 法进行有效的模拟。位并行算法b a c k w a r dn o n d e t e r m i n i s t i cd a w g m a t c h i n g ( b n d m ) 比b d m 算法更快，更易于实现。 当模式串较长时，b a c k w a r do r a c l em a t c h i n g ( b o m ) 算法能够获得与 b d m 算法相同的效果。但是，b o m 使用的自动机更加简单。 2 6 小结 本章详细介绍了前缀搜索、后缀搜索和子串搜索的基本思想，并在每 种类型下列举了相应的实例算法，通过对各个算法的描述、分析以及举例， 进一步阐述了这三种思想。 1 5 第三章单模式精确字符串匹配算法研究 3 1 引言 上章介绍了三种不同类型的模式串匹配方法，由于它们的基本原理各 不相同，导致它们的适用范围也不一样，因此有必要从这三种类型的角度 入手研究其相应的思想及相关算法。基于前缀搜索的s h i f t a n d 及s h i f t o r 算法它们的思想较前