动态规划 近似串匹配.ppt

1、1计算机算法计算机算法设计与分析导论设计与分析导论南开大学南开大学 计算机科学与技术系计算机科学与技术系刘璟2v 7.1 动态规划的基本原理动态规划的基本原理v 7.2 最优二分搜索树最优二分搜索树(Optimal Binary Search Tree)v 7.3 近似串匹配近似串匹配(Approximate String Matching)问题问题37.1 动态规划的基本原理动态规划的基本原理v7.1.1 Fibonacci数的计算数的计算 Fibonacci数又称为数又称为Fibonacci数列，定义为：数列，定义为：F0=0,F1=1,Fn=Fn-1+Fn-2(n 2)计算计算Fibon

2、acci数列可由递归函数数列可由递归函数fibo完成。完成。递归函数递归函数fibo 由此可知，函数由此可知，函数fibo的计算量随的计算量随n的增加而急剧增加，的增加而急剧增加，n=6时时需需25次调用，次调用，n=10时需时需177次调用，次调用，n=15时需时需1974次调用。次调用。进一步的研究表明，调用次数进一步的研究表明，调用次数 An=2Fn+1-1，其中，其中 ，。可以估计，可以估计，其计算量是，其计算量是n的指数函数。的指数函数。)(nnF 618.1)15(21 )2()(/2 nnAnT 4从从Fig.7.1中可以看出，大量的调用过程是重复的，此算法可中可以看出，大量的调

3、用过程是重复的，此算法可以改进。以改进。函数函数fibo的改进函数的改进函数fib这个程序的时间代价为这个程序的时间代价为O(n)阶。阶。5v7.1.2 矩阵连乘的顺序问题矩阵连乘的顺序问题 1.一个实例一个实例四个矩阵四个矩阵A1、A2、A3、A4相乘，设其阶数分别为相乘，设其阶数分别为A1：301，A2：140，A3：4010，A4：1025。因为矩阵相乘满足结合因为矩阵相乘满足结合律律，所以可有下面五种（实际为六种）所以可有下面五种（实际为六种）不同的运算次序，而且不同的运算次序所需的元素间乘法的不同的运算次序，而且不同的运算次序所需的元素间乘法的次数不同，如下面所列：次数不同，如下面所

4、列：(A1 A2)A3)A4 30140+304010+301025=20700(A1 A2)(A3 A4)30140+401025+304025=41200(A1(A2 A3)A4 14010+30110+301025=8200A1(A2 A3)A4)14010+11025+30125=1400A1(A2(A3 A4)401025+14025+30125=117506五种运算次序的计算结果相同，但所花费的时间代价相差极五种运算次序的计算结果相同，但所花费的时间代价相差极大。如果某一应用问题需要经常进行矩阵连乘运算，应首先大。如果某一应用问题需要经常进行矩阵连乘运算，应首先确定最优的矩阵连乘的

5、次序。确定最优的矩阵连乘的次序。2.最优矩阵连乘次序（最优矩阵连乘次序（Optimal Matrix Multiplication Order）问题问题给定给定n个矩阵个矩阵A1,A2,.,An的维数为的维数为d0,d1,d2,.,dn，即：即：Ai的维数的维数为为di-1di(1in)。求一种连乘次序，使得计算时所需的元素求一种连乘次序，使得计算时所需的元素乘法的总数最少。乘法的总数最少。3.算法的思路算法的思路如同上面实例中所做的那样，把所有可能的运算次序所需的如同上面实例中所做的那样，把所有可能的运算次序所需的计算量全计算出来，选择最小者，这种方法称为穷举法。不计算量全计算出来，选择最小

6、者，这种方法称为穷举法。不过，当过，当n值较大时，这种方法的计算量过高。值较大时，这种方法的计算量过高。n个矩阵相乘应个矩阵相乘应有（有（n-1）！）！种不同的运算次序，计算每种运算次序所需的时种不同的运算次序，计算每种运算次序所需的时间代价需要间代价需要2(n-1)次乘法和次乘法和n-2次加法运算。当次加法运算。当n=11时需要时需要7257.6万次乘法万次乘法。7由于由于不能事先决定最初在何处进行划分，所以分治策略难以不能事先决定最初在何处进行划分，所以分治策略难以解决这个问题。解决这个问题。但但这个问题满足最优子结构性质：即，当选这个问题满足最优子结构性质：即，当选择了进行最外层相乘的位

7、置之后，其左右两边的矩阵相乘序择了进行最外层相乘的位置之后，其左右两边的矩阵相乘序列都必须是时间代价最小的，可以考虑采用贪心策略。列都必须是时间代价最小的，可以考虑采用贪心策略。一种使用贪心策略的解决方法是：每次优先选择其相乘代价一种使用贪心策略的解决方法是：每次优先选择其相乘代价最小的两个矩阵。例如在本实例中，最小的两个矩阵。例如在本实例中，A1A2A3A4有三个可能有三个可能的相邻矩阵乘积，其中的相邻矩阵乘积，其中A2A3的代价的代价400为最小。那么首先完为最小。那么首先完成成A2A3，在余下的两个可能的相邻矩阵乘积中：在余下的两个可能的相邻矩阵乘积中：30110和和11025相比较，后

8、者较小。于是得到的解为相比较，后者较小。于是得到的解为A1(A2 A3)A4)，与穷举法的最优结果一致。不过该贪心策略不能保证得与穷举法的最优结果一致。不过该贪心策略不能保证得到最优解。例如反例：到最优解。例如反例：矩阵矩阵A、B、C，维数分别为：维数分别为：401，120，2050，(AB)C 40120+402050=40800 A(BC)12050+40150=30008另外一种采用贪心策略的方法是，对于另外一种采用贪心策略的方法是，对于n个矩阵个矩阵A1.An的维数的维数序列序列d0.dn，每次从每次从d1.dn-1中取最大值中取最大值di，首先进行首先进行Ai与与Ai+1的乘法使最大

