多模式匹配算法及硬件实现.pdf
《多模式匹配算法及硬件实现.pdf》由会员分享,可在线阅读,更多相关《多模式匹配算法及硬件实现.pdf(13页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、ISSN 1000-9825,CODEN RUXUEW E-mail: Journal of Software,Vol.17,No.12,December 2006,pp.24032415 http:/ DOI:10.1360/jos172403 Tel/Fax:+86-10-62562563 2006 by Journal of Software.All rights reserved.多模式匹配算法及硬件实现 李伟男1,2+,鄂跃鹏1,2,葛敬国1,钱华林1 1(中国科学院 计算机网络信息中心,北京 100080)2(中国科学院 研究生院,北京 100049)Multi-Pattern M
2、atching Algorithms and Hardware Based Implementation LI Wei-Nan1,2+,E Yue-Peng1,2,GE Jing-Guo1,QIAN Hua-Lin1 1(Computer Network Information Center,The Chinese Academy of Sciences,Beijing 100080,China)2(Graduate School,The Chinese Academy of Sciences,Beijing 100049,China)+Corresponding author:Phn:+86
3、-10-58812364,Fax:+86-10-58812306,E-mail:,http:/ Li WN,E YP,Ge JG,Qian HL.Multi-Pattern matching algorithms and hardware based implementation.Journal of Software,2006,17(12):24032415.http:/ Abstract:This paper surveys the algorithms and hardware implementations of the multi-pattern matching.Firstly,t
4、wo commonly used multi-pattern algorithms,Aho-Corasicks automata based algorithm and Wu-Manbers hash based suffix matching with skipping algorithm are introduced.And then,some improving ways are referred.Next,time and space complexity of these algorithms are analyzed,and the experimental results sho
5、w their performances.Further,several hardware based implementations are taken as examples to demonstrate the general methods and strategies for the implementation on hardware.The developing trend is predicted in the end.Key words:multi-pattern matching;Aho-Corasick algorithm;finite state automata;Wu
6、-Manber algorithm;FPGA (field programmable gate array);TCAM(ternary content addressable memory);bloom filter 摘 要:介绍了多模式匹配的算法和硬件实现方法.首先介绍了两种常用的多模式匹配算法Aho-Corasick基于自动机的算法和 Wu-Manber 基于 hash 的后缀匹配加移位跳跃的算法以及相关的改进算法.并通过实验对各种多模式匹配算法的时空复杂度进行了分析比较.通过几个硬件实现的实例介绍了多模式匹配的硬件实现方法及策略.最后对多模式匹配的发展趋势进行了展望.关键词:多模式匹配;
7、Aho-Corasick 算法;有限状态自动机;Wu-Manber 算法;FPGA(现场可编程门阵列);TCAM(三态内容寻址存储器);bloom filter 中图法分类号:TP301 文献标识码:A 模式匹配问题是计算机科学中的一个基本问题,其研究内容在信息检索、模式识别等众多领域均有重要价值,在拼写检查、语言翻译、数据压缩、搜索引擎、入侵检测、内容过滤、计算机病毒特征码匹配以及基因序列比较等应用中起着重要的作用.模式匹配按照匹配模式的数目分为单模式匹配和多模式匹配两类.最初的单 Supported by the National Natural Science Foundation of
8、 China under Grant No.90412011(国家自然科学基金);the Special Foundation of President of the Chinese Academy of Sciences under Grant No.KGCX2-YW-106(中国科学院院长基金)Received 2006-05-16;Accepted 2006-08-18 2404 Journal of Software 软件学报 Vol.17,No.12,December 2006 模式匹配 KMP 算法、Commentz-Walter 算法以及 Boyer-Moore 算法等为后来多模
9、式的发展提供了一些借鉴与启发.因为多模式匹配通过一次扫描可以找到多个模式的所有出现,较之于单模式匹配实现复杂,应用范围也更广泛,所以本文主要围绕多模式匹配来展开.1 概 述 设集合 P=p1,p2,pk是一组模式的集合,每个模式 pi由来源于字符集合的字符串组成.给定长度为 n 的文本串 T=T1n,文本串的每个字符也来源于字符集集合.多模式匹配就是在文本 T 中找出模式集合 P 中的每个模式的所有出现.Aho 和 Corasick 于 1975 年最早提出了基于自动机的多模式匹配算法1,随后,围绕这一算法,一些改进的算法被提了出来,比如压缩存储空间基于位图的算法2、反向构建自动机引入跳跃的启
10、发式方法3等.而 Wu 和Manber 于 1994 年提出了采用 hash 方法的基于后缀匹配方法,同时采用移位来加速比较4,5.这两种方法是当前主流的软件实现的多模式匹配算法,本文主要介绍这两种基本算法及其相关的改进.随着各种新的应用的出现,基于软件的实现已经不能充分满足对匹配速度日益增长的需求,因此,基于硬件的多模式匹配的实现逐渐出现,并成为当前的研究热点.本文后面以 3 个具体的实现为例,介绍了基于硬件的实现方法和策略.本文第 2 节首先介绍基本的 Aho-Corasick 算法,而后依次介绍 3 种基于它的改进算法.第 3 节介绍Wu-Manber 算法.第 4 节给出实验数据,比较
11、上述算法的性能.第 5 节给出多模式匹配的一些硬件实现方法策略以及具体的实现.最后对多模式匹配的发展趋势进行了展望.2 Aho-Corasick 算法 2.1 基本的Aho-Corasick算法 Aho-Corasick 算法1是基于有穷状态自动机的,在进行匹配之前,先对模式串集合进行预处理,构建树型有限状态自动机 FSA(finite state automata),然后,依据该 FSA,只需对文本串 T 扫描一次就可以找出与其匹配的所有模式串.预处理生成 3 个函数:goto(转移)函数、failure(失效)函数和 output(输出)函数.转移函数 goto 表明,在当前状态下读入下一
12、个待比较文本的字符后到达的下一个状态.失效函数 failure 用来指明在某个状态下,当读入的字符不匹配时应转移到的下一个状态.输出函数 output 的作用是,在匹配过程中,当出现匹配时输出匹配到的模式.Aho-Corasick 算法的匹配过程是:从初始状态 0 出发,每次取出文本串中的一个字符,根据当前的状态和扫描到的字符,利用 goto 或 failure 函数进入下一状态.当某个状态的 output 函数不为空时,表明达到该状态时找到了匹配的模式,于是输出其值.下面首先介绍 3 个预处理函数的构建.为了构造 goto 函数,首先要根据模式构建 goto 图,设置一个初始状态0,然后依次
13、扫描各个模式,根据模式逐步为这个图添加新的边和顶点,构造出自动机:从状态 0 出发,由当前状态和读到的下一个字符决定下一状态.如果有从当前状态出发并标注该字符的矢线,则将矢线所指的状态赋为当前状态;否则,添加一个标号比已有状态标号大 1 的新状态,并用一条矢线从当前状态指向新加入的状态,并将新加入的状态赋为当前状态;所有模式串处理完毕后,再画一条 0 状态的自返矢线,标注的字符为不能从 0 开始的字符集.这样,每个模式都可以由一条从初始状态出发的路径标识出来.对模式串集合she,he,hers,his构建的goto 图如图 1 所示.失效函数 f 是逐层构造的,设某个状态的层深度为初始状态到该
14、状态的最短路径长度.令第 1 层状态的failure 函数值为 0,如 f(1)=f(3)=0;对于非第 1 层状态 s,若其父状态为 r,即存在字符 a 使 g(r,a)=s(这里,s 的层深度比 r 少 1),则 f(s)=g(f(s*),a),其中,状态 s*为追溯 s 的祖先状态得到的第 1 个使 g(f(s*),a)存在的状态,如 f(4)=g(f(3),h)=g(0,h)=1,f(5)=g(f(4),e)=g(1,e)=2.输出函数 output的作用是在匹配过程中输出匹配到的模式串.output的构造分两步:第1步是在构造转移函 李伟男 等:多模式匹配算法及硬件实现 2405 数
15、 g 时,每处理完一个模式串,则将该模式串加入到当前状态 s 的输出函数中,如 output(2)=he,output(5)=she.第 2步是在构造失效函数 f时,若f(s)=s,则 output(s)=output(s)output(s),如 output(5)=output(5)output(2)=she,he.Fig.1 The goto graph for the Aho-Corasic algorithm h erssihs e501 2863 74NOT h,s 9 图 1 依据 Aho-Corasick 算法构建的 goto 图 构造完 3 个函数以后,就可以依次扫描文本,逐个
16、读取输入字符.从状态 0 开始,根据当前状态和输入的字符,采用 goto 和 failure 函数转移到下一个状态,当到达状态的 output 函数不空时输出匹配模式.Aho-Corasick 算法模式匹配的时间复杂度是 O(n),而且与模式集中模式串的个数和每个模式串的长度无关.无论模式串 P 是否出现在 T 中,T 中的每个字符都必须输入状态机中,所以,无论是在最好情况还是最坏情况下,Aho-Corasick 算法模式匹配的时间复杂度都是 O(n).包括预处理时间在内,Aho-Corasick 算法总时间复杂度是 O(M+n),其中,M 为所有模式串的长度总和.2.2 基于Aho-Cora
17、sick算法的改进方法 2.2.1 去掉 failure 函数的改进 Aho-Corasick 算法 基于基本 Aho-Corasick 算法,通过修改转移函数,可以去掉 failure 函数,将其合并到 goto 函数中.这样,在对文本进行匹配的过程中,对于每个输入字符仅进行一次状态转移,而不必在调用 goto 函数失败的情况下,再去通过 failure 函数进行状态转移.对于长度为 d 的字符串,最坏情况可能进行 d1 次 failure 转移.文献1在给出基本A-C 实现后,提出了改进的方式,通过合并 failure 函数和 goto 函数,构建 next_move 函数.如果 g(s,
18、a)!=failure,那么 g(s,a)=(s,a);否则,(s,a)=(f(s),a).这样,整个转移过程就只根据函数进行.利用这个确定的有穷自动机(DFA)可以减少状态转移的次数,使得效率得到一定程度的提高.2.2.2 位图压缩的 Aho-Corasick 算法 对于 goto 函数的存储,基本 A-C 算法采用二维数组,然而,实际上,这个数组的很多元素是空的,因为每个状态的下一个有效转移状态通常是很少的几个,这样就浪费了大量的存储空间.假设字符集大小为 256,为了节约空间,仅仅为每个状态保存指向第一个下一个有效状态的指针以及 256 比特的位图,用以指示读入哪些字符可以跳转到下一个有
19、效状态,哪些导致失效.这里,每一个比特位对应一个输入的字符,如果输入相应的字符能够跳转到下一个有效状态,那么该位置“1”,否则置“0”.而对于所有指向有效的下一个状态的指针,采用连续的地址空间存储,这样,只要找到了第 1 个有效状态,再根据位图信息就可以找出对应的有效状态相对于第 1 个有效状态的偏移,于是就能够找到对应状态的指针,这就是基于位图压缩的 A-C 算法2.图 2 给出了表示每个状态的存储结构.failptr 指向当前匹配失效情况下应该转移到的下一个状态,功能上相当于原来的 failure 函数.patternptr 指向到达当前状态时匹配出的模式串,功能上相当于原来的 outpu
20、t 函数.nextptr 指向第 1 个下一个有效状态 1st valid state(所有的有效状态:1st valid state,2nd valid state,3rd valid state,在内存连续空间中存储).bitmap 位图每位标识一个字符,指示输入该字符能否达到有效状态.对于每次查询,首先根据位图判断当前状态下,读入的字符是否能够产生有效的状态转移,这里是通过测试 2406 Journal of Software 软件学报 Vol.17,No.12,December 2006 位图中该字符对应的比特位是否为“1”来实现的.如果为“0”表明失效,则通过 failptr 指针实
21、现失效状态下的转移;否则,计算该字符对应的转移状态前面还有多少个有效状态,这里就是计算位图中该字符对应的比特位之前还有多少个“1”,从而获得偏移量.由于有效状态是连续存储的,通过将偏移量加上第 1 个有效状态的地址,就能够找到当读入当前字符时,应该转到的下一个有效状态.3rd valid state 2nd valid state 1st valid state Pattern2Pattern1Bitmap NextptrPatternptr FailptrFig.2 The storage structure of each state in the bitmap based A-C alg
22、orithm 图 2 位图压缩 A-C 算法中的每个状态的存储结构 该算法压缩了存储空间,在指针长度为 32bit 的机器上,当字符集大小为 256 时,那么,位图占 32 字节,每个状态存储需要 44 字节的空间;而基本的 Aho-Corasick 算法每个状态需要存储对于所有字符所转移到的下一个状态,则需要 4256 字节的存储空间.即便考虑到位图压缩算法中为存储所有下一个有效状态提供的额外开销,存储空间的压缩也是相当可观的.但是,计算状态转移的过程引入了额外的开销,包括对于位图的测试以及计算 偏移.2.2.3 王方法 王永成等人3通过构建 goto 函数以及 skip 函数协助实现模式匹
23、配.该算法对于模式采取从右向左进行比较,在一般情况下,该算法不需要匹配目标文本串中的每个字符,并充分利用了匹配过程中本次匹配不成功的信息,采用“坏字符”启发式规则,跳过尽可能多的字符,加快处理速度.下面介绍两个主要的函数 goto 和 skip 的构造.对于 goto 函数的构造,与基本的 Aho-Corasick 算法类似,也是设初始状态为 0,因为算法是从右向左进行模式比较,进行逆向匹配,所以采用从后向前扫描模式串,构建逆向自动机,图 3 给出了对于模式串集合为her,where,redo构建出的 goto 图.owerehe r876NOTr,e,o5r12ed 10 1194 32 1
24、0hFig.3 The reversely constructed goto graph 图 3 反向构建的 goto 图 skip 函数是用来依据当前字符判断向后可以跳过扫描的字符数目.这里,假设模式集合中最短模式的长度为 minlen,那么+0 so move right immediately m SHIFTh B m Fig.4 Wu-Manber algorithm searching for match progress 图 4 Wu-Manber 算法的扫描匹配 Wu-Manber 算法的时间复杂度平均情况是 O(BN/m).B 是块字符的长度,而 N 是文本的长度,m 是模式的
25、最短长度.该算法对最短模式长度敏感,SHIFT 函数的最大值受最短模式长度的限制,如果最短模式长度很短,则移位的值不可能很大,因此对匹配过程的加速有限.4 实现的分析以及实验数据比较 4.1 预处理复杂度分析 上述这些算法都要进行预处理,生成相关的函数和表,可以在匹配之前独立完成.尽管它们的执行效率不影响匹配的速度,但它们也会占用一些资源,因此,我们先讨论一下各种算法的预处理的复杂度.对于基本的Aho-Corasick 算法,生成 goto 函数需要扫描所有模式的每个字符,所以,时间复杂度随着所有模式的总长度线性增加;而 failure 函数的生成时间也与所有模式的总长度成正比;output
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模式 匹配 算法 硬件 实现
限制150内