（计算机应用技术专业论文）高性能精确单模式串匹配算法研究.pdf

哈尔滨t 稗大学硕十学伊论文 摘要 串匹配问题是计算机科学的基础问题之一，几乎所有涉及字符串处理的 应用中都或多或少的存在字符串匹配的要求。特别是在信息检索，网络安全， 计算生物学等领域，字符串匹配为这些领域的核心问题。在所有字符串匹配 问题中，精确单模式匹配算法设计又是串匹配问题的基础。目前，随着网络 安全问题的凸显，网络技术、计算生物学的高速发展，以及“信息爆炸”现象 愈加严重，字符串匹配应用对字符串匹配性能的要求越来越高，这对高性能 字符串匹配应用的串匹配算法设计( 特别是精确单模式匹配算法) 提出了新 的挑战。 本文主要对高性能精确单模式串匹配算法进行研究。首先对现有高性能 精确单模式算法发展进行分析，给出目前在英文语料匹配下，性能最高的精 确单模式串匹配算法。并分别对当前英文语料匹配下性能最高的两个串匹配 算法t u n e db m 和s b n d m 2 提出改进，提出了d q m 算法和s 2 b n d m 算法。 具体来说，本文成果主要在于： 1 总结前人研究结果，分析了现有精确单模式串匹配算法，并给出了目 前进行字符串匹配领域研究的研究方向，以及目前性能最高的精确单 模式串匹配算法。 2 提出一种基于后缀匹配机制的高性能精确单模式串匹配算法d q m 算法。d q m 算法以t u n e db m 算法为基础算法，在t u n e db m 算法基 础上引入两个判定字交替进行跳跃的方法降低了随跳跃进行判定字 匹配概率动态增长对算法性能的影响；引入了一种改进的越界保护机 制以降低越界检查的开销；并通过位操作和合并操作的方法改进算法 在判定字匹配后的动作，使分支与跳转的次数降至最低。实验表明， d q m 性能比t u n e db m 算法更高。 3 提出了一种基于位并行、循环展开、按子串匹配机制的高性能精确单 模式串匹配算法- - s 2 b n d m 系列算法。s 2 b n d m 算法以s b n d m 2 算 法为基础算法，通过修改b n d m 类算法的位掩码定义，成功将b n d m 类算法的核心循环化简至五条指令的最简形式。同时，本文在 哈尔滨t 稗大学硕十学伊论文 s b n d m 2 算法中引入下标越界保护，将下标越界检查的开销也降至最 低。实验数据显示，在模式长度不超过机器字长的英文语料检索应用 中，和模式长度不超过8 的d n a 序列检索应用中，s 2 b n d m 算法是 目前所有精确单模式串匹配算法中性能最高的算法。 关键词：字符串匹配：算法设计；精确单模式；文本搜索 哈尔滨：r 程大学硕十学何论文 a b s 仃a c t s t r i n gm a t c h i n gp r o b l e mi saf u n d a m e n t a lp r o b l e mi nc o m p u t e rs c i e n c e i ti s u s e di nm o s to ft h ea p p l i c a t i o nr e l a t e dt os t r i n gt r e a t m e n t m e a n w h i l e ，i ti st h ek e y p r o b l e mo fi n f o r m a t i o nr e t r i e v a l ，n e t w o r ks e c u r i t y , a n dc o m p u t a t i o n a lb i o l o g y t h ee x a c ts i n g l ep a t t e ms t r i n gm a t c h i n gp r o b l e mi st h eb a s i so fa l lo fs t r i n g m a t c h i n gp r o b l e m w i t ht h eh i g h l i g h to fn e t w o r ks e c u r i t y , w i t ht h eh i g hs p e e d d e v e l o p m e n to fn e t w o r k i n ga n dc o m p u t a t i o nb i o l o g y , a n dw i t ht h ep h e n o m e n o n o f “i n f o r m a t i o ne x p l o s i o n ”b e c o m i n gs e r i o u s ，t h es t r i n gm a t c h i n ga p p l i c a t i o n s r e q u i r eh i g h e rp e r f o r m a n c es t r i n gm a t c h i n ga l g o r i t h m t h e r e f o r e ，i th a sb e c o m ea n e wc h a l l e n g et od e s i g nt h es t r i n gm a t c h i n ga l g o r i t h m s ( t h ee x a x ts i n g l ep a t t e r n s t r i n gm a t c h i n ga l g o r i t h m se s p e c i a l l y ) w i t hh i g h e rp e r f o r m a n c e t h i sd i s s e r t a t i o nm a i n l yd e s c r i b et h er e s e a r c ho fh i g hp e r f o r m a n c ee x a c ts i n g l e p a t t e ms t r i n gm a t c h i n ga l g o r i t h m i th a sb e e nc o n s i d e r e dt h a tt h e r ea r et w o a l g o r i t h m sa r et h ef a s t e s ta b o v ee n g l i s h ，t u n e db ma n ds b n d m 2 ，t h r o u g h a n a l y z i n gt h ee x i s t i n ge x a c ts i n g l ep a t t e r ns t r i n gm a t c h i n ga l g o r i t h m s i nt h i s p a p e r , t h e s et w of a s t e s ta l g o r i t h m sw e r ei m p r o v e dr e s p e c t i v e l y , a n dd q m a l g o r i t h ma n ds 2 b n d ma l g o r i t h mw e r ep u tf o r w a r d o nt h ew h o l e ，t h em a i nr e s u l t so ft h i sd i s s e r t a t i o na r ea sf o l l o w i n g ： 1 t h ee x i s t i n gh i g hp e r f o r m a n c ee x a c ts i n g l ep a t t e ms t r i n gm a t c h i n ga l g o r i t h m s w e r ea n a l y z e d t h er e s e a r c hd i r e c t i o nf o rs t r i n gm a t c h i n gw a sg i v e n t h e r e s u l ts h o w e dt h a tt h e r ea r et w oa l g o r i t h m sa r et h ef a s t e s ta b o v ee n g l i s h ， t u n e db ma n ds b n d m 2 2 as u f f i xm a t c h i n gt y p ee x a c ts i n g lep a t t e r ns t r i n gm a t c h i n ga l g o r i t h m d q m b a s e do nt u n e db m ，w a sp r e s e n t e d i tu s et w oj u d g e m e n tc h a r a c t e r sj u m p a l t e r n a t e l yb yb m b a d c h a rr o l et or e d u c et h ei n c r e a s eo ft h ep r o b a b i l i t yo ft h e j u d g e m e n t - c h a r a c t e rm a t c h i n g i th a sa ni m p r o v e dc r o s s - b r o a d e rp r o t e c t i o n m e t h o dt or e d u c et h ec o s to fc h e c k i n gc r o s s b r o a d e r a n di tu s eb i to p e r a t i o n a n da c t i o nc o m b i n a t i o nm e t h o dt o i m p r o v e t h ea c t i o na f t e rt h e 哈尔滨t 程大学硕十学位论文 j u d g e m e n t c h a r a c t e rm a t c h i n gs o a st or e d u c et h eb r a n c ho p e r a t i o n s t h e e x p e r i m e n tr e s u l t ss h o wt h a td q m i sf a s t e rt h a nt u n e db m 3 as u b s t r i n gm a t c h i n gt y p eh i g hp e r f o r m a n c ee x a c ts i n g l ep a t t e r ns t i r n g m a t c h i n ga l g o r i t h m s 2 b n d m ，b a s e do ns b n d m 2 ，w a sp r e s e n t e d i tr e a c h t h es i m p l e s tf o r mo ft h ec o r el o o po fb n d m ( 5i n s t r u c t i o n sp e rc h a r a c t e rr e a d ) b ya m e n d i n gt h ed e f i n i t i o no ft h eb i t m a s k a n d i ta d dt h ec r o s s b o r d e r p r o t e c t i o nm e t h o dw h i c hi su s e di nd q m t oo u ra l g o r i t h m t h ee x p e r i m e n t a l r e s u l t si n d i c a t e dt h a ts 2 b n d mc o u l db ec o n s i d e r e da st h ef a s t e s ta l g o r i t h m a b o v ee n g l i s ht e x tf o rt h ep a t t e r ns h o r t e rt h a nt h el e n g t ho fm a c h i n ew o r da n d a b o v ed n a s e q u e n c ef o rt h ep a t t e r ns h o r t e rt h a n8 k e y w o r d s ：s t r i n gm a t c h i n g ；d e s i g no fa l g o r i t h m ；e x a c ts i n g l ep a t t e r n ；t e x t s e a r c h 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下， 由作者本人独立完成的。有关观点、方法、数据和文献的引用 已在文中指出，并与参考文献相对应。除文中已注明引用的内 容外，本论文不包含任何其他个人或集体已经公开发表的作品 成果。对本文的研究做出重要贡献的个人和集体，均己在文中 以明确方式标明。本人完全意识到本声明的法律结果由本人承 担。 作者( 签字) ：俐博 日期：细乡，年3 月侈日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 1 g f - 在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、 作者( 签字) ：丐客房博 日期： 力矿夕年了ni t 日 导师( 签字) 哈尔滨t 稗大学硕十学伊论文 第1 章引言 1 1 字符串匹配技术的应用领域与面临的挑战 串匹配问题指按照一定的匹配条件在某一符号序列( 称为文本t ) 中查找 另一个( 或一些) 符号序列( 称为模式p ) 的所有出现位置的搜索问题】。 字符串匹配问题是计算机科学的基础问题之一，也是被研究的最为广泛和深 入的问题之一，现已经发展成- - f - j 相对独立的学科字符串学( s t r i n g o l o g y ) 【2 【3 】【4 1 。随着计算机技术和网络技术的发展，新的应用对匹配实时性的要求不 断提高，同时需要进行匹配的文本量正成几何级数增长。但字符串匹配技术 的发展却明显滞后于信息总量和计算机硬件的发展，现已成为制约串匹配类 应用的瓶颈。字符串匹配技术的应用领域广泛的难以想象，几乎所有涉及文 本或符号处理的应用领域都或多或少的存在着搜索问题，如文本处理【5 j 、拼 写检查【6 、语言翻译【7 】【8 1 、数据压缩9 3 等领域中均大量使用字符串匹配技术。 尤其在网络安全，计算生物学与信息检索与过滤等领域中，应用程序对串匹 配算法性能的要求尤为突出，而当下这些领域的高速发展也刺激了学术界对 字符串匹配技术研究。 1 1 1 入侵检测技术与病毒检测技术 入侵检测技术( i d s ，i n t r u s i o nd e t e c t i o ns y s t e m s ) 与病毒检测技术( v d s ， v i r u sd e t e c t i o ns y s t e m s ) 是网络安全的重要组成部分。其目的为在入侵攻击 和病毒攻击发生时，此类安全软件能及时发现与确认，并实现在入侵攻击和 病毒攻击在对计算机系统没有完成实质性破坏之前快速响应，通过删除或隔 离攻击以保障网络安全。入侵检测与病毒检测的基础为“数据监听”，是将网 络流量、磁盘i o 等内容在给定攻击库或病毒库中进行检索。攻击库与病毒 库是根据各种攻击行为的特点而建立的一种特殊的攻击特征模式集，并包含 对应处理动作。这实际是一个典型的精确多模式串匹配问题，利用串匹配算 法通过对待搜索文本的一次扫描获得模式集中模式在文本中的所有出现，若 1 哈尔滨t 程大学硕十学伊论文 发现攻击库或病毒库中某个模式出现则判定攻击成立，并根据匹配结果确定 处理动作。其中网络流量和处理器中处理的内容为待搜索文本，而病毒库和 攻击库为模式集。 入侵检测和病毒检测的关键是检测速度，如果检测晚于攻击对系统的破 坏，则无法保证系统的安全。虽然入侵检测技术不断发展，现在的研究很多 集中于机器学习和行为判断等方向上，但是在面向高带宽网络的入侵检测技 术中，因为基于机器学习和行为判断等机制的入侵检测软件由于操作复杂度 较高，无法处理高速数据流，目前大多数入侵检测软件还是使用串匹配技术 进行检测，而且目前入侵检测性能主要与串匹配算法相关1 1 。典型的开源入 侵检测软件s n o r t 11 1 就采用了传统的精确单模式串匹配算法一b o y e r - m o o r e 陪】 算法进行匹配。大量的研究将精确多模式串匹配算法应用与s n o r t 中，极大的 提高了s n o r t 进行入侵检测的速度。而随着网络带宽不断增高，干兆以太网络 现在己进入普及阶段，目前主干网络上带宽更高。在如此高带宽的网络下进 行入侵检测和病毒检测对字符串匹配算法性能提出了严峻的挑战，因为目前 在通用计算机上，进行精确多模式匹配的典型算法还无法达到1 0 g b s 级别。 如果不能提出更高速的精确串匹配算法，在高速网络上，网络安全将成为一 种空谈。 1 1 2 计算生物学与分子生物学 计算生物学( c o m p u t a t i o n a lb i o l o g y ) 与生物信息学( b i o i n f o r m a t i c s ) 1 2 j 是计算机技术、生物技术、计算数学、统计学相结合的两个新兴的交叉学科。 主要研究分子生物学应用中复杂的计算问题，主要包括序列比对，序列组合， 序列分析，基因认定，种族树结构，蛋白质三维结构推测，功能基因学，功 能蛋白质学等等方向。随着分子生物学快速发展，分子生物学已成为一种拥 有极高信息量、极高计算量的学科，急需计算机辅助；而计算机理论科学也 需要新的发展方向，因此计算生物学和生物信息学的研究非常热门。这两个 学科在人类疾病与功能基因的发现与识别、基因与蛋白质的表达与功能研究 2 哈尔滨t 程大学硕十学伊论文 方面都发挥着关键的作用，在基于基因与蛋白质功能的药物设计方面也有着 巨大的潜力，同时这两个学科在亲子鉴定、罪犯识别等各方面都有重要的应 用。 计算生物学和生物信息学领域中，在海量的基因组序列数据( 如每个人 类基因的碱基数目高达3 0 亿对) 和蛋白质序列数据中进行比对、分析、组合 的基础是字符串匹配技术。计算生物学中串匹配的特点是数据量巨大，字符 集小( d n a 中字符集大小为4 ， a ，t ，g c ) ，存在大量的噪声信号等问题。原 有字符串匹配算法很难适应这样的文本，这为字符串匹配算法研究提出了新 的挑战与机遇。在计算生物学和生物信息学领域中急待发展的是近似搜索和 多模式近似搜索。而目前高速的近似搜索和多模式近似搜索算法仍属空白。 1 1 3 信息检索与过滤 目前，信息资源的高速膨胀_ 1 1 信息爆炸”已成为一个全球性的共同现象。 加利福尼亚大学伯克利分校研究人员发现，从1 9 9 9 年至2 0 0 2 年全球新生产 出的信，亩、量就翻了一番。该校信息管理及系统学院莱曼教授领导的小组在研 究中对多种信息源进行了采样分析，结果发现，2 0 0 2 年中，全球由纸张、胶 片以及磁、光存储介质所记录的信息生产总量达到5 万亿兆字节，足以填满 5 0 万座美国国会图书馆，世界范围内信息生产量以平均每年3 0 左右的速度 递增。与记录在物理介质上的信息生产量相比，世界范围内通过电话、广播、 电视和因特网这四大电子渠道流通的信息量更为惊人。2 0 0 2 年，有多达1 8 万亿兆字节的信息通过这些渠道在全球流通。而据i d c ( 互联网数据中心， i n t e m e td a t ac e n t e r ) 于2 0 0 6 年估计，信息总量的增长速度在不断上升，未来 五年内信息总量的增长速率应调整至每年5 7 。同时i d c 也提出，在2 0 1 0 年，全球所有数据总量将与全球所有沙粒的总数一样多。 伴随“信息爆炸”现象，信息的良莠不齐现象也逐渐凸显。随着互联网的 发展，任何一个能够接入互联网的用户都可能有意或无意的发布涉及国家、 企业或个人秘密的信息，或者反动、色情信息，造成了惨重的经济损失并严 哈尔滨t 程大学硕士学位论文 重影响社会的安定。对网络信息的过滤已经刻不容缓。同时用户也希望在海 量信息中按照自己的喜好对信息进行个性化检索和过滤，需求远超过现有搜 索引擎所能提供的服务。 在如此海量的数据中进行检索和过滤的需求非常强烈。而检索与过滤均 属于字符串匹配技术领域。在信息过滤时，特别是在主干网络上进行检索与 过滤，对字符串匹配的实时性要求非常高，串匹配好坏直接影响了检索与过 滤系统的性能。由于现有字符串匹配算法在通用处理器上还无法达到处理 1 0 g b s 级别流量的能力，现在只能通过专门设计的硬件通过大规模并行来实 现高速信息过滤，无法通用化并且造价高昂。如何在通用处理器上实现高速 信息检索与过滤己成为目前研究的热点问题。 在字符串匹配的其他应用领域中，同样存在类似的匹配速度无法满足应 用的需求的问题。字符串匹配成为众多应用的核心组件，已经成了影响应用 系统性能的关键。字符串匹配算法的发展速度远远落后于计算机硬件的发展， 急待更高速的字符串匹配算法的出现。 1 2 精确单模式串匹配技术的研究目的与意义 按照匹配需要，字符串匹配技术主要包含精确单模式串匹配、精确多模 式串匹配、正则表达式匹配、近似匹配等几个主要研究方向。如上节所述， 字符串匹配技术作为众多领域的技术核心，其研究与发展对社会发展的意义 非常重大。精确单模式字符串匹配算法为字符串匹配领域的基础，本身就有 大量的应用，同时字符串匹配技术领域中算法均由精确单模式串匹配算法扩 展而来，而且很多时候，这种扩展都是很容易和自然的，比如精确多模式匹 配中经典算法：a h o c o r a s i c k 算法【1 3 】、w u m a n b e r 算法【1 4 】、s b o m 算法【1 5 】 分别是精确单模式中经典算法k m p 算法【1 6 】，h o r s p o o l 算法旧( 或b m 算法 p s i ) 、和b o m 算法【1 5 在多模式中的自然扩展。相对而言，字符串匹配领域中， 精确单模式匹配算法研究的理论与实际意义更为明显。 在实际匹配应用中的匹配速度为评价精确单模式串匹配算法优劣的唯一 4 哈尔滨t 程大学硕十学位论文 评价指标。本文的目的为提出在实际的匹配应用中性能更高的精确单模式匹 配算法。 1 3 本文的研究内容与安排 本文主要对高性能精确单模式匹配算法进行研究，并致力于提出实际匹 配中匹配速度更高的精确单模式串匹配算法。基于现有精确单模式中两个性 能较高的算法，分别提出了相应的改进机制，己获得目前性能最高的精确单 模式算法。 本文后续内容安排如下： 第二章对现有精确单模式算法研究现状进行介绍。对精确单模式串匹配 的基本概念进行定义，指出目前精确串匹配算法研究历史与方向，并对精确 单模式匹配的方法进行分类，并对每种匹配机制的典型算法进行介绍。并给 出现有性能较高的精确单模式算法的性能评价与分析。 第三章提出一种基于后缀匹配机制的高性能精确单模式串匹配算法 d q m 算法。d q m 算法以t u n e db m 算法为基础算法，在t u n e db m 算法 基础上引入两个判定字交替进行跳跃的方法降低了随跳跃进行判定字匹配概 率动态增长对算法性能的影响；引入了改进的越界保护机制降低了越界检查 的开销；并通过位操作和合并操作的方法改进算法在判定字匹配后的动作， 使分支与跳转的次数降至最低。本章对d q m 算法进行详细介绍，并给出实 验数据。 第四章提出了一种基于位并行子串匹配机制的高性能精确单模式串匹配 算法一s 2 b n d m 系列算法。s 2 b n d m 算法以s b n d m 2 算法为基础算法， 通过修改b n d m 类算法的位掩码定义，成功将b n d m 类算法的核心循环化 简至五条指令的最简形式。同时，本文在s b n d m 2 算法中引入下标越界保护， 将下标越界检查的开销也降至最低。本章对s 2 b n d m 算法进行了详细介绍， 并给出实验数据。 哈尔滨t 稗大学硕+ 学位论文 第2 章精确单模式串匹配算法研究现状 2 1 字符串匹配的定义 字符串匹配领域中各主要研究分枝的定义如下【1 ： 1 ) 精确单模式匹配( e x a c ts i n g l ep a a e ms t r i n gm a t c h i n g ) 已知字符集， l i = c r ，为其正闭包，文本串t = t o t l 厶一1 ，模式串p = p o p l p 埘一l ，p ，丁。 精确单模式匹配指对给定p 与t ，求解集合： o = ip k = t i + k ，其中0 k m 的问题。 2 ) 精确多模式匹配( e x a c tm u l t i - p a a e r ns t r i n gm a t c h i n g ) - 已知字符集， | - 盯，为其正闭包，文本串t = t o t l 川，模式串集合p = 鼻，最p ， 叩= 仇局p 。h ，其中m i 表示p 的长度。精确多模式匹配指对给定p ， t 求解集合： o = iw ，0 ，s ，g k = 丁 f + 尼 ，其中0 k m i 的问题。 3 ) 扩展字符串匹配( e x t e n d e ds t r i n gm a t c h i n g ) ：一种模式中包含扩展字 符c o 的串匹配问题，其中彩主要包含三种形式：a c o 为一个字符的集合， 匹配时，当文本对应字符为集合中的任何字符，则该字符匹配成功；b 0 9 为 限长通配字，这些位置可以与文本中长度指定的任意字符串匹配；c 0 9 为允 许的可选字符或可重复字符，0 9 对应字符在文本中可以出现0 次，1 次或任 意多次。 4 ) 正则表达式匹配( r e g u l a re x p r e s s i o nm a t c h i n g ) ：待匹配模式为正则 表达式的匹配问题，可以是单模式匹配也可以是多模式匹配。 5 ) 近似匹配( a p p r o x i m a t es t r i n gm a t c h i n g ) 已知字符集，l l = 仃， 为其正闭包，文本串t = t o t 厶一l ，模式串p = p o p l p 州一l ，p ，丁。为自 然数集，k n 为近似匹配中允许的最大误差，定义距离函数d ：x e + 一n ， 则近似单模式匹配问题值求解集合对于给定t 、p 、k 、d ( ) ，求解集合 o = f | d ( p ，巧m 一，) 尼 的问题。近似匹配也可以向多模式进行扩展。 6 哈尔滨t 稗大学硕十学傅论文 6 ) 其他方向：如直接在压缩文件上进行串匹配的方法，多维串匹配( 常 见于媒体匹配) 等问题。 以上为字符串匹配领域的各个研究分支，由于本文主要对精确单模式串 匹配算法进行研究，其他领域的目前研究现状不再介绍。 2 2 精确单模式串匹配技术的研究历史与方向 精确单模式字符串匹配作为字符串匹配领域的基础，被研究的最为广泛 和深入。目前已经有上几百种不同的精确单模式字符串匹配算法出现。如在 2 0 0 4 年出版的由c c h a r r a s 和t l e c r a q 编写的h a n d b o o ko fe x a c ts t r i n g m a t c h i n g a l g o r i t h m s 2 j 中就介绍了经典的3 5 种精确单模式串匹配算法，同时 每年有大量的本领域的论文不断出现，在万方数据库和维普数据库中以串匹 配和模式匹配为关键字，相关文章有近千篇。 较早的字符串匹配算法研究出现于2 0 世纪7 0 年代。1 9 7 0 年，s a c o o k 从理论上证明了串匹配问题可以在o ( m + n ) ( m 为模式p 的长度，n 为文本t 的长度，该标号在本文中始终沿用) 时间内解决。同年，m o r r i s 和p r a t t 仿 照c o o k 的证明构造了第一个匹配时拥有线性最差时间复杂度的m p 算法 【2 2 1 。随后，k n u t h 对这个算法进行了一些改进，在1 9 7 6 年提出了k m p ( k n u t h m o r r i s p r a t t ) 算法【1 6 j ，它的时间复杂度为0 ( m + n ) 。在1 9 7 7 年，b o y e r 和m o o r e 提出了首个拥有亚线性时间复杂度的算法( b m 算法) 。b m 算法 在实际的模式匹配中，跳过了很多无用的字符，这种跳跃式的比较方式，使 b m 算法获得了极高的效率，特别是在大字符集上进行字符串的模式匹配时。 在实际的应用中，b m 算法比k m p 算法更有效率。此后，又有一些更有效 率的算法被提出，大多都是在k m p 算法或b m 算法的基础上做了一些改进。 在1 9 7 9 年由a cy a o 提出了串匹配算法存在时间复杂度的下界，其中最优、 最差、平均时间复杂度的下界分别为o ( n m ) 、o ( n ) 、o ( ( n l o g 圜n ) m ) 【2 3 1 。1 9 9 4 年出现了b d m 算法【4 1 ，这个是首个拥有最优的平均时间复杂度的算法。现 已有大量算法达到了各种时间复杂度下界，如t u r b o b d m 2 4 1 。t u r b o r f 2 4 】， 哈尔滨丁稗大学硕十学伊论文 l n d m l 2 5 j ，d f d m i 2 6 】等算法均达到了此最优时间复杂度。 在字符串匹配领域，时间复杂度优秀的算法并不能代表性能优秀。其中 典型的是具有最优的最差时间复杂度的k m p 算法，在本文所采用的实验平 台上，其匹配性能甚至比基本的暴力匹配算法( 时间复杂度为o ( m * n ) ) 性能 更低，其原因是k m p 算法在处理每个读入字符时的操作过于复杂，影响了 匹配性能。同时，目前在最好，平均，最差时间复杂度都达到最优的各算法， 其实际性能也不是最好的。在字符串匹配领域，一个公认的假设为“算法越简 单，其性能越高”【1 】。如经典算法b m 算法，该算法存在众多简化算法，而这 些简化算法的性能均比b m 算法更高。为此，研究精确单模式匹配算法应该 在满足或近似满足最优的平均时间复杂度的条件下，尽可能简化算法。 目前的研究逐渐从简单的提高算法时间复杂度向具有更高的实际匹配性 能方向回归，高效的串匹配算法不断出现。在字符串匹配领域的众多算法中， 各个算法的性能受到字符集大d , s f d 模式长度的影响，目前己公布的算法中， 尚未有能在各种情况下性能均为最高的算法出现。 算法的时间复杂度是影响算法性能的重要因素，一般串匹配算法待处理 的文本很长，而模式的长度相对与文本长度可以忽略不计。待处理文本一般 服从一定的统计特征，这样可以使算法达到最优、最差时间复杂度的文本出 现概率一般较小。因此，在设计高性能串匹配算法时，一般只需考虑平均时 间复杂度。在平均时间复杂度一致的情况下，串匹配算法性能主要受以下几 个方面的影响，因此在设计高性能算法时，必须考虑在这些方面进行优化。 1 、核心循环或高频执行语句中的操作总数 算法中各条语句的执行频率有很大的差别。若定义串匹配算法中用于读 入字符并比较的循环为算法的核心循环，很显然核心循环要占用算法的绝大 多数的执行时间。为提高算法的整体性能，应将可以在非核心循环或低频执 行的语句中完成的工作尽可能的移出核心循环。使核心循环中只保留最基本 的代码，这将使执行的总指令数目降至最低。在移动指令的同时，核心循环 应该进行精心的优化，用尽可能少的时钟总数来完成核心循环的所有工作。 r 哈尔滨t 程大学硕七学位论文 这也就是“算法越简单，实际性能越好”的原因，也是设计串匹配算法中最基 本的指导方向。 2 、分支语句 在流水处理器中，分支语句是一种开销巨大的指令。其开销与分支预测 失败率和分支语句的密集程度称正比。分支预测失败会导致流水线内指令流 执行顺序错误，将使整条流水线的工作全部作废。流水线的作废与重建需要 大量的时钟。为降低独立的分支预测失败的开销，现有处理器大多拥有多条 流水线同时执行分支后的不同指令流，预测失败的流水线在重建时，备用流 水线中执行的时正确的指令流，因此，降低了分支预测失败的开销。但密集 的分支语句将可能产生密集的分支预测失败。这导致备用流水线中也无足够 的时间作废与重建，因此可能产生非常大的延时。因此在算法设计时，要避 免密集的分支语句的出现，特别是核心循环的循环体中，应尽可能的避免出 现分支语句。如果必须出现分支时，应让可能性较大的指令序列紧邻分支语 句，使代码以较大的概率以顺序的方式执行。在避免出现分支语句中，最常 见的技术是循环展开，即在读入若干字符后，才存在一次比较操作。目前的 高性能精确单模式串匹配算法中，几乎全部使用了循环展开技术。 3 、算法的空间利用情况 鉴于c a c h e 的运行速度远高于内存的速度，高性能串匹配算法必须有效 的利用c a c h e 。利用c a c h e 的前提是算法预处理后得到的内容的空间占用必 须小于c a c h e 的容量。由于这部分内容在串匹配的过程中被频繁的调用，如 果空间占用大于c a c h e 的容量，将引起c a c h e 的颠簸现象而严重影响性能( 一 次缓存缺页可能造成数百个时钟的延迟) 。由于现有主流处理器的c a c h e 并不 大如i n t e lp e n t i u m4 处理器只有8 k b 的指令c a c h e 和8 k b 的数据c a c h e 。高 性能串匹配算法必须保证预处理信息的空间占用小于l 1 c a c h e 的限制。多数 采用自动机方式实现的匹配算法，其与处理信息的空间占用不小于状态总数 木a s i z e 木s i z e o f ( i n t ) ；在a s c i i 字符集下，8 个状态的自动机的空间占用就已 经大于此限制，因此，大多数自动机算法的实用性能均不理想。在进行串匹 o 哈尔滨t 稃大学硕十学位论文 配算法设计的时候，必须充分考虑时间与空间占用之间的均衡。 4 结合硬件发展技术 由于通用处理器上串匹配性能较低，大量研究设计用专用硬件，通过大 规模并行来加速串匹配的速度。利用专用硬件能设计出匹配性能极高的串匹 配算法，目前已经能超过1 0 g b s 。但专用硬件通用性差，且价格高昂，无法 大范围适用。同时，也有面向较新型处理器支持的新指令，如s s e 系列指令 加速通用处理器上进行串匹配算法的性能。现有处理器新指令不断增加，为 此类研究提供了大量的研究空间，如最新的s s e 4 2 系列指令中有专门为进行 串匹配设计的s t t n i 系列指令，而该系列指令的使用，可能对字符串匹配领 域算法研究带来革命性的变革。此外也有利用g p u 进行串匹配的研究。 5 继续深度挖掘现有算法 目前串匹配理论研究领域已经取得足够优秀的成果，在该领域中获得重 大理论突破的难度很大。研究者应该更主要面向现有算法，对现有算法进行 深度挖掘，以获取更大的跳跃能力和更简单的算法实现之间的平衡，以期获 得更高性能的算法。 2 3 精确单模式串匹配算法分类 目前的串匹配算法均使用滑动窗口概念完成匹配。滑动窗口与模式等长 并沿着文本单向滑动，窗口中字符可以与模式建立顺序的对应关系，这样将 精确单模式匹配问题转换为判断模式与窗口内文字是否匹配的问题。称窗口 中每对对应字符相等为该字符匹配，反之，则称该字符失配。若已读入字符 串中每个字符均匹配，则称该串匹配。若窗口中任意字符失配，则称模式失 配，若窗口中所有字符均匹配，则此时窗口内内容为模式的一次出现，或称 此时发生模式匹配，应报告此时窗口所在位置。在窗口中按照一定的搜索机 制完成搜索后，移动窗口位置，当窗口移动至文本尾部时匹配完成。 1 0 哈尔滨jr = 程大学硕十学位论文 i i 一；i t p y l y jj 图2 1 滑动面1 3 不葸图 若设u ，y ，w ( u ，v w 可以为空串) ，则称u 为串u v 的前缀，v 为串u v 的后缀，u ，v w 均为串u w v 的子串。为描述方便，若对串u 和串 v ，若i u l = l v l ，且u i = v i 对v i iui 均成立，则称串u 和v 能够完全匹配， 记为u = v 。若发生模式匹配，此时窗口内的任意子串和p 中对应位置的子串 都可以完全匹配。 按照算法在窗口中的搜索策略，现有精确单模式串匹配算法主要包含三 个基本类型：按前缀匹配，按后缀匹配，按子串匹配。 2 4 按前缀匹配机制及其经典算法 按前缀匹配指在搜索窗口内从前向后( 沿着文本正向) 逐个读入文本中 的字符，每读入一个字符后，确定窗口中已读入字符串和模式的最长共同前 缀，如果发现共同前缀的长度与窗口等长，则说明发现了一次模式的匹配。 按前缀匹配中的典型算法为朴素的串匹配算法b f 算法【2 1 】，k m p 算法【16 1 ， s h i f t a n d s h i f t o r 算法【2 7 】以及k a r p r a b i n 算法 2 8 】。 c 读入方向i 旦； t e x t i - - - - - + t l i ll i p a t t e r n s h i f t i n gw i n d o w 图2 2 按前缀匹配示意图 哈尔滨- t 稗大学硕士学伊论文 2 4 1b f 算法 b f 算法 2 l 】是最基础的字符串匹配算法。在图2 2 中，如果发现待读入字 符口和模式中对应字符0 9 不相同，则此时的窗口内不会发生模式匹配，窗口 向后移动个字符后继续在窗口中从前向后读入字符并比较。重复以上操作 直到文本末尾。b f 算法的最差时间复杂度为o ( m 木n ) ，存在大量的重复字符 读入，性能较低。 2 4 2k m p 算法 k m p 算法 】6 维护一个既是窗1 3 中已读入字符串u 的后缀也是模式串p 的前缀的最长字符串，并且每读入一个字符就更新此串，当发现窗口中某字 符匹配失败后，k i v i p 实际将产生滑动窗口一次移动多个字符的现象以避免字 符的重复读入，( 这称一次跳跃) 。虽然以前的研究没有明确提出k m p 算法 的跳跃概念，但相对于其他描述方法，跳跃的概念有助于更好的理解k m p 算法本质。 为方便描述，对串w ，称由w o 到w j 的子串为w o j ，若 j s ，s t w o s 一1 = 形 1w 卜s i 形i - 1 ，( s m ) ，则称串w 存在边界 w o m a x ( s ) 一1 ( 或称存在边界缈 1 l - m a x ( s ) i 形i - 1 ) 。记p 中长为l u i 的| i 缀为异，根据前缀匹配定义，在未发现字符失配前，u 为窗口的已匹配 前缀，显然u = 露，。 定理2 1 在k m p 算法中，若在前缀匹配过程中发现一次字符失配，滑动 窗口的跳跃距离不小于1 。若u 的边界的长度为s ( 0 s m ) ，则滑动窗口可 以跳跃i u i s 。跳跃完成后，u 在窗口中剩余的后缀为p 的前缀。 证明：设只，的边界长度为0 ，则对u 的任意一个后缀s u f ，在发现字符失 配后，窗口至少应该移动一个字符。记窗1 3 移动前，s u f 对应模式中的只串 ( 显然有s u f = g ) ，移动后，s u f 对应模式中的p s u f 串。若窗口移动后窗1 3 内能发生模式匹配，则移动后，也必有s u f = p 。，。为满足此条件，p 吖应 为兄中岛自右向左的某次出现。设只在昂中自后向前的首次出现其首字 12 哈尔滨t 程大学硕十学何论文 符位于p 1 0 c 位置，若跳跃后窗口内能发生模式匹配，则必有串p o l o c 一1 与s u f 前的l o c 字符组成的串也匹配。而在跳跃前，s u f 和该串前l o c 字符组 成的串为u 的后缀，又u = 丘，这样，卑，中将存在一个长度为l o c + l s u t 7 的相 同前后缀。而这与我们的假设，曰，中边界长度为o 的假设相矛盾。因此，窗 口不可能在此时发生匹配，窗口将继续跳跃至在兄中自后向前的下一次 出现处。重复以上的证明，可知，若文本中s u f 串对齐模式中只吖的任何一次 出现时，若此时可以发生模式匹配，则都能推出只，中边界长度不为0 ，与题 设矛盾。故当只，中边界长度为。时，窗口应跳跃至s u f 串后。由于s u f 的任 意性，令i s u f l = 0 ，则此时窗口的跳跃距离为i u l 。窗口中剩余部分为空串，是p 的前缀。 设只，中边界长度s 大于o 。令s u f 为u 中长度为s 的后缀，并假设s u f 在 尼中有多次出现，记s u f 在尼中的某次非兄后缀的出现为p 吖，p ，首字 符为只小o c 。假设窗口由w i n 0 位置跳跃至w i n l 位置，如果此时窗口内可以 发生模式匹配，则s u f 比对齐某个p 耐，且跳跃后窗口的前l o c + l s u f l 个字符必 和文本中对应跳跃前窗口的后l o c + l s u e 个字符