9、的维数仅参加一次乘法运算，这样做有可能有的乘法使最大的维数仅参加一次乘法运算，这样做有可能有利于减少矩阵连乘的计算量。使用这一策略，对上面的两个利于减少矩阵连乘的计算量。使用这一策略，对上面的两个简单实例进行计算，其结果都是正确的。但是这个贪心算法简单实例进行计算，其结果都是正确的。但是这个贪心算法仍然不能总是找出最优解。仍然不能总是找出最优解。可以从可以从Fibonacci数的计算得到启发，采用动态规划的方法设数的计算得到启发，采用动态规划的方法设计算法。最简单的递归算法描述如下：计算法。最简单的递归算法描述如下：递归算法递归算法MinCost nknkdddnkMinCostkMinCos

10、tnnMinCost01,1,1min1,0,19此算法的递归过程中，存在与此算法的递归过程中，存在与fibo函数相似的地方，即会有大函数相似的地方，即会有大量的重复调用，其调用关系如量的重复调用，其调用关系如Fig7.2所示，其中所示，其中n=4。10递归函数递归函数MinCost的调用过程在的调用过程在n=4时共时共27次，次，n=5时为时为81次，次，n=6时为时为249次，当次，当n增大时，计算量急剧增加。如果采用自底增大时，计算量急剧增加。如果采用自底向上的计算方式，函数向上的计算方式，函数MinCost(1,n)的计算代价将大大减少。的计算代价将大大减少。其计算过程为：其计算过程为

11、：MinCost(1,1)=MinCost(2,2)=MinCost(3,3)=MinCost(4,4)=0MinCost(1,2)=MinCost(1,1)+MinCost(2,2)+d0d1d2=30140=1200类似地，类似地，Mincost(2,3)=d1d2d3=14010=400；Mincost(3,4)=d2d3d4=401025=10000；在第二步计算在第二步计算MinCost(1,3)和和MinCost(2,4)，最后计算最后计算MinCost(1,4)。由此可以看出，由此可以看出，n=4时函数时函数MinCost(1,4)的计算量是的计算量是4+3+2+1=10次，次，

12、n=5时为时为15次，次，n=6时为时为21次。次。114.矩阵连乘的矩阵连乘的DP算法算法设矩阵个数为设矩阵个数为n，维数为维数为dimn+1（n+1个值），同时用数组个值），同时用数组MultiOrdern保存程序运行时得到的最优乘法顺序，可得：保存程序运行时得到的最优乘法顺序，可得：算法算法7.1 最优矩阵连乘算法最优矩阵连乘算法 MatrixOrder 函数函数MatrixOrder返回最优连乘次序所需的最小时间代价，同返回最优连乘次序所需的最小时间代价，同时将最优次序保存在数组时将最优次序保存在数组MultiOrder中，从此数组中得到最中，从此数组中得到最优乘法次序的算法为：优乘法

13、次序的算法为：ExtractOrder 用上述算法计算本节给出的实例，其结果为：用上述算法计算本节给出的实例，其结果为：最小代价为最小代价为cost0n=1400，最优乘法次序最优乘法次序MultiOrder1.3=2,3,1，即即A1(A2A3)A4)。*0*100000*6504000*140070012000*cos t *1*31*321*1111*last12v7.1.3 动态规划（动态规划（DP）算法的基本条件）算法的基本条件 1.最优子结构性质最优子结构性质最优化原理。最优化原理。其特征是：当要求一个问题的最优解时，构成其特征是：当要求一个问题的最优解时，构成整体解的子问题的解也

