字符串模式匹配算法综述.doc

《字符串模式匹配算法综述.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、个人收集整理勿做商业用途字符串模式匹配算法综述摘要：字符串匹配问题是在给定符号序列(称为文本）中按照一定的匹配条件，搜索给定符号序列或给定符号序列集合中元素（称为模式）出现位置的搜索问题。该问题是计算机科学的基础问题之一，被广泛的应用于各种涉及文字和符号处理的领域中，是网络安全、信息检索、计算生物学等重要领域的关键问题.本文主要介绍了BF算法、KMP算法、BM算法、BMH算法、AC算法和AC—BM算法.关键词：模式匹配，BF算法，KMP算法,改进算法，BM算法，AC算法,ACH算法。0.前言字符串是一种线性表，它在计算机应用系统中如文本编辑、情报检索、自然语言翻译有着广泛的应用.在这

2、些应用中常常需要在一堆文字符串中检测是否有某一指定的字符串。设Pattern（下文简称P）和Text（下文简称T)是给定的两个字符串，在字符串T中寻找等于P的子串的过程称为模式匹配,其中字符串T称为主串,字符串P称为模式串.如果在字符串T中找到等于P的子串，则称匹配成功，否则匹配失败。比较著名的模式匹配算法有BF算法、KMP算法、AC算法和BM算法，本文对所述算法进行探讨。随着计算机技术的快速发展,计算机网络在国民经济中发挥了日益重要的作用，己成为人们日常生活中不可缺少的一部分.同时，网络安全也日益引起人们的关注。1。模式匹配算法1。1单模式匹配算法1.1.1BF（BruceForc

3、e）算法1.算法思想从文本字符串T的第一个字符起和模式字符串P中的第一个字符开始个人收集整理勿做商业用途比较，若相等，逐个比较后续字符,否则从文本字符串的下一个字符起再重新和模式字符串的第一个字符比较。1.算法描述对于文本字符串模式字符串（1）P和T从左端对齐,使得与对齐；(2)从左到右匹配P与T的字符，直到出现不匹配的情况,则执行（3），或是P己被完全匹配的情况则结束比较；（3）将P右移一个字符,重新从P的第一个字符开始匹配;（4）重复上述（2)过程，直到P被完全匹配,或P移到T的右端.1.1.2KMP（KnuthMorrisPratt)算法KMP算法是Knuth等人在BF算法的基

4、础上提出来的。从本质上讲，KMP算法就是出现不匹配情况下带有智能指针初始化的BF算法。为了在不匹配时重新定位指针，KMP算法需要进行预处理算出一个next数组来。1.基本思想KMP算法利用己匹配成功部分的信息，即前缀（模式字符串中存在的相同子串),可以使模式字符串向前推进若干个字符位置，而不只是一个字符，避免了重复比较，同时也实现了文本字符串指针的无回溯.2.算法描述当模式匹配执行到比较字符和,其中l=i=n，l=j=m。（l)若=则继续往右做匹配检测，即对和进行匹配检测.（2）若当j=l，则对和进行匹配检测，即把模式和正文向右移动一位再从模式的第一个字符进行匹配;若l

5、将试图在模式中找到一个合适位置再进行比较,我们把这个下标记做next[j]。执行和的匹配，其中next［j]的构造是算法的核心，约定如下：个人收集整理勿做商业用途1.1.3改进的字符串匹配算法字符串模式匹配算法要解决的关键问题是：在模式与文本在某个位置比较失败时，如何使模式串窗口向右移动最佳距离，尽量多的跳过不必要比较的字符，减少匹配的次数,并使产生这种距离的算法复杂度降低和易于理解。通过对现有的各种字符串匹配算法进行分析研究,我们提出一种改进算法,该算法简单实用,便于理解。1。基本思想与KMP算法类似,在模式串的匹配过程中,字符比较采用符合人们习惯的从左到右顺序，模式窗口也是从左到

6、右移动.2.算法描述设当前的比较窗口是,在某次比较过程中失败于处,即前j个字符匹配成功:=，而≠.首先定义一个函数S来确定正文中出现的字符x在模式P中的位置，考虑到要使用模式对应窗口后的第一个字符，在模式串P中补充一个字符Pm与之对应,以使和文本中的窗口对齐，这样，如图1所示.图1模式串P与主串T对应位置函数S的定义如下：个人收集整理勿做商业用途其中：x取当前窗口匹配失败位置j及其后的字符即x=,j≤k≤m,并且x取值位置的变化引起前面子串｛}长度的变化。S(x)函数实质是用来求匹配失败时模式串的向右移动距离。有以下三种情况：（1）当x不在前面的子串（子串包括P本身)中时，启发移动的

7、距离是子串的字符个数；（2）在子串中从后向前查找第一个与x相同的字符，启发移动的距离是它们之间的间隔距离；（3）如果，子串的下标0-1＝—1，为统一使用函数S(x)而规定的取值.图2改进算法的具体实现流程我们采用3个位置的字符：、、进行计算，之所以考虑用个人收集整理勿做商业用途、来参与决定模式窗口的移动距离，是因为如前面的字符发生不匹配，则模式至少向后移动一个位置,二者处于移动后的窗口之内，作为新窗口之内的字符，、也需要与模式中与之相同的字符对齐，它们也要