动态规划近似串匹配.ppt

《动态规划近似串匹配.ppt》由会员分享，可在线阅读，更多相关《动态规划近似串匹配.ppt（51页珍藏版）》请在金锄头文库上搜索。

1、计算机算法计算机算法设计与分析导论设计与分析导论南开大学南开大学 计算机科学与技术系计算机科学与技术系刘璟1Chapter 7. 动态规划动态规划（Dynamic Programming） v 7.1 动态规划的基本原理动态规划的基本原理v 7.2 最优二分搜索树最优二分搜索树(Optimal Binary Search Tree)v 7.3 近似串匹配近似串匹配(Approximate String Matching)问题问题27.1 动态规划的基本原理动态规划的基本原理v7.1.1 Fibonacci数的计算数的计算 Fibonacci数又称为数又称为Fibonacci数列，定义为：数列，

2、定义为：F0=0, F1=1, Fn=Fn-1 + Fn-2 (n 2)计算计算Fibonacci数列可由递归函数数列可由递归函数fibo完成。完成。 递归函数递归函数fibo 由此可知，函数由此可知，函数fibo的计算量随的计算量随n的增加而急剧增加，的增加而急剧增加，n=6时时需需25次调用，次调用，n=10时需时需177次调用，次调用，n=15时需时需1974次调用。次调用。进一步的研究表明，调用次数进一步的研究表明，调用次数 An = 2Fn+1 - 1，其中，其中 ， 。可以估计，可以估计， ，其计算量是，其计算量是n的指数函数。的指数函数。3从从Fig.7.1中中可可以以看看出出，

3、大大量量的的调调用用过过程程是是重重复复的的，此此算算法法可可以以改进。改进。 函数函数fibo的改进函数的改进函数fib这个程序的时间代价为这个程序的时间代价为O(n)阶。阶。 4v7.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=117505五五种种运运算算次次序序的的计计算算结结果果相相同同，但但所所花花费费的的时时间间代代价价相相差差极极大大。如如果果某某一一应应用用问问题题需需要

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万次乘法万次乘法。6由由于于不不能能事事先先决决定定最最初初在在何何处进行行划划分分，所所以以分分治治策策略略难以以解解决决这个个问题。但但这个个问题满足足最最优子子结构构性性质：即即，当当选择了了进行行最最外外层相相乘乘的的位位置置之之后后，其其左左右右

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

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

9、做做有有可可能能有有利利于于减减少少矩矩阵阵连连乘乘的的计计算算量量。使使用用这这一一策策略略，对对上上面面的的两两个个简简单单实实例例进进行行计计算算，其其结结果果都都是是正正确确的的。但但是是这这个个贪贪心心算算法法仍然不能总是找出最优解。仍然不能总是找出最优解。 可可以以从从Fibonacci数数的的计计算算得得到到启启发发，采采用用动动态态规规划划的的方方法法设设计算法。最简单的递归算法描述如下：计算法。最简单的递归算法描述如下： 递归算法递归算法MinCost 8此算法的此算法的递归过程中，存在与程中，存在与fibo函数相似的地方，即会有大函数相似的地方，即会有大量的重复量的重复调用

10、，其用，其调用关系如用关系如Fig7.2所示，其中所示，其中n=4。 9递递归归函函数数MinCost的的调调用用过过程程在在n=4时时共共27次次，n=5时时为为81次次，n=6时时为为249次次，当当n增增大大时时，计计算算量量急急剧剧增增加加。如如果果采采用用自自底底向向上上的的计计算算方方式式，函函数数MinCost(1,n)的的计计算算代代价价将将大大大大减减少少。其计算过程为：其计算过程为：MinCost(1,1)=MinCost(2,2)=MinCost(3,3)=MinCost(4,4)=0MinCost(1,2)=MinCost(1,1)+MinCost(2,2)+d0d1d

11、2=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次，次，n=5时为时为15次，次，n=6时为时为21次。次。 104. 矩阵连乘的矩阵连乘的DP算法算法设矩阵个数为设矩阵个数为n，维数为维数为dimn+1（n+1个值），同时用