14、必须是最优的。整体解的子问题的解也必须是最优的。例如，例如，为了使计算为了使计算n个个矩阵连乘矩阵连乘A1A2.An的代价最小，无论最后一次乘法的位置的代价最小，无论最后一次乘法的位置k在何处（在何处（1kn），），其左右两部分其左右两部分A1.Ak，Ak+1.An的乘积的乘积也必须是代价最小的。这也可用最短路径问题来说明：若也必须是代价最小的。这也可用最短路径问题来说明：若V1V2.Vn是一条从是一条从V1到到Vn的最短路径，那么这条路径的任何的最短路径，那么这条路径的任何一段，比如从一段，比如从Vi到到Vj（1ijn）也必须是一条最短路径。也必须是一条最短路径。2.子结构重迭性质子结构重迭

15、性质 简单的递归程序解法都是一种自顶向下进行递归分解的过程，简单的递归程序解法都是一种自顶向下进行递归分解的过程，其中包含了大量的重复调用，在这种情况下采用动态规划方其中包含了大量的重复调用，在这种情况下采用动态规划方法特别有效。因此，问题法特别有效。因此，问题中中这种这种子结构重迭性质子结构重迭性质是采用动态是采用动态规划方法的另一个条件。动态规划算法的一个特征是自底向规划方法的另一个条件。动态规划算法的一个特征是自底向上，它可以大幅度减少计算代价。上，它可以大幅度减少计算代价。13解决这类具有子结构重迭性质的问题还有另外一种被称为解决这类具有子结构重迭性质的问题还有另外一种被称为备备忘录（

16、忘录（memorization）方法的自顶向下的递归方式。方法的自顶向下的递归方式。其思想是其思想是：由程序设置由程序设置“备忘录备忘录”，每计算出一个新的子结，每计算出一个新的子结构的解时，都保存起来。当遇到一次递归时，判断是否已经构的解时，都保存起来。当遇到一次递归时，判断是否已经计算，如果已经计算，只需取出先前保存的结果即可。这种计算，如果已经计算，只需取出先前保存的结果即可。这种方式与动态规划算法相比，要增加保存与检索中间结果的代方式与动态规划算法相比，要增加保存与检索中间结果的代价。价。算法算法7.2 求求Fibonacci数的备忘录算法数的备忘录算法 MemoFib 147.2 最

17、优二分搜索树最优二分搜索树（Optimal Binary Search Tree）v7.2.1 OBST问题问题 二分字典树是构造数据存储与检索系统的一种方便形式，例二分字典树是构造数据存储与检索系统的一种方便形式，例如一个翻译系统需要一个字典数据库。可以按照单词的字典如一个翻译系统需要一个字典数据库。可以按照单词的字典顺序构造一个二分搜索树，能获得较高的搜索效率。顺序构造一个二分搜索树，能获得较高的搜索效率。假定字典中只包含假定字典中只包含15个单词：个单词：and，cabbage，come，has，king，of，pig，ring，said，talk，the，thing，time，walr

18、us，wing。按照字典顺序插入显然形成一个退化的二分树即线性链表，按照字典顺序插入显然形成一个退化的二分树即线性链表，其平均搜索代价是其平均搜索代价是(1+15)/2=8次单词比较。次单词比较。15采用采用Fig7.3中的二分搜索树，最多仅需中的二分搜索树，最多仅需4次比较，平均需要次比较，平均需要(1+22+34+48)/15=3.17次比较，因此完全二分搜索树具次比较，因此完全二分搜索树具有最小的平均搜索代价。有最小的平均搜索代价。16在实用系统中，还要考虑到不同的单词在实际使用过程中被在实用系统中，还要考虑到不同的单词在实际使用过程中被搜索的概率不同，例如，搜索的概率不同，例如，and

19、、the等经常被搜索，而等经常被搜索，而pig、cabbage等则很少被搜索。因此若把等则很少被搜索。因此若把and、the放在树的最底层放在树的最底层必然增大词典的平均搜索代价，这时的必然增大词典的平均搜索代价，这时的平均搜索代价平均搜索代价应为：应为：即，二分搜索树即，二分搜索树T的平均搜索代价应为从根到各个单词节点在的平均搜索代价应为从根到各个单词节点在T中的路长中的路长Ci与其查找概率与其查找概率Pi乘积之和。当各个单词的查找概乘积之和。当各个单词的查找概率不同时，完全二分搜索树就不一定最优了。率不同时，完全二分搜索树就不一定最优了。例如，例如，假定词假定词典仅由典仅由4个单词个单词c

