跳转至

最长公共子序列（LCS）算法

算法简介

最长公共子序列（Longest Common Subsequence，简称 LCS）算法是一种用于找出两个序列中最长的共同子序列的经典动态规划算法。与 Myers 差异算法不同，LCS 不直接计算编辑操作，而是专注于找出两个序列共有的部分。LCS 在生物信息学、文件比较、版本控制系统和自然语言处理等领域有广泛应用。

算法原理

LCS 算法基于以下核心概念：

子序列与公共子序列

  • 子序列：从一个序列中删除某些元素（可以不删除）后得到的新序列。例如，"ACE" 是 "ABCDE" 的一个子序列。
  • 公共子序列：同时是两个序列的子序列。例如，"BC" 是 "ABCD" 和 "XBCZ" 的一个公共子序列。
  • 最长公共子序列：所有公共子序列中最长的一个。

动态规划思想

LCS 算法使用动态规划来解决问题，通过构建一个二维表格来存储中间结果：

  1. 定义状态：dp[i][j] 表示序列 A 的前 i 个元素和序列 B 的前 j 个元素的最长公共子序列长度。
  2. 状态转移方程：
  3. 如果 A[i-1] = B[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
  4. 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  5. 边界条件：dp[0][j] = dp[i][0] = 0（空序列的 LCS 长度为 0）

算法步骤详解

  1. 初始化：
  2. 创建一个 (n+1) × (m+1) 的二维数组 dp，其中 n 和 m 分别是序列 A 和 B 的长度

  3. 初始化第一行和第一列为 0

  4. 填充 dp 表格：

  5. 对于每个位置 (i,j)，1 ≤ i ≤ n, 1 ≤ j ≤ m：

    • 如果 A[i-1] = B[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
    • 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])

  6. 回溯构建 LCS：

  7. 从 dp[n][m] 开始回溯
  8. 如果 A[i-1] = B[j-1]，将该字符加入 LCS，并移动到 dp[i-1][j-1]
  9. 否则，移动到 dp[i-1][j] 或 dp[i][j-1] 中较大的一个

图解示例

让我们通过一个例子来理解 LCS 算法。假设我们有两个字符串： - A = "ABCBDAB" - B = "BDCABA"

构建 dp 表格

我们构建一个 (8×7) 的表格：

    |   | B | D | C | A | B | A
----+---+---+---+---+---+---+---
    | 0 | 0 | 0 | 0 | 0 | 0 | 0
----+---+---+---+---+---+---+---
  A | 0 | 0 | 0 | 0 | 1 | 1 | 1
----+---+---+---+---+---+---+---
  B | 0 | 1 | 1 | 1 | 1 | 2 | 2
----+---+---+---+---+---+---+---
  C | 0 | 1 | 1 | 2 | 2 | 2 | 2
----+---+---+---+---+---+---+---
  B | 0 | 1 | 1 | 2 | 2 | 3 | 3
----+---+---+---+---+---+---+---
  D | 0 | 1 | 2 | 2 | 2 | 3 | 3
----+---+---+---+---+---+---+---
  A | 0 | 1 | 2 | 2 | 3 | 3 | 4
----+---+---+---+---+---+---+---
  B | 0 | 1 | 2 | 2 | 3 | 4 | 4

回溯构建 LCS

从 dp[7][6] = 4 开始回溯：
1. A[6] = B[5] = 'A'，加入 LCS，移动到 dp[6][5]
2. A[5] = 'D' ≠ B[4] = 'A'，dp[5][5] > dp[6][4]，移动到 dp[5][5]
3. A[4] = 'B' = B[4] = 'B'，加入 LCS，移动到 dp[4][4]
4. A[3] = 'C' ≠ B[3] = 'A'，dp[3][4] = dp[4][3]，移动到 dp[3][4]
5. A[2] = 'C' ≠ B[2] = 'C'，dp[2][4] > dp[3][3]，移动到 dp[2][4]
6. A[1] = 'B' = B[0] = 'B'，加入 LCS，移动到 dp[1][0]
7. 到达边界

因此，LCS 是 "BBA"（反向）或 "ABB"（正向）。

动画演示

代码实现