12、数组个值），同时用数组MultiOrdern保存程序运行时得到的最优乘法顺序，可得：保存程序运行时得到的最优乘法顺序，可得： 算法算法7.1 最优矩阵连乘算法最优矩阵连乘算法 MatrixOrder 函数函数MatrixOrder返回最优连乘次序所需的最小时间代价，同返回最优连乘次序所需的最小时间代价，同时将最优次序保存在数组时将最优次序保存在数组MultiOrder中，从此数组中得到最中，从此数组中得到最优乘法次序的算法为：优乘法次序的算法为：ExtractOrder 用上述算法用上述算法计算本算本节给出的出的实例，其例，其结果果为：最小代价为最小代价为cost0n=1400，最最优乘法次序

13、乘法次序MultiOrder1.3=2,3,1，即即A1(A2A3)A4)。 11v7.1.3 动态规划（动态规划（DP）算法的基本条件）算法的基本条件 1. 最最优子子结构性构性质最优化原理。最优化原理。其特征是：当要求一个其特征是：当要求一个问题的最的最优解解时，构成，构成整体解的子整体解的子问题的解也必的解也必须是最是最优的。的。例如，例如，为了使了使计算算n个个矩矩阵连乘乘A1A2.An的代价最小，无论最后一次乘法的位置的代价最小，无论最后一次乘法的位置k在何处（在何处（1kn），），其左右两部分其左右两部分A1.Ak，Ak+1.An的乘的乘积也必也必须是代价最小的。是代价最小的。这也

14、可用最短路径也可用最短路径问题来来说明：若明：若V1V2.Vn是一条从是一条从V1到到Vn的最短路径，那么的最短路径，那么这条路径的任何一条路径的任何一段，比如从段，比如从Vi到到Vj（1ijn）也必也必须是一条最短路径。是一条最短路径。2. 子子结构重迭性构重迭性质 简单的的递归程序解法都是一种自程序解法都是一种自顶向下向下进行行递归分解的分解的过程，程，其中包含了大量的重复其中包含了大量的重复调用，在用，在这种情况下采用种情况下采用动态规划方划方法特法特别有效。因此，有效。因此，问题中中这种种子结构重迭性质子结构重迭性质是采用是采用动态规划方法的另一个条件。划方法的另一个条件。动态规划算法

15、的一个特征是自底向划算法的一个特征是自底向上，它可以大幅度减少上，它可以大幅度减少计算代价。算代价。12解决解决这类具有子具有子结构重迭性构重迭性质的的问题还有另外一种被称有另外一种被称为备备忘录（忘录（memorization）方法的自方法的自顶向下的向下的递归方式。方式。其思想是其思想是：由程序由程序设置置“备忘忘录”，每，每计算出一个新的子算出一个新的子结构构的解的解时，都保存起来。当遇到一次，都保存起来。当遇到一次递归时，判断是否已，判断是否已经计算，如果已算，如果已经计算，只需取出先前保存的算，只需取出先前保存的结果即可。果即可。这种方种方式与式与动态规划算法相比，要增加保存与划算法

16、相比，要增加保存与检索中索中间结果的代价。果的代价。算法算法7.2 求求Fibonacci数的备忘录算法数的备忘录算法 MemoFib 137.2 最优二分搜索树最优二分搜索树（Optimal Binary Search Tree）v7.2.1 OBST问题问题 二分字典二分字典树是构造数据存是构造数据存储与与检索系索系统的一种方便形式，例的一种方便形式，例如一个翻如一个翻译系系统需要一个字典数据需要一个字典数据库。可以按照。可以按照单词的字典的字典顺序构造一个二分搜索序构造一个二分搜索树，能，能获得得较高的搜索效率。高的搜索效率。 假定字典中只包含假定字典中只包含15个个单词：and，cab

17、bage，come，has，king，of，pig，ring，said，talk，the，thing，time，walrus，wing。按照字典按照字典顺序插入序插入显然形成一个退化的二分然形成一个退化的二分树即即线性性链表，表，其平均搜索代价是其平均搜索代价是(1+15)/2=8次次单词比比较。14采用采用Fig7.3中的二分搜索中的二分搜索树，最多，最多仅需需4次比次比较，平均需要，平均需要(1+22+34+48)/15=3.17次比较，因此完全二分搜索树具有次比较，因此完全二分搜索树具有最小的平均搜索代价。最小的平均搜索代价。 15在在实用系用系统中，中，还要考要考虑到不同的到不同的单词

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

