Myers差异算法可视化 - Git Diff核心

Myers差异算法是由Eugene W. Myers在1986年提出的，用于计算两个序列之间的最小编辑距离。它是Git diff、GNU diff等工具的核心算法。该算法通过在"编辑图"上搜索从左上角到右下角的最短路径来找出差异，每次向右移动表示删除，向下移动表示插入，对角线移动表示匹配。

编辑图 (Edit Graph)

编辑距离 D = 0

核心概念

构建编辑图：X轴代表源序列，Y轴代表目标序列
水平移动 = 删除源序列字符，垂直移动 = 插入目标序列字符
对角线移动 = 字符匹配（免费）
目标：找到从(0,0)到(N,M)的最短路径
使用D值（编辑距离）逐层搜索，找到最小D的路径

算法从D=0开始，逐步增加D值，直到找到一条从(0,0)到(N,M)的路径。这保证了找到的是最短编辑路径。

时间与空间复杂度

指标	复杂度	说明
时间复杂度	O((N+M)D)	D是编辑距离，最坏情况D=N+M
最坏时间	O((N+M)²)	两个完全不同的序列
空间复杂度	O(N+M)	只需存储当前和前一行的状态

在实际应用中，大多数差异较小，因此平均性能非常好。

应用场景

Git版本控制系统的diff功能
GNU diff工具
代码审查工具的变更对比
文档比较和合并工具
DNA序列比对（生物信息学）

Git Diff 版本控制代码审查文档对比

代码实现

def myers_diff(a, b):
    """Myers差异算法 - 返回编辑距离"""
    n, m = len(a), len(b)
    max_d = n + m
    
    # V数组存储每个k对角线能到达的最远x坐标
    v = {1: 0}
    
    for d in range(max_d + 1):
        for k in range(-d, d + 1, 2):
            # 决定从哪个方向来
            if k == -d or (k != d and v.get(k-1, -1) < v.get(k+1, -1)):
                x = v.get(k + 1, 0)  # 从上方下来(插入)
            else:
                x = v.get(k - 1, 0) + 1  # 从左边过来(删除)
            
            y = x - k
            
            # 沿对角线移动(匹配)
            while x < n and y < m and a[x] == b[y]:
                x, y = x + 1, y + 1
            
            v[k] = x
            
            if x >= n and y >= m:
                return d  # 找到最短编辑距离
    
    return -1


# 使用示例
a = "ABCDEF"
b = "ABXDEF"
distance = myers_diff(a, b)
print(f"编辑距离: {distance}")  # 输出: 2

import java.util.*;

public class MyersDiff {
    
    /**
     * Myers差异算法 - 返回编辑距离
     */
    public static int myersDiff(String a, String b) {
        int n = a.length();
        int m = b.length();
        int maxD = n + m;
        
        // V数组存储每个k对角线能到达的最远x坐标
        Map<Integer, Integer> v = new HashMap<>();
        v.put(1, 0);
        
        for (int d = 0; d <= maxD; d++) {
            for (int k = -d; k <= d; k += 2) {
                int x;
                
                // 决定从哪个方向来
                if (k == -d || (k != d && 
                    v.getOrDefault(k-1, -1) < v.getOrDefault(k+1, -1))) {
                    x = v.getOrDefault(k + 1, 0);
                } else {
                    x = v.getOrDefault(k - 1, 0) + 1;
                }
                
                int y = x - k;
                
                // 沿对角线移动(匹配)
                while (x < n && y < m && 
                       a.charAt(x) == b.charAt(y)) {
                    x++; y++;
                }
                
                v.put(k, x);
                
                if (x >= n && y >= m) {
                    return d;
                }
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        String a = "ABCDEF";
        String b = "ABXDEF";
        int distance = myersDiff(a, b);
        System.out.println("编辑距离: " + distance);
        // 输出: 2
    }
}