每日算法 — 使用java实现Myers差分算法：O(ND)最小编辑脚本与对角线回溯重建

在体素沙盒类游戏里，一个 16×16×256 的区块（chunk）包含超过 6 万个方块位置。玩家挖掉几块石头、放下几块木板，服务端就需要把这份改动同步给所有客户端。最朴素的做法是把整个区块的方块数组序列化后发过去——单次同步几十 KB，一秒几十次，带宽瞬间被吃光。工程上的标准答案是只发送差异：把旧快照和新快照做一次差分（diff），得到一串”保留 / 删除 / 插入”的编辑指令，客户端照着指令重放即可。

问题在于”差异”并不唯一。从 [石头, 泥土, 石头, 木头] 变成 [石头, 石头, 泥土, 木头]，你可以说”删掉第 2 项、在第 2 项插入泥土”，也可以说”删掉第 3 项、在第 3 项插入泥土”，两者都是 2 步。真正想要的是编辑步数最少的那个结果，因为它对应最小的网络流量。求最少编辑步数的经典算法，就是 Myers 在 1986 年那篇 4 页论文里给出的 O(ND) 算法——它至今仍是 git、diff、rsync 这类工具的核心。

一、把方块同步建模成最短编辑脚本问题

先把游戏语义剥掉，只留下序列。设旧快照为序列 A（长度 N），新快照为序列 B（长度 M）。定义三种编辑操作：

一个编辑脚本（edit script）就是把 A 变成 B 的操作序列。脚本长度 = DELETE 数 + INSERT 数（KEEP 不算开销），记作编辑距离 D。这里要立刻澄清一个常见误解：这个 D 不等于 Levenshtein 距离，因为 Myers 只允许”删”和”插”，不允许”替换”。一次替换在 Myers 里表现为一次 DELETE 加一次 INSERT，代价是 2。

由此得到最基本的关系式：

D = (N - L) + (M - L) = N + M - 2L

其中 L 是被 KEEP 的元素个数，也就是 A 与 B 的最长公共子序列（LCS）长度。于是”最小编辑脚本”和”求 LCS”是同一个问题的两个面。LCS 的教科书解法是 O(NM) 动态规划——对 6 万方块的区块就是 36 亿次比较，实时同步完全不可接受。

Myers 算法的洞察是：不要以位置为坐标，而要以对角线为坐标，并且只沿着”最远可达点”前进。它把复杂度从 O(NM) 降到 O((N+M)·D)，而实际同步场景中 D 通常只有几十到几百，因此比 DP 快几个数量级。

二、算法核心：对角线、最远可达点、蛇形扩展

2.1 编辑图与对角线

把 A 放在横轴、B 放在纵轴，构成一个 (N+1)×(M+1) 的网格。每个格点 (x, y) 表示”已消耗 A 的前 x 个元素、B 的前 y 个元素”。从 (0,0) 走到 (N,M)：

• 水平移动 (x,y)→(x+1,y)：DELETE，代价 1
• 垂直移动 (x,y)→(x,y+1)：INSERT，代价 1
• 对角移动 (x,y)→(x+1,y+1)：仅当 A[x] == B[y] 时合法，表示 KEEP，代价 0

最优编辑脚本就是这个网格上从 (0,0) 到 (N,M) 的最小代价路径。定义对角线编号 k = x - y，落在同一条对角线上的所有格点，其编辑步数都是相同的（因为每走一步水平或垂直，x-y 要么 +1 要么 -1，而走过的步数正好等于 |k| 加上额外的往返）。这正是 Myers 用 k 做外层循环的原因：第 d 轮，只可能落在 k ∈ {-d, -d+2, …, d} 这些奇偶性与 d 相同的对角线上。

2.2 V 数组：每条对角线的最远 x

对每条对角线 k，记录”在恰好 d 步编辑之内，能到达的最大 x”，记作 V[k]。一旦某条对角线上的最远点 x 对应的 y 已经越过边界，说明这条线走完了；当 x >= N && y >= M 时，第 d 轮就是答案，最小编辑步数 = d。

关键递推只有三行：

if (k == -d || (k != d && V[k-1] < V[k+1])) {
    x = V[k+1];          // 从上方下来：INSERT
} else {
    x = V[k-1] + 1;      // 从左侧过来：DELETE
}
int y = x - k;
while (x < N && y < M && A[x] == B[y]) { x++; y++; }   // 免费对角线狂奔

