2010年第7期福建电脑串匹配算法与改进算法的研究王锋(苏州大学电子信息学院江苏苏州215021)摘要：串匹配算法在数字通信等方面应用广泛，算法是主要的串匹配算法之一。文章在分析了算法过程和一些现有的改进算法，对这些算法进行了比较，并结合算法，提出了一个新的改进算法。该算法考虑了模式匹配时出现重复字符时，比较的前一个字符的出现情况以及模式串首字符的特性，提高了模式串移动+这样不太好位的概率，提高了匹配速度。关键词：算法；模式串；改进算法；模式匹配、引富串匹配是字符串的一个基本运算．对于给出的长度为的正文字符-。和长度为的模式串=皿(>>)，要找出模式在正文中的首次出现。一旦模式在正文中找到，则匹配成功，否则匹配失败。字符串匹配应用广泛，在数字通信、文本编辑、图像处理、数据压缩、模式识别等应用中，都需要进行串匹配。近年来对于一维字符串的匹配问题研究较多。1970年．．．从理论上证明了一维模式匹配问题可以在0(+)时问内解决，为串匹配算法的进一步发展奠定了坚实的理论基础，其中、分别为正文和模式的长度；．．。．．和．．仿照的证明构造了算法：．．和．5100设计了算法；和给出了算法和随机算法．这些算=法都是精确的串匹配算法。本文主要介宝算法及其改进算法，1、现有模式匹配算法的分析日前关于模式匹配的算法很多．其中最著名的两个是算法11和算法吲。两个算法在最坏情况下均具有线性的搜索时间。-1算法算法的基本思想堤将正文和模式左端对齐进行比较，匹配和时，若，则继续往前匹配比较；若≠，则正文中不变，模式中指向]所指示的位置。啪表示当模式中第个字符与正文中相应字符匹配失败时。在模式中需重新和正文中该字符进行比较的字符的位置．这一位置只与模式本身有关．而与正文无关最新版。
算法虽然能使样本右移若干位。但存在一个局限．即移动距离不可能大于一次匹配操作所进行的字符比较次数，存在这一局限的根本原因是算法的匹配操作必须从左向右进行。由和共同设计的快速字符串匹配算法～算法打破了这种限制．实践证明算法往往比算法快上3—5倍·。当然算法还不是最快的算法．还有很多改进的算法存在，如算法、算法161、算法[岿等网友真愿意玩。1．2算法算法的基本思想是从右向左的将模式串同文本做比较。开始时仍是的最左边与的最左边对齐。
当在某～趟比较中出现不匹配时，计算模式串右移的距离．将模式串向右移动该距离，再进行从右至左的匹配：当与最右的模式符号做比较的文本符号在模式中根本就没有出现．则模式可以在这个文本符号之后移位个位置，这种情况在算法中是不可能出现的。表1是对文本串-『．”和模式串=””。用算法进行匹配的过程(加粗部分为匹配失败的字符)。
23456789012131415161792012322522281234567表1模式匹配过程下面我们对表1中的模式匹配过程作一简单分析：(1)第一次匹配是模式串的与文本中的酋字符对齐．然后从模式串的最后一个字符开始从右向左比较．即先将[91与91进行比较，旺『己失败，因此模式串向右移动，同时[91位置的字符·在模式串中仪出现1次．模式串移动1个字符，即81与，91对齐，从而完成第二次匹配。(2)第三次匹配是将[91与01先作比较，发现匹配失败，且[101字符””仅在模式串[71位置出现一次．模式串向右移动2个字符，使71与；同理，第四次匹配后模式串再向右移动3个字符，使『9与1151对齐，准备第五次匹配。(3)在完成第四次匹配后，[9这才叫权威1与15进行比较，匹配成功，然后]与Ⅱ14进行比较，匹配失败，模式串向右移动。(4)第六次匹配时，由于上一次匹配后[91与18对齐，经比较发现不匹配。模式串再次向右移动2个字符。(5)同理，第七次匹配时，模式串向右移动8个字符，使与，『201对齐，然后从右向左进行比较，发现每个字符都能够匹配．最终匹配成功。2、现有的改进算法2．1算法一般情况下．在算法实际应用中每个字符匹配失败的应用次数要远远超过匹配成功的次数。
凶此应用失配字符的相关函数在匹配过程中起到的是主导作用，因此．1980年提出了算法的改进算法．即算法。算法将匹配失败与计算右移量独立计算．计算右移量时不关心文本中哪个字符匹配失败．而是使用与模式串最右端的字符对齐的那个文本字符来决定右移量。
一般情况下算法比算法有更好的性能。2．2算法1990年，在的基础上提出了算法．该算法的主要思想是在字符匹配失败时考虑下一个字符1+的情况．利用与模式串最后一个字符对齐的文本字符的下一个字符来决定右移量的多少。如果下～个字符不在模式串中出现时．则78福建电脑2010年第7期直接跳过该字符．即将模式串最后一个字符向右移动+1个字符；如果下一个字符出现在模式串中，则将模式串中的出现该字符与文本中的啦+字符对齐。2346789101112131415161718192022223242526281234表2算法模式匹配过程表2为利用算法实现的模式匹配过程．具体如下：(1)首先将模式串的与文本中的首字符对齐。(2)第二次匹配时，将前一次的[91与[9进行比较，匹配失败，且文本中的下一个字符01出现在了模式串中，于是模式串右移，将『71与101对齐。(3)第三次匹配。将第二次比较结果中的『91与文本中的『12仳较，匹配失败，且文本中的下一个字符[131没有出现在模式串中，因此模式串直接划过10个字符，使『91与『221对齐。(4)同理，19]与[221比较，匹配失败，且231字符出现在模式串中，右移模式串，将『41与[23]齐。同时从右向左对比每个字符．匹配成功相关。
2．3算法文献『71结合了算法和算法的优点，同时考虑字符串后一位字符的唯一性．提出了一种快速的模式匹配算法一算法。该算法避免了死循环问题．同时大大提高了最大位移+的出现概率。算法中产生+位移主要有两种情况。一是下一位字符1+1不在模式串中，这与算法相同；二是下一个字符+1在模式串中唯一，且与模式串末位对齐的那个文本串字符[+一11决定的移动量比下一个字符+]决定的移动量大。算法过程是：当比较进行到文本的处．首先计算出由模式串末端对应文本串字符“+一11得到的右移位置1和+一11后一位置字符+1得到的右移位置2，再判断1玩家爽和2的大小。如果>2，再判断+1在模式串出现频次，用函数岱)判断[+]在模式串出现的频次。若0"+1)=，即『+1在模式串只出现一次，则将模式串移动+位进行新一轮匹配；若(+)-0，即+在模式串出现大于一次，则将模式串末端和处对齐进行新一轮匹配；如果2一>，则将模式串末端和2处对齐进行新一轮匹配。其移动过程见表3所示。3456789101112145171819202212324：526：7134表3算法模式匹配过程2．4算法文献[81中提出算法，其基本思想是：在长为111的模式串中找出一个最长的前缀子串．是长度，是正文串的长度，令该子串的末字符为模式串所有字符中最后一个首次出现的字符，根据末字符的惟一性．确定在正文中每次出现的位置．并对的位置加以标注，在正中仅就每两个被标注的相邻之间长度不小于的字段．对进行模式匹配。若匹配成功。则对模余下的部分=进行匹配；若匹配不成功．则在正中寻找下两个相邻的被标注的之问长度不小于的长度的字段．这样模式从正文中每次滑过的字段长度不小于的长度。3、算法与改进算法的比较算法执行效率较高．但算法在匹配时的尝试中，采用从后向前比较的方式．对模式串的后缀进行匹配，在完成一次尝试包括匹配失败或者成功)后．利用两个根据模式串预处理好的移动表坏字符移动与好后缀移动来尝试位置后移．但是由于它没有问题处理考虑已匹配的后缀与导致匹配失败的当前字符之间的相邻关系．使得算法的效率不够高。算法时间复杂度却为0(舢)，大大高于算法的时间复杂度(+)。算法在匹配过程中不管坏字符在哪个位置．只根据与模式串末字符对应的字符在模式串中出现最大的位置来移动模式串．进行下一轮匹配．其在最好的情况下的时间复杂度为0。但该算法未考虑，'+11在模式串中是否存在，以及+11与在模式串中的关系。同时也未考虑+11是否在模式串的串首等特性。
算法的在最好的情况下的时间复杂度为0(+1)。
其右移量比算法的右移量大．算法最大移动距离为+位，算法最大的移动量为位。所以通常情况下．算法比算法快．但当与模式串最后一个字符对齐的文本字符不出现在模式串中．而下一个字符出现在模式串中时．算法的效果就不如算法了。算法的最大右移量为+位．时间复杂度为(+11。同时在综合最大移动量、产生最大位移的概率、模式串跳跃位置、时间复杂度等方面因素．算法在提高匹配速度上要比、和算法要高。但当下一个字符[+现多次时．只是将模式串移动最小距离．而没有考虑到该字符在串中出现时，其前一个字符『+一11如果不在模式串中则可以直接跳过．减少匹配次数．4、一种改进的算法通过几种改进算法的比较．各种改进算法各有优缺点．但这几种改进算法都有一个共同的缺点．就是在模式串和文本对比时．如果对比字符在中多次出现时．这几种算法的效率就没有大的差别。针对这一问题，说明的改进算法中还是有可以改进的地方。因为算法在字符重复率不高的情况下的匹配速度相对较高，在此基础上提出了对算法的一点改进。改进思路是将算法与算法结合起来．当下一个字符+1在模式串中多次出现时，则去判断前一个字符+．11在模式串中是否存在．若存在则与原有算法相同．若不存在．则说明用算法得到的下一次比较肯定是不成功的。同时判断+1是否是模式串的首字符，模式串可以最大划过+1个字符。算法思路过程如下(比较进行到文本的处)：(1)首先计算出由模式串末端对应文本串字符『+一11得到的右移位置和+—1]后一位置字符[+得到的右移位置2，其中=+-1+[+～卫；2=+一1++Ⅱ。(2)若>2，则判断+在模式串出现频次，用函数判断『+在模式串出现的频次。，在模式串中出现一次户10，在模式中出现大于一次2010年第7期福建电脑79若[+西=，即[+在模式串中只出现一次，则将模式串移动+位进行新一轮匹配．若(+=0，即+1在模式串中出现大于一次，则判断+—是否存在于模式串中。
如果¨+一11存在于模式串中，则模式串末端移到和『11处对齐进行新～轮匹配，如果[+一11不在模式串中，则再判断+1是否是模式串的首字符，如果是首字符则模式串移动位．若不是酋字符．则模式串可移动+位。
(3)若2≥1，则将模式串末端和[2处对齐进行新一轮匹配。2345678910111213141516718粥改进表4改进算法思路袭4中，先将81与[8]对齐，对于算法『81与『81不匹配，且8不在模式串中，向右移动8个字符。用算法时，先比较81与[81，发现不匹配技术支持，则计算1和2，=8+(8—0)=16，2=8+(9—8)=9。结果为>2，然后91在模式串中出现的次数大于一次，因此模式串末端向右移动到，61处。改进的算法中．当得到>2．且[91在模式串中出现的次数大于一次，则判断91是否是模式串的首字符，发现不是首字符，则可以跳过[91，模式串末端移到，71位置。这种改进的算法相比算法进一步提高了模式串移动+为的概率。5、结论通过对相同纯英文文本(文本长约1，模式串长9)采用不同方的算法．改进的算法相比算法比较次数减小约50％．比算法的比较次数约减少35％，比算法的比较次数减少约22％．相比算法的比较次数约减少1％。改进的算法相比算法虽然没有大幅减少比较的次数，但也有所改善。主要是在普通文本中在模式串长度范围内字符出现重复概率相对比较小。如果文本中存在较多的重复字符时，改进的算法性能将有较为明显的改善。6、结束语目前对于算的改进算法有很多，各有特点，在对不同文本模式进行匹配时也有各自的优势。本文在算法的基础上提出的改进算法。迸一步提高了匹配过程中产生+位移动的概率。由于时间关系，并未对改进算法进行大量的匹配实验，该算法的实际效果还没有得到有效的验证．但通过简单文本的验证。改进的算法的性能已得到初步验证．具有一定的实用性。参考文献：1，]．，1977，(6)：323—350．2，．1痂蛔册．-，1977，20(10)：762—772．3阅联营，赵婷婷．算法的研究与改进卟武汉理工大学学报(交通科学与工程版)，2006，300)：528—530．4王建固，郑家恒．串匹配算法的一个改进算法Ⅱ．计算机工程与科学．2007。29(5)：94-95．5]．]．'2。1980，10：501-506．6]．Ⅱ．，1990，33(8)：132—142．1张椰，侯整风．一种快速的模式匹配改进算"法．合肥工业大学学报(自然科学版)，2006，29仍：834-838．8李志清．,-5-模,-匹配和协议分析的入侵检测系统研究[．广州：广东工业犬学．2007．。-1。一一。
一。-+-+—+一-+-。．．一+-+一+-+·+-+-+-+·+一+-+-—+一+-+-+—·-+-+-+-+·+·+-+-+-+-+-+一+·+—+-+-·卜-+-—-+-+·+-+·(上接第46页)于迭代和增量方式开发过程闭。每～个迭代过程被分为4个阶段：初始、细化、构建和转换。每个阶段代表的是一个时间段．阶段的结束代表一个主要里程碑的达成。每个阶段可以可以包含多个工作流。如需求分析、设计、实现等。四层架构的应用系统的设计过程采用了并行的方式．各个层次的组件的设计可以相对独立地进行。
在这个设计过程中，参与者包括界面设计人员和软件设计人员．两者的设计过程可以同时进行。另一方面用户也将是设计过程的参与者。设计用户界面组件采取用户界面的可视化设计方法旧．包括对显示界面和导航过程的建模。程序逻辑、业务逻辑以及数据访问层组件的设计可以采用面向对象的方法进行设计同。5、小结在事务处理系统中采用四层层次架构所涉及的关键技术包括：迭代和增量式开发方法、面向对象的设计方法、快速原型技术、基于组件的开发方法等。
通过软件开发实践表明．采用四层层次架构能够明显提高中型和大型事务处理系统的开发效率、可维护性与可重用性。参考文献：1，等著龚晓庆等译面向对象系统分析与设计清华大学出版社2008．12]2200931，。，．．2．-。2003．4]暑刘红伟等译．2．0网络应用开发桂·心技术1机械工业出版社2007．85，．．．3．1．-．19996(，-，．辨．．臼．．2010串匹配算法与改进算法的研究作者：王锋作者单位：苏州大学,电子信息学院,江苏,苏州,215021刊名：福建电脑英文刊名：年，卷(期)：2010,26(7)参考文献(8条)1.1990(08)2.19803.王建国;郑家恒串匹配算法的一个改进算法[期刊论文]-计算机工程与科学2007(05)4.闵联营;赵婷婷算法的研究与改进[期刊论文]-武汉理工大学学报（交通科学与工程版）2006(03)5.李志清基于模式匹配和协议分析的入侵检测系统研究20076.张娜;侯整风一种快速的模式匹配改进算法[期刊论文]-合肥工业大学学报（自然科学版）2006(07)7.;1977(10)8.;1977(06)。
上一篇：２００６１－２电子与电脑??９５家用宽带有线无线通信有志一同的
下一篇：《Ｃ语言程序设计》精品课程网站论坛的建设
０５各种常见自动组卷方法的研究
２００６ＥＣＲ大会发言选登实现中国供应链现代化的三个硬件和一
ＢＢＳ跳蚤版的校园代理
２００６１－２电子与电脑??９５家用宽带有线无线通信有志一同的
２０们年第１期◇黔让你的数码影音作品显示拍摄时间
Ｃ＋＋Ｂｕｉｌｄｅｒ开发虚拟仪器模拟表组件
《Ｃ语言程序设计》精品课程网站论坛的建设
ＢＭ串匹配算法与改进算法的研究
ＣＡＤ软件二次开发方法的分析与探讨
２型糖尿病患者心率变异与ＱＴ离散度的关系