19、典典仅由由4个个单词cat、come、of、the组成，它成，它们的的查找概率分找概率分别为：cat:0.12，come:0.08，of:0.35，the:0.4516由由这四个四个单词可以可以组成成许多种不同的二分字典多种不同的二分字典树，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次比较；次比较；(a) 0.35+2(0.12

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

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

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

23、2 动态规划算法的思路动态规划算法的思路设n个个单词为a1,a2,.,an，则由它由它们构成二分搜索构成二分搜索树T1,n可以表可以表示示为Fig7.6的形式。其中的形式。其中ak(1kn)为T1,n的根，其左子的根，其左子树T1,k-1由由a1.ak组成，右子成，右子树Tk+1,n由由ak+1.an组成。成。 19用代价函数用代价函数Cost(low,high)表示由表示由alow.ahigh及相及相应的外部的外部节点点blow-1,blow,.,bhigh组成的二分搜索成的二分搜索树的最小代价。特的最小代价。特别地，当地，当high=low-1时表示空表示空树，Cost(i,i-1)=0。

24、 Cost(low,high,r)表示指定以表示指定以ar为根根时，组成的二分搜索成的二分搜索树的最的最小搜索代价。小搜索代价。如果如果T1,n是最是最优的，那么的，那么T1,k-1，Tk+1,n两个子两个子树也必然是最也必然是最优的，的，因此，因此，该问题具有最具有最优子子结构构性性质；另一方面，；另一方面，单词序列中序列中任意几个相任意几个相邻单词组成的子成的子树将同将同时出出现在多个包含它在多个包含它们的的更大的更大的树中，因此，中，因此，子子结构重构重迭迭性性质也是很明也是很明显的。的。T1,k-1是由a1至ak-1元素构成子树中最优者20权函数函数W(low,high)表示相表示相应

25、二分搜索二分搜索树的所有的所有节点的搜索概点的搜索概率之和，称率之和，称为该树的的权：特特别地：地：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) =W(low,high)+Cost(low,r-1)+Cost(r+1，high)Cost(low,high) =MinCost(low,high,r)|lowrhigh依照自底向上的依照自底向上的顺序，序，很容易很容易

26、计算出算出Cost(1,n)以及最以及最优树的的各各级子子树的根。的根。(注意路径的注意路径的长度如何度如何计算的算的,如如,根根结点点r,在在计算中最算中最终结果果为pr*1,而其他而其他结点点,如在根的下如在根的下层,则计算两次算两次为pj+pj=pj*2) 第i个单词为树的权第i个单词前一个未找到的为树的权21v7.2.3 算法算法OBST已知：已知：n个单词个单词a1.an的成功与不成功查找概率分别为：的成功与不成功查找概率分别为：p1.pn，q0.qn。即：即：P1.n，Q0.n。求求：由由a1.an组组成成的的最最优优二二分分搜搜索索树树。为为此此设设置置二二维维数数组组Cnn，W

27、nn，Rnn。算法算法7.3 最优二分搜索树构造算法最优二分搜索树构造算法 OBST 算算法法OBST的的结结果果是是数数组组C和和数数组组R，其其中中C1n为为求求得得的的最最优二分搜索树的搜索代价，优二分搜索树的搜索代价，R中包含了构造该树的信息。中包含了构造该树的信息。假定单词序列假定单词序列A1.n类型为类型为word，树节点的类型为：树节点的类型为：struct node word key; node * left,* right;可得到：可得到：由数组由数组R构造搜索树的算法构造搜索树的算法 BuildTree22v7.2.4 算法算法OBST的复杂度分析的复杂度分析算算法法7.3

28、中中，T(n)=O(n3)，再再有有T(n)=(n3)。算算法法BuildTree表表面面上上看看是是一一个个双双递递归归程程序序，但但由由于于算算法法每每调调用用一一次次即即生生成成一一个个（内内部部）节节点点，因因此此至至多多调调用用n次次程程序序就就结结束束，其其复复杂杂度度是是O(n)阶的。阶的。算算法法的的空空间间代代价价主主要要体体现现在在计计算算过过程程中中所所必必需需的的二二维维数数组组，故有故有S(n)=(n2)。 v7.2.5 讨论讨论1. DP算算法法应用用于于OBST构构造造问题的的效效果果非非常常明明显。n个个单词的的二二分分字字典典树的的个个数数是是n的的一一个个增