为什么这样取最大 x 是对的？因为对角线 k 只能由 k+1（垂直移动，x 不变）或 k-1（水平移动，x+1）到达。要最大化 x，就从两条前驱里挑 x 更大的那条：V[k+1] 与 V[k-1]+1。k == -d 时只有 k+1 可达，k == d 时只有 k-1 可达，这就是两个边界条件的由来。

选完起点后，沿着对角线尽可能多地匹配相同元素——这一步不花编辑步数，是”白捡”的前进，也是整个算法能超越 O(NM) 的根本原因。

2.3 为什么是 O((N+M)·D)

第 d 轮处理 d+1 条对角线，每条对角线上的 while 循环总推进量受 N、M 限制。可以证明：所有 while 循环在整个算法中的总推进次数不超过 N+M（每条对角线上 x 单调增且不回头，跨轮的同一对角线上 V 只增不减）。于是总时间为 O(D²)（枚举对角线）+ O(N+M)（扩展）= O((N+M)·D)。空间上，若保存每轮的 V 快照用于回溯，是 O(D²)，最坏 O((N+M)²)。

2.4 回溯：从 (N,M) 倒推操作序列

只算出 d 还不够，还要还原具体操作。回溯时从 (N,M) 出发，沿着每轮的 V 快照反查”我是从哪条对角线来的”，并沿途把免费匹配的对角步记为 KEEP。反向收集后翻转即为正序脚本。这段回溯是 Myers 实现里最容易写错的部分，下面的 Java 代码把它拆成了清晰的三段：先回收对角 KEEP，再判定单步方向，最后同步指针。

三、完整 Java 项目结构

项目基于 Maven，JDK 17，无第三方依赖（只用 JUnit 5 做测试），可直接 mvn test 或 mvn exec:java 运行。

voxel-chunk-diff/
├── pom.xml
└── src
    ├── main
    │   └── java
    │       └── com/example/chunkdiff
    │           ├── EditType.java        // KEEP / DELETE / INSERT
    │           ├── EditOp.java          // 单条操作（类型 + 元素）
    │           ├── EditScript.java      // 脚本容器 + 应用/校验
    │           ├── MyersDiff.java       // 核心算法
    │           └── ChunkSyncDemo.java   // 演示入口：区块快照差分
    └── test
        └── java
            └── com/example/chunkdiff
                └── MyersDiffTest.java

pom.xml：

<project xmlns="http://maven.apache.org/POM/4.0.0">
  <modelVersion>4.0.0</modelVersion>
  <groupId>com.example</groupId>
  <artifactId>voxel-chunk-diff</artifactId>
  <version>1.0</version>
  <properties>
    <maven.compiler.source>17</maven.compiler.source>
    <maven.compiler.target>17</maven.compiler.target>
    <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
  </properties>
  <dependencies>
    <dependency>
      <groupId>org.junit.jupiter</groupId>
      <artifactId>junit-jupiter</artifactId>
      <version>5.10.2</version>
      <scope>test</scope>
    </dependency>
  </dependencies>
</project>

3.1 数据类型

package com.example.chunkdiff;

/** 三种编辑操作的枚举。KEEP 不计入编辑距离。 */
public enum EditType { KEEP, DELETE, INSERT }

/** 一条编辑操作：类型 + 该步对应的元素值（KEEP 取 A 的值，INSERT 取 B 的值）。 */
public record EditOp(EditType type, int value) {
    @Override public String toString() {
        return switch (type) {
            case KEEP   -> "  = " + value;
            case DELETE -> "- " + value;
            case INSERT -> "+ " + value;
        };
    }
}

3.2 编辑脚本容器

package com.example.chunkdiff;

import java.util.ArrayList;
import java.util.List;

/**
 * 编辑脚本：把 A 变成 B 的操作序列。
 * 提供 apply() 用于在客户端重放，verify() 用于断言脚本正确性。
 */
public final class EditScript {
    private final List<EditOp> ops;

    public EditScript(List<EditOp> ops) {
        this.ops = List.copyOf(ops);
    }

    public List<EditOp> ops() { return ops; }

    /** 客户端重放：把脚本作用到源序列上，得到目标序列。 */
    public int[] apply(int[] source) {
        int[] out = new int[source.length + countInsert() - countDelete()];
        int ai = 0, oi = 0;
        for (EditOp op : ops) {
            switch (op.type()) {
                case KEEP   -> { out[oi++] = source[ai++]; }
                case DELETE -> { ai++; }
                case INSERT -> { out[oi++] = op.value(); }
            }
        }
        if (ai != source.length || oi != out.length) {
            throw new IllegalStateException("脚本与应用不一致：ai=" + ai + ", oi=" + oi);
        }
        return out;
    }

