计算机科学

首页 > 计算机科学

最长公共子序列

2018-07-27 10:05:29     所属分类:算法
Confusion grey.svg
提示:本条目的主题不是最长公共子串

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

目录

  • 1 定义
  • 2 复杂度
  • 3 两个序列的解法
    • 3.1 计算LCS的长度
  • 4 参见
  • 5 引用
  • 6 外部链接

定义

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

复杂度

对于一般性的LCS问题(即任意数量的序列)是属于NP-hard。但当序列的数量确定时,问题可以使用动态规划(Dynamic Programming)在多项式时间内解决。[1]

两个序列的解法

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

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

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



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

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

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


计算LCS的长度

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

function LCSLength(X1..m, Y1..n)
    C = array(0..m, 0..n)
    for i := 0..m
       Ci,0 = 0
    for j := 0..n
       C0,j = 0
    for i := 1..m
        for j := 1..n
            if Xi = Yj
                Ci,j := Ci-1,j-1 + 1
            else
                Ci,j := max(Ci,j-1, Ci-1,j)
    return Cm,n

参见

  • 莱文斯坦距离

引用

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

外部链接

  • (英文) longest common subsequence
  • (英文) Longest Common Subsequences

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
无需打赏可直接关闭阅读全文
1分,2分不嫌少,钱不钱的无所谓,重要的是你的话语激励我前行!

愿你每天温暖如春!!!


相关推荐