diff 真正决定的是什么
diff 的难点不在于发现某一行变了,而在于判断第一段文本中的哪一行对应第二段中的哪一行。一个在开头附近插入了段落的文档,并不是“后面所有内容都变了”的文档;配对糟糕的 diff 会显示一百行变更,而人眼看到的只是一次插入。
本页使用 **patience diff**,也就是 `git diff --patience` 采用的算法。它先找出在两侧都只出现一次的单位——某一行在两段文本中各出现一次,几乎可以确定就是同一行——再取这些单位在两侧顺序一致的最长递增子序列作为锚点,锚点之间的区间递归套用同一规则。作为背景,传统 diff 常基于最长公共子序列做动态规划,复杂度与两侧长度乘积相关;Myers 算法按编辑距离推进,在差异较少时更快;patience 则借唯一行避开重复行造成的错误配对。三者的取舍不同,但对“插入一段”这类常见修改,锚点法通常更接近人的判断。