    /** 编辑距离 = DELETE 数 + INSERT 数。 */
    public int distance() {
        return countDelete() + countInsert();
    }

    public int countDelete() { return (int) ops.stream().filter(o -> o.type() == EditType.DELETE).count(); }
    public int countInsert() { return (int) ops.stream().filter(o -> o.type() == EditType.INSERT).count(); }

    @Override public String toString() {
        StringBuilder sb = new StringBuilder();
        ops.forEach(o -> sb.append(o).append('\n'));
        return sb.toString();
    }
}

3.3 核心算法实现

package com.example.chunkdiff;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Myers O(ND) 差分算法（带完整回溯）。
 *
 * 记号：N=|A|, M=|B|, 最大编辑步数 max = N+M。
 * 对角线 k = x - y，取值范围 [-max, max]，用 offset = max 平移到数组下标。
 */
public final class MyersDiff {

    private final int[] a;
    private final int[] b;

    public MyersDiff(int[] a, int[] b) {
        this.a = a;
        this.b = b;
    }

    /** 计算最小编辑脚本。 */
    public EditScript diff() {
        int n = a.length, m = b.length;
        int max = n + m;                  // 编辑距离的平凡上界：全删全插
        int offset = max;                 // k 的平移量，保证下标非负
        int size = 2 * max + 3;           // 多留 2 个哨兵，避免 k±1 越界判断

        int[] v = new int[size];          // V[k] = 第 d 步时对角线 k 的最远 x
        // trace[d] 保存"开始处理第 d 轮之前"的 V 快照，即第 d-1 轮的结果，
        // 回溯时用它还原第 d 轮的父子关系。
        int[][] trace = new int[max + 1][];
        int dFound = -1;

        // ---------- 阶段一：正向推进，求最小 d ----------
        for (int d = 0; d <= max && dFound < 0; d++) {
            trace[d] = v.clone();          // 快照（深拷贝，否则会被本轮覆盖）
            for (int k = -d; k <= d; k += 2) {
                // 选前驱：优先取 V[k+1]（INSERT，x 不变），否则 V[k-1]+1（DELETE）
                int x;
                if (k == -d || (k != d && v[k - 1 + offset] < v[k + 1 + offset])) {
                    x = v[k + 1 + offset];
                } else {
                    x = v[k - 1 + offset] + 1;
                }
                int y = x - k;
                // 免费前进：相等元素沿对角线一路狂奔，不消耗编辑步数
                while (x < n && y < m && a[x] == b[y]) { x++; y++; }
                v[k + offset] = x;
                if (x >= n && y >= m) {    // 已抵达终点，d 即最小编辑距离
                    dFound = d;
                    break;
                }
            }
        }

        // ---------- 阶段二：从 (n, m) 反向回溯 ----------
        int x = n, y = m, d = dFound;
        List<EditOp> reversed = new ArrayList<>();
        while (d > 0) {
            int[] prev = trace[d];         // 第 d 轮开始前的 V（= 第 d-1 轮结果）
            int k = x - y;
            int prevK;                     // 第 d 轮的落点来自哪条对角线
            if (k == -d || (k != d && prev[k - 1 + offset] < prev[k + 1 + offset])) {
                prevK = k + 1;
            } else {
                prevK = k - 1;
            }
            int prevX = prev[prevK + offset];
            int prevY = prevX - prevK;

            // 从 (x,y) 往回"吐"对角 KEEP，直到落到 (prevX, prevY)
            while (x > prevX && y > prevY) {
                reversed.add(new EditOp(EditType.KEEP, a[x - 1]));
                x--; y--;
            }
            // 剩下的那一步就是水平(DELETE)或垂直(INSERT)
            if (x == prevX) {
                reversed.add(new EditOp(EditType.INSERT, b[y - 1]));
                y--;
            } else {
                reversed.add(new EditOp(EditType.DELETE, a[x - 1]));
                x--;
            }
            x = prevX; y = prevY;          // 指针归位，进入上一轮
        }
        // d = 0 阶段：起点之前可能还有一段纯对角匹配
        while (x > 0 && y > 0) {
            reversed.add(new EditOp(EditType.KEEP, a[x - 1]));
            x--; y--;
        }

        Collections.reverse(reversed);
        return new EditScript(reversed);
    }
}

3.4 演示入口：区块快照同步

package com.example.chunkdiff;

import java.util.Random;