20、at、come、of、the组成，它们的查找概率分组成，它们的查找概率分别为：别为：cat:0.12，come:0.08，of:0.35，the:0.45 niiiCPTA1)(17由这四个单词可以组成许多种不同的二分字典树，由这四个单词可以组成许多种不同的二分字典树，Fig7.4中给中给出了其中的三个。出了其中的三个。按照上面给出的计算方法，三棵树（按照上面给出的计算方法，三棵树（a,b,c）的平均搜索代价的平均搜索代价分别为：分别为：(a)0.08+2(0.12+0.35)+30.45=2.37次比较；次比较；(a)0.35+2(0.08+0.45)+30.12=1.77次比较；次比较；(

21、a)0.35+2(0.12+0.45)+30.08=1.73次比较。次比较。18平均搜索代价的差别说明，不同的二分搜索树在一定的查找平均搜索代价的差别说明，不同的二分搜索树在一定的查找概率条件下，性能是不同的。概率条件下，性能是不同的。因此，在单词集合及其查找概因此，在单词集合及其查找概率给定的条件下，构造一个平均搜索代价最小的二分搜索树率给定的条件下，构造一个平均搜索代价最小的二分搜索树的意义是很明显的。的意义是很明显的。在实际问题中，还要考虑不成功的搜索在实际问题中，还要考虑不成功的搜索，即查找给定单词集，即查找给定单词集合之外的单词。合之外的单词。这时可以把二分搜索树加以扩充，例如这时可

22、以把二分搜索树加以扩充，例如Fig7.4Fig7.4中的中的(c)(c)，可以为这棵，可以为这棵4 4个节点的树增加个节点的树增加5 5个外部节点，个外部节点，形成一棵新树，如形成一棵新树，如Fig7.5Fig7.5所示。所示。其中其中4 4个内部节点表示单词集个内部节点表示单词集的的4 4个单词，个单词，5 5个外部节点则表个外部节点则表示检索其它单词时不成功的搜示检索其它单词时不成功的搜索路径。例如：搜索单词索路径。例如：搜索单词asas，将到达最左边的外部节点，其将到达最左边的外部节点，其代价为两次比较。代价为两次比较。19最优二分搜索树（最优二分搜索树（OBST）问题可以描述为：问题可

23、以描述为：已知：已知：n个单词的查找概率个单词的查找概率p1,p2,.,pn和对应于和对应于n+1个外部个外部节点的不成功查找概率节点的不成功查找概率q0,q1,q2,.,qn，。求：构造一种二分搜索树求：构造一种二分搜索树T，使平均搜索代价使平均搜索代价A(T)最小。最小。解这个问题最简单的方法是把由解这个问题最简单的方法是把由n个单词（节点）组成的所有个单词（节点）组成的所有二分搜索树的平均搜索代价全算出来，取其最小者。不过，二分搜索树的平均搜索代价全算出来，取其最小者。不过，4个单词的二分搜索树有个单词的二分搜索树有14种，种，7个单词的二分搜索树有个单词的二分搜索树有429种种就可知道

24、，就可知道，n较大时，这种方法是根本行不通的。较大时，这种方法是根本行不通的。v7.2.2 动态规划算法的思路动态规划算法的思路设设n个单词为个单词为a1,a2,.,an，则由它们构成二分搜索树则由它们构成二分搜索树T1,n可以表可以表示为示为Fig7.6的形式。其中的形式。其中ak(1kn)为为T1,n的根，其左子树的根，其左子树T1,k-1由由a1.ak组成，右子树组成，右子树Tk+1,n由由ak+1.an组成。组成。101 niiniiqp20用代价函数用代价函数Cost(low,high)表示由表示由alow.ahigh及相应的外部节点及相应的外部节点blow-1,blow,.,bhi

25、gh组成的二分搜索树的最小代价。特别地，当组成的二分搜索树的最小代价。特别地，当high=low-1时表示空树，时表示空树，Cost(i,i-1)=0。Cost(low,high,r)表示指定以表示指定以ar为根时，组成的二分搜索树的最为根时，组成的二分搜索树的最小搜索代价。小搜索代价。如果如果T1,n是最优的，那么是最优的，那么T1,k-1，Tk+1,n两个子树也必然是最优的，两个子树也必然是最优的，因此，因此，该问题具有最优子结构该问题具有最优子结构性质性质；另一方面，单词序列中；另一方面，单词序列中任意几个相邻单词组成的子树任意几个相邻单词组成的子树将同时出现在多个包含它们的将同时出现在

26、多个包含它们的更大的树中，因此，更大的树中，因此，子结构重子结构重迭迭性质也是很明显的。性质也是很明显的。T1,k-1是由a1至ak-1元素构成子树中最优者21权函数权函数W(low,high)表示相应二分搜索树的所有节点的搜索概表示相应二分搜索树的所有节点的搜索概率之和，称为该树的权：率之和，称为该树的权：特别地：特别地：W(i,i)=pi+qi-1+qi；W(i,i-1)=qi-1。（。（1in）。以上各式有如下的递推关系：以上各式有如下的递推关系：Cost(low,high,r)=pr+W(low,r-1)+Cost(low,r-1)+W(r+1,high)+Cost(r+1,high)

27、=W(low,high)+Cost(low,r-1)+Cost(r+1，high)Cost(low,high)=MinCost(low,high,r)|lowrhigh依照自底向上的顺序，依照自底向上的顺序，很容易很容易计算出计算出Cost(1,n)以及最优树的以及最优树的各级子树的根。各级子树的根。(注意路径的长度如何计算的注意路径的长度如何计算的,如如,根结点根结点r,在计算中最终结果为在计算中最终结果为pr*1,而其他结点而其他结点,如在根的下层如在根的下层,则计算两次为则计算两次为pj+pj=pj*2)highlowiihighlowiiqphighlowW1),(第i个单词为树的权第

28、i个单词前一个未找到的为树的权22v7.2.3 算法算法OBST已知：已知：n个单词个单词a1.an的成功与不成功查找概率分别为：的成功与不成功查找概率分别为：p1.pn，q0.qn。即：即：P1.n，Q0.n。求：求：由由a1.an组成的最优二分搜索树。为此设置二维数组组成的最优二分搜索树。为此设置二维数组Cnn，Wnn，Rnn。算法算法7.3 最优二分搜索树构造算法最优二分搜索树构造算法 OBST 算法算法OBST的结果是数组的结果是数组C和数组和数组R，其中其中C1n为求得的最为求得的最优二分搜索树的搜索代价，优二分搜索树的搜索代价，R中包含了构造该树的信息。中包含了构造该树的信息。假定

29、单词序列假定单词序列A1.n类型为类型为word，树节点的类型为：树节点的类型为：struct node word key;node*left,*right;可得到：可得到：由数组由数组R构造搜索树的算法构造搜索树的算法 BuildTree23v7.2.4 算法算法OBST的复杂度分析的复杂度分析算法算法7.3中，中，T(n)=O(n3)，再有再有T(n)=(n3)。算法算法BuildTree表面表面上看是一个双递归程序，但由于算法每调用一次即生成一个上看是一个双递归程序，但由于算法每调用一次即生成一个（内部）节点，因此至多调用（内部）节点，因此至多调用n次程序就结束，其复杂度是次程序就结束，

30、其复杂度是O(n)阶的。阶的。算法的空间代价主要体现在计算过程中所必需的二维数组，算法的空间代价主要体现在计算过程中所必需的二维数组，故有故有S(n)=(n2)。v7.2.5 讨论讨论1.DP算法应用于算法应用于OBST构造问题的效果非常明显。构造问题的效果非常明显。n个单词的个单词的二分字典树的个数是二分字典树的个数是n的一个增长很快的指数函数。例如，的一个增长很快的指数函数。例如，10个节点的二分字典树就有个节点的二分字典树就有16796种，因此穷举法是任何高速计种，因此穷举法是任何高速计算机都不能接受的。但算机都不能接受的。但DP算法把计算量降到了算法把计算量降到了(n3)阶，而且阶，而

31、且可以估计出可以估计出n3项的系数大约为项的系数大约为1/6，当，当n较大时其加速的倍数已较大时其加速的倍数已经是天文数字了。由此可以看出经是天文数字了。由此可以看出DP算法的强大威力。算法的强大威力。242.构造二分搜索树的问题与矩阵连乘的顺序问题十分相似，构造二分搜索树的问题与矩阵连乘的顺序问题十分相似，关键是代价函数递推关系的确定，这也是许多应用动态规划关键是代价函数递推关系的确定，这也是许多应用动态规划方法设计有效算法的共同之处。同时，由于问题的不同，处方法设计有效算法的共同之处。同时，由于问题的不同，处理细节时又是有差别的。理细节时又是有差别的。3.该算法仍然可以改进，该算法仍然可以

32、改进，D.Knuth提出了一个重要的改进方法，提出了一个重要的改进方法，把最核心的关系式：把最核心的关系式：Cost(low,high)=MinCost(low,high,r)|lowrhigh改进为：改进为：Cost(low,high)=MinCost(low,high,r)|R(low,high-1)rR(low+1,high)。也就是在算法也就是在算法7.3中的内层循环中的内层循环 for(r=low;r=high;r+).改变为改变为 for(r=Rlowhigh-1;r=Rlow+1high;r+).。25这一改动虽然使程序变化不大，但却明显这一改动虽然使程序变化不大，但却明显地地改

33、变了计算量。改变了计算量。这这可以通过一个简化实例来说明：设有可以通过一个简化实例来说明：设有100个单词个单词a1.a100，如如果每个单词的查找概率相同，则应有果每个单词的查找概率相同，则应有R199=50，R2100=51，即原算法变量即原算法变量r从从r=1到到r=100循环循环100次，改进次，改进之后变量之后变量r从从r=50到到r=51循环循环2次，计算量减少几十倍。次，计算量减少几十倍。改进后算法的时间复杂度可由下式估计，内层循环的计算次改进后算法的时间复杂度可由下式估计，内层循环的计算次数为：数为：因此算法因此算法7.3的时间复杂度为的时间复杂度为O(n2)。Knuth的改进

34、，使计算复杂度从的改进，使计算复杂度从(n3)降为降为(n2)。nsnsnnsnsRnsnRslowlowRslowlowRsnlow2221)1(11)111(11 26这一成果更为重要的部分是证明其结果的正确性，即证明：这一成果更为重要的部分是证明其结果的正确性，即证明：Rij-1RijRi+1j,直观上看是显然的，但严格证明却相当困难。直观上看是显然的，但严格证明却相当困难。4.关于二分字典树的研究还有许多成果，例如可以用贪心算关于二分字典树的研究还有许多成果，例如可以用贪心算法来构造几乎最优的二分字典树，还有最优二分分裂树法来构造几乎最优的二分字典树，还有最优二分分裂树（Optimal

35、 Binary Split Tree）、）、偏斜二分搜索树（偏斜二分搜索树（Biased Search Tree）、）、自调节二分搜索树自调节二分搜索树(Self-adjusting BST）等等。等等。277.3 近似串匹配问题近似串匹配问题（Approximate String Matching）v7.3.1 近似串匹配问题近似串匹配问题 设样本为设样本为P：p1p2.pm，文本为文本为T：t1t2.tn。K-近似匹配（近似匹配（K-approximate match）：对于非负整数对于非负整数K，样样本本P在文本在文本T中的中的K-近似匹配，是指近似匹配，是指P在在T中的包含至多中的包含

36、至多K个差个差别的匹配。别的匹配。这里所指的差别（这里所指的差别（difference）是指下列三种情况之一：是指下列三种情况之一：修改（修改（revise）：）：P与与T中的对应字符不同；中的对应字符不同；删去（删去（delete）：）：T中含有一个未出现在中含有一个未出现在P中的字符；中的字符；插入（插入（insert）：）：T中不含有出现在中不含有出现在P中的一个字符。中的一个字符。28例如，下面是一个包含上述三种差别的例如，下面是一个包含上述三种差别的3-近似匹配，一般的近似匹配，一般的情形是样本情形是样本P是正确的，文本是正确的，文本T中包含上述三类错误，一般称中包含上述三类错误，一

37、般称之为之为编辑错误编辑错误。事实上，能够指出上例中的两个字符串有三个差别，并不是事实上，能够指出上例中的两个字符串有三个差别，并不是一件容易的事，因为不同的对应方法可以得到不同的一件容易的事，因为不同的对应方法可以得到不同的K值。例值。例如，把两者从字符如，把两者从字符a开始，顺序一一对应，可以计算出有开始，顺序一一对应，可以计算出有6个个修改（修改（revise）错误。改变对应方法，就会产生不同的结论。错误。改变对应方法，就会产生不同的结论。因此应该指出，因此应该指出，P与与T为为K-近似匹配，包含下面两层含义：近似匹配，包含下面两层含义：1 二者的差别数至多为二者的差别数至多为K；2 差

38、别数是指二者在所有不同匹配对应方式下的差别数是指二者在所有不同匹配对应方式下的最小编辑错误最小编辑错误总数。总数。P:a p p r o x i m a t l yT:a p r o x i o m a l l y29因此，一般的因此，一般的K-近似匹配问题可以描述为：近似匹配问题可以描述为：已知：已知：字符串字符串P：p1p2.pm（称为称为Pattern），），字符串字符串T：t1t2.tn（称为称为Text），），和一个正整数和一个正整数K。求：求：样式样式P在文本在文本T上的上的K-近似匹配的第一次出现或所有出现。近似匹配的第一次出现或所有出现。在完全串匹配中，在完全串匹配中，P在在T

39、上的一次匹配检查十分简单，用至多上的一次匹配检查十分简单，用至多m次字符比较即可完成，问题的关键是确定一次匹配检查之次字符比较即可完成，问题的关键是确定一次匹配检查之后样本后样本P的移动方法。最简单的方法是移动一位，更巧妙的方的移动方法。最简单的方法是移动一位，更巧妙的方法则可以在不丢解的条件下移动较大的距离。法则可以在不丢解的条件下移动较大的距离。K-近似匹配的关键是近似匹配的关键是P在在T上的上的K-近似匹配检查，即计算样本近似匹配检查，即计算样本P与当前对应的文本与当前对应的文本T之子串的最小差别数。如果该值小于等之子串的最小差别数。如果该值小于等于于K，则找到结果，否则样本则找到结果，

40、否则样本P右移。过程中的计算集中在计右移。过程中的计算集中在计算最小差别数上，这实际上是一个优化问题，算最小差别数上，这实际上是一个优化问题，比完全匹配问比完全匹配问题复杂得多题复杂得多。30近似串匹配的一个简化问题是比较两个字符串的差别。例如，近似串匹配的一个简化问题是比较两个字符串的差别。例如，OCROCR（光学字符识别）系统是通过在计算机上运行识别算法，光学字符识别）系统是通过在计算机上运行识别算法，将扫描仪扫描得到的字符文本的图像信息转化为作为识别结将扫描仪扫描得到的字符文本的图像信息转化为作为识别结果的字符串。为了确定果的字符串。为了确定OCROCR系统的识别率，需要对原始字符串系统

41、的识别率，需要对原始字符串和识别结果字符串进行比较。这种比较，实际上就是简化的和识别结果字符串进行比较。这种比较，实际上就是简化的近似串匹配问题，它应计算出结果字符串与原始字符串间的近似串匹配问题，它应计算出结果字符串与原始字符串间的最小编辑错误数。最小编辑错误数。v7.3.2 DP算法的思路算法的思路 近似串匹配问题同样具有最优子结构性质和子结构重迭性质。近似串匹配问题同样具有最优子结构性质和子结构重迭性质。l如果样本如果样本p1p2.pm在文本在文本T的某一位置上有一最优（差别数最小）的对应的某一位置上有一最优（差别数最小）的对应关系，那么样本关系，那么样本P的任意一个子串的任意一个子串p

42、i.pj（1ijm）与与T的对应关系也必然的对应关系也必然是最优（差别数最小）的。是最优（差别数最小）的。(最优子结构最优子结构)l计算样本计算样本P对应文本对应文本T某一位置的最小差别数时，对某一位置的最小差别数时，对P的任一子串的任一子串pi.pj与与T相应位置上的最小差别数的计算，必然包含计算任何包含相应位置上的最小差别数的计算，必然包含计算任何包含pi.pj的的P及其及其子串的最小差别数的过程中。子串的最小差别数的过程中。(子结构覆盖子结构覆盖)31因此，可以考虑用动态规划方法设计出快速的近似串匹配算因此，可以考虑用动态规划方法设计出快速的近似串匹配算法法。问题的关键是如何找出代价函数

43、的自底向上的递推关系。问题的关键是如何找出代价函数的自底向上的递推关系。为此为此可可定义一个代价函数定义一个代价函数Dij，0im，0jn。Dij表示表示样本子串样本子串p1.pi与文本子串与文本子串t1.tj之间的最小差别数。之间的最小差别数。由此可知：由此可知：Dmj表示样本表示样本P在文本在文本T的位置的位置j处的最小差别数，如果处的最小差别数，如果DmjK，说明说明P在在tj处找到了处找到了K-近似匹配。近似匹配。代价函数的初始值很容易确定：代价函数的初始值很容易确定：D0j=0，这是因为样本这是因为样本P为空串，与文本为空串，与文本t1.tj有有0个字符不个字符不同；同；Di0=i，

44、这是因为样本串这是因为样本串p1.pi与空文本串相比，有与空文本串相比，有i个字符个字符不同。不同。32可以通过下面的简单分析得出代价函数的递推关系。当样本可以通过下面的简单分析得出代价函数的递推关系。当样本子串子串p1.pi与文本子串与文本子串t1.tj对应时，有四种可能的情况：对应时，有四种可能的情况：(1)字符字符pi与与tj相对应且相对应且pi=tj，总差别数为总差别数为Di-1j-1；(2)字符字符pi与与tj相对应且相对应且pitj，总差别数为总差别数为Di-1j-1+1；(3)字符字符tj为多余，即为多余，即tj对应于空格，总差别数为对应于空格，总差别数为Dij-1+1；(4)字

45、符字符pi对应于对应于tj后的空格，总差别数为后的空格，总差别数为Di-1j+1。根据代价函数根据代价函数Dij的定义，它应该取所有可能值之中的最小的定义，它应该取所有可能值之中的最小者，即者，即：jijitpjijiDjiDjiDtpjijiDjiDjiDjiijiD,0,1 1,11,1min,0,1 1,11,min0,0,033代价函数代价函数Dij实际上是一个二维数组，其初始值和实际上是一个二维数组，其初始值和Dij的的计算方法由计算方法由Fig7.7表示，每个表示，每个Dij的值总是由其左上方的三的值总是由其左上方的三个已知值来确定。个已知值来确定。34v7.3.3 DP算法算法算

46、法算法7.4 近似串匹配算法近似串匹配算法 ASM v7.3.4 算法的复杂度分析与实例算法的复杂度分析与实例在算法在算法7.4的内层循环语句中，进行了一次字符比较和取三个的内层循环语句中，进行了一次字符比较和取三个整 数 中 最 小 值 的 操 作，因 此，算 法 的 时 间 复 杂 度 为整 数 中 最 小 值 的 操 作，因 此，算 法 的 时 间 复 杂 度 为T(n)=O(nm)。算法的空间代价显然由代价函数矩阵算法的空间代价显然由代价函数矩阵Dmn决定，因此也是决定，因此也是O(nm)。与近似串匹配问题本身的复杂性相。与近似串匹配问题本身的复杂性相对照，动态规划的解决算法十分简明和

47、有效，这一点可以通对照，动态规划的解决算法十分简明和有效，这一点可以通过下面的实例看出。过下面的实例看出。已知：已知：样本样本P=happy，K=1，T=Have a hsppy day.是一是一个可能有编辑错误的文本。个可能有编辑错误的文本。求：求：P在在T中的中的K-近似出现。近似出现。35按照算法按照算法7.4解这一问题的计算过程，实际上就是逐列计算二解这一问题的计算过程，实际上就是逐列计算二维数组维数组D1.m1.n的过程，当在第的过程，当在第m=5行出现小于或等于行出现小于或等于K的值时，计算即可终止。这个过程可用的值时，计算即可终止。这个过程可用Fig7.8中给出的二维数中给出的二

48、维数组表示。组表示。36在计算过程中，首先在计算过程中，首先D0j全部置为全部置为0，Di0置为置为i。由于认为大写的由于认为大写的“H”与小写与小写“h”是不同的，因此是不同的，因此D11在在D00+1=1、D01+1=1、D10+1=2三者中取最小值，故三者中取最小值，故D11=1。在逐列的计算过程中，总是根据在逐列的计算过程中，总是根据Dij对应的两个对应的两个字符字符pi、tj是否相同，以及位于是否相同，以及位于Dij左上方、正上方、正左左上方、正上方、正左方的三个已计算值决定方的三个已计算值决定Dij的取值。例如：的取值。例如：计算计算D26时，因为样本与文本的对应字符都为时，因为样

49、本与文本的对应字符都为“a”，所以所以应在应在1、1+1=2、2+1=3三个值中取最小者，故三个值中取最小者，故D26=1。计算计算D412时，样本字符为时，样本字符为“p”，文本字符为文本字符为“y”，这时三这时三个相关的已知值为个相关的已知值为2、3、1，所以应在，所以应在3、4、2中取最小值，中取最小值，故故D412=2。37由于由于D512=1=K，且且m=5，所以在所以在T12处找到了差别数为处找到了差别数为1的的K-近似匹配。这时文本近似匹配。这时文本T和样本和样本P的对应关系为：的对应关系为：T：Have a hsppyP：happy事实上，当事实上，当K=2时，在时，在T11、

50、T12、T13三处都可以找到三处都可以找到2-近似匹配。近似匹配。v7.3.5 讨论讨论1.近似串匹配问题由于允许有三种类型的差别，两个字符串近似串匹配问题由于允许有三种类型的差别，两个字符串的对应关系可以有很多种选择，不同的选择方法总数为样本的对应关系可以有很多种选择，不同的选择方法总数为样本长度长度m的指数函数。如果采用穷举算法，计算各种不同对应的指数函数。如果采用穷举算法，计算各种不同对应关系的差别数，再求最小值，计算量是很大的。然而，通过关系的差别数，再求最小值，计算量是很大的。然而，通过使用动态规划方法，使得计算复杂度仅为使用动态规划方法，使得计算复杂度仅为O(nm)，十分简捷。十分