（计算机应用技术专业论文）基于有序二叉树的多模式匹配算法的研究.pdf

基于有序二叉树的多模式匹配算法的研究 摘要 模式匹配是计算机研究领域中一个重要的研究方向。随着互联网的普及和 发展，模式匹配技术广泛应用于网络安全、搜索引擎以及生物计算等领域中。 本文总结了当前模式匹配算法的研究现状及其应用，介绍了经典的单模式 匹配算法，包括k m p 算法、b m 算法、b m h 算法以及q s 算法，深入研究了a c 算 法、w m 算法以及s m a 算法等多模式匹配算法，分析了各算法的时空性能，并通 过实验对这些算法进行时间性能测试，详细分析了实验结果，讨论了各个算法 的优缺点。 针对s 1 4 a 算法的不足，对s b i a 算法进行了改进，提出了一种基于有序二又 树的快速多模式匹配算法一一q s m a 算法。该算法不需要比较待匹配文本中的每 个字符，能充分利用已匹配的字符信息，尽可能多地跳过待匹配文本中的字符， 减少字符比较操作，实现快速多模式匹配。从理论上分析比较了q s m a 算法与 s m a 算法的时间复杂度，分析结果显示q s m a 算法提高了匹配速度。 在v c + + 6 0 环境下实现了q s m a 算法，并测试了q s m a 算法与s m a 算法的时 间性能。实验结果验证了q s m a 算法的正确性与有效性，与s m a 算法比较，q s m a 算法在时间性能上有所提高。 最后，对本文进行总结和展望。 关键词：网络安全：模式匹配；有序二叉树；模式匹配算法 t h er e s e a r c ho fm u l t i - - p a t t e r nm a t c h i n ga l g o r i t h m b a s e do ns e q u e n t i a lb i n a r yt r e e a b s t r a c t t h ep a r e mm a t c h i n gi so n eo ft h ei m p o r t a n tr e s e a r c hd i r e c t i o n si nc o m p u t e rr e s e a r c h f i e l d w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e m e t ，i th a sb e e nw i d e l ya p p l y i n gt om a n ya r e a s ， s u c ha sn e t w o r ks e c u r i t y ，s e a r c he n g i n e ，c o m p u t a t i o n a lb i o l o g ya n ds oo n t h ed i s s e r t a t i o ns u m su pt h er e s e a r c hs t a t u sa n da p p l i c a t i o n so nt h ep r e s e n tp a t t e r n m a t c h i n ga l g o r i t h m s ，a n di n t r o d u c e st h ec l a s s i c a ls i n g l ep a r e mm a t c h i n ga l g o r i t h m s t h e s e a l g o r i t h m sa r ek m pa l g o r i t h m ，b ma l g o r i t h m ，b m ha l g o r i t h ma n dq sa l g o r i t h m m u l t i p l e p a r e mm a t c h i n ga l g o r i t h m sa n dt h e i rc a p a b i l i t i e sa r ed e e p l yr e s e a r c h e da n da n a l y z e d t h e s ea l g o r i t h m sa r ea ca l g o r i t h m ，w ma l g o r i t h ma n ds m aa l g o r i t h m t h et i m e p e r f o r m a n c ei st e s t e db ye x p e r i m e n t s ，a n dt h ee x p e r i m e n t a lr e s u l t sa r ed e t m l e da n a l y z e d t h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h o s ea l g o r i t h m sa r ed i s c u s s e d f o rt h ew e a k n e s so fs m aa l g o r i t h m ，af a s ta l g o r i t h m - q s m af o rp e r f o r m i n gm u l t i - p a t t e r nm a t c h i n gi sp r o p o s e do nt h eb a s i so fs e q u e n t i a lb i n a r yt r e e q s m aa l g o r i t h md o e s n o tn e e dt oi n s p e c te a c hc h a r a c t e ri nt h ep a r e m b ym a k i n gf u l lu s eo ft h er e s u l t so f m a t c h i n gs u c c e s s e sa n df a i l u r e s ，t h ea l g o r i t h mc a no f t e ns k i p a sm a n yc h a r a c t e r sa s p o s s i b l et od e c r e a s ec h a r a c t e rm a t c ho p e r a t i o n s t h et i m ec o m p l e x i t yo f t h o s ea l g o r i t h m si s c o m p a r e do nt h et h e o r y t h er e s u l t so ft h ea n a l y s i ss h o wt h a tq s m aa l g o r i t h mi m p r o v e s t h es p e e d q s m aa l g o r i t h mi si m p l e m e n t e do nt h ee n v i r o n m e n to fv ca n dt e s t e dw i t h s m aa l g o r i t h mo nt i m ep e r f o r m a n c e t h er e s u l t so ft h ee x p e r i m e n tp r o v et h a t q s m aa l g o r i t h mi sc o r r e c ta n de f f i c i e n c y ，a n dh a sb e t t e rc a p a b i l i t yo ns p e e d f i n a l l y ，w ec o n c l u d ea l lt h ew o r ka n d d i s c u s s et h ef u t u r ew o r k k e y w o r d s ：n e t w o r ks e c u r i t y ；p a t t e r nm a t c h i n g ；s e q u e n t i a lb i n a r yt r e e ；p a t t e r nm a t c h i n g a l g o r i t h m i i 插图清单 图3 1转移函数图1 6 图3 2带有失效函数指向的有限自动机1 6 图3 3有序二叉树结构的有限状态自动机2 2 图3 4带有失败指针的有序二叉树2 2 图3 5模式串个数为2 0 0 时，模式串长度对匹配时间的影响2 5 图3 - 6m i n l e n = 6 时模式串个数对算法匹配时间的影响2 6 图4 1有序二叉树结构有限状态自动机2 8 图4 2模式串个数为2 0 0 时，预处理时间随m i n l e n 的变化3 3 图4 3m i n l e n = 3 时，预处理时间随模式串个数的变化3 4 图4 4模式串个数为2 0 0 时，匹配时间随m i n l e n 的变化3 4 图4 5m i n l e n - - 3 时，匹配时间随模式串个数的变化3 5 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。掘我所知，除了文中特别加以标志和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得合肥工业大学 或 其他教育机构的学位或证书而使用过的材料。与我一同：工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谓 意。 学位论文作者签字： 闻蓖 签字隅年月日 学位论文版权使用授权书 本学位论文作者完全了解盒月巴至些太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被 查阅或借阅。本人授权合肥工业大学可以将学位论文的全部或部分论文内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇 编学位论文。 ( 保密的学位论文在解密后适用本授权书) 黧f i 警：月f t 闰燕签字期：年月 、 导师签名： 签字f l 期： 电话： 邮编： 致谢 经过近三年的努力，在硕士论文完成之际，心中充满了对给予过我帮助的 老师、同学和亲友们的感激之情。 本文的工作从研究方向的确定、论文的选题到定稿都是在我的导师侯整风 教授的悉心指导下完成的。在读研究生的三年时间内，侯老师在学习、开发和 研究上对我严格要求、耐心指导，使我的独立科研能力得到了锻炼和提高，我 将终生受益。衷心感谢侯老师在整个学习生活期间给予我孜孜不倦的教诲和无 微不至的关怀。他渊博的知识、严谨的工作作风和务实的治学态度为我树立了 良好的科研榜样，对我的论文的完成给了极大的支持和帮助。侯老师敏锐的思 维和高尚的人格修养深深地感染着我。 感谢读研究生期间，教授过我的所有老师，我从他们那里吸取了丰富的知 识以及分析、解决问题的思路和方法。 感谢审阅本文的专家教授们，他们在百忙之中抽出时间给本文提出宝贵的 意见和建议。 感谢师兄弟以及同学，一起工作、学习期间，他们经常给我有益的帮助， 让我受益匪浅。 最后，感谢我的家人，他们无论从物质上还是精神上都给了我极大的关怀 与帮助。 i i i 作者：周燕 2 0 1 0 年0 4 月 第一章绪论 1 1 概述 1 1 1 本论文研究的背景、目的 计算机网络的迅猛发展给当今社会人们带来了诸多便利，成为人们工作、 生活和学习紧密联系的组成部分。人们对计算机网络的依赖使得网络安全问题 日益突出，如何增强计算机网络的安全性成为计算机研究领域的热点之一。 模式匹配是在文本中搜索指定模式的所有出现位置。模式匹配分为单模 式匹配和多模式匹配。随着互联网信息的迅速增长，多模式匹配广泛应用于网 络安全、搜索引擎等领域中，如内容过滤防火墙、入侵检测系统等，成为网络 安全领域的重点研究方向。 1 1 2 国内外研究状况分析 最早的单模式匹配算法是b r u t e - f o r c e 算法【2 1 ，该算法简单，但效率较低。 1 9 7 0 年，s a c o o k 在理论上证明了串匹配问题可以在o ( m + n ) ( m 和n 分别为模式 串和文本的长度) 时间内解决【3 】。随后，j h m o r r is 、v r p r a t t 和d e k n u t h 提出了一种单模式匹配算法，称为k n u t h - m o r r i s - p r a t t 算法【4 1 ( 简称k m p 算法) ， 该算法是第一个在线性时间内解决模式匹配问题的算法。 1 9 7 7 年，r s b o y e r 和j s m o o r e 设计了一种单模式匹配算法，称为 b o y e r m o o r e 算法1 5 】( 简称b m 算法) 。b m 算法通过对组成模式串的字符进行分析， 构造坏字符函数和好后缀函数，采用自右向左扫描正文的方式进行匹配，大大 减少了需要比较的字符数目。该算法思想与k m p 算法思想截然不同，却具有相同 的线性时间复杂度。基于b m 算法，派生出了许多单模式匹配算法，例如： t u n e d b o y e r _ m o o r e 算法【6 l 、b o y e r - m o o r e h o r s p o o l 算法【7 】和q u i c ks e a r c h 算法 【8 】刍苣 寸0 1 9 8 7 年，r m k a r p 和m 0 r a b i n 提出了一种新算法，称为k a r p r a b i n g 法 【9 】( 简称k r 算法) 。该算法开辟了模式串匹配算法设计的新思路与新方法。k r 算 法运用h a s h 方法和素数理论，匹配时只需比较与模式串具有相同h a s h 值的子串， 从而可以加快匹配速度。k r 算法也是线性时间复杂度的单模式匹配算法。 多模式匹配是另一个研究热点。多模式匹配算法最初只是作为一个处理文 献目录检索的算法被提出。随着网络搜索、入侵检测、内容过滤等研究热潮的 兴起，多模式匹配广泛应用于网络安全、信息检索等领域中。 1 9 7 5 年，a v a h o 和m j c o r a s i c k 借鉴k m p 算法的思想，首次提出了一种多 模式匹配算法，称为a h o - c o r a s i e k 算法【1 0 j ( 简称a c 算法) 。该算法基于有限自动 机理论，可以在只对文本进行一次扫描的情况下找出多个模式串。基于a c 算法， 1 9 7 9 年，c o m m e n t z w a l t e r 将b m 算法跳跃的思想应用到多模式匹配中，提出了一 种新的算法，称为c o m m e n t z - w a l t e r 算法【】( 简称c w 算法) 。该算法将a c 算法和 b m 算法思想结合起来，匹配效率较高。1 9 9 3 年，j a n g j o n gf a n 和k e h y ihs u 基于有限自动机，设计出了一种新的算法一一f s 算法【l2 1 ，该算法在平均情况下 比a c 算法性能更好。 1 9 9 4 年，s u nw u 和u d im a n b e r 提出了种多模式匹配算法，称为w u - m a n b e r 算法【1 3 1 。该算法结合了b m 算法的跳跃式查找和哈希数值散列的优点，在实际应 用中，是大规模多模式匹配最快的算法之一。 1 9 9 9 年，s u nk i m 和y a n g g o nk i m 基于数据压缩和位操作的思想提出了一个 新的多模式匹配算法，c e 算法【i 引。该算法在小字符集上比w m 算法有更好的表现。 国内对模式匹配算法的研究起步较晚，主要集中于对经典模式匹配算法的 改进，主要的改进思想有：组合状态自动机，将两个状态组合匹配一个双字节 字符【1 5 】、基于字符出现的频率l 1 6 l 等。 1 2 本论文的研究内容及解决的关键问题 1 2 1 研究内容 ( 1 ) 分析经典的模式匹配算法，比较各个算法的性能。 ( 2 ) 深入研究常用的多模式匹配算法，分析这些算法的实现原理，并通过 设计实验方案测试各个算法的时间性能，对实验结果进行分析研究，在此基础 上，比较各个算法性能。 ( 3 ) 将q s 算法扩展到多模式匹配算法中，对s m a 算法进行改进，提出一 种改进算法一一q s m a 算法。从理论上分析该算法的时间复杂度等性能，在v c + + 6 0 中实现了q s m a 算法，并测试比较q s m a 算法与s m a 算法的时间性能。 1 2 2 解决的关键问题 ( 1 ) 有序二叉树的构造 本课题是基于有序二叉树提出的，在预处理阶段，需要设计有序二叉树的 状态转移函数以及确定各状态节点的失败转向。 ( 2 ) 移动距离函数的构造 结合q s 算法的坏字符函数思想，根据坏字符的下一个字符来决定失配情况 下文本指针的跳跃距离。 ( 3 ) 模式匹配算法的设计 匹配过程中结合有序二叉树的特性对s m a 算法进行改进，扩大跳跃距离， 提高匹配速度。 1 3 论文的组织结构 本论文的组织结构如下： 第一章绪论简要介绍了模式匹配算法的研究目的和意义、研究历史及 2 现状。 第二章模式匹配技术。阐述了模式匹配的概念及其分类，介绍了模式匹 配技术的应用。 第三章模式匹配算法分析。对经典的模式匹配算法给出详细的原理阐述， 并对其时间复杂度进行了分析比较。深入研究了a c 算法、w m 算法和s m a 算法等多模式匹配算法，详细分析了各算法的实现原理，并通过实验比较了各 算法的性能。 第四章基于有序二叉树的多模式匹配算法。针对s m a 算法的不足，提出 了基于有序二叉树的快速多模式匹配算法一一q s m a 算法，详述了该算法的工 作原理，并通过举例来进一步阐述其工作过程，分析了算法的时间复杂度等性 能，通过实验验证了该算法改进的有效性。 第五章总结与展望。对全文工作作了总结，并就未来进一步工作研究的 方向做出了展望。 第二章模式匹配技术 2 1 模式匹配概述 模式匹配是指在文本序列t e x t = t 1 t 2 t n 中检索某个特定模式子 串p a t t e r n = p 1 ，pe 2 ，pe m 的所有出现位置。其中，t e x t 和p a t t e r n 都是 在有限字符集上的字符序列，n 为文本t e x t 长度，m 为模式串长度。模式匹 配的结果有两种：如果t e x t 中存在模式串集合p a t t e r n 中的模式子串，则匹配 成功，并给出该子串在t e x t 中的位置，否则匹配失败。 模式匹配问题的研究已经有很多年的历史，人们提出了多种模式匹配算法。 影响模式匹配算法性能的因素有很多，包括有限字符集的大小、模式串集合的 规模、最短模式串的长度、算法的设计思路以及匹配过程中差异等等，这些因 素对算法性能的影响程度各有不同。 模式匹配技术广泛应用于入侵检测、内容过滤防火墙以及计算生物学的 d n a 序列匹配等领域中。模式匹配技术的发展与其应用密切相关，随着网络技 术与生物计算的迅速发展，近年来新的应用和需求对模式匹配技术提出了新的 挑战。 2 2 模式匹配的分类 2 2 1 按功能分类 模式匹配【lj 按照其功能可分为三类：精确模式匹配、近似模式匹配和正则 表达式匹配。精确模式匹配是在数据序列中找出与一个或一组特定的模式串完 全相同的所有串的出现位置；近似模式匹配是按照算法定义的相似程度度量标 准，在数据序列中找出所有与一个或一组特定的模式串的相似程度在一定范围 内的所有串的出现位置；而正则表达式匹配则是根据正则表达式的描述，在数 据序列中找出能够被正则表达式接收的所有子串的出现位置。 精确模式匹配主要应用在文本检索和网络安全的入侵检测领域中，近似模 式匹配主要应用在计算生物学和信号处理等领域中，正则表达式匹配则主要用 来处理简单的序列匹配无法描述的问题，主要应用在深度分组检测和数据挖掘 等领域中。 ( 1 ) 精确模式匹配 精确模式匹配是使用一个固定长度的窗口来搜索文本，检验窗口内文本是 否匹配，然后尽可能地向右移动窗口，直至扫描完整个文本。精确模式匹配依 照其检索符号序列的方式，又可分为三种：前缀模式、后缀模式和子串模式i l l 。 它们的差别主要体现在如何检验窗口内文本的匹配，以及窗口移动的策略上。 前缀模式主要是通过计算窗口内文本和模式串的最长公共前缀，并据此尽 可能地移动窗口，从而减少不必要的匹配。前缀模式主要有两种实现途径：一 4 种方法是每次都计算出当前的最长匹配前缀，因此对于每一个输入字符都消耗 固定的时间和空间，例如单模式串匹配中的k m p 算法【4 】以及多模式串匹配中的a c 算法【io 】；另一种途径是保存窗口文本和模式串的所有匹配前缀的集合，每次根 据当前输入字符更新这个集合，例如使用位并行机制的s h i f t - a n d 和s h i f t - o r 【1 7 l 算法。 后缀模式主要是通过计算窗口内文本和模式串的最长公共后缀，并据此计 算窗口的安全移动距离。它的特点是在窗口内的匹配过程是从右向左进行的。 主要算法有单模式串的b o y e r - m o o r e t 5 1 算法和多模式串的c o m m e n t z w a l t e r 【1 1j 算 法、w u - m a n b e r j 算法等。 子串模式是计算一个最长的序列，该序列既是窗口内文本的后缀，又是模 式串的某个子串。子串模式在窗口内是从右向左进行匹配的，在移动距离计算 上是通过识别在窗口中的模式串最长前缀来确定最大安全移动距离的。主要算 法有单模式串匹配算法中的b d m ( b a c k w a r dd a w gm a t c h in g ) 【1 8 】算法和b o m ( b a c k w a r do r a c l em a t c h i n g ) 1 9 】算法，以及相应的多模式串匹配算法中的s b d m ( s e tb a c k w a r dd a w gm a t c h i n g ) 算法【2 u j 和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 1 1 。 ( 2 ) 近似模式匹配 近似模式匹配【2 2 , 2 3 , 2 4 是按照某种近似标准在文本中找出与模式串匹配的子 串。近似模式匹配算法允许文本中的子串和模式串之间有一定的误差，它们之 间的误差可以用距离来计算，常用的距离有：编辑距离和汉明距离。近似模式 匹配又可分为允许k 一差别的近似模式匹配和允许k 一误配的近似串匹配。允许k 一 差别的近似模式匹配是在允许对文本或模式进行最多k 个字符的“插入、删除或 替换 操作之后，搜索出模式在文本中的所有出现的终止位置。而允许k 一误配 的近似串匹配是在允许对文本或模式进行最多k 个字符的“替换”操作之后，搜 索出模式在文本中的所有出现的起始位置。前者的求解方式为计算模式串与文 本中子串之间的编辑距离，后者的求解方式则是计算模式串与文本中子串之间 的汉明距离。 近似模式匹配方法包括：动态规划( d y n a m i cp r o g r a m m i n g ) 方法、自动机 ( a u t o m a t o n ) 方法、位并行( b i t - p a r a l l e l i s m ) 方法和过滤( f i l t e r i n g ) 方 法。动态规划方法【25 】是研究近似模式匹配问题的最早解决方法，该方法通过计 算文本中的子串与模式串之间的编辑距离来实现近似模式匹配：基于自动机的 方法【2 6 1 是把近似模式匹配问题用有穷自动机来( n f a ) 来描述；位并行方法【2 7 】 主要利用计算机存储器中的物理字在进行位操作时所固有的并行运算的特性来 提高匹配速度；过滤方法【28 1 是通过快速略过不满足匹配条件的文本段加快匹配 速度的。 ( 3 ) 正则表达式匹配 正则表达式【2 9 j 通常是由普通a s c i i 字符以及特殊字符组成的文字模式。正 则表达式可以用来检查一个串是否含有某个子串、将匹配的子串做替换或者从 某个模式串中取出符合某个条件的子串等。它可以表达比多模式和扩展模式更 复杂的搜索模式，具有较强的表达能力。 正则表达式匹配是用正则表达式作为一个模板，将模式串与文本字符进行 匹配。正则表达式匹配算法主要包括两种解决方案：f p g a ( 现场可编程门阵列) 逻辑【3o j 和面向存储的体系架构。f p g a 逻辑具有并行性和可重构性，但其缺乏可 伸缩性和规则更新的实时性。面向存储的体系架构可以克服以上不足，对于每 个输入的字符只要进行一次状态转换，处理速度快。 正则表达式匹配的实现分别基于n f a 和d f a 。由于d f a 占用大量的内存空 间，算法的研究都集中在如何压缩d f a 空间上。目前，主要的压缩方式有：转 换压缩、状态压缩和字母表压缩。转换压缩是指对自动机的转移函数的边进行 压缩，通过消除边与边之间的冗余来减少存储空间，相关算法有d 2 f a 算法【3 、 c d 2 f a 算法等【3 2 1 ；状态压缩指对自动机的有穷状态集进行压缩，通过引入辅助 变量、模式分组、自动机之间结合等方法来减少存储空间，相关算法主要有 s t a t e m e r g i n g 算法【3 3 j 、h i s t o r y b a s e df a 算法等【3 4 】；字母表压缩则是对输入 的字符表进行压缩，主要算法有i m p r o v e d d 2 f a 算法等【3 引。 2 2 2 按一次能够匹配的模式数量分类 模式匹配按照一次能够匹配的模式数量可分为单模式匹配和多模式匹配。 单模式匹配每次只能在文本t e x t 中查找出一个特定的子串。多模式匹配在文本 t e x t 中一次可以查找多个模式串的所有出现位置。 ( 1 ) 单模式匹配 单模式匹配是基于有限字符集中的模式串和文本，搜索文本中某个特定 模式串所有出现的位置。单模式匹配最基本的方法是从文本中逐个读入字符， 检查是否存在一个可能的模式匹配。如b f 算法【2 1 、k m p 算法【4 】等。 单模式匹配也可以基于滑动窗口来进行匹配。滑动窗口沿着文本滑动，在 窗口中从右向左搜索文本与模式串的公共后缀。即先将文本与模式串左对齐， 然后从模式串的最后一个字符开始从后往前逐个比较。主要算法有b m 算法【5 j 及其改进算法【6 ，7 】等。 另外，也有一些利用散列技术和素数理论进行单模式匹配的算法，如k r 算法【9 1 等。 ( 2 ) 多模式匹配 多模式匹配是基于有限字符集中的模式串和文本，在文本中同时搜索多 个模式串，并给出其出现的位置。 6 多模式匹配算法又可分为基于自动机算法、基于跳跃算法、基于数值型算 法和基于编码算法。基于自动机算法是使用有限状态自动机来组织模式串，例 如a c 算法【1 0 】及其改进算法【3 6 】；基于跳跃算法是在匹配过程中基于跳跃思想来 实现多模式匹配，相关算法主要有w m 算法【1 3 】、c w 算法【1 1 】等：基于数值型算法 是运用数学知识对模式串进行预处理，例如b e a z a - y a t e s 等人将s h i f t o r 算法 扩展到多模式匹配算法中；基于编码算法是通过编码方式进行模式匹配，例如 c e 算法【14 1 。 2 3 模式匹配技术的应用 2 3 i 模式匹配技术在网络安全领域的应用 入侵检测技术是网络安全问题的一个主要研究方向，入侵检测系统( i d s ) 【3 7 】在网络安全系统中起着重要作用。入侵检测的目的是建立一种计算机系统的 安全保护措施，防止未授权者操作计算机系统，访问系统中存储的数据和资源。 入侵检测系统中的误用检测方法是将已知的攻击特征存储在误用特征知识库 中，然后根据用户的当前操作行为与知识库里的误用入侵规则进行模式匹配。 模式匹配是入侵检测系统中的一种重要的检测方法，它是在已建立攻击特征库 的基础上，通过检查发送过来的数据是否包含这些攻击特征( 如特定的命令等) ， 来判断它是不是攻击行为。 在入侵检测系统中，模式匹配技术是影响系统性能的重要因素。开源入侵 检测系统s n o r t 系统【38 】采用了b m 单模式匹配算法，取得了很好的检测效率。后 来又有很多研究者将多模式匹配算法应用于s n o r t 系统中，使s n o r t 系统的平均 性能得到了很大的提高，在处理网络数据包的追踪问题上其性能更是提升了不 少。 病毒检测【3 9 】是模式匹配算法的重要应用领域之一。病毒检测系统有一个庞 大的病毒特征库，病毒检测技术通过一定的技术手段来判定特定计算机病毒特 征，即根据计算机病毒特征码采用模式匹配技术进行病毒检测。 此外，在网络内容过滤系统中，模式匹配技术是过滤黄色信息、垃圾邮件 等有害信息的基本的手段之一。 2 3 2 模式匹配技术在信息检索中的应用 信息检索是模式匹配技术应用的一个方面。信息检索【4o 】是按一定的方式将 信息组织起来，并根据用户的需要找出有关信息的过程和技术。例如，在 i n t e r n e t 网络中搜索信息，需要找出标题中出现“计算机”字样的论文时，我 们只需要在搜索栏中打出“计算机”一词，这时，这些搜索工具就会在目标文 本中进行匹配，而且会以很快的速度显示出匹配的结果。再如，我们经常使用 的m i c r o s o f to f f i c ew o r d2 0 0 3 软件，其中的“替换”和“查找”功能就是利 用模式匹配算法来实现的。 7 2 3 3 模式匹配技术在计算生物学中的应用 随着生命科学的发展，人们对生命物质的微观结构也有了越来越清晰的认 识。目前，人类基因组序列的绘制工作己完成，p r o s i t e 、g e n b a n k 等大型序列 库也已经建立。计算生物学的一个基本问题是序列比对，即研究两个或多个序 列间的相似性，通俗点说就是寻找一个或一组基因片段在一个基因序列中出现 的位置，以比较基因的相似性。由于可以把基因序列看成是在特定字母表上的 文本串，于是许多计算生物学、生物信息学的相关问题可以用模式匹配技术来 解决【4 。因此，作为关键技术的模式匹配技术的性能直接影响处理和分析当前 生物信息数据的效率。 2 4 本章小结 本章概述了模式匹配的概念，从功能和一次匹配的模式数量两个方面总结了模式 匹配的分类，并介绍了模式匹配技术在网络安全、信息检索和计算生物学等领域中的 应用。 8 第三章模式匹配算法分析 模式匹配是计算机科学研究领域的一个基本问题，很多学者对该问题进行 了研究，提出了很多有效的模式匹配算法。本章介绍几种经典的模式匹配算法， 并对他们的性能进行分析比较。 3 1 单模式匹配算法 单模式匹配是指在文本t e x t 中找出模式串p 0 m - 1 所有出现的位置。经 典的单模式匹配算法包括b f 算法【2 1 、k m p 算法【4 1 、b m 算法【5 1 等。本节将对单模式 匹配算法中的一些经典算法进行深入研究，并对其性能进行分析。 3 1 1b f ( b r u t e f o r c e ) 算法 b f 算法【2 】是最早最简单的单模式匹配算法，其匹配过程是将文本t e x t 和 模式串p 0 m 一1 对齐，从左向右逐个搜索，依次比较文本与模式串中的字符 是否全部相同，若全部相同，则匹配成功，若模式串p 0 m - 1 中的某一个字 符匹配失败，则将模式串向右移动一位，继续从模式串的第一位向右开始搜索， 直至文本末尾结束。 该算法简单、直观，无需任何预处理，因而不需要额外的存储空间，但是 对文本的扫描需要回溯，效率很低。匹配过程的时间复杂度为o ( n m + 1 ) ，最坏 时间复杂度为o ( m 木n ) 。 3 1 2k m p ( k n u t h - m o r r i s p r a t t ) 算法 k m p 算法1 4 j 是由d e k n u t h 、j h m o r r i s 以及v r p r a t t 提出的一种不产 生回溯的单模式匹配算法。该算法的基本思想是：假设在匹配过程中，当前正 执行到比较字符t i 和p j ( 1 i n ，1 j m ) ： ( 1 ) 若t i = p j ，继续向右匹配，检查t i + 1 和p j + 1 是否相等； ( 2 ) 若t i p j ，则分别考虑以下两种情况： 若j = 1 ，则执行t i + 1 和p j 的匹配检查，这相当于把模式串、 文本右移一个字符位置后再从头进行匹配检查； 若1 m 或i n 结束。 综上可知，k m p 算法最大的优点是匹配过程中出现模式串比较不相等时，不 需回溯文本指针，此时可以利用已经得到的“部分匹配 结果将模式向右“滑 动”尽可能远的一段距离后，继续进行比较。而k m p 算法的核心是构造n e x t 函数， 9 当l j m 时，n e x t 函数的定义如下： l o ，j = 1 n e x t j 】= m a x kii k j 勘【1 ，k i 】= p 【一k + l ，j 一1 】 i i ，e l s e k m p 算法描述如下： ( 1 ) k m p 算法中的n e x t 函数： n e x t ( c h a rp ，i n tn e x t ，i n tm ) i n tj ，k ： j = o ：k = l ： n e x t 0 = 一l ； w h i l e ( j m ) i f ( k = = - ip j = = p k ) j + + ： k + + ： n e x t j = k ： e ls e k = n e x t k ：) ) ( 2 ) k m p 匹配算法 i n tk m p ( c h a rp ，c h a rt ，i n tn e x t ) i n ti ，3 ，m ，n ： m = l e n ( t ) ： n = l e n ( p ) ： w h i l e ( i s ) ， p s + 1 m _ p 1 聊 ( s j ) ) 其中，s 为t 与t 的距离( 第一种情况) 或者x 与p ”的距离( 第二种情 况) ，j 为当前所匹配的字符位置。 偏移量取s k i p c 和s h i f t j 中的较大者，因为小于较大偏移量的文本移 动是不可能出现模式匹配的。 ( 2 ) 匹配阶段 首先，将模式串与文本左端对齐，然后从模式串最右端字符开始与文本进 行匹配，若文本字符t i + j 与模式串字符p j 匹配不成功，则比较s k i p c 一m + j 与s h i f t j 值，取较大者作为偏移量。然后，将文本指针i 往后移动偏移量，再 从后往前进行比较。如果模式串被扫描完，则找到了模式串的一次出现，文本 指针右移s h i f t 0 。 按以上方式处理文本，直至文本末尾结束。 下面举例说明b m 算法的匹配过程。 假设文本t e x t 为：a b c d b a b e a c a c a b c a c a c a f c b a 模式串为：a b c a c a c a 匹配过程如表3 1 所示。 表3 - 1b m 算法匹配过程 1234567891 01 1l2 1 31 4 l51 61 718l92 0 ab c dbabeacacabca c ac a abcacaca abcacaca abcacaca 首先，将文本与模式串左端对齐，从模式串的最后一个字符开始与文本字 符进行比较，从右向左方向进行，比较可发现e 与a 不匹配，由s k i p 与s u f f i x 的计算公式可知：s k i p e 一m + j = 8 ，s u f f i x 7 = 1 ，s k i p e 卜m + j s u f f ix 7 ， 所以模式串向右移动8 位，继续比较。 然后从模式串的最后一个字符a 开始比较，这次比较到模式串的倒数第三 个字符a 时发生了不匹配，计算s k i p b - m + j = 6 - 8 + 6 = 4 ，s u f f ix 5 = 4 ，两者相等， 将模式串右移4 位，继续比较。 再从模式串的最后一个字符a 开始比较，一直比较下去，可以发现，这次 匹配成功。 上例中，b m 算法一共进行了9 次字符比较，移动了12 位，跳过了很多不 必要的匹配。 1 2 b m 算法预处理阶段的时间复杂度为o ( m + a ) ，其中，a 为字符集的大小； 匹配阶段的最坏时间复杂度是o ( m * n ) ，最好时间复杂度是o ( n m ) 。b m 算法跳过 了很多无用的字符，具有很高的效率，被认为是亚线性串匹配算法。b m 算法不 足之处是要计算两个偏移量函数b a d c h a r 和g o o d s u f f i x ，其中，o o o d s u f f i x 函数 的计算过程很复杂。 下面将介绍b m 算法的一种简化算法。 3 1 4b m h ( b o y e r - m o o r e h o r s p 0 0 1 ) 算法 b m 算法中的g o o d s u f f i x 函数的计算非常难于实现，h o r s p o o l 发表了改进 与简化b m 算法的论文，即b o y e r - m o o r e h o r s p o o l ( b m h ) 算法【7 1 。b m h 算法在 移动模式时仅考虑了b a d c h a r 函数。它首先比较文本指针所指字符和模式串 p 0 i l l 一1 中的最后一个字符，如果相等再比较其余m - 1 个字符。无论文本中 哪个字符造成了匹配失败，都将由文本中和模式串最后一个位置对应的字符来 决定模式向右移动的距离。 b m h 算法对b m 算法进行了以下改进： 在算法中仅使用了b a d c h a r 函数； 不匹配发生时，必须要右移模式串。不像b m 中的b a d c h a r 函数在模式 串p 0 m 一1 中寻找文本中当前不匹配字符，而是看与p 0 m - 1 中末字符对 应的文本字符在p 0 m