29、增长很很快快的的指指数数函函数数。例例如如，10个个节点点的的二二分分字字典典树就就有有16796种种，因因此此穷举法法是是任任何何高高速速计算算机机都都不不能能接接受受的的。但但DP算算法法把把计算算量量降降到到了了(n3)阶阶，而而且且可可以以估估计计出出n3项项的的系系数数大大约约为为1/6，当当n较较大大时时其其加加速速的的倍倍数数已已经是天文数字了。由此可以看出经是天文数字了。由此可以看出DP算法的强大威力。算法的强大威力。 232. 构构造造二二分分搜搜索索树的的问题与与矩矩阵连乘乘的的顺序序问题十十分分相相似似，关关键是是代代价价函函数数递推推关关系系的的确确定定，这也也是是许多

30、多应用用动态规划划方方法法设计有有效效算算法法的的共共同同之之处。同同时，由由于于问题的的不不同同，处理理细节时又是有差又是有差别的。的。 3. 该该算算法法仍仍然然可可以以改改进进，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

31、;r+).改变为改变为 for(r=Rlowhigh-1;r=Rlow+1high;r+).。24这一改一改动虽然使程序然使程序变化不大，但却明化不大，但却明显地地改改变了了计算量。算量。这这可以通可以通过一个一个简化化实例来例来说明：明：设有有100个个单词a1.a100，如如果每个单词的查找概率相同，则应有果每个单词的查找概率相同，则应有R199=50，R2100=51，即原算法变量即原算法变量r从从r=1到到r=100循环循环100次，改进次，改进之后变量之后变量r从从r=50到到r=51循环循环2次，计算量减少几十倍。次，计算量减少几十倍。 改改进进后后算算法法的的时时间间复复杂杂度度

32、可可由由下下式式估估计计，内内层层循循环环的的计计算算次次数为：数为：因此算法因此算法7.3的时间复杂度为的时间复杂度为O(n2)。Knuth的改进，使计算复杂度从的改进，使计算复杂度从(n3)降为降为(n2)。25这一成果更为重要的部分是证明其结果的正确性，即证明：这一成果更为重要的部分是证明其结果的正确性，即证明：Rij-1RijRi+1j,直直观上看是上看是显然的，但然的，但严格格证明却相当困明却相当困难。4. 关关于于二二分分字字典典树的的研研究究还有有许多多成成果果，例例如如可可以以用用贪心心算算法法来来构构造造几几乎乎最最优的的二二分分字字典典树，还有有最最优二二分分分分裂裂树（O

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

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

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

36、最小编辑错误总数。总数。P:a p p r o x i m a t l yT:a p r o x i o m a l l y28因此，一般的因此，一般的K-近似匹配问题可以描述为：近似匹配问题可以描述为：已知：已知：字符串字符串P： p1p2.pm（称为称为Pattern），），字符串字符串T：t1t2.tn（称为称为Text），），和一个正整数和一个正整数K。求：求：样式样式P在文本在文本T上的上的K-近似匹配的第一次出现或所有出现。近似匹配的第一次出现或所有出现。在在完完全全串串匹匹配配中中，P在在T上上的的一一次次匹匹配配检检查查十十分分简简单单，用用至至多多m次次字字符符比比较较即即可

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

38、上是是一一个个优优化化问问题题，比比完完全全匹匹配配问问题复杂得多题复杂得多。29近近似似串串匹匹配配的的一一个个简简化化问问题题是是比比较较两两个个字字符符串串的的差差别别。例例如如，OCROCR（光光学学字字符符识识别别）系系统统是是通通过过在在计计算算机机上上运运行行识识别别算算法法，将将扫扫描描仪仪扫扫描描得得到到的的字字符符文文本本的的图图像像信信息息转转化化为为作作为为识识别别结结果果的的字字符符串串。为为了了确确定定OCROCR系系统统的的识识别别率率，需需要要对对原原始始字字符符串串和和识识别别结结果果字字符符串串进进行行比比较较。这这种种比比较较，实实际际上上就就是是简简化化

