十分钟搞定LCS.ppt
- 文档编号:18755886
- 上传时间:2023-10-30
- 格式:PPT
- 页数:21
- 大小:486KB
十分钟搞定LCS.ppt
《十分钟搞定LCS.ppt》由会员分享,可在线阅读,更多相关《十分钟搞定LCS.ppt(21页珍藏版)》请在冰点文库上搜索。
十分钟搞定LCS,2/22,主要内容,LCS的定义暴力求解LCS分析LCS的性质导出LCS的递推公式实现算法涉及的数据结构降低LCS空间复杂度的方法LCS的多解性LCS的应用,3/22,LCS的定义,最长公共子序列,即LongestCommonSubsequence,LCS。
一个序列S任意删除若干个字符得到新序列T,则T叫做S的子序列;两个序列X和Y的公共子序列中,长度最长的那个,定义为X和Y的最长公共子序列。
字符串13455与245576的最长公共子序列为455字符串acdfg与adfc的最长公共子序列为adf注意区别最长公共子串(LongestCommonSubstring)最长公共字串要求连续,4/22,LCS的意义,求两个序列中最长的公共子序列算法,广泛的应用在图形相似处理、媒体流的相似比较、计算生物学方面。
生物学家常常利用该算法进行基因序列比对,由此推测序列的结构、功能和演化过程。
LCS可以描述两段文字之间的“相似度”,即它们的雷同程度,从而能够用来辨别抄袭。
另一方面,对一段文字进行修改之后,计算改动前后文字的最长公共子序列,将除此子序列外的部分提取出来,这种方法判断修改的部分,往往十分准确。
简而言之,百度知道、百度百科都用得上。
5/22,暴力求解:
穷举法,假定字符串X,Y的长度分别为m,n;X的一个子序列即下标序列1,2,m的严格递增子序列,因此,X共有2m个不同子序列;同理,Y有2n个不同子序列,从而穷举搜索法需要指数时间O(2m.2n);对X的每一个子序列,检查它是否也是Y的子序列,从而确定它是否为X和Y的公共子序列,并且在检查过程中选出最长的公共子序列;显然,不可取。
6/22,LCS的记号,字符串X,长度为m,从1开始数;字符串Y,长度为n,从1开始数;Xi=x1,xi即X序列的前i个字符(1im)(Xi不妨读作“字符串X的i前缀”)Yj=y1,yj即Y序列的前j个字符(1jn)(字符串Y的j前缀);LCS(X,Y)为字符串X和Y的最长公共子序列,即为Z=z1,zk。
注:
不严格的表述。
事实上,X和Y的可能存在多个子串,长度相同并且最大,因此,LCS(X,Y)严格的说,是个字符串集合。
即:
ZLCS(X,Y).,7/22,LCS解法的探索:
xm=yn,若xm=yn(最后一个字符相同),则:
Xm与Yn的最长公共子序列Zk的最后一个字符必定为xm(=yn)。
zk=xm=ynLCS(Xm,Yn)=LCS(Xm-1,Yn-1)+xm,8/22,结尾字符相等,则LCS(Xm,Yn)=LCS(Xm-1,Yn-1)+xm,记LCS(Xm,Yn)=W+xm,则W是Xm-1的子序列;同理,W是Yn-1的子序列;因此,W是Xm-1和Yn-1的公共子序列。
反证:
若W不是Xm-1和Yn-1的最长公共子序列,不妨记LCS(Xm-1,Yn-1)=W,且|W|W|;那么,将W换成W,得到更长的LCS(Xm,Yn)=Wxm,与题设矛盾。
9/22,举例:
xm=yn,对于上面的字符串X和Y:
x3=y3=C,则:
LCS(BDC,ABC)=LCS(BD,AB)+Cx5=y4=B,则:
LCS(BDCAB,ABCB)=LCS(BDCA,ABC)+B,10/22,LCS解法的探索:
xmyn,若xmyn,则:
要么LCS(Xm,Yn)=LCS(Xm-1,Yn),要么LCS(Xm,Yn)=LCS(Xm,Yn-1)。
证明:
令Zk=LCS(Xm,Yn);由于xmyn则zkxm与zkyn至少有一个必然成立,不妨假定zkxm(zkyn的分析与之类似)。
因为zkxm,则最长公共子序列Zk是Xm-1和Yn得到的,即:
Zk=LCS(Xm-1,Yn)同理,若zkyn,则Zk=LCS(Xm,Yn-1)即,若xmyn,则:
LCS(Xm,Yn)=maxLCS(Xm-1,Yn),LCS(Xm,Yn-1),11/22,举例:
xmyn,对于字符串X和Y:
x2y2,则:
LCS(BD,AB)=maxLCS(BD,A),LCS(B,AB)x4y5,则:
LCS(BDCA,ABCBD)=maxLCS(BDCA,ABCB),LCS(BDC,ABCBD),12/22,LCS分析总结,显然,属于动态规划问题。
13/22,算法中的数据结构:
长度数组,使用二维数组Cm,nci,j记录序列Xi和Yj的最长公共子序列的长度。
当i=0或j=0时,空序列是Xi和Yj的最长公共子序列,故ci,j=0。
14/22,算法中的数据结构:
方向变量,使用二维数据Bm,n,其中,bi,j标记ci,j的值是由哪一个子问题的解达到的。
即ci,j是由ci-1,j-1+1或者ci-1,j或者ci,j-1的哪一个得到的。
取值范围为Left,Top,LeftTop三种情况。
15/22,实例,X=Y=,16/22,计算LCS长度,17/22,根据b提供的方向,构造最长公共子序列,18/22,进一步思考的问题,方向数组b是完全可以省略的:
数组元素ci,j的值仅由ci-1,j-1,ci-1,j和ci,j-1三个值之一确定,因此,在计算中,可以临时判断ci,j的值是由ci-1,j-1,ci-1,j和ci,j-1中哪一个数值元素所确定,代价是
(1)时间。
若只计算LCS的长度,则空间复杂度为min(m,n)。
在计算ci,j时,只用到数组c的第i行和第i-1行。
因此,只要用2行的数组空间就可以计算出最长公共子序列的长度。
19/22,最大公共子序列的多解性:
求所有的LCS,当xmyn时:
若LCS(Xm-1,Yn)=LCS(Xm,Yn-1),会导致多解:
有多个最长公共子序列,并且它们的长度相等。
B的取值范围从1,2,3扩展到1,2,3,4广度优先遍历,20/22,LCS的应用:
最长递增子序列LIS,LongestIncreasingSubsequence给定一个长度为N的数组,找出一个最长的单调递增子序列。
例如:
给定数组5,6,7,1,2,8,则其最长的单调递增子序列为5,6,7,8,长度为4。
分析:
其实此LIS问题可以转换成最长公子序列问题,为什么呢?
21/22,使用LCS解LIS问题,原数组为A5,6,7,1,2,8排序后:
A1,2,5,6,7,8因为,原数组A的子序列顺序保持不变,而且排序后A本身就是递增的,这样,就保证了两序列的最长公共子序列的递增特性。
如此,若想求数组A的最长递增子序列,其实就是求数组A与它的排序数组A的最长公共子序列。
此外,本题也可以直接使用动态规划来求解,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分钟 搞定 LCS