📚 课程目录第2章核心算法原理

2、核心算法原理：最长公共子序列（LCS）算法、Myers差分算法、编辑距离（Levenshtein Distance）算法

聊差分补丁，绕不开三个核心算法。它们就像三把不同的刀，各有各的脾气。我最早接触这些算法是在做代码版本管理工具的时候，那时候为了搞清楚「为什么 git diff 这么快」，硬啃了好几天的论文。今天我把这些心得掰开揉碎讲给你听。

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

LCS 要解决什么问题？说白了，就是找两个序列里「最长的那个共同子序列」。注意，子序列不要求连续，但顺序必须一致。

举个例子：ABCBDAB 和 BDCABA，它们的 LCS 是 BCBA 或 BDAB。你想想看，这不就是找两个文件里「没改动的那些行」吗？

2.1.1 动态规划思路

LCS 的经典解法是动态规划。我习惯用一个二维表格来推演：

// 伪代码：LCS 长度计算
function LCSLength(X, Y):
    m = len(X), n = len(Y)
    dp = new int[m+1][n+1]  // 全部初始化为 0
    for i = 1 to m:
        for j = 1 to n:
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

这个表格的每个格子 dp[i][j] 表示 X[0..i-1] 和 Y[0..j-1] 的 LCS 长度。回溯的时候，从右下角往左上角走，就能还原出具体的子序列。

核心要点：LCS 算法的时间复杂度是 O(mn)，空间复杂度也是 O(mn)。对于大文件，这个开销不小。我在项目中遇到过 10 万行的日志对比，直接用 LCS 内存就爆了，后来不得不改用分块策略。

2.1.2 从 LCS 到差分

有了 LCS，怎么生成补丁？很简单：LCS 里的字符就是「不变」的部分，剩下的就是「删除」和「插入」。

在 X 中但不在 LCS 中的 → 删除
在 Y 中但不在 LCS 中的 → 插入

但 LCS 有个问题：它只保证长度最长，不保证「看起来最自然」。比如两个文件只有一行变了，LCS 可能给出一个很别扭的匹配结果。嗯，这里就要引出 Myers 了。

2.2 Myers 差分算法

Myers 算法是 git diff 的默认算法。它比 LCS 高明在哪？它追求的是「最短的编辑脚本」——也就是让增删操作的总数最少，而且尽量让删除和插入「对齐」。

我个人觉得，Myers 最漂亮的地方在于它把问题转化成了「在图里找最短路径」。你想想看：

把两个字符串放在一个网格里，横轴是旧序列，纵轴是新序列
向右走一步 = 删除一个旧字符
向下走一步 = 插入一个新字符
向右下走对角线 = 字符匹配，不产生操作

我们要找的就是从左上角到右下角，对角线走得最多、横竖走得最少的那条路径。

2.2.1 贪心 + 回溯

Myers 用了一个很聪明的贪心策略：它从 (0,0) 出发，每次尝试走尽可能多的对角线，然后才考虑横竖移动。它维护一个「k 线」的概念——k = x - y，也就是当前路径偏离对角线的程度。

// 伪代码：Myers 核心逻辑（简化版）
function shortestEditScript(old, new):
    max = len(old) + len(new)
    v = new int[2*max + 1]  // 记录每个 k 线能到达的最远 x
    v[1] = 0
    for d = 0 to max:  // d 是编辑距离
        for k = -d to d step 2:
            // 决定从哪条路径延伸
            if k == -d or (k != d and v[k-1] < v[k+1]):
                x = v[k+1]
            else:
                x = v[k-1] + 1
            y = x - k
            // 尽量走对角线
            while x < len(old) and y < len(new) and old[x] == new[y]:
                x++, y++
            v[k] = x
            if x >= len(old) and y >= len(new):
                return reconstructPath(v, d, k)

避坑指南：我曾经在实现 Myers 时踩过一个坑——k 线的索引偏移。因为 k 可能是负数，数组下标不能为负，所以需要加一个偏移量。这个细节很容易被忽略，但错了就是段错误。

2.2.2 LCS vs Myers 对比

维度	LCS	Myers
目标	最长公共子序列	最短编辑脚本
时间复杂度	O(mn)	O((m+n)D)，D 为编辑距离
空间复杂度	O(mn)	O(m+n)
输出	子序列	增删操作序列
适用场景	文本相似度、基因序列	版本控制、差分补丁

你看，Myers 在大多数情况下比 LCS 快得多，因为 D（编辑距离）通常远小于 m+n。但最坏情况下，D 接近 m+n，Myers 就退化到 O((m+n)²) 了。

2.3 编辑距离（Levenshtein Distance）算法

编辑距离，也叫 Levenshtein 距离。它衡量的是「把一个字符串变成另一个字符串，最少需要多少次操作」。操作有三种：插入、删除、替换。

你可能会问：这和差分补丁有什么关系？关系大了。编辑距离本身就是一种「最小代价补丁」的度量。如果你把每行当作一个字符，编辑距离就是「最少改多少行」。

2.3.1 动态规划实现

编辑距离的 DP 表格和 LCS 很像，但递推公式不同：

// 编辑距离 DP
function levenshteinDistance(s1, s2):
    m = len(s1), n = len(s2)
    dp = new int[m+1][n+1]
    // 初始化边界
    for i = 0 to m: dp[i][0] = i
    for j = 0 to n: dp[0][j] = j
    // 填表
    for i = 1 to m:
        for j = 1 to n:
            cost = 0 if s1[i-1] == s2[j-1] else 1
            dp[i][j] = min(
                dp[i-1][j] + 1,      // 删除
                dp[i][j-1] + 1,      // 插入
                dp[i-1][j-1] + cost  // 替换或匹配
            )
    return dp[m][n]

注意：编辑距离的替换操作代价是 1，但在某些场景下（比如基因序列），替换的代价可能不同。我在做代码相似度检测时，就把替换代价设成了 2，因为「改一行」比「删一行再加一行」更常见。这个调参经验，你可以记一下。

2.3.2 三种算法的关系

其实这三个算法是「一家人」：

LCS 长度 + 编辑距离 = 字符串总长（当替换代价为 2 时）
Myers 的 D 值 = 编辑距离（当替换代价为 2 时）
LCS 回溯 + 补集 = 差分补丁

说白了，它们从不同角度描述同一件事：两个序列的差异有多大、差异在哪。

2.4 算法对比与选型建议

我做了这么多年工具，选型经验就一句话：看数据规模和实时性要求。

场景	推荐算法	理由
小文件（<1000 行）	LCS 或 Myers	性能差异不大，实现简单优先
大文件（>10000 行）	Myers	空间友好，平均速度快
需要相似度分数	编辑距离	直接输出数值，方便排序
实时交互预览	Myers + 分块	避免全量计算，分段 diff

我的习惯：做通用差分工具时，默认用 Myers。如果用户需要「相似度百分比」，我再额外算一个归一化的编辑距离。这样既保证了 diff 质量，又提供了量化指标。

2.5 知识体系总览

下面这张图把三个算法的关系、输入输出、适用场景串起来了。我建议你多看几遍，理解它们之间的转换关系。

这张图把三个算法的关系理清楚了。你从输入出发，经过不同的算法，得到不同的输出，最后都落到实际应用里。我个人建议你先把 LCS 和编辑距离的 DP 实现写一遍，再去看 Myers 的贪心策略，这样理解起来会顺很多。