39、的的近近似似串串匹匹配配问问题题，它它应应计计算算出出结结果果字字符符串串与与原原始始字字符符串串间间的的最小编辑错误数。最小编辑错误数。v7.3.2 DP算法的思路算法的思路 近似串匹配近似串匹配问题同同样具有最具有最优子子结构性构性质和子和子结构重迭性构重迭性质。 l如如果果样样本本p1p2.pm在在文文本本T的的某某一一位位置置上上有有一一最最优优（差差别别数数最最小小）的的对对应应关关系系，那那么么样样本本P的的任任意意一一个个子子串串pi.pj（1ijm）与与T的的对对应应关关系系也也必必然然是最优（差别数最小）的。是最优（差别数最小）的。(最优子结构最优子结构)l计计算算样样本本P

40、对对应应文文本本T某某一一位位置置的的最最小小差差别别数数时时，对对P的的任任一一子子串串pi.pj与与T相相应应位位置置上上的的最最小小差差别别数数的的计计算算，必必然然包包含含计计算算任任何何包包含含pi.pj的的P及及其其子串的最小差别数的过程中。子串的最小差别数的过程中。(子结构覆盖子结构覆盖)30因因此此，可可以以考考虑用用动态规划划方方法法设计出出快快速速的的近近似似串串匹匹配配算算法法。问题的的关关键是是如如何何找找出出代代价价函函数数的的自自底底向向上上的的递推推关关系系。为此此可可定定义一一个个代代价价函函数数Dij，0im，0jn。Dij表表示示样本子串本子串p1.pi与文

41、本子串与文本子串t1.tj之之间的最小差的最小差别数。数。由此可知：由此可知：Dmj表表示示样样本本P在在文文本本T的的位位置置j处处的的最最小小差差别别数数，如如果果DmjK，说明说明P在在tj处找到了处找到了K-近似匹配。近似匹配。代价函数的初始代价函数的初始值很容易确定：很容易确定： D0j=0，这这是是因因为为样样本本P为为空空串串，与与文文本本t1.tj有有0个个字字符符不不同；同；Di0=i，这这是是因因为为样样本本串串p1.pi与与空空文文本本串串相相比比，有有i个个字字符符不同。不同。31可可以以通通过过下下面面的的简简单单分分析析得得出出代代价价函函数数的的递递推推关关系系。

42、当当样样本本子串子串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) 字符字符pi对应于对应于tj后的空格，总差别数为后的空格，总差别数为Di-1j+1。根根据据代代价价函函数数Dij的的定定义，它它应该取取所所有有可可能能值之之中中的的最最小小者，即

43、者，即： 32代代价价函函数数Dij实实际际上上是是一一个个二二维维数数组组，其其初初始始值值和和Dij的的计计算算方方法法由由Fig7.7表表示示，每每个个Dij的的值值总总是是由由其其左左上上方方的的三三个已知值来确定。个已知值来确定。 33v7.3.3 DP算法算法算法算法7.4 近似串匹配算法近似串匹配算法 ASM v7.3.4 算法的复杂度分析与实例算法的复杂度分析与实例在在算算法法7.4的的内内层层循循环环语语句句中中，进进行行了了一一次次字字符符比比较较和和取取三三个个整整 数数 中中 最最 小小 值值 的的 操操 作作 ， 因因 此此 ， 算算 法法 的的 时时 间间 复复 杂

44、杂 度度 为为T(n)=O(nm)。算算法法的的空空间间代代价价显显然然由由代代价价函函数数矩矩阵阵Dmn决决定定，因因此此也也是是O(nm)。与与近近似似串串匹匹配配问问题题本本身身的的复复杂杂性性相相对对照照，动动态态规规划划的的解解决决算算法法十十分分简简明明和和有有效效，这这一一点点可可以以通通过下面的实例看出。过下面的实例看出。已已知知：样样本本P=happy，K=1，T=Have a hsppy day.是是一一个可能有编辑错误的文本。个可能有编辑错误的文本。求：求：P在在T中的中的K-近似出现。近似出现。34按按照照算算法法7.4解解这这一一问问题题的的计计算算过过程程，实实际际

