Myers Diff Algorithm Visualization - Git Diff Core

The Myers diff algorithm was proposed by Eugene W. Myers in 1986 for computing the minimum edit distance between two sequences. It is the core algorithm of Git diff, GNU diff, and other tools. The algorithm finds differences by searching for the shortest path from the top-left to the bottom-right corner on an 'edit graph', where moving right represents deletion, moving down represents insertion, and diagonal moves represent matches.

Source Sequence (A)

Target Sequence (B)

Core Concepts

Build edit graph: X-axis represents source, Y-axis represents target
Horizontal move = delete from source, Vertical move = insert from target
Diagonal move = character match (free)
Goal: Find shortest path from (0,0) to (N,M)
Search layer by layer with increasing D (edit distance)

Algorithm starts with D=0, incrementally increasing D until finding a path from (0,0) to (N,M). This guarantees finding the shortest edit path.

Time and Space Complexity

Metric	Complexity	Description
Time Complexity	O((N+M)D)	D is edit distance, worst case D=N+M
Worst Case Time	O((N+M)²)	Two completely different sequences
Space Complexity	O(N+M)	Only need current and previous row states

In practice, most differences are small, so average performance is excellent.

Applications

Git version control diff functionality
GNU diff tool
Code review change comparison
Document comparison and merge tools
DNA sequence alignment (bioinformatics)

Git Diff Version Control Code Review Document Comparison

Implementation

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
    }
}