/**
 * 用真实场景跑一遍：两个 16×16×16 区块的方块数组，只改了几处，观察差分规模。
 * 运行：mvn -q compile exec:java -Dexec.mainClass=com.example.chunkdiff.ChunkSyncDemo
 */
public final class ChunkSyncDemo {

    /** 方块类型 ID：0=空气 1=石头 2=泥土 3=草方块 4=圆石 5=木头 6=沙子 7=水 */
    private static final int AIR = 0, STONE = 1, DIRT = 2, GRASS = 3, COBBLE = 4, LOG = 5, SAND = 6, WATER = 7;

    public static void main(String[] args) {
        Random rnd = new Random(42);
        int volume = 16 * 16 * 16;                 // 4096 个方块，够演示内存特性

        int[] server = new int[volume];
        for (int i = 0; i < volume; i++) {
            // 模拟地层：y 越大越深，方块类型随深度变化
            int y = (i >> 8) & 0xF;
            server[i] = (y == 0) ? GRASS : (y < 4 ? DIRT : (y < 9 ? STONE : STONE));
        }

        int[] client = server.clone();
        // 客户端视角：玩家挖了 3 块石头、放了 2 块木头、倒了一桶水
        client[300] = AIR; client[510] = AIR; client[744] = AIR;
        client[301] = LOG; client[302] = LOG;
        client[1200] = WATER;

        long t0 = System.nanoTime();
        EditScript script = new MyersDiff(server, client).diff();
        long elapsed = System.nanoTime() - t0;

        int[] rebuilt = script.apply(server);
        boolean same = java.util.Arrays.equals(rebuilt, client);

        System.out.printf("方块总量       : %d%n", volume);
        System.out.printf("最小编辑距离 D : %d%n", script.distance());
        System.out.printf("KEEP/DEL/INS   : %d / %d / %d%n",
                script.ops().size() - script.distance(), script.countDelete(), script.countInsert());
        System.out.printf("耗时           : %.2f ms%n", elapsed / 1_000_000.0);
        System.out.printf("重放结果精准   : %s%n", same);
        // 粗略估算带宽节省：原始快照按 short 计 2 字节/方块
        int rawBytes = volume * 2;
        int diffBytes = script.distance() * 6;   // 每条指令约 6 字节（类型 + 位置 + 方块 ID）
        System.out.printf("原始字节 / 差分字节 : %d / %d (节省 %.1f%%)%n",
                rawBytes, diffBytes, 100.0 * (rawBytes - diffBytes) / rawBytes);
    }
}

3.5 单元测试

package com.example.chunkdiff;

import org.junit.jupiter.api.Test;
import java.util.Arrays;
import java.util.Random;
import static org.junit.jupiter.api.Assertions.*;

class MyersDiffTest {

    /** 性质测试：脚本必须能把 A 精确变成 B，且编辑距离等于 N+M-2*LCS。 */
    @Test
    void scriptAlwaysRebuildsTarget() {
        Random rnd = new Random(20261103L);
        for (int iter = 0; iter < 2000; iter++) {
            int[] a = randomArray(rnd, rnd.nextInt(20));
            int[] b = randomArray(rnd, rnd.nextInt(20));
            EditScript s = new MyersDiff(a, b).diff();
            assertArrayEquals(b, s.apply(a), "重放失败: " + Arrays.toString(a) + " -> " + Arrays.toString(b));
            int lcs = lcsDp(a, b);
            assertEquals(a.length + b.length - 2 * lcs, s.distance(), "非最小编辑距离");
        }
    }

    @Test
    void emptyInputs() {
        assertEquals(0, new MyersDiff(new int[0], new int[0]).diff().distance());
        assertEquals(5, new MyersDiff(new int[0], new int[]{1,2,3,4,5}).diff().distance());
        assertEquals(5, new MyersDiff(new int[]{1,2,3,4,5}, new int[0]).diff().distance());
    }

    @Test
    void identicalSequencesProduceZeroCost() {
        int[] a = {1,2,3,4};
        EditScript s = new MyersDiff(a, a.clone()).diff();
        assertEquals(0, s.distance());
        assertEquals(4, s.ops().size());        // 全是 KEEP
    }

    private static int[] randomArray(Random rnd, int len) {
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) arr[i] = rnd.nextInt(4);   // 小字母表，制造大量重复
        return arr;
    }

    /** O(NM) 参考实现，仅用于测试对拍。 */
    private static int lcsDp(int[] a, int[] b) {
        int[][] dp = new int[a.length + 1][b.length + 1];
        for (int i = 1; i <= a.length; i++)
            for (int j = 1; j <= b.length; j++)
                dp[i][j] = a[i-1] == b[j-1]
                        ? dp[i-1][j-1] + 1
                        : Math.max(dp[i-1][j], dp[i][j-1]);
        return dp[a.length][b.length];
    }
}