45、上上就就是是逐逐列列计计算算二二维维数数组组D1.m1.n的的过过程程，当当在在第第m=5行行出出现现小小于于或或等等于于K的的值值时时，计计算算即即可可终终止止。这这个个过过程程可可用用Fig7.8中中给给出出的的二二维维数数组表示。组表示。 35在计算过程中，首先在计算过程中，首先D0j全部置为全部置为0，Di0置为置为i。由由于于认认为为大大写写的的“H”与与小小写写“h”是是不不同同的的，因因此此D11在在D00+1=1、D01+1=1、D10+1=2三三者者中中取取最最小小值值，故故D11=1。在在逐逐列列的的计计算算过过程程中中，总总是是根根据据Dij对对应应的的两两个个字字符符p

46、i、tj是是否否相相同同，以以及及位位于于Dij左左上上方方、正正上上方方、正正左左方的三个已计算值决定方的三个已计算值决定Dij的取值。例如：的取值。例如：计计算算D26时时，因因为为样样本本与与文文本本的的对对应应字字符符都都为为“a”，所所以以应在应在1、1+1=2、2+1=3三个值中取最小者，故三个值中取最小者，故D26=1。计计算算D412时时，样样本本字字符符为为“p”，文文本本字字符符为为“y”，这这时时三三个个相相关关的的已已知知值值为为2、3、1，所所以以应应在在3、4、2中中取取最最小小值值，故故D412=2。36由由于于D512=1=K，且且m=5，所所以以在在T12处处

47、找找到到了了差差别别数数为为1的的K-近似匹配。这时文本近似匹配。这时文本T和样本和样本P的对应关系为：的对应关系为：T： Have a hsppyP： happy事实上，当事实上，当K=2时，在时，在T11、T12、T13三处都可以找到三处都可以找到2-近似匹配。近似匹配。v7.3.5 讨论讨论1. 近近似似串串匹匹配配问问题题由由于于允允许许有有三三种种类类型型的的差差别别，两两个个字字符符串串的的对对应应关关系系可可以以有有很很多多种种选选择择，不不同同的的选选择择方方法法总总数数为为样样本本长长度度m的的指指数数函函数数。如如果果采采用用穷穷举举算算法法，计计算算各各种种不不同同对对应

48、应关关系系的的差差别别数数，再再求求最最小小值值，计计算算量量是是很很大大的的。然然而而，通通过过使使用动态规划方法，使得计算复杂度仅为用动态规划方法，使得计算复杂度仅为O(nm)，十分简捷。十分简捷。372. 算算法法7.4只只计计算算出出样样本本P在在文文本本T各各个个位位置置的的最最小小差差别别数数，以以及及相相应应的的位位置置Ti，没没有有给给出出得得到到最最小小差差别别的的字字符符对对应应关关系系。做做到到这这一一点点并并不不困困难难，可可以以再再设设置置一一个个mn阶阶的的二二维维数数组组B1.m1.n，Bij的的值值可可以以在在计计算算Dij的的过过程程中中求求得得。在在计计算算

49、最最小小值值时时，Bij的的值值依依据据Di-1j-1、Dij-1、Di-1j而而 分分 别别 取取 为为 r（ revise） 、 i（ insert） 、d（delete）。当当Dmj=K时时，即即可可由由Bmj回回溯溯，求求出出这这一匹配的字符对应关系。一匹配的字符对应关系。3. 近近似似串串匹匹配配问问题题可可以以定定义义为为求求样样本本P在在文文本本T中中所所有有的的K-近近似似匹匹配配，实实现现方方法法是是把把二二维维数数组组Dnm的的所所有有值值全全计计算算出出来来即可。这只需对算法即可。这只需对算法7.4稍作修改：稍作修改：将原程序中的将原程序中的“if(Dmj=K) retu

50、rn j;”改为改为“if(Dmj=K) coutK=Dmj:jendl;”在在Fig7.8中，虚线右侧的值就是由修改后的程序计算出来的。中，虚线右侧的值就是由修改后的程序计算出来的。384. 另另一一个个很很有有实实用用价价值值的的近近似似串串匹匹配配问问题题，是是比比较较两两个个文文本本文文件件f1和和f2的的差差别别。例例如如，检检验验电电脑脑录录入入人人员员的的文文字字输输入入的的准准确确率率，总总是是给给出出一一个个标标准准文文本本f，请请录录入入员员在在指指定定时时间间内内输输入入得得到到一一个个结结果果文文件件f，由由计计算算机机判判定定其其出出错错数数。实实际际上上就就是是计计

