最长公共子序列

维基百科,自由的百科全书
跳转至: 导航搜索
Confusion grey.svg
提示:本条目的主题不是最长公共子串

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

定義[编辑]

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

複雜度[编辑]

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

两个序列的解法[编辑]

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

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

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



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

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

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


计算LCS的长度[编辑]

下面算法计算了所有子问题的最长公共子序列长度C[i,j],并且用B[i,j]来作标记。用"↖"表示序列和的最后两项相等。用"↑"表示选择的时候不考虑,他们最长公共子序列就是的最长公共子序列。同理可得"←"表示他们最长公共子序列就是的最长公共子序列

for i := 1 to m
    C[i,0] := 0
for j := 1 to n
    C[0,j] := 0
for i := 1 to m
     for j := 1 to n
         if X[i] = Y[j]
             C[i,j] := C[i-1,j-1] + 1
             B[i,j] := "↖"
         else if C[i-1,j] >= C[i, j-1]
             C[i,j] := C[i-1,j]
             B[i,j] := "↑"
         else
             C[i,j] := C[i,j-1]
             B[i,j] : "←"

参见[编辑]

引用[编辑]

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

外部連結[编辑]