在日常工作与生活中，我们经常需要比较两个文本、文件或数据序列的差异，例如代码版本管理中的修改追踪、文档编辑中的变更对比等。1986 年，计算机科学家 Eugene W. Myers 提出的 O(ND) 差异算法，为这类问题提供了高效解决方案。该算法不仅能快速找到两个序列的差异，还能生成最短的编辑脚本（即从一个序列转换为另一个序列所需的最少操作），如今已被广泛应用于 Git、文本比较工具等场景。

Myers 算法编辑图示意

算法核心思想：从“编辑图”看序列差异

Myers 算法的核心在于将序列比较问题转化为“编辑图”中的路径搜索问题，通过直观的几何模型简化复杂的差异计算。

编辑图的构建

假设有两个待比较的序列：

  • 序列 A：[a, b, c, d]（长度为 m）
  • 序列 B：[a, c, d, e]（长度为 n）

我们可以构建一个 (m+1)×(n+1) 的网格（即编辑图）：

  • 横轴：表示序列 A 的位置（从 0 到 m）。
  • 纵轴：表示序列 B 的位置（从 0 到 n）。
  • 节点：网格中的每个点 (x, y) 代表“已处理完 A 的前 x 个元素和 B 的前 y 个元素”。

从起点 (0, 0) 到终点 (m, n) 的路径中，每一步移动都对应一种编辑操作：

  • 向右移动 (x+1, y)：表示删除 A 中的元素（操作：DELETE）。
  • 向上移动 (x, y+1)：表示插入 B 中的元素（操作：INSERT）。
  • 对角线移动 (x+1, y+1)：表示 A 和 B 的当前元素相同，无需操作（操作：MATCH）。

最短路径与最少编辑操作

Myers 算法的目标是找到从 (0, 0) 到 (m, n) 的最短路径，这条路径对应的编辑操作数量最少（即最小编辑距离）。其中，“距离”由非对角线步骤（插入/删除）的数量决定，对角线步骤（匹配）不增加距离。

为了高效找到最短路径，算法引入了 "k 线” 概念：

  • 定义 k = x - y（x 为横轴坐标，y 为纵轴坐标）。
  • 每条 k 线代表一组满足 x - y = k 的点。
  • 路径在 k 线上的移动，本质上是在平衡插入和删除操作的数量。

算法执行流程：分层探索

Myers 算法采用“分层探索”的方式，从距离 d=0 开始，逐步增加距离，直到抵达终点。每一层 d 代表“当前已使用 d 次插入/删除操作”，算法通过记录每层中能到达的最远位置，快速缩小搜索范围。

具体步骤可简化为：

  1. 初始化：设距离 d=0，记录每条 k 线上能到达的最远 x 坐标（表示在该 k 线下，用 d 次操作能处理 A 的最多元素）。
  2. 检查终点：判断是否已抵达终点 (m, n)，若是则停止搜索。
  3. 扩展搜索：增加距离 d，探索新的 k 线（k 的范围为 -d 到 +d，步长为 2），计算每条 k 线上能到达的最远 x 坐标。
  4. 循环迭代：重复步骤 2-3，直到找到终点。

实例演示

下面通过一个具体例子，展示 Myers 算法如何比较两个短序列的差异。

示例序列

  • 序列 A：ABCABBA（长度 7）
  • 序列 B：CBABAC（长度 6）

目标是找到从 A 到 B 的最短编辑脚本（插入 I、删除 D、匹配 M）。

算法执行过程

  1. 构建编辑图：横轴为 A 的位置（0-7），纵轴为 B 的位置（0-6），起点 (0,0)，终点 (7,6)。

  2. 分层探索路径：

    • d=0 时：只能沿 k=0 线移动（x=y），最远到达 (0,0)（未匹配任何元素）。
    • d=1 时：探索 k=-1 和 k=1 线，最远到达 (1,0)（删除 A 的第一个元素"A"）或 (0,1)（插入 B 的第一个元素"C"）。
    • 随着 d 增加：算法逐步推进，在 d=4 时，最终抵达终点 (7,6)。

生成的编辑脚本

通过回溯最短路径，得到从 A 到 B 的最少操作序列：

  1. D（删除 A 的第一个"A"）
  2. M（匹配"B"）
  3. M（匹配"C"）
  4. M（匹配"A"）
  5. M（匹配"B"）
  6. I（插入"C"，B 中新增的元素）
  7. D（删除 A 的最后一个"A"）

即编辑脚本为：D, M, M, M, M, I, D。共 7 步操作，其中 4 步为插入/删除（d=4），与算法计算的最小编辑距离一致。

算法优势与应用场景

Myers 算法的最大优势是在序列差异较小时（即相似性高）效率极高。其时间复杂度为 O(ND)（N 为两序列长度之和，D 为最小编辑距离），远优于传统的动态规划算法（O(N²)）。这使得它在实际场景中表现出色，例如：

  • 版本控制系统（如 Git）：用于比较代码文件的不同版本，生成差异补丁（Patch）。
  • 文本编辑器（如 VS Code）：实时显示两个文档的修改位置，提供高亮对比。
  • 数据同步工具：快速检测两个数据集的差异，实现增量同步。

总结

Myers 的 O(ND) 差异算法通过将序列比较转化为编辑图中的最短路径搜索，以高效的分层探索策略，在处理相似序列时展现了优异的性能。它不仅是理论上的重要突破，更成为了工业界解决差异比较问题的标准工具，深刻影响着我们对文本、数据的管理与处理方式。无论是开发人员使用 Git 追踪代码变更，还是普通人用工具对比文档修改，背后都可能有 Myers 算法的默默支撑。

参考资料