51、算算字字符符串串f与与标标准准串串f之之间间的的差差别别数数。这这个个问问题题并并不不简简单单，它它是是近近似似串串匹匹配配问问题题的的一一个个变变种种，其其中中两两个个字字符符串串的的地地位位是是平平等的，其算法应与算法等的，其算法应与算法7.4有所不同。有所不同。5. 字字符符串串的的近近似似匹匹配配问问题题可可以以看看作作最最简简单单的的模模式式识识别别问问题题。当当把把字字符符串串扩扩展展为为数数据据串串时时，可可以以发发现现，语语音音识识别别问问题题、在在线线（on-line）手手写写字字符符的的识识别别问问题题与与近近似似串串匹匹配配问问题题在在本本质质上上有有很很大大的的相相似似

52、性性，因因此此，动动态态规规划划算算法法在在语语音音识识别别和和手手写写字字符符识识别别领领域域可可以以发发挥挥很很大大的的作作用用。笔笔者者曾曾经经设设计计一一种种二二维维的的动动态态规规划划算算法法用用以以解解决决平平面面手手写写字字符符的的脱脱机机弹弹性性匹匹配配问问题题中，也取得了成功。中，也取得了成功。第七章完第七章完3940递归函数递归函数fibo int fibo(int n) int f; if(n2) f=n; else f=fibo(n-1)+fibo(n-2); return f;返回返回41函数函数fibo的改进函数的改进函数fib int fib(int n) int

53、 i,f,f0=0,f1=1; for(i=2;i=0;i-) for(j=i+1;j=n;j+) if(j-i=1) mcost=0; mlast=-1; else mcost=maxint;返回返回下页44算法算法7.1 最优矩阵连乘算法最优矩阵连乘算法MatrixOrder（续（续） for(k=i+1;kj;k+) a=costik; b=costkj; c=dimi*dimk*dimj; if( (a+b+c)1) k=lastlowhigh; ExtractOrder(low,k,last,MultiOrder); ExtractOrder(k,high,last,MultiOrd

54、er); MultiOrdernext+1=k; 返回返回46算法算法7.2 求求Fibonacci数的备忘录算法数的备忘录算法MemoFib int MemoFib(int n) int dictn=0,0,.,0; int f1,f2; if(n2) return n; if(dictn-1=0) f1=MemoFib(n-1); else f1=dictn-1; if(dictn-1=0) f2=MemoFib(n-2); else f2=dictn-2; dictn=f1+f2; return (f1+f2);返回返回47算法算法7.3 最优二分搜索树构造算法最优二分搜索树构造算法OB

55、ST void OBST(int n,floatP,float Q,floatC,floatW,intR) int i,s,r,low,high,broot; float bcost,rcost; for(i=1;i=n;i+) Cii-1=0; Wii-1=Qi-1; for(s=0;sn;s+) for(low=1;lown-s;low+) high=low+s; Wlowhigh=Wlowhigh-1+Phigh+Qhigh; bcost=MAXINT; 返回返回下页48算法算法7.3 最优二分搜索树构造算法最优二分搜索树构造算法OBST（续）（续） for(r=low;r=high;r

56、+) rcost=Wlowhigh+Clowr-1+Cr+1high; if(rcostbcost) bcost=rcost; broot=r; Clowhigh=bcost; Rlowhigh=broot; return;返回返回上页49BuildTree void BuildTree(int low, int high, node * root) root=new(node); root.key=ARlowhigh; if(lowRlowhigh) BuildTree(Rlowhigh+1,high,root.right); return;返回返回50算法算法7.4 近似串匹配算法近似串匹配算法ASM int ASM(char P, char T, int m, int n, int K) int i,j,k,Dmn; for(j=1;j=n;j+) D0j=0; for(i=0;i=m;i+) Di0=i; for(j=1;j=n;j+) for(i=1;i=m;i+) if(Pi=Tj) Dij=minDi-1j-1,Di-1j+1,Dij-1+1; else Dij=minDi-1j-1+1,Di-1j+1,Dij-1+1; if(Dmj=K) return j; 返回返回51