【Python】最长公共子序列LCS

雨点打透心脏的1/2处 2022-05-22 01:52 298阅读 0赞

LCS的定义

最长公共子序列,即Longest Common Subsequence,LCS。
一个序列S任意删除若干个字符得到新序列T,则T叫做S的子序列;
两个序列X和Y的公共子序列中,长度最长的那个,定义为X和Y的最长公共子序列。
字符串13455 与245576的最长公共子序列为455
字符串acdfg与adfc的最长公共子序列为adf
注意区别最长公共子串(Longest Common Substring)最长公共字串要求连续

LCS的意义

求两个序列中最长的公共子序列算法,广泛的应用在图形相似处理、媒体流的相似比较、计算生物学方面。生物学家常常利用该算法进行基因序列比对,由此推测序列的结构、功能和演化过程。

LCS可以描述两段文字之间的“相似度”,即它们的雷同程度,从而能够用来辨别抄袭。另一方面,对一段文字进行修改之后,计算改动前后文字的最长公共子序列,将除此子序列外的部分提取出来,这种方法判断修改的部分,往往十分准确。简而言之,百度知道、百度百科都用得上。

LCS的记号

字符串X,长度为m,从1开始数;
字符串Y,长度为n ,从1开始数;
Xi=﹤x1,⋯,xi﹥即X序列的前i个字符(1≤i≤m)(Xi不妨读作“字符串X的i前缀”)
Yj=﹤y1,⋯,yj﹥即Y序列的前j个字符 (1≤j≤n)(字符串Y的j前缀);
LCS(X , Y) 为字符串X和Y的最长公共子序列,即为Z=﹤z1,⋯,zk﹥。
注:不严格的表述。事实上,X和Y的可能存在多个子串,长度相同并且最大,因此,LCS(X,Y)严格的说,是个字符串集合。即:Z∈ LCS(X , Y) .

LCS解法的探索:

若xm=yn(最后一个字符相同),则:
Xm与Yn的最长公共子序列Zk的最后一个字符必定为xm
zk=xm=yn
LCS(Xm,Yn) = LCS(Xm-1,Yn-1)+xm

若xm≠yn,则:
LCS(Xm,Yn)= max{LCS(Xm-1,Yn),LCS(Xm,Yn-1)}

算法中的数据结构:长度数组

使用二维数组C[m,n]
c[i,j]记录序列Xi和Yj的最长公共子序列的长度。
当i=0或j=0时,空序列是Xi和Yj的最长公共子序列,故c[i,j]=0

算法中的数据结构:方向变量

使用二维数据B[m,n],其中,b[i,j]标记c[i,j]的值是由哪一个子问题的解达到的。即c[i,j]是由c[i-1,j-1]+1或者c[i-1,j]或者c[i,j-1]的哪一个得到的。取值范围为LeftTop ↖,Left ←,Top ↑ 三种情况

实例

X=< A,B,C,B,D,A,B >
Y=< B,D,C,A,B,A >

LCS

以上引用自七月在线

Pyhton代码如下:

  1. def LCS(s1, s2):
  2. size1 = len(s1) + 1
  3. size2 = len(s2) + 1
  4. # 程序多加一行,一列,方便后面代码编写
  5. chess = [[["", 0] for j in list(range(size2))] for i in list(range(size1))]
  6. for i in list(range(1, size1)):
  7. chess[i][0][0] = s1[i - 1]
  8. for j in list(range(1, size2)):
  9. chess[0][j][0] = s2[j - 1]
  10. print("初始化数据:")
  11. print(chess)
  12. for i in list(range(1, size1)):
  13. for j in list(range(1, size2)):
  14. if s1[i - 1] == s2[j - 1]:
  15. chess[i][j] = ['↖', chess[i - 1][j - 1][1] + 1]
  16. elif chess[i][j - 1][1] > chess[i - 1][j][1]:
  17. chess[i][j] = ['←', chess[i][j - 1][1]]
  18. else:
  19. chess[i][j] = ['↑', chess[i - 1][j][1]]
  20. print("计算结果:")
  21. print(chess)
  22. i = size1 - 1
  23. j = size2 - 1
  24. s3 = []
  25. while i > 0 and j > 0:
  26. if chess[i][j][0] == '↖':
  27. s3.append(chess[i][0][0])
  28. i -= 1
  29. j -= 1
  30. if chess[i][j][0] == '←':
  31. j -= 1
  32. if chess[i][j][0] == '↑':
  33. i -= 1
  34. s3.reverse()
  35. print("最长公共子序列:%s" % ''.join(s3))

调用:

  1. LCS("ABCBDAB", "BDCABA")

输出结果:

  1. 初始化数据:
  2. [[['', 0], ['B', 0], ['D', 0], ['C', 0], ['A', 0], ['B', 0], ['A', 0]],
  3. [['A', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]],
  4. [['B', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]],
  5. [['C', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]],
  6. [['B', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]],
  7. [['D', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]],
  8. [['A', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]],
  9. [['B', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]]]
  10. 计算结果:
  11. [[['', 0], ['B', 0], ['D', 0], ['C', 0], ['A', 0], ['B', 0], ['A', 0]],
  12. [['A', 0], ['↑', 0], ['↑', 0], ['↑', 0], ['↖', 1], ['←', 1], ['↖', 1]],
  13. [['B', 0], ['↖', 1], ['←', 1], ['←', 1], ['↑', 1], ['↖', 2], ['←', 2]],
  14. [['C', 0], ['↑', 1], ['↑', 1], ['↖', 2], ['←', 2], ['↑', 2], ['↑', 2]],
  15. [['B', 0], ['↖', 1], ['↑', 1], ['↑', 2], ['↑', 2], ['↖', 3], ['←', 3]],
  16. [['D', 0], ['↑', 1], ['↖', 2], ['↑', 2], ['↑', 2], ['↑', 3], ['↑', 3]],
  17. [['A', 0], ['↑', 1], ['↑', 2], ['↑', 2], ['↖', 3], ['↑', 3], ['↖', 4]],
  18. [['B', 0], ['↖', 1], ['↑', 2], ['↑', 2], ['↑', 3], ['↖', 4], ['↑', 4]]]
  19. 最长公共子序列:BCBA

发表评论

表情:
评论列表 (有 0 条评论,298人围观)

还没有评论,来说两句吧...

相关阅读

    相关 公共序列LCS问题

    好久没有写博客了,刚才在网上看了清华大学的数据结构公开课,链接:https://www.xuetangx.com 可以注册个账号去听数据结构课程,老师讲的特好。 我的代码是按

    相关 LCS 公共序列

    首先要明白什么是子序列,什么是子串; 设:主串长度为n; 子序列:从主串中抽出少于n的元素组成的序列(这些抽出的元素比一定是连续的他们的相对位置不变);