《kmp算法报告》word版.docx

摘 要关键词匹配(Keyword Matching)有时也称为模式匹配(Pattern Matching)，是计算机科学中一个基本问题，也是一个经典的算法问题。该算法目前被广泛用于信息处理、网络信息过滤、入侵检测系统和生物信息计算的基因序列比较等工作中。本文首先分别介绍单模式匹配和多模式匹配的经典算法，单模式匹配算法主要分析了KMP算法和BM算法，多模式匹配算法详细分析了Wu-Manber多模式匹配算法，并对其进行了改进，最后通过实验对几种算法的复杂度进行了比较。1. 引言简单的说关键词匹配问题就是从给定的文本(Text)中，找出所有的需要匹配的模式(Pattern)。一类匹配问题是预先知道文本，再根据动态给出的模式进行匹配，例如搜索引擎预先收集Web页信息，再跟据用户输入的关键词进行匹配查找，处理这类问题需要对已知的文本做一些处理来加速匹配过程，一般采用对文本加索引的方式；另一类匹配问题是预先知道模式，在不同的文本中进行匹配，例如用关键词过滤信息，根据特征码检查病毒等都属于这类问题。根据待匹配的关键词的个数又可以分为单模式匹配和多模式匹配。另外根据匹配的方式还可以分为基于字符比较匹配(character comparison)和基于非字符比较匹配(主要将字符串看作bit串来处理和一些数值型的方法)两种。本文要讨论的是预先知道模式的情况下基于字符比较的模式匹配问题，本文首先分别介绍单模式匹配和多模式匹配的经典算法，其中详细分析了Wu-Manber多模式匹配算法，并对其进行了改进，最后通过实验对几种算法的复杂度进行了比较。2. 单模式匹配算法单模式匹配就是在给定的文本(Text)中对给定的单个关键词样本(Pattern)进行搜索，并且返回所有的匹配。最原始的匹配算法是平凡算法，即用关键从文本起始位置开始比较，每次匹配不论成功与否都将关键词在当前文本处右移一位。平凡算法在正确性上是没有问题的，但是由于每次只将Pattern右移一位导致匹配时间很长。2.1 KMP算法2.1.1 KMP算法原理针对平凡算法时间复杂度高的缺点，KMP算法提出了当样本Pattern在文本Text中的某一位置匹配失败时样本可以右移不只一位并且仍然不丢失解的基本思想，这样就可以大量地减少不必要的匹配从而降低时间复杂度。KMP算法的重点之处在于当Pattern在位置j处与文本Text相应位匹配失败后，Pattern在位置1到j-1处是匹配成功的，KMP算法正是利用1到j-1处的成功匹配计算出在不丢解的前提下， Pattern可以右移的最大距离。KMP算法分为2个部分，首先计算GetNext()函数初始化Nextj数组，然后进行串匹配。其核心就是初始化Nextj数组，Nextj的值表示Pattern的部分字符串P1j-1从两端计算的最大可匹配的长度再加上1，用公式表示为：Nextj=1kjMAXk|P1k-1=Pj-k-1.j-1有了Nextj数组，在进行字符串匹配时，当Pattern在位置j处与文本Text相应位匹配失败后，Pattern可以向右移动j- Nextj的距离。其中GetNext()函数的计算代码如下：void GetNext(char P, int m ,int& Next) int i,j ; Next1=0 ; for (j=2; j0)&(Pi!=Pj-1) i=Next i ; Nextj=i+1 ; return ;KMP匹配算法代码如下：void KmpSM(charP, charT, int m, int n, int Next) int i=1,j=1 ; while(i0)&(Pj!=Ti) j=Nextj ; if(j=m) coutiendl ; return ; else i+ ; j+ ; cout”Failure”endl ; return ;2.1.2 KMP算法时间复杂度KMP算法不像平凡算法那样每次匹配失败后只将Pattern右移1位，且字符比较从P1开始，因此KMP算法的时间复杂度要比平凡算法的O(m .n)复杂度低。KMP算法在初始化Nextj数组的步骤中时间复杂度为O(m)，在字符串匹配过程中时间复杂度为O(n)，因此KMP算法的时间复杂度为O(m+n)阶。2.2 Boyer-Moore(BM)算法2.2.1 BM算法原理KMP算法虽然能够使样本右移若干位，但是存在一个局限，即移动距离不可能大于一次匹配操作所进行的字符比较次数j，存在这一局限的根本原因是KMP算法的匹配操作必须从左向右进行。BM算法打破了这种限制，将样本Pattern的匹配顺序改为从右向左进行，当Pattern的Pj匹配失败时记录下文本Text中与其对应的字符x=Ti，并通过x与P1m的m个字符的关系决定Pattern右移的距离大小。BM算法也分为2个部分，首先要通过函数Dist(x)对Dist数组进行初始化，然后再进行字符串的匹配。同样Dist数组的构造也是BM算法的核心之处。Dist(x)的含义可以表示为：Dist(x)-m+j是在产生一次匹配失败时，根据当前样本字符Pj所对应的文本字符x，以及x与样本P1m 的m个字符的关系之间的关系计算出的Pattern右移的距离。Dist(x)函数的定义域为字符表，值域为1,m。具体含义可以用下面公式定义：Distx=m, &xPj(1jm)m-j, & 其他情况其中j=Maxk|Pk=x,1kmDist(x)函数的计算代码如下：void bmDist(char P, int m, int Dist) char ch ; int k ; for(ch=a;ch=z;ch+) Distch-96=m ; / a的ASCII码值为61H for(k=1;k=m-1;k+) DistPk-96=m-k ; return ;BM匹配算法的代码如下：void bmSM(char P,char T,int m,int n,int Dist) int i, j, k ; i = m ; while(i0)&(Pj=Tk) j- ; k- ; if(j=0) coutkendl ; return ; else i=i+DistTi-96 ; cout”Failure”endl ; return ;2.2.2 BM算法时间复杂度Dist(x)函数的计算与两个参数有关：字符表的大小c和样本Pattern长度m，因此Dist(x)函数的时间代价是(m+c)阶的。BM算法的比较次数不会超过m.(n-m+1)，因此BM算法的最坏情形时间复杂度为(m.n)。BM算法比起KMP算法有明显的优势，KMP算法每次比较后样本Pattern右移的距离不可能大于该次匹配字符比较的次数，因此KMP算法在最好情形下，其不成功搜索或搜索所有匹配的比较次数至少为n-m+1。而BM算法中样本Pattern右移的距离与字符比较数无关，多数情况下每次匹配只需比较一次便可以右移m位，从而使得字符比较总数大大小于文本Text长度n。2.3 QuickSearch (QS)算法该算法是对在BM算法的基础上的一点改进，其核心思想是：发生不匹配时(Tj-iPm-i)，至少要向前移动一个字符，也就是说Tj+1一定会参与下一次匹配，可以利用该字符在Pattern中的出现情况决定本次移动的距离。由于该算法并不利用已匹配部分所带来的good-suffix shift和bad-character shift，只是根据Tj+1所得到的跳越情况进行移动，所以在理想情况下，会比BM算法的最大跳越距离多一个字符(因为将Tj+1本身计算在内了)，所以最优情况下复杂度可以是O(nm+1)，该算法能够取得较高效率的前提是Text中绝大多数的字符都是Pattern中没有的字符，对应实际的情况就是字符集较大，Pattern的数目比较少且短，这点比较符合中文字符的特征，所以在解决面向中文的匹配问题时该算法比较适用。3. 多模式匹配算法多关键词匹配问题可以描述为：设待处理文本为Text1n ,其定义在一个有限的字符表(大小为c) 上，给定的模式集合为 Pattern = P1 ,P2 , , Pk 共k个模式，m为最短模式串的长度，要求一次找到Pattern中所有模式在Text中出现的情况。3.1 Wu-Manber算法3.1.1 Wu-Manber算法原理Wu-Manber算法是从BM算法发展而来的一种高效的多模式匹配算法，与BM算法不同之处在于：BM算法是根据文本Text中匹配失败的单个字符与样本Pattern中所有字符的关系计算出样本右移的距离，而Wu-Manber算法则是以字符块为单位，通过比较文本Text中的字符块与样本模式集合Pattern = P1 ,P2 , , Pk中字符块的关系决定样本右移的距离。Wu-Manber算法也分为预处理和字符匹配2个阶段。在预处理阶段中，Wu-Manber算法需要构造SHIFT、HASH和PREFIX三张表。SHIFT表类似于BM算法中的Dist数组，SHIFT数组的值是根据块字符的比较来决定的，可以用下面的公式表示：SHIFThashBc=m-B+1,BcsubStr(pattern) &minm-B-kj patternjk+i=Bci0iB,其它其中Bc表示字符表中所有块字符的组合，B为预先规定的块字符的大小(B一般设为2或3)。块字符经过hash散列后的值作为SHIFT数组的下标，因此可知SHIFT数组的大小为CB，其中C为字符表的大小。HASH表的每一项存储着一个next链表，链表中存储着具有相同块字符Bc的的模式集合P。图3-1 HASH表的数据结构从图3-1可以看出，当块字符Bc为is时，hash(is)的值为i，则所有包含is块字符的模式样本Pi都存储在HASHi指向的next链表中。PREFIX表用来存储尾块字符散列值相同的模式串的首块字符散列值，其作用就是辅助HASH表提高在有可能存在匹配模式的情况下(SHIFT表的值为0)找出匹配模式的速度。Wu-Manber算法的代码流程如下：While(texttextend) hash_value = hash(text); /计算当前文本text的最后一个字符块的哈希值 shift_distance = SHIFThash_value; if(shift_distance=0) shift_distance = 1; p = HASHhash_value; /获得可能与当前文本text相匹配的模式集合的入口 Check(p); /判断是否存在匹配的模式 text += shift_distance; /选择下一个匹配入口点3.1.2 Wu-Manber算法时间复杂度Wu-Manber算法的平均时间复杂度是O(B*nm)，其中是B块字符的长度，而n是文本的长度，m是模式集合中最短模式的长度。Wu-Manber算法主要优势是匹配入口点少，从而字符比较的次数减少。但是Wu-Manber算法在一个可能的匹配入口点处，对HASHi的next链表中的每一个模式逐个进行比较，不论是否发现完全匹配的模式都会将下一次匹配的位置右移一位，针对这一点该算法的时间复杂度仍然可以改进。3.2 改进的Wu-Manber算法在经典的Wu-Manber算法中，最大的转移距离是,在扫描匹配阶段，如果SHIFThash_value的值为0，那么无论是否存在匹配串，下一次匹配的转移距离都等于1。针对这些特点，新算法(下文中称为IWM算法：Improved Wu-Manber Algorithm)首先吸收QS算法的思想，进一步扩大了匹配失败时下一个匹配入口点移动的距离。同时为了在SHIFThash_value为1时，扩大下一步的移动距离，新算法又引进一个良好后缀转移距离表GBSSHIFT,GBSSHIFT记录每一个模式的前m长子串的长度为B的后缀在所有模式的前m长子串中的所有非后缀出现位置与后缀之间的距离的最小值。改进的算法IWM包括两个阶段，预处理阶段和搜索阶段。预处理阶段构建五张表：SHIFT表、HASH表、PREFIX表以及TAIL表和GBSHIFT表。与经典Wu-Manber算法相比，多出了TAIL表和GBSSHIFT表，其中TAIL表用于记录判定当前匹配窗口的最后一个块字符是否与某个模式的相应块字符相同，而GBSSHIFT表记录SHIFThash_value为1的情况下下一步的转移距离。另外HASH表和PREFIX表的构造和Wu-Manber算法相同，而SHIFT表与Wu-Manber有一些不同的地方。下面介绍TAIL、SHIFT和GBSSHIFT表的构造：1) TAIL表的构造首先，初始化TAIL表为0；然后，根据每个模式的m长前缀的最后一个块字符的哈希值hash_value把TAILhash_value设置为1。2) SHIFT表的构造SHIFT表的构造稍微复杂一些，假设X=x1xB是当前扫描文本的第m个块字符，并且通过哈希函数映射到SHIFT表的第i个元素中。那么SHIFT表的构造过