最长公共子序列

最长公共子序列LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的問題。这与查找最長公共子串的问题不同的地方是:子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题,也是数据比较英语data comparison程序,比如Diff工具,和生物信息学应用的基础。它也被广泛地应用在版本控制,比如Git用来调和文件之间的改变。

定義

一个数列 ,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则 称为已知序列的最长公共子序列。

複雜度

對於一般性的LCS問題(即任意數量的序列)是屬於NP-hard。但當序列的數量確定時,問題可以使用动态规划(Dynamic Programming)在多項式時間内解決。[1]

两个序列的解法

最长公共子序列问题存在最优子结构:这个问题可以分解成更小,更简单的“子问题”,这个子问题可以分成更多的子问题,因此整个问题就变得简单了。最长公共子序列问题的子问题的解是可以重复使用的,也就是说,更高级别的子问题通常会重用低级子问题的解。拥有这个两个属性的问题可以使用动态规划算法来解决,这样子问题的解就可以被储存起来,而不用重复计算。这个过程需要在一个表中储存同一级别的子问题的解,因此这个解可以被更高级的子问题使用。

动态规划的一个计算最长公共子序列的方法如下,以两个序列  为例子:

设有二维数组 表示  位和  位之前的最长公共子序列的长度,则有:

 
 

其中,  的第 位与 的第 位完全相同时为“1”,否则为“0”。

此时, 中最大的数便是  的最长公共子序列的长度,依据该数组回溯,便可找出最长公共子序列。

算法的空间、时间复杂度均为 ,经过优化后,空间复杂度可为 

计算LCS的长度

下面算法计算了所有子问题的最长公共子序列长度C[i,j]

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

参见

引用

  1. ^ 屈, 婉玲. 算法设计与分析. 北京清华大学学研大厦A座: 清华大学出版社. 2011: 67. ISBN 978-7-302-24756-2. 

外部連結