算法,最长公共子序列.docx

最长公共子序列（LCS）问题（非连续子序列）的两种解法 最长公共子序列也称作最长公共子串，英文缩写是LCS（Longest Common Subsequence）。其定义是：一个序列S，如果分别是两个或多个已知序列的子序列，且是符合此条件的子序列中最长的，则称S为已知序列的最长公共子序列。 关于子序列的定义通常有两种方式，一种是对子序列没有连续的要求，其子序列的定义就是原序列中删除若干元素后得到的序列。另一种是对子序列有连续的要求，其子序列的定义是原序列中连续出现的若干个元素组成的序列。求解子序列是非连续的最长公共子序列问题是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。本文将介绍对子序列没有连续性要求的情况下如何用计算机解决最长公共子序列问题，对子序列有连续性要求的情况下如何用计算机解决最长公共子序列问题将在后续的文章中介绍。一、 动态规划法（Dynamic Programming） 最长公共子序列问题应该是属于多阶段决策问题中求最优解一类的问题，凡此类问题在编制计算机程序时应优先考虑动态规划法，如果不能用动态规划法，而且也找不到其它解决方法，还可以考虑穷举法。对于这个问题，只要能找到描述最长公共子序列的最优子结构和最优解的堆叠方式，并且保证最优子结构中的每一次最优决策都满足“无后效性”，就可以考虑用动态规划法。使用动态规划法的关键是对问题进行分解，按照一定的规律分解成子问题（分解后的子问题还可以再分解，这是个递归的过程），通过对子问题的定义找出最优子结构中最优决策序列（对于子问题就是最有决策序列的子序列）以及最优决策序列子序列的递推关系（当然还包括递推关系的边界值）。 如果一个给定序列的子序列是在该序列中删去若干元素后得到的序列，也就意味着子序列在原序列中的位置索引（下标）保持严格递增的顺序。例如,序列S = 是序列K = 的一个子序列（非连续），序列S的元素在在K中的位置索引I = 2,3,5,7，I是一个严格递增序列。1.1 最优子结构定义与边界值 现在来分析一下本问题的最优子结构。首先定义问题，假设有字符串str1长度为m，字符串str2长度为n，可以把子问题描述为：求字符串str1中从第1个到第i（i = m）个字符组成的子串str1和字符串str2中从第1个到第j(j = n)个字符组成的子串str2的最长公共序列，子问题的最长公共序列可以描述为di,j = Z1,Z2, Zk ，其中Z1-Zk为当前子问题已经匹配到的最长公共子序列的字符。子问题定义以后，还要找出子问题的最优序列di,j的递推关系。分析di,j的递推关系要从str1i和str2j的关系入手，如果str1i和str2j相同，则di,j就是di-1,j-1的最长公共序列1，Zk=str1i=str2j；如果str1i和str2j不相同，则di,j就是di-1,j的最长公共序列和di,j-1的最长公共序列中较大的那一个。 最后是确定di,j的边界值，当字符串str1为空或字符串str2为空时，其最长公共子串应该是0，也就是说当i=0或j=0时，di,j就是0。di,j的完整递推关系如下：1.1 反求最长公共子序列 根据1.1得到的最优解子结构递推关系，依次计算i从到m，j从1到n的di,j值，最后得到的dm,n就是最长公共子序列的长度。dm,n只是最长公共子序列的长度值，表示了两个字符串的相似程度，如果要获得最长公共子序列，就需要在计算出dm,n矩阵的值后分析每一步决策的结果，根据每一个最优决策逆向构造出最长公共子序列。为此需要在递推计算di,j的过程中，需要同时记录下最优决策的过程，最优决策的过程用矩阵r表示，ri,j表示最长公共子序列的长度值di,j的“递推来源”。根据前面整理的递推关系，如果ri,j的值是1，则表示di,j的值由di-1,j-1 + 1递推得到；如果ri,j的值是2，则表示di,j的值由di-1,j递推得到；如果ri,j的值是3，则表示di,j的值由di,j-1递推得到。以字符串“abcdea”和“aebcda”为例，根据递推关系得到的d和r合并到一个矩阵中显示：图（1）逆向构造最长公共子序列示意图逆向构造最长公共子串的过程从rm,n开始，如果ri,j1，则表示两个字符串中的str1i和str2j相同，可以将str1i或str2j插入到当前构造的最长公共子序列中。如果ri,j1，则不改变当前构造的最长公共子序列，但是要根据ri,j的值是2还是3，调整ri,j倒推的下一个位置。以上述两个字符串构造出的d矩阵和r矩阵为例，逆向构造最长公共子序列的过程如下：r6,6=1表示当前公共子串lcs = （str16和值一样），同时前一次最优决策来自于d5,5。r5,5=2表示前一次决策来自于d4,5，此时r4,5=1，表示当前公共子串lcs = ，同时前一次最优决策来自于d3,4。r3,4=1表示当前公共子串lcs = ，同时前一次最优决策来自于d2,3。r2,3=1表示当前公共子串lcs = ，同时前一次最优决策来自于d1,2。r1,2=3表示前一次决策来自于d1,1，此时r1,1=1，表示当前公共子串lcs = 。由于r0,0是边界，因此逆向构造过程结束，得到最长公共子串的最终结果是lcs = ，对应的字符串就是。1.1 动态规划算法实现 在编写实现代码时，将每次决策的策略和最优值用一个数据结构描述：11typedef struct tagDPLCS1213 int d;14 int r;15DPLCS;d是最优决策的值，r是决策方向。整个算法分成两部分，首先根据递推关系得到最优值（包括决策方向），这部分由InitializeDpLcs()函数完成，然后是逆向构造出最长公共序列，由GetLcs()函数实现。InitializeDpLcs()函数实现了本文1.1小节介绍的di,j的递推计算算法以及ri,j的构造过程：17int InitializeDpLcs(const std:string& str1, const std:string& str2, DPLCS dpMAX_STRING_LENMAX_STRING_LEN)1819 std:string:size_type i,j;2021 for(i = 1; i = str1.length(); i+)22 dpi0.d = 0;23 for(j = 1; j = str2.length(); j+)24 dp0j.d = 0;2526 for(i = 1; i = str1.length(); i+)27 28 for(j = 1; j = dpij - 1.d )38 39 dpij.d = dpi - 1j.d;40 dpij.r = 2;41 42 else43 44 dpij.d = dpij - 1.d;45 dpij.r = 3;46 47 48 49 5051 return dpstr1.length()str2.length().d;52GetLcs()函数则是1.2小节描述的算法实现，巧妙的利用了递归算法实现了逆向构造最长公共子串，构造过程基于第一个字符串，lcs就是最终得到的最长公共字串：54void GetLcs(DPLCS dpMAX_STRING_LENMAX_STRING_LEN, int i, int j, const std:string& str1, std:string& lcs)5556 if(i = 0) | (j = 0) 57 return;5859 if(dpij.r = 1)60 61 GetLcs(dp, i - 1, j - 1, str1, lcs);62 lcs += str1i - 1;63 64 else65 66 if(dpij.r = 2)67 GetLcs(dp, i - 1, j, str1, lcs);68 else69 GetLcs(dp, i, j - 1, str1, lcs);70 71一、 穷举的方法 除了动态规划法，求最长公共子序列问题也可以使用穷举算法。穷举算法的实质就是使用各种匹配两个字符串的方法，对两个字符串求解最长公共子串，然后找出各种方法得到子串中最长的一个。穷举法匹配字符串有很多种方法，本文介绍一种模仿人类思维方式，用递归方式求解最长公共子串的算法。2.1 算法分析 人脑解决此类问题的方法就是逐个比较两个字符串的每个字符，比如str1i和str2j，如果str1i=str2j，则将str1i或str2j附加到str1i和str2j之前计算得到的最长公共子串后面，然后继续计算str1i+1开始的子串和和str2j+1开始的子串的最长公共子串。如果str1i!=str2j，则采用三种方法穷举，第一种方法是删除str1i，继续计算str1i+1开始的子串和str2j开始的子串的最长公共子串；第二种方法是删除str2j，继续计算str1i开始的子串和str2j+1开始的子串的最长公共子串；第三种方法是删除str1j和str2j，继续计算str1i+1开始的子串和str2j+1开始的子串的最长公共子串。使用三种方法计算完成后比较结果，取最长的子串附加到str1i和str2j之前计算得到的最长公共子串后面组成新的最长公共子串。以上继续计算都是递归过程，递归的终止条件是到达str1字符串结尾或str2字符串结尾。2.2 算法实现 RecursionLCS()函数就是对上述2.1分析的实现：108void RecursionLCS(const std:string& str1, const std:string& str2, std:string& lcs)109110 if(str1.length() = 0 | str2.length() = 0)111 return;112113 if(str10 = str20)114 115 lcs += str10;116 RecursionLCS(str1.substr(1), str2.substr(1), lcs);117 118 else119 120 std:string strTmp1,strTmp2,strTmp3;121122 RecursionLCS(str1.substr(1), str2, strTmp1); /尝试删除str1123 RecursionLCS(str1, str2.substr(1), strTmp2); /尝试删除str2124 RecursionLCS(str1.substr(1), str2.substr(1), strTmp3); /尝试同时删除str1和str2125 lcs += GetLongestS