Myers 差异算法¶

def myers_diff(a, b):
    """
    使用 Myers 差异算法计算两个序列之间的差异

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

    返回:
        编辑操作列表，其中:
        - ('+', i, x) 表示在位置 i 插入元素 x
        - ('-', i, x) 表示在位置 i 删除元素 x
    """
    # 创建编辑图
    n = len(a)
    m = len(b)
    max_edit = n + m

    # 存储每个 k 线上能到达的最远 x 坐标
    v = {1: 0}
    # 存储路径
    trace = []

    # 计算最短编辑路径
    for d in range(max_edit + 1):
        # 保存当前 d 的路径信息
        trace.append(v.copy())

        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, -1)  # 向下移动
            else:
                x = v.get(k - 1, -1) + 1  # 向右移动

            # 计算 y 坐标
            y = x - k

            # 沿对角线移动（匹配）
            while x < n and y < m and a[x] == b[y]:
                x += 1
                y += 1

            # 更新 v
            v[k] = x

            # 如果到达终点，回溯并返回编辑脚本
            if x >= n and y >= m:
                return _backtrack(a, b, trace, n, m)

    # 如果没有找到路径（不应该发生）
    return []

def _backtrack(a, b, trace, x, y):
    """回溯并构建编辑脚本"""
    result = []
    d = len(trace) - 1

    while d > 0:
        v = trace[d]
        k = x - y

        # 确定前一个 k 值
        if k == -d or (k != d and v.get(k - 1, -1) < v.get(k + 1, -1)):
            prev_k = k + 1
        else:
            prev_k = k - 1

        # 计算前一个位置
        prev_x = v.get(prev_k, 0)
        prev_y = prev_x - prev_k

        # 处理对角线移动（匹配）
        while x > prev_x and y > prev_y:
            x -= 1
            y -= 1

        # 记录编辑操作
        if x == prev_x:
            # 插入操作
            result.insert(0, ('+', x, b[prev_y]))
        else:
            # 删除操作
            result.insert(0, ('-', prev_x, a[prev_x]))

        # 更新位置
        x = prev_x
        y = prev_y
        d -= 1

    return result

# 测试
a = "ABCABBA"
b = "CBABAC"
diff = myers_diff(a, b)
print("差异结果:", diff)

import java.util.*;

public class MyersDiff {
    public static void main(String[] args) {
        String a = "ABCABBA";
        String b = "CBABAC";
        List<EditOperation> diff = myersDiff(a, b);
        System.out.println("差异结果:");
        for (EditOperation op : diff) {
            System.out.println(op);
        }
    }

    // 编辑操作类
    static class EditOperation {
        char type; // '+' 表示插入, '-' 表示删除
        int position;
        char element;

        public EditOperation(char type, int position, char element) {
            this.type = type;
            this.position = position;
            this.element = element;
        }

        @Override
        public String toString() {
            return "(" + type + ", " + position + ", " + element + ")";
        }
    }

    public static List<EditOperation> myersDiff(String a, String b) {
        char[] aChars = a.toCharArray();
        char[] bChars = b.toCharArray();
        int n = aChars.length;
        int m = bChars.length;
        int maxEdit = n + m;

        // 存储每个 k 线上能到达的最远 x 坐标
        Map<Integer, Integer> v = new HashMap<>();
        v.put(1, 0);

        // 存储路径
        List<Map<Integer, Integer>> trace = new ArrayList<>();

        // 计算最短编辑路径
        for (int d = 0; d <= maxEdit; d++) {
            // 保存当前 d 的路径信息
            trace.add(new HashMap<>(v));

            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, -1);  // 向下移动
                } else {
                    x = v.getOrDefault(k - 1, -1) + 1;  // 向右移动
                }

                // 计算 y 坐标
                int y = x - k;

                // 沿对角线移动（匹配）
                while (x < n && y < m && aChars[x] == bChars[y]) {
                    x++;
                    y++;
                }

                // 更新 v
                v.put(k, x);

                // 如果到达终点，回溯并返回编辑脚本
                if (x >= n && y >= m) {
                    return backtrack(aChars, bChars, trace, n, m);
                }
            }
        }

        // 如果没有找到路径（不应该发生）
        return new ArrayList<>();
    }

    private static List<EditOperation> backtrack(char[] a, char[] b, List<Map<Integer, Integer>> trace, int x, int y) {
        List<EditOperation> result = new ArrayList<>();
        int d = trace.size() - 1;

        while (d > 0) {
            Map<Integer, Integer> v = trace.get(d);
            int k = x - y;

            // 确定前一个 k 值
            int prevK;
            if (k == -d || (k != d && v.getOrDefault(k - 1, -1) < v.getOrDefault(k + 1, -1))) {
                prevK = k + 1;
            } else {
                prevK = k - 1;
            }

            // 计算前一个位置
            int prevX = v.getOrDefault(prevK, 0);
            int prevY = prevX - prevK;

            // 处理对角线移动（匹配）
            while (x > prevX && y > prevY) {
                x--;
                y--;
            }

            // 记录编辑操作
            if (x == prevX) {
                // 插入操作
                result.add(0, new EditOperation('+', x, b[prevY]));
            } else {
                // 删除操作
                result.add(0, new EditOperation('-', prevX, a[prevX]));
            }

            // 更新位置
            x = prevX;
            y = prevY;
            d--;
        }

        return result;
    }
}