def longest_common_subsequence(a, b):
    """
    计算两个序列的最长公共子序列

    参数:
        a: 第一个序列
        b: 第二个序列

    返回:
        最长公共子序列
    """
    n = len(a)
    m = len(b)

    # 创建 dp 表格
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # 填充 dp 表格
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # 回溯构建 LCS
    lcs = []
    i, j = n, m
    while i > 0 and j > 0:
        if a[i-1] == b[j-1]:
            lcs.append(a[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1

    # 反转得到正确顺序
    return ''.join(reversed(lcs))

# 测试
a = "ABCBDAB"
b = "BDCABA"
lcs = longest_common_subsequence(a, b)
print(f"序列 A: {a}")
print(f"序列 B: {b}")
print(f"最长公共子序列: {lcs}")

public class LongestCommonSubsequence {
    public static void main(String[] args) {
        String a = "ABCBDAB";
        String b = "BDCABA";
        String lcs = findLCS(a, b);
        System.out.println("序列 A: " + a);
        System.out.println("序列 B: " + b);
        System.out.println("最长公共子序列: " + lcs);
    }

    public static String findLCS(String a, String b) {
        int n = a.length();
        int m = b.length();

        // 创建 dp 表格
        int[][] dp = new int[n + 1][m + 1];

        // 填充 dp 表格
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // 回溯构建 LCS
        StringBuilder lcs = new StringBuilder();
        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                lcs.append(a.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        // 反转得到正确顺序
        return lcs.reverse().toString();
    }
}

复杂度分析

  • 时间复杂度：O(n×m)
  • 需要填充 n×m 大小的 dp 表格

  • 每个单元格的计算是 O(1) 操作

  • 空间复杂度：O(n×m)

  • 需要存储 n×m 大小的 dp 表格
  • 可以优化为 O(min(n,m))，只保存两行或两列

LCS 与差异算法的关系

LCS 算法与差异算法（如 Myers 差异算法）有密切关系：

  1. 差异表示：找到 LCS 后，可以将不在 LCS 中的元素标记为插入或删除操作
  2. A 中不在 LCS 中的元素表示删除操作

  3. B 中不在 LCS 中的元素表示插入操作

  4. 编辑距离：编辑距离 = len(A) + len(B) - 2×len(LCS)

  5. 这是因为每个不在 LCS 中的元素都需要一次编辑操作

  6. 效率对比：

  7. LCS：时间复杂度 O(n×m)，适用于一般情况
  8. Myers：时间复杂度 O(n×d)，当编辑距离 d 远小于序列长度时更高效

算法优化

LCS 算法有几种常见的优化方式：

  1. 空间优化：
  2. 只保存两行（或两列）的 dp 值，将空间复杂度降低到 O(min(n,m))

  3. 使用滚动数组技术

  4. 剪枝优化：

  5. 预先计算序列的公共前缀和后缀，只对中间部分应用 LCS 算法

  6. 对于很长但差异很小的序列特别有效

  7. 分治策略：

  8. 使用"分而治之"的思想，将问题分解为更小的子问题
  9. 可以与并行计算结合，提高大规模序列比较的效率

应用场景

LCS 算法在多个领域有广泛应用：

  1. 生物信息学：
  2. DNA 和蛋白质序列比对

  3. 基因组研究和进化分析

  4. 文本比较：

  5. 文件差异比较工具（如 diff）

  6. 抄袭检测系统

  7. 版本控制系统：

  8. 识别文件版本之间的变化

  9. 合并不同版本的文件

  10. 自然语言处理：

  11. 文本相似度计算

  12. 自动摘要生成

  13. 数据压缩：

  14. 某些差分压缩算法的基础

练习题

  1. 基础实现：实现 LCS 算法，计算两个字符串的最长公共子序列。

  2. 空间优化：修改 LCS 算法，使其只使用 O(min(n,m)) 的空间复杂度。

  3. 应用：使用 LCS 算法实现一个简单的文本差异比较工具，高亮显示插入和删除的部分。

  4. 扩展：实现最长公共子串（Longest Common Substring）算法，与 LCS 不同，子串要求连续。

  5. 多序列 LCS：扩展 LCS 算法，使其能够处理三个或更多序列的最长公共子序列。

  6. LCS 与编辑距离：证明并实现：编辑距离 = len(A) + len(B) - 2×len(LCS)，并解释这个公式的含义。

  7. 高效实现：实现一个能够处理非常长序列（如基因组数据）的高效 LCS 算法，结合多种优化技术。

参考资料

  1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). "Introduction to Algorithms" (3rd ed.). MIT Press. [经典算法教材，详细介绍了 LCS 的动态规划解法]

  2. Hirschberg, D. S. (1975). "A linear space algorithm for computing maximal common subsequences". Communications of the ACM, 18(6), 341-343. [介绍了线性空间复杂度的 LCS 算法]

  3. Hunt, J. W., & McIlroy, M. D. (1976). "An Algorithm for Differential File Comparison". Computing Science Technical Report, Bell Laboratories 41. [早期的差异算法，使用 LCS 作为基础]

  4. Myers, E. W. (1986). "An O(ND) Difference Algorithm and Its Variations". Algorithmica, 1(1), 251-266. [介绍了与 LCS 相关的差异算法]

  5. Bergroth, L., Hakonen, H., & Raita, T. (2000). "A survey of longest common subsequence algorithms". In Proceedings of the Seventh International Symposium on String Processing and Information Retrieval (SPIRE'00). [LCS 算法的综述论文]



📅 Created 0 days ago ✏️ Updated 0 days ago
daichangya