用 2000 组随机用例与小字母表（大小 4）做对拍，是最有效的验证手段——小字母表会制造大量”同样最优距离但路径不同”的情况，最容易暴露回溯逻辑的 off-by-one。

四、复杂度与实测特性

表中的结论值得展开：Myers 的时间上界是 O((N+M)·D)，但当 D 接近 N+M 时（例如客户端切换到完全不同的区域），复杂度退化为 O((N+M)²)，同时 trace 的二维快照会吃掉 O(D²) 内存——4096 个方块彻底换血时，max=8192，trace 是 8193×16387 int ≈ 536 MB，直接 OOM。工程上有三条对策：

1. 前后缀剥离：先扫一遍，剥掉公共前缀和公共后缀，实测能把 D 再降一到两个数量级（绝大多数改动只集中在局部）。
2. 线性空间版本：不保存所有轮次的 V，而是用”前向 V 与反向 V 在中间回合相遇”的middle snake 技术，二分递归，得到 Hirschberg 式 O(N+M) 空间。核心是把一次 diff 拆成”在中间找一个必经的对角蛇形段，然后对左右两半递归”，递归深度 O(log D)，每层扫描 O(N+M)。
3. 超阈值降级：若 D 超过预设阈值（例如 D > 0.5*(N+M)），直接发送全量快照，或改用基于哈希分块的 rsync 式同步——这也是实际游戏服务端（如主流体素游戏的 chunk 全量/增量双通道）采用的策略。

五、工程化要点与常见坑

坑 1：trace 快照必须深拷贝。 trace[d] = v 只是引用赋值，v 在下一轮被原地覆盖，回溯时读到的全是终态。代码里必须 v.clone()。这也是被问得最多的 Myers 实现 bug。

坑 2：数组长度要留哨兵。 k 循环里访问 v[k+1+offset]，当 k = d = max 时下标为 max+1+max = 2max+1，若数组长度只有 2max+1 就会越界。写成 2*max+3 可以省掉每个分支的额外判断。

坑 3：方块 ID 的映射成本。 真实区块里方块是对象（含 BlockState、NBT、光照），直接 equals 比较代价高。务必先做一次规范化为 int 字典序：把出现的所有 BlockState 收集到 Map<BlockState,Integer>，再转成 int[] 做差分，比较退化为一次整数比较，整体能快 5～10 倍。

坑 4：多解不唯一。 当 A、B 中存在重复元素时，最优脚本可能有很多个，Myers 返回哪个取决于前驱选择规则（V[k-1] < V[k+1] 严格小于）。这对同步正确性无关，但会让”看起来像 git 的输出”这件事变得不可复现——若要稳定输出，需要对相同距离时固定 tie-break 规则（git 的做法是 xdl_change_compact 后处理，把相邻的增删块尽量合并对齐）。

坑 5：脚本需要重放校验。 客户端可能因乐观锁顺序错乱导致重放后状态不一致。生产环境务必在 apply() 后追加一次区块哈希（例如累加 CRC32）比对，作为一致性断言。

六、小结

Myers 算法的价值不在于它多复杂，而在于它把”求最小编辑脚本”这个看似需要 O(NM) 的问题，变成了以 D 为导向的稀疏搜索：外层按编辑步数迭代，内层沿对角线贪心地吞掉所有能免费匹配的元素，因此每一步都物有所值。它的思想与 A、IDA 一脉相承——都是”按代价分层扩展，直到触及目标”，只是这里的启发式退化为零，取而代之的是”对角线免费前进”这一结构性剪枝。

放到体素沙盒游戏的语境里，这套算法让 4096 个方块的区块同步从几十 KB 降到几十字节量级；放到更一般的语境里，它是所有版本控制、增量备份、文本编辑器撤销栈的共同底座。理解 V 数组的几何含义（每条对角线的最远可达 x），你就同时理解了 LCS、编辑距离和 diff 输出三件事。

下一步可以尝试：把本文实现改成线性空间 middle-snake 版本；或者把 int 比较换成 滚动哈希 + 前缀和，把对角线扩展从”逐元素比较”升级为”二分求最长公共前缀”，让单次扩展从 O(len) 降到 O(log len)——这就是 git 的 xdiff 与 Google 的 diff-match-patch 在生产环境里做的事。