模式匹配BM算法改进

减小字体 增大字体 作者:张红梅 范明钰  来源:www.zhonghualunwen.com  发布时间:2009-10-12 14:55:06

  0 引言
  
  串匹配是文本挖掘、文献检索、搜索引擎、IP路由查找、模式识别、图像处理以及入侵检测技术等普遍采用的技术策略之一。串匹配算法是系统性能改进中极为重要的部分,系统性能的好坏取决于匹配算法及其实现的效率。学者们已提出大量串匹配算法,如Knuth等人[1]构造出KMP 算法, Boyer等人 [2]于1977 年设计出BM算法。在这些常用的字符串匹配算法中,KMP和BM算法是其中较为著名的两种算法。这两种算法在最坏情况下均具有线性的查找时间,KMP算法匹配从左向右进行,移动距离不可能大于一次匹配操作所进行的字符比较次数;而BM算法匹配从右向左进行,当模式串P的末字符P[m]与对应的正文串T中的字符T[i+m]进行比较时,若T[i+m]在模式串P中并不存在,则模式串可以一次向右移动m个字符,使模式串只经一次比较就可以移动模式串的长度,这使BM比KMP算法更快。在实用上,BM要比KMP算法快3~5倍。
  本文分析BM算法及其各种相关改进算法,结合其优点对BM算法作出新的改进。针对坏字符在模式串中出现的惟一性,坏字符的前驱以及坏字符在正文串中对应字符的后继字符在模式串中的存在性,模式串末字符是否为模式串串首字符,以及坏字符与其后继字符在模式串中是否存在同样的子串进行分析,作出进一步的改进。
  
  1 BM算法及其相关改进算法
  
  1.1 BM算法原理
  BM算法设置如下初始条件:
  正文串T={T[0],T[1],T[2],…,T[n]}
  模式串P={P[0],P[1],P[2],…,P[m]}
  字符集Σ=a,b,…,z
  其中:n>m,需要从T中查找出与P完全匹配的子串,并返回该子串在正文串的首字符的位置。
  BM算法原理如下:在正文串T第i个位置开始与模式串P第0个位置对齐,从右往左进行比较。首先比较模式串P末字符P[m]与正文串T对应字符T[i+m]是否相匹配。一旦发现不匹配,通过查找预处理好的坏字符移动表Badchar与好后缀移动表GoodBuffer,对所得到的结果进行比较,用移动距离较大值向后移动模式串P的尝试位置。其中坏字符移动表用式(1),好后缀移动表用式(2)求出。
  Badchar[c]=m+1;c!=P[j];0≤j≤mm-j;j=max{j|P[j]=c;0≤j≤m}(1)
  GoodBuffer[i+1]=mins|s>0,i  s  虽然BM算法执行效率较高,由于没有考虑好后缀与坏字符之间的前驱后继关系,使得算法在总体上效率不高,仍可以有更多的改进。目前就有多种对BM算法的改进,如BMG、SBM、BMH、IMBM等算法。
  1.2 分析已有的BM改进算法
  1.2.1 BMH算法
  Nigel[3]提出BMH算法。BMH算法在匹配过程中不管坏字符在哪个位置,只根据与模式串P末字符对应的字符在模式串中出现最大的位置来移动模式串,进行下一轮匹配;而未考虑T[m+1]在模式串中是否存在,以及T[m+1]与T[m]在模式串P中的前驱后继性以及T[m+1]是否在模式串P的串首等特性。以下是匹配比较过程。
  1.2.2 BMG算法
  文献 [4]提出BMG算法。该算法结合BMH和BMHS算法的特点,考虑模式串末字符的惟一性,以及串末字符与其对应的正文串字符的后继字符在模式串中的位置差别。当出现多次时,只是将模式串移动最小距离,而没有考虑到该字符在串中出现但是其后继与前驱字符并不一起出现。如果在模式串中并不存在该字符与其后继前驱的子串,则可以直接跳过,减少匹配次数。
  1.2.3 SBM算法
  文献[5]中提出一种面向入侵检测的BM模式匹配改进算法。采用对模式串从两边向中间进行匹配。但对匹配未成功的字符进行移动时,只考虑末字符的对应正文串中字符的后继字符,没有考虑该末字符在模式串中的位置以及末字符对应正文串中字符的后继字符在模式串中的位置相关性。由于在语言中每个字符出现的几率一样,从两边向中间匹配和从右往左匹配效率相当。该算法针对串匹配中如果存在特殊情况,即模式串为“aabaa”正文串为 “aaaaaaaaaaaaa”时,算法的复杂度与BM算法针对模式串为“baaaa”正文串为 “aaaaaaaaaaaaa”时匹配次数一样。
  1.2.4 PBM算法
  文献[6]中提出了PBM算法,其基本思想是:在长为m的模式串P中找出一个最长的前缀子串subp,k是subp长度,n是正文串的长度,令该子串的末字符Pk为模式串所有字符中最后一个首次出现的字符,根据subp末字符Pk的惟一性,确定Pk在正文T中每次出现的位置,并对Pk的位置加以标注,在正文T中仅就每两个被标注的相邻Pk之间长度不小于subp的字段,对subp进行模式匹配。若subp匹配成功,则对模式P余下的部分endp=P-subp进行匹配;若匹配不成功,则在正文T中寻找下两个相邻的被标注的Pk之间长度不小于subp的长度的字段,这样模式P从正文中每次滑过的字段长度不小于subp的长度。
     PBM算法的时间复杂度为(qmn/k+mn(l-q))。PBM算法在对最长前缀进行匹配时,只查找一个表即可得到模式串的移动值;而BM算法在匹配过程中需要查找两个表并对这两个查找值进行比较取其中的较大值。因此,每次在向后移动模式串时,PBM都要比BM算法少查一次表,同时少作一次比较。PBM算法的匹配最长前缀时计算出来的移动值不小于BM算法的移动值,从而减少了匹配时间。
  此算法只是对模式串预处理时构造末字符仅出现一次,但对该前缀模式子串subp的匹配并未采用任何改进。对模式串P满足末字符只出现一次的情况下,该算法仅仅是BM算法,效率显然低下。而且在自然语言中模式串P末字符只出现一次的情况很普遍,因此需要对subp的匹配中采取更有效的算法。
  1.2.5 其他改进算法
  文献[7]中提出一种新的BM改进算法,算法时间复杂度为O(m(n-m))。该算法与BM算法的结构基本相同,在原有模式串移动的基础上,通过对模式串与正文串匹配时比较模式串末字符的下一个字符对应的正文串字符在模式串中出现的位置,加速了在匹配失败后向后跳跃的幅度,减少了比较次数,提高了运算效率。但该算法并未对模式串末字符以及坏字符的惟一性及是否为首字符的特性进行判断。假设如下:

[1] [2] [3]  下一页

Tags:

作者:张红梅 范明钰
  • 好的评价 如果您觉得此文章好,就请您
      0%(0)
  • 差的评价 如果您觉得此文章差,就请您
      0%(0)

文章评论评论内容只代表网友观点,与本站立场无关!

   评论摘要(共 0 条,得分 0 分,平均 0 分) 查看完整评论