Myers DiffMyers difference algorithm
在编辑图上逐层扩展可达路径，寻找较短的编辑脚本。
- 核心约束
- 每个编辑层保留各对角线上最远的匹配进展。
- 适用问题
- 版本差异与序列比较。
- 边界与取舍
- 实际实现可能采用提前退出等启发式，不能默认得到最小脚本。
时间与空间#
N 为两段序列长度之和，D 为最短插入 / 删除编辑脚本长度；单个序列元素的相等判断按 计。
- 时间复杂度
- 辅助空间
- 保存回溯轨迹的基本版 ；线性空间变体
常写作 的主项，D=0 时仍需 扫描。比较单位可为行、字符或 token；按行 / token 比较需已建立可常数判等的编号，否则另计内容比较与预处理。D 只计插入和删除。工程 diff 还可能为时延或可读性采用启发式截断。
工程中的应用#
1 个案例 · 附源码Git 文本差异默认采用 Myers 路径；选择 patience 时先利用双方唯一的公共行建立锚点，再处理锚点之间的差异。
附源码片段 · 检索与计算
基础原理参考资料
Myers 1986 · An O(ND) difference algorithm作者所在机构收录的原论文，包含线性空间变体。
Git 2.47 · xdiff core最短编辑路径及工程启发式的实现。