Patience DiffPatience difference algorithm
先以双方唯一的公共行建立有序锚点，再比较锚点之间的片段。
- 核心约束
- 锚点序列必须在两个输入中保持一致的相对顺序。
- 适用问题
- 希望保留代码块结构、改善 diff 可读性的文本比较。
- 边界与取舍
- 不保证最少编辑，重复行多时会退回其他差异算法。
时间与空间#
N 为当前两段输入总行数，u 为两侧唯一匹配行数；行内容已预处理为可常数比较的分类编号。
- 时间复杂度
- 一轮唯一行建表期望 ，LIS 阶段 ；总成本含递归与回退
- 辅助空间
- 当前轮哈希表和候选链 ，递归 / 回退另计
以 Git 2.47 为例，原始文本哈希与行分类的字节处理另计；再找双方唯一行，取顺序一致的锚点。没有合适锚点时回退普通 diff；不是一个对所有输入保证 的整体算法。
工程中的应用#
1 个案例 · 附源码Git 文本差异默认采用 Myers 路径；选择 patience 时先利用双方唯一的公共行建立锚点，再处理锚点之间的差异。
附源码片段 · 检索与计算
基础原理参考资料
Git 2.47 · xpatience.c文件顶部说明唯一行、最长递增子序列、递归和回退步骤。