设为首页 - 加入收藏
广告 1000x90
您的当前位置:188144com黄大仙救世网 > 近似匹配 > 正文

带有换位操作的近似串匹配算法及其并行实现

来源:未知 编辑:admin 时间:2019-07-28

  中国科学技术大学硕士学位论文 带有换位操作的近似串匹配算法及其并行实现 姓名:姚珍 申请学位级别:硕士 专业:计算机软件与理论 指导教师:陈国良 2002.5.1 中周科学技术大学硕十学位论文摘要 \串匹配问题是计算机科学中的一个基本问题,也是复杂性理论中研究得最广泛的问题之一。它在文本检索、信号处理、计算生物学、图像处理、模式识别等 诸多领域中都有着广泛的应用。因此,研究并设计快速的串匹配算法具有重要的 理论价值和实际意义。按照匹配是否允许有错误来划分,串匹配问题可以分为精 确串匹配和近似串匹配。所谓近似串匹配问题,是指不要求模式串与文本串的子 串完全精确地匹配而允许有错误的一类串匹配问题。本文研究的正是这类问题。 一般的近似串匹配问题,即最多带k个误差的串匹配问题可描述为:在文本 串T中找出所有与模式串P的编辑距离小于等于k的子串%--t,,输出匹配结束 位置t。。这里,串P与串t。…t。的编辑距离小于等于k是指,最多需要对P做k 个字符的插入、删除和替换操作,可以使P与t。…t,完全精确匹配。插入、删除 和替换操作分别用于纠正P中少一个字符、多一个字符以及P中一个字符与 t.…t,中对应字符不匹配的情况。然而,在许多实际情况中,文本串和模式串中 往往还存在另一种错误,即相邻两字符的位置发生了交换,尤其是在日常书写和 文字录入时,这种错误更是经常发生。因此,有必要在一般的近似串匹配问题所 允许的三种编辑操作(插入、删除、替换)以外,再增加一种用于纠正上述错误 的换位操作。我们将这种允许有插入、删除、替换和换位四种编辑操作的近似串 匹配问题称为带有换位操作的近似串匹配问题,为方便起见,又称为扩展近似串 匹配问题。本文正是针对这个问题进行研究的。事实上,在k一定的情况下,,增 加换位操作后,能够找出更多的匹配位置,从而使得算法更加实用有效。V 本文的主要研究内容与贡献是:对带有换位操作的近似串匹配问题进行了讨 论,提出了一个基于过滤思想的快速的串行算法。理论分析表明,在误差率a(n =k/m)比较小的情况下,该串行算法的时间性能较好,其平均时间复杂度为 0(kn+m),其中,n和111分别是文本串和模式串的长度,k是近似匹配允许的最大 误差数。本文还给出了上述串行过滤算法在PRAM模型和分布式存储模型上的 并行化,并行化的算法使用P个处理器,平均时间复杂度为0(kn/p+km)。我们 还在分布式存储的并行计算机曙光-2000上实现了我们的并行化算法,实验结果 表明,并行化算法在分布式存储的并行计算机系统上的并行性能良好。 关键询近似串壶葩,编辑谴离,最多带k个误差的串匹配,带有换位操作的近 似串匹配问题,曙光一2000,分布式存储的并行计算机系统 中国科学技术大学颂士学位论文Abstract Abstract Stringmatching isabasic problem computerscienceanditisalsooneofthe most extensively studied problems complexitytheory.Ithasextensive applications intext retrieval,signal processingcomputationalbiologyimageprocessingpattem recognition andsoon.Ithas veryimportant theoreticalvalueand practicalmeaning researchanddesign fast stringmatchingalgorithms.Stringmatchingproblems carlbe classifiedintoexact stringmatching whetherallowing errors.The approximatestringmatchingproblem canbe simply describedasthe type stringmatchingproblemwhichallowsdifferencesbetween pattemandthe substring ofthetext.Wefocusonthis type stringmatchingproblem inthisthesis. Thecommon approximatestring matchingproblem whichrefers stringmatching withatmostkdifferencescanbedescribedasthe following:Given atextT anda pattemP.finding allthe substrings ti...tj ofTwhoseeditdistancesfromPareat most k,outputting thematch endingpositions q.Here,the editdistanceisatmostk meansthatPcallbe changed intothe substringti...q ofT through atmostk insertion, deletionorsubstitution operations.Howeverinmanypracticalcases,there isanother type errorsinthetextandthepattem,thatis,twoadjacent charactersis transposed bymistake.People oftenmakethesesmistakeswhile writing verynecessary operationsallowed commonapproximatestringmatchingproblem tocorrecttheerrorsdescribed above,that isthe transpositionoperation.We callthe approximatestringmatchingproblemallowing transpositions astheextended approximatestring matchingproblem forshort.We mainly researchthis problem inthis thesis.Actuallywhen kis fixed,we canfind more matchingplaces while addingtransposition allowedoperations, thereforethe algorithm ismore practical powerfulthan previous. Themainworkofthisthesisisasthe following:we discussthe approximate string matchingproblemallowing transpositions,presenting afastserial algorithm basedonfiltrationmethod.Thetheoretical analysis showsthatwhentheerrorlevel lowthetime performance oftheserial algorithm quitegoodandits average timecostis O(kn+m).We also present two parallel algorithms onPRAMand distributed memory models respectively.Theaverage timecost ofthe parallel algorithm thenumberofprocessors used.Wealso implement our parallel algorithm onthe distributed memoryparallel computer lI 中国科学技术大学硕-:学位论文 Abstract Dawning一2000.Theexperimental resultsshowthatthe parallelalgorithm has good performance ondistributed memoryparallelcomputer Keywords Approximatestringmatching,Editdistance,Stringmatching withat mostk differences,Approximatestringmatchingproblemallowing transpositions,Dawning一2000,Distributedmemoryparallelcomputer Ill 中周科学技术大学硕士学位论文 第一章近似串匹配问题和近似串匹目E算法 第一章近似串匹配问题和近似串匹配算法 本章首先阐述了近似串匹配问题的研究背景和研究意义,然后介绍了近似串 匹配问题的一些相关概念,最后介绍了一些已有的近似串匹配算法。 1.1近似串匹配问题的研究背景和研究意义 近似串匹配问题的提出最早可以追溯到二十世纪六、七十年代,该问题出现 在许多不同的应用领域中,主要包括计算生物学、信号处理、文本检索与处理等。 计算生物学DNA和蛋白质分子序列可以被看作是定义在特定字母表上的长度非常长的 字符串,例如,DNA序列就是定义在只含有四个字母A,C,G,T的字母表上的 字符长串。DNA和蛋白质分子序列代表了生物的基因编码,在这样的字符长串中 查找特定的字符序列是在DNA链中查找具有给定特征的片段,或者判定两个基因 序列的相似程度等问题的一种基本操作。因此,该问题被提出来,抽象成在一个 给定的文本串中查找一个给定的模式串的问题。但是,在实际应用中精确匹配可 以说是毫无价值的,因为模式串极少与文本串的子串精确匹配。同一生物物种的 两个不同个体的基因序列仅仅是非常相似,而不是完全相同的。另外,判定两个 基因序列的相似程度也需要引入“近似”的概念。这些实际问题的需要引起了对 允许有错误的字符串匹配问题的研究。在计算生物学领域中,字符串中允许出现 的错误是指在基因序列中经常发生的一些操作。两个序列之间的距离定义为将一 个序列变成另一个序列所需要的最小操作序列的代价值。考虑到相似程度的度量 问题,每种操作被赋予一个代价值,一种操作对相似度的改变越小,那么这种操 作的代价值就越小。这样一来,该问题就变成如何使总的代价值最小的问题。 信号处理引起近似串匹配问题的提出的另一个领域是信号处理,其中最主要的就是语 音识别,即,给定一个语音信号,要求确定它所对应的正文信息。语音识别问题 通常很复杂,即使是最简单的语音识别问题,如在一个很小的单词候选集合中识 别出一个特定的单词,也是非常复杂的。因为语音信号的完整性和正确性无法保 证,有些语音信息可能被压缩掉了,有些可能丢失了,完全精确匹配几乎是不可 能的。信号处理领域中的另一个问题是信号的恢复。信号的物理传输过程是很容 易发生错误的,因此,有必要找到一种方法来修正传输过程中可能发生的错误, 从而获得正确的信息。从信号处理理论中可以得到各种错误发生的概率,用它可 以来定义每种错误的代价值。尽管信号处理领域的发展与字符串近似匹配问题的 中国科学技术人学硕lj学位论文 第一章近似串匹配问题和近似串匹配算法 相关性并不是很大,但在该领域中提出了近似串匹配问题的一个最重要的串距离 函数,即Levenshtein距离,或称为编辑距离。 文本检索与处理近似串匹配问题的一个非常重要的应用领域就是文本的检索与处理。实际 上,该问题最早的一个实际应用就是用来纠正文本书写中的拼写错误。目前,全 世界可以获取的总的文本信息数量非常庞大,在许多实际应用中,文本的大小也 已经用GB来度量。要想在这样庞大的文本中快速检索相关信息是一件比较困难, 也比较复杂的事情。 其它领域目前,又出现了近似串匹配问题的一些新的应用领域。例如,在目前发展很 快的多媒体数据库领域中,往往需要能够在庞大的物理信号数据库中迅速搜索出 某个模式串的近似出现的算法。又如,在Internet的搜索引擎上完成某些模式 串的近似匹配搜索。近似串匹配问题的应用领域还包括信息检索、手写体识别、 病毒检测、图像压缩、数据挖掘和模式识别等。 在实际应用中,需要进行匹配查找的文本串往往包含有一些错误,这使得匹 配查找问题更加复杂化。例如,通过OCR采集到的文本信息不可避免地会包含一 定数量的错误,在用键盘进行打字输入时也经常会发生敲错键的错误。许多文本 数据库规模非常庞大,增长速度也非常快,不可能很好地控制其质量,完全保证 其数据的正确性,尤其是在互连网上,这个问题尤为突出。在数据库中,一个拼 写不正确的单词有可能永远都不会被检索到,除非提交的查询请求也包含有相同 的错误。近期的一项实验表明,在Web上由于这种文本信息的不正确性,大约有 10%的与查询请求相关的信息不能被检索出来。 人们采用了许多技术和方法来提高在文本串中查找出匹配位置的概率。为此 引入了扩展模式(extendedpattern)的概念,它拓宽了最基本的字符串精确匹配 查找,例如查找时不区分大小写字母,甚至可以查找正则表达式等。在所有的扩 展模式匹配查找问题中,能够很好地解决文本串和模式串中包含有错误这类问题 的,就是近似串匹配问题。在近似串匹配问题中,研究得最多的一类是基于 Levenshtein距离或称为编辑距离这种串距离函数的。编辑距离通常记作ed(), 它定义为将一个串变成另一个串所需要插入,删除和替换字符的最小个数。例如, ed(“amicable”,“admirable”)=2。 中国科学技术大学硕士学位论文第一章近似串匹配问题和近似串匹配算法 曾经有研究者做过这样两项实验。其中一项是在一个大小为1.2GB的文本集 合中检索一个很常见的英文单词,允许有一个或两个插入(对应于少一个字符), 删除(对应于多一个字符)或替换(对应于错一字符)操作。待检索的文本集合 是由从报纸杂志上节选的一些文章构成的。检索结果显示,拼写错误的单词(带 一个或两个错误)与拼写正确的单词数之比约为0.1%。将类似的实验拿到Web 上去做,上述比值上升为0.5%。这一实验结果表明,在实际应用中,待检索的 文本通常都包含有相当数量的错误,只有通过近似匹配查找工具,才能更好地完 成用户的查询请求。另一项实验是通过一个搜索引擎在Web上搜索一个不常见的 人名,允许发生的错误包括少一个字母或者有两个相邻的字母发生了交换。搜索 结果显示,如果只考虑精确匹配搜索,将有超过三分之一的与用户查询请求相关 的网页不能被搜索出来,这个比例是相当惊人的。这一实验结果同样证明了近似 匹配查找工具的重要性。 综上所述可以看出,研究近似串匹配问题,设计出快速有效的近似串匹配算 法不仅具有一定的理论价值,而且具有非常重要的实际意义。 1.2近似串匹配问题描述 简单地说,近似串匹配问题就是在文本串和模式串可能包含有错误的情况 下,在一个文本串中找出一个模式串的所有出现位置。具体地可以描述如下:给 定一个长度为m的模式串P,一个长度为n的文本串T,以及一个近似匹配允许 的最大错误(或误差)数k,在文本串T中找出所有的位置J,使得存在某个子 串T。.与模式串P发生最多带k个错误的匹配。 值得注意的是,近似串匹配最后返回的是匹配的结束位置,之所以这样做 是因为与模式串发生近似匹配的文本段长度是不固定的。同样,也可以返回匹配 的起始位置作为结果,但一般还是按照传统的做法返回匹配的结束位置。 在本论文讨论的近似串匹配问题中,一般假定文本串非常长,而模式串的长 度相对于文本串的长度来说是很小的,一般情况下,模式串的长度在几十字符以 内。这样的假定与文本检索问题的情况非常符合,因此本论文讨论的近似串匹配 算法比较适用于文本检索问题。近似串匹配问题中另一个重要的参数是误差率, 即近似匹配允许的最大误差数k与模式串长度m的比值。在实际应用的各种问题 中,误差率通常都是很小的,一般在0.1到0.3之间。误差率越高,也就是说允 许的错误数越多,那么发生近似匹配的概率就会越大,找出的匹配位置越多。而 实际上,这往往是不需要的,因为在实际问题中,文本串和模式串中包含的错误 中国科学技术大学硕士学位论文 第一章近似串匹配问题和近似串匹配算法 毕竟是少数,增大误差率的值,匹配搜索将会返回更多的成功匹配位置,而实际 上其中有许多并不是查询请求真正需要的,这将降低匹配结果的准确率。由此可 见,误差率比较小的假定是符合实际问题需要的。 1.3近似串匹配问题的相关概念 1.近似串匹配问题的正规定义。 在上节中,我们将近似串匹配问题描述为:在文本串中找出所有与模式串发 生最多带k个误差(differences)或称为错误(errors)的匹配的结束位置。 下面我们给出该问题的一个更加正规的定义。 在后面的讨论中,我们有如下约定:用S,x,y,z,v,w表示任意字符串, 而a,b,C,…表示任意字符。对于任意字符串S+,记S的长度为lSl,而 S.表示字符串S的第i个字符,i{1,ISI)。记s,.=s。s。…S。。空串则用e表 令是一个大小为O(O=I)的有限字母表,T+是一个长度为n(n=lTl)的文本串,P+是一个长度为m(m=lP1)的模式串,kEN是近似匹配允许的最 大误差数,d:++--)N是串距离函数。近似串匹配问题定义为:给定T,P, k和d0,在文本串T中找出所有这样的位置J,使得d(T。.。P)k。 2.串距离函数、编辑操作与编辑距离。 串距离函数d0定义为:串X与串y的距离d(X,Y)是指将串x变成串Y所 需要经过的一系列编辑操作的代价之和的最小值。在上一章中讲过,通常每个编 辑操作被赋予一个正整数作为它的代价值。串距离函数的定义表明,按照某个编 辑操作序列对串x进行变换,可以用最小的代价值将串X变成串Y,这个代价值 就被定义成串x与串Y的距离。如果通过任何编辑操作序列都不能将串x变成串 Y,那么串x与串Y的距离为无穷大,即d(x,Y)=一。 最常见的编辑操作有如下三种: (1)插入:向串x中插入一个字符。例如,向串X=VW中插入一个字符a可 以得到串x’=vaw。 (2)删除:从串x中删除一个字符。例如,从串X=VRW中删除一个字符a 可以得到串X’=VW。 (3)替换:将串X中的一个字符替换成串Y中的一个不同的字符。例如,将 中国科学技术大学硕士学位论文 第一章近似串匹配问题和近似串匹配算法 串x=vaw中的字符a替换成字符b可以得到串x’=vbw。 最常见的串距离函数一般有如下几种: Levenshtein距离,或称为编辑距离(editdistance)允许有插入、删除和替换操作,三种操作的代价值均为1。在这种情况下, 串X与串Y的距离可以重新定义为:将串x变成串Y所需要的最少编辑操作(包 括插入、删除和替换操作)的个数,称为Levenshtein距离或编辑距离。采用编 辑距离作为串距离函数的近似串匹配问题一般被称为最多带k个误差的串匹配 问题,或简称为k-differences问题。编辑距离具有对称性,并且满足04d(x, y)max(1Xl,Iy1)。 Hamming距离只允许有替换操作,其代价值为l。采用Hamming距离作为串距离函数的近 似串匹配问题一般被称为最多带k个不匹配的串匹配问题(stringmatching withatmostk mismatches)。Hamming距离也具有对称性,并且只要有Ixl=IYl, 则Hamming距离总是有限的,它满足04d(X,y)IX】。 Episode距离只允许有插入操作,其代价值为1。这个串距离函数不是对称的,只通过插 入操作可能无法将串X变成串y。因此d(x,y)=lyI一(xl或oo。 最长公共子序列距离只允许有插入和删除操作,两种操作的代价值均为1。最长公共子序列距离 具有对称性,并且满足04d(x,Y)JX+IYr。 除了Episode距离以外,其它几种串距离函数都具有对称性,这是因为插 入和删除这两种操作是互逆的,而替换操作本身是可逆的。向串x中插入一个字 符相当于从串y中删除一个相应的字符,反之亦然;将串x中的一个字符a替换 成串Y中的另一个字符b与将串Y中的字符b替换成串x中的相应字符a效果是 一样的。 目前,近似串匹配问题的研究大都采用编辑距离(editdistance)作为串距 离函数,编辑距离一般记作ed()。在下一章中,我们将对传统编辑距离的定义 进行扩展,在它所允许的编辑操作中加入第四种操作——换位,其代价值也为1。 我们把这样定义的编辑距离称为扩展编辑距离,基于扩展编辑距离的近似串匹配 问题则称为扩展近似串匹配问题,或扩展的k-differences问题。相应地,把基 于传统编辑距离的近似串匹配问题称为一般近似串匹配问题,或一般的 k—differences问题。 中国科学技术人学硕上学位论文 第一章近似串匹配问题和近似串匹配算法 1.4一般近似串匹配问题的串行算法 近似串匹配问题的一类最经典的算法就是动态规划算法。这类算法的优点是 思想简单,灵活性好,一般可以适用于各种不同的串距离函数,不足之处是在实 际应用中往往速度比较慢。 下面介绍两个非常经典的动态规划算法”1。 1.4.1最平凡的动态规划算法 该算法的基本思想是:根据文本串T[1,n]和模式串P[1,m]计算一个矩阵 与文本串T的任意以t,结尾的子串之间的最小误差个数(即最小编辑距离)。显然,如果D[m,j]k,则表明在文本串T的t。处有一个最多带k个误差的匹配。 图1.1是文本串为GGGTCTA,模式串为GTTC,k=2时,利用上述算法计算出 的D矩阵。由于D[4,4]=2,D[4,5]-l,D[4,6]=2,D[4,7]=2,所以在文本 串的t。,t。,t。和t,处存在最多带2个误差的近似匹配,t。,t。,t。,t,是这些近 似匹配的结束位置。 图1.1:文本串为GGGTCTA,模式串为GTTC,k=2时的D矩阵在该算法中,D[i,j】由以下公式计算 其中,6(P,,t,)=0,如果Pi=t,:否则,6(P。,t。)=1。可以看出,D[i,j]的计算是通过递推方式进行的。D[0,j]对应于模式串为空 串,而文本串长度为j的情况,显然,空串不需要任何编辑操作就能在文本串的 任何位置处匹配,所以DCO,j卜0。D[i,0]对应于模式串长度为i,而文本串为空 中国科学技术大学硕士学位论文 第一章近似串匹配问题和近似串匹配算法 串的情况,此时,至少需要对模式串进行i次删除操作才能与文本串(空串)匹 配,所以D[i,O]=i。在计算D[i,J]时,D[i-I,j],D[i,j-1],D[i—l,j—1]都已 计算出,D[i一1,j]+l,D[i,j-1]+1,D[i-1,j一1]+5(P。,t。)分别对应于对模式串 进行插入、删除、替换操作的情况,由于D[i,j]是最小编辑距离,所以取三者 中的最小值。 显然,该算法的时间复杂为D细形。 1.4.2 Ukkonen的动态规划算法 本小节介绍E.Ukkonen于1983年提出的一个近似串匹配问题的动态规划算 法,其时间复杂度与上小节介绍的动态规划算法一样,也是0(ran),m和n分别 是模式串和文本串的长度。 在该算法中,引入了对角线d的概念。对角线d是指矩阵D中满足j—i=d 的那些矩阵元素D。构成的对角线,其中矩阵D的定义与上小节中的相同。 与上小节介绍的动态规划算法不同,该算法不是直接计算矩阵 D[O.-.m,O…n],而是计算另一个矩阵L,其矩阵元素L。的定义如下:给定一个 误差数e和矩阵D的一条对角线d,L。表示的是对角线d上最后一个出现的e 值所在行的行号,也就是说,如果有Dlj=e且D。在对角线d上,并且不存在i’ >i满足上述两个条件,则L“=i。简言之,Ld。=max{i|Oim使得Dii+d=e)。 L。的定义说明了以下两点: a)e是模式串P的前缀子串PP。…p。与文本串T的任意以t。。结尾的子串之间 的最小误差个数。 b)PLge*ltLd。。否则有DLde+'Lde*d+l=e,也就是说,对角线行对应 的元素值仍为e,这与L。取最大值的定义矛盾。 对于k—differences问题,显然只需要计算矩阵L中那些满足ek的L。 中国科学技术大学硕士学位论文第一章近似串匹配问题和近似串匹配算法 如果某个L“=m,且ek,则表明在文本串T的t。,。=t。+。处有一个最多带k个误差的匹配。 矩阵L的元素L“的计算同样也是通过递推的方式进行的。假定对所有的误 差数x<e和所有的对角线y,L。的值已经计算出。令i=L。,也就是说,i是满 足Di.i:e且D。在对角线d上的最大行号。由上节的算法可知,D。的值(D。=e) 是通过以下的一个或多个矩阵元素的值递推得到的: (a)Di-j-=e一1且ptt。:(D。。.是D。在对角线d上的前驱元素) 或者Dij-I=e—l;(D。一-是D。在第i行上的前驱元素,D。:在对角线d—l上) 或者D.一。=e—l。(D一.。是D。在第J列上的前驱元素,D。.,在对角线d+l上) 这说明Du值的计算可以按如下方式逆推:首先沿着D。在对角线d上的前驱元素一直向上,此时遵循情况(b),直到情况(a)第一次出现。 将上述过程逆过来进行就可以得到计算L。值的算法如下: 1.初始化 fora11 d,0dn,Ld_l:=一l fora11 d,一(k+1)d一l,L….:=Id|_1,L“”。:=ld|_2 forall e,一lek,Ln.1。:一1 2.fore:=Otokdo ford:2一e tondo 3.row::max(L“一l+l,L.H,Ld+l。I+1) row:=min(FOW,m) 4.whilerow<mandrow+d<nand dorow:=row+l 5.Ld。:=row 6.if Ld.o=m print“Thereisanoccurrence ending 从上面的算法可以看出,实际上有row=max(L,1+l,Ld_l,H,Ld*{e-i+1) 中国科学技术大学硕士学位论文 第一章近似串匹配问题和近似串匹配算法 Ld:row+p。r—P。与t r01+d+i'""t。的最长公共前缀串的长度。 有两点需要说明一下。首先,矩阵D满足如下性质:D。=D。,。或者 D..-D.。。+1,二者必居其一,这个性质E.Ukkonen在他的文章里已经证明过。其 次,在矩阵D中,对角线d上满足d>n—m+k+l和d<一k的元素显然不符合 k—differences问题的要求,可以不予考虑。 图13是文本串为GGGTCTA,模式串为GTTC,k=2时,利用上述算法计算出 L矩阵。 N.1 图1.3:文本串为6GGTCTA,模式串为GTTC,k=2时的L矩阵E.Ukkonen动态规划算法的时间复杂度是0(mn),m和n分别是模式串和文 本串的长度。在该算法中一共计算了n+k+l条对角线上的L。值,对于每条对角 线,变量row最多可以取m个不同的值,因此时间复杂度为0(ran)。 中国科学技术人学硕十学位论文 第二章带有换位操作的近似串匹配问题的过滤算法 第二章带有换位操作的近似串匹配问题的过滤算法 本章首先对带有换位操作的近似串匹配问题进行了定义,然后给出了该问 题的一个动态规划算法,接着详细阐述了我们针对该问题设计的一个快速的串行 过滤算法,并对算法进行了理论分析,最后给出了实验结果和分析。 2.1概述 串匹配问题是计算机科学中的一个基本问题,也是复杂性理论中研究得最 广泛的问题之一。它在文本检索、信号处理、计算生物学、图像处理、模式识别 等诸多领域中都有着广泛的应用。因此,研究并设计快速的串匹配算法具有重要 的理论价值和实际意义。 按照匹配是否允许有错误来划分,串匹配问题可以分为精确串匹配和近似 串匹配两大类。精确串匹配问题要求模式串与文本串的子串完全匹配,不允许有 错误。该问题的两个最著名的算法是线性的KMP算法和亚线性的Boyer-Moore 算法。然而在许多实际情况中,并不要求模式串与文本串的子串完全精确地匹配, 因为模式串和文本串都有可能并不是完全准确的。例如,在检索文本时,文本中 可能存在一些拼写错误,而待检索的关键字也可能存在输入或拼写错误。在这种 情况下的串匹配问题就是近似串匹配问题,该问题可大致描述为:按照一定的近 似标准,在文本串中找出所有与模式串近似匹配的子串。近似串匹配问题的算法 有很多,按照研究方法的不同可大致分为动态规划算法,有限自动机算法,过滤 算法等。但上述所有算法都是针对一般近似串匹配问题的,也就是只允许有插入、 删除、替换这三种操作的情况。在本章中,我们还考虑了另外一种很常见的错误 ——换位,即,文本串或模式串中相邻两字符的位置发生了交换,这是在手写和 用键盘进行输入时经常会发生的一类错误。为修正这类错误,本章引入了换位操 作,讨论了允许有插入、删除、替换和换位四种操作的扩展近似串匹配问题,结 合过滤算法的思想,给出了该问题的串行过滤算法,并分析了算法的时间复杂度。 在误差率a很小的情况下,该串行过滤算法的平均时间复杂度为O(kn+m),其中 rl和m分别是文本串和模式串的长度,k是近似匹配允许的最大误差数。 2.2问题描述 给定两个长度分别为m和rl的字符串A[1,m】和B[I,n],a.,bj(1im, 1jn,是字母表),串A与串B的编辑距离是指将串A变成串B所需要的 中同科学技术大学硕十学位论文 !g--e带有换位操作的近似串匹配问题的过滤算法 最少编辑操作的个数。最常见的编辑操作有三种:插入:向串A中插入一个字 符;删除:从串A中删除一个字符;替换:将串A中的一个字符替换成串B中 的一个字符。其中,每个编辑操作修正的串A与串B之间的一个不同之处称为 一个误差或者错误。 最多带k个误差的串匹配问题(简称为k-differences问题)可描述如下:给 定一个长度为n的文本串T=t卜..tn,一个长度为m的模式串P=pI.pm,以及整 数k(k1),在文本串T中进行匹配查找,如果T的某个子串th.t.与模式串P 的编辑距离小于等于k,则称在tj处匹配成功,要求找出所有这样的匹配结束位 置tj。 在本章中,我们还考虑了另外一种很常见的编辑操作,即换位:将串A中 的两个相邻字符进行交换。该操作用于修正相邻两字符位置互换的错误。一个换 位操作相当于一个插入操作加上一个删除操作。但是,当近似匹配允许的最大误 差数k一定时,允许有换位操作的情况较之不允许有换位操作的情况,往往能够 找出更多的匹配位置。下面举一个例子来说明这一点。 例:假定文本串T=abcdefghij,模式串P=bxcegfhy,k=4,我们来看看在文串 的第9个字符处是否存在最多带4个误差的匹配。 首先考虑允许有换位操作的情况,文本串与模式串的对应关系如下: tt t2 t3 t4 t5 t6 t7 ts t9 tto ,,,4个位置分别对应于删除、插入、换位和替换操作,可见在t9处确实存在最多带4个误差的匹配。 再来看看不允许有换位操作的情况,对应关系如下: t1 t2 t3 t4 t5 t6 t7 t8 t9 tlo 可以看出,在t9处不存在最多带4个误差的匹配,因为匹配成功所需要的最少编辑操作个数为5。口 由此可见,允许有换位操作的近似串匹配算法比以往未考虑换位操作的算 法更加实用有效。尤其是在文本检索和手写体识别等实际应用中,新算法的检索 成功率和识别率更高,准确性更好,功能更强。 中同科学技术大学硕I-学位论文 第二章带有换位操作的近似串!!垦塑壁塑堇鲨簦鲨 在本文后续章节中,为方便起见,我们将带有换位操作的k-differences问题 又称为扩展近似串匹配问题,或扩展的k-differences问题。相应地,将基于传 统编辑距离的近似串匹配问题称为一般近似串匹配问题,或一般的 k—differences问题。 2.3带有换位操作的近似串匹配问题的动态规划算法 我们首先来回顾一下一般近似串匹配问题(即一般的k—differences问题)的 动态规划算法。 一般的k-differences问题的一个最著名的算法采用动态规划的技术,可以在 O(mn)时间内解决该问题。其基本思想是:根据文本串T【l,n】和模式串PB,In]计 算矩阵D[0…1TI,0…n】,其中D[iJ](0im,0jn)是模式串P的前缀子串Pl…Pi 与文本串T的任意以tt结尾的子串之间的最小误差个数(即最小编辑距离)。显 然,如果D[mj]k,则表明在文本串T的处存在最多带k个误差的匹配。 D[ij1由以下公式计算: D[ij]=min(D[i一1j]+l,D[ij一1】+1,D[i—lJ—l】+6(pi,々))其中,8(pi,9=0,如果pi=tj;否则,6(pi,)-1。 可以看出,D0j]的计算是通过递推方式进行的。D[0J】对应于模式串为空串, 而文本串长度为i的情况,显然,空串不需要任何编辑操作就能在文本串的任何 位置处匹配,所以D【oJ】=o。D【i,o】对应于模式串长度为i,而文本串为空串的情 况,此时,至少需要对模式串进行i次删除操作才能与文本串(空串)匹配,所 以D[i,0]=i。在计算Dlij]时,Dli-1加,D[ij 1],D[i-1j一1]都已计算出,D[i一1J]+l, D[id-1]+1,D[i_1J-1]+8(pi,々)分别对应于对模式串进行插入、删除、替换操作的 情况,由于D[id]是最小编辑距离,所以取三者中的最小值。 上述动态规划算法只考虑了插入、删除、替换三种编辑操作,但很容易将 其推广到允许有换位操作的情况。考虑D嘶]的计算,若Pi.api=titi.1,则D[ij]的 一个可能取值是O[i一2j.2】+l,即,将pi.1pi变成titi.1只需要进行一次换位操作, 从而最小编辑距离只增加l。由此可对上述算法进行简单的修改,使之适用于允 许有插入、删除、替换和换位四种编辑操作的情况。 算法2.1:带有换位操作的近似串匹配问题的动态规划算法 输入:文本串T[I,n】,模式串P[1,m】,近似匹配允许的最大误差数k 输出:所有匹配位置 14 中图科学技术人学硕七学位论文 第二章带有换位操作的近似串匹配问题的过滤算法 begin(1)forj=0 tondo D[OJ]一O endfor endfor(3)fori=l tomdo (3.1)forj=1 tondo (3.1.1)if(P[i]=TD])then D[ij]=min(D[i一10]+1,D[ij 1]+1,D[i—lJ—l】) else D[iJ]=min(D[i2j一2]+1,D[i—lJ]+l,D[ij—1]+1) else D[ij]=min(D[i—lo]+l,D[ij—l】+1,D[i一1i—l】+1) endif endif (3.1.2)if(i--an&&D【U]<=k)then 找到P在T中的一个最多带k个误差的近似匹配,输出匹配结 束位置j; endif endfor endfor end 显然,该算法的时间复杂度为O(mn)。 2.4带有换位操作的近似串匹配问题的过滤算法 2.4.1算法的基本原理 经典的动态规划算法在实际应用中速度很慢,往往不能满足实际问题的需 要。为此,s.Wu和U.Manber,GonzaloNavarro和Ricardo Baeza—Yate等人先后 提出了多个基于过滤思想的更加快速的近似串匹配算法。这些算法一般分为两 步:首先按照一定的过滤原则搜索文本串,过滤掉那些不可能发生匹配的文本段; 然后再进一步验证剩下的匹配候选位置处是否真的存在成功匹配。由于在第一步 中已经滤去了大部分不可能发生匹配的文本段,因此大大加速了匹配查找过程。 在实际应用中,这些过滤算法一般速度都很快。但是,这些算法都只研究了一般 中国科学技术大学硕上学位论文 第二章带有换位操作的近似串匹配问题的过滤算法 的k-differences问题,即只允许有插入,删除和替换这三种编辑操作的情况。下 面我们针对本文定义的扩展近似串匹配问题,讨论加入换位操作后的 k—differences问题的过滤算法。 我们的过滤算法基于这样一种直观的认识:若模式串P在文本串T的t。处 有一个最多带k个误差的近似匹配,则P中必然有一些子串是不带误差地出现在 T中的,也就是说,P中必然有一些子串与T中的某些子串是精确匹配的。 定理:在允许有换位操作的最多带k个误差的串匹配问题中,如果将模式串P 划分成2k+l段,那么对于P在T中的每一次近似出现(最多带k个误差), 这2k+l段中至少有一段是不带误差地出现在T中的。 证明:这个定理的证明很简单。 试想,将k个误差,也就是对模式串P所做的k个编辑操作,分布于2k+1 个子模式串中。由于一个插入,删除或替换操作只能改变一个子模式串, 而一个换位操作有可能改变两个子模式串(例如,在子模式串i的最后一 个字符与子模式串i+l的第一个字符之间进行一次换位操作),所以k个 编辑操作最多只能改变2k个子模式串。这就是说,在这2k+1个子模式串 中,至少有一个是未被改变的,它不带误差地出现在文本串T中,与T 的某个(些)子串精确匹配。

  带有换位操作的近似串匹配算法及其并行实现,字符串近似匹配算法,近似匹配算法,最短并行调度近似比,近似算法,并行算法,并行算法导论,算法与并行计算,vlookup近似匹配,并行算法的设计与分析

本文链接:http://storkroadfarm.com/jinsipipei/238.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top