LCS最长公共子序列

应用

• 图形相似处理
• 媒体流的相似比较
• 描述文本相似度 来辨别抄袭

定义

• 最长公共子序列
• 一个序列S任意删除若干个字符得到的新字符T，则T叫做S的子序列
• 两个序列X和Y的公共子序列中，长度最长的那个，定义为X和Y的最长公共子序列
  1. 字符串13455与245576 的最长公共子序列是455
  2. 字符串acdfg 与adfc 的最长公共子序列是adf
• 最长公共子序列要求连续

穷举法

假设字符型X 和 字符串Y的长度分别为m 和 n

X的一个子序列即下标{1,2,3,...,m}严格递增子序列 , 因此X共有2m个不同的子序列，同理Y也有2n

从穷举搜索法需要的时间复杂度 O(2m * 2n)

这种方式显然是不可取的： 对X的每一个序列，检查它是否在Y的子序列从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长公共子序列

动态规划法

• 字符串X ，长度为m ，从1开始数
• 字符串Y ，长度为n ，从1开始数
• Xi = <X1,...,Xi > 即X序列的前i个字符(1<=i<=m) (Xi 记作“字符串X的i前缀”)
• Yj = <Y1,...,Yj > 即Y序列的前i个字符(1<=j<=n) (Yj 记作“字符串Y的i前缀”)
• LCS(X,Y)为字符串X和Y的最长公共子序列，即<Z1,...,Zk >
• 如果Xm = Yn(最后一个字符相同)，则：Xm 和 Yn的最长公共子序列Zk的最后一个字符必定为Xm = (Yn)
• Zk = Xm = Yn
• 推导出公式

LCS(X_m,Y_n)=LCS(X_{m-1} , Y_{n-1})+X_mLCS(Xm​,Yn​)=LCS(Xm−1​,Yn−1​)+Xm​

例如： 字符串 BDC 和 字符串 ABC

对于上面字符的X和Y

• 找Xm = Ym
• X3 = Y3
• LCS(BDC,ABC) = LCS(BD,AB) + C

• 如果Xm !=Yn

LCS(X_m,Y_n)=max\{LCS(X_{m-1} , Y_{n}) ,LCS(X_{m} , Y_{n-1}\}LCS(Xm​,Yn​)=max{LCS(Xm−1​,Yn​),LCS(Xm​,Yn−1​}

• X2 != Y2
• LCS(BD,AB) =max{LCS(BD,A),LCS(B,AB)}

• 得到公式

LCS(X_m,Y_m) = \begin{cases} LCS(X_{m-1},Y_{n-1})+Xm &{\text{当}}X_m=Y_m \\ max\{LCS(X_m,Y_{n-1}),LCS(x_{m-1},Y_{n}) \}&{\text{当}}X_m!=Y_m \\ \end{cases}LCS(Xm​,Ym​)={LCS(Xm−1​,Yn−1​)+Xmmax{LCS(Xm​,Yn−1​),LCS(xm−1​,Yn​)}​当Xm​=Ym​当Xm​!=Ym​​

如果使用二维数组C[m][n]

• C[i,j]记录序列Xi和Yj的最长公共子序列的长度

• X=acdfg

• Y=adfc

      a  d  f  c
  [0. 0. 0. 0. 0.]
a [0. 1. 1. 1. 1.]
c [0. 1. 1. 1. 2.]
d [0. 1. 2. 2. 2.]
f [0. 1. 2. 3. 3.]
g [0. 1. 2. 3. 3.]

--得到的最长公共子序列长度为3
--相似度则为 3*2/(5+4) = 0.67

• 最终得到公式

c(i,j)= \begin{cases} 0 &{\text{当i=0或者j=0}} \\ c(i-1,j-1)+1 &{\text{当i,j>0 并且}}X_i=Y_j \\ max\{c(i-1)(j),c(i,j-1)\} &{\text{当i,j>0 并且}}X_i !=Y_j\\ \end{cases}c(i,j)=⎩⎪⎨⎪⎧​0c(i−1,j−1)+1max{c(i−1)(j),c(i,j−1)}​当i=0或者j=0当i,j>0 并且Xi​=Yj​当i,j>0 并且Xi​!=Yj​​

相似度 = 最长公共子序列的长度 * 2 / 两个对比文本的总长度

使用python来实现LCS

"""
LCS最长公共子序列对比文本相似度对比
"""


import numpy as np
# 反序
def lcs(str1,str2):
    list_np = np.zeros([len(str1)+1,len(str2)+1]) # 浮点类型的
    li1 = list(range(0,len(str1)))
    li1.reverse()
    li2 = list(range(0, len(str2)))
    li2.reverse()
    for i in li1:
        for j in li2:
            if str1[i] == str2[j]:
                list_np[i][j] = list_np[i+1][j+1] + 1
            else:
                list_np[i][j] = max(list_np[i+1][j],list_np[i][j+1])
    print(list_np)
    ret =  list_np[0][0] * 2 /(len(str1) +len(str2))
    return ret;

# 正序
def lcs2(str1,str2):
    list_np = np.zeros([len(str1) + 1, len(str2) + 1])  # 浮点类型的
    li1 = list(range(1, len(str1)+1))
    li2 = list(range(1, len(str2)+1))
    for i in li1:
        for j in li2:
            if str1[i-1] == str2[j-1]:
                list_np[i][j] = list_np[i-1][j-1]+1
            else:
                list_np[i][j] = max(list_np[i - 1][j ],list_np[i ][j - 1])
    print(list_np)
    ret = list_np[len(str1)][len(str2)] * 2 / (len(str1) +len(str2))
    return ret

def main():
    str1 = "adsadasdaa"
    str2 ="sdasdsadsa"
    print("文本相似度为",lcs(str1,str2))

if __name__ == '__main__':
    main()

使用scala 来实现

object LCSDemo {
  def main(args: Array[String]): Unit = {
    val str1 = "acdfg"
    val str2 = "adfc"
    println(lcs(str1, str2))
  }

  def lcs(str1: String, str2: String): Double = {
    //Array.ofDim[Int](x,y) 生成一个二维数组初始值为Int类型，并且维度为x 和 y
    val list_arr = Array.ofDim[Int](str1.length + 1, str2.length + 1)
    for (i <- 1 to str1.length; j <- 1 to str2.length) {
      if (str1(i - 1) == str2(j - 1)) {
        list_arr(i)(j) = list_arr(i - 1)(j - 1) + 1
      } else {
        list_arr(i)(j) = list_arr(i)(j - 1).max(list_arr(i - 1)(j))
      }
    }
    val ret = list_arr(str1.length)(str2.length)
    ret * 2 / (str1.length + str2.length).toDouble
  }
}