比较两段文字的程序并不会像人一样读懂内容、判断“哪里改了”。它要做的是：在两个列表之间，找出用最少的删除和插入把一方变成另一方的方法。本文介绍 diff 如何计算出这个答案，以及为什么结果有时会和人的预期不一样。
比较的单位：行、词、字符
diff 首先把文本拆分成由标记（token）组成的列表。传统的 diff 和 git 把一整行当作一个标记。因此，即使一行里只改了一个字符，整行也会显示为“删除 1 行 + 新增 1 行”。
按行比较速度快，也很适合代码审查；但对于一整段长文写在同一行的文档，就很难看出具体改了哪里。所以许多工具分两步比较：
- 按行比较，找出变更的行。
- 把变更的行两两配对，再按词或字符比较行内的内容。
本站也采用同样的方式。行内比较的单位可以在词、按空格分段、字符之间选择。
最长公共子序列（LCS）
diff 的数学核心是最长公共子序列（Longest Common Subsequence，LCS）。子序列是在保持顺序的前提下挑出部分元素得到的序列。例如，ABCABBA 和 CBABAC 的最长公共子序列长度为 4，CABA、BABA 都是其中的例子。
LCS 中的元素是“保持不变的部分”，其余元素要么是“被删除的”（只在左侧），要么是“新增的”（只在右侧）。LCS 越长，所需的删除和新增就越少。设两个列表的长度分别为 N、M，LCS 长度为 L，则所需删除与新增的总数 D 为：
D = (N - L) + (M - L)在上面的例子中，N=7、M=6、L=4，所以 D = 3 + 2 = 5。这个 D 称为（只允许插入和删除时的）编辑距离，删除与新增的操作列表称为编辑脚本。
编辑图与 Myers 算法
用教科书上的方法（动态规划）求 LCS，需要一张 N×M 大小的表。两份 1 万行的文件相比，就是 1 亿个格子，既慢又占内存。1986 年，Eugene W. Myers 在论文《An O(ND) Difference Algorithm and Its Variations》中提出了更快的方法，它成为今天 GNU diff 和 git 默认算法的基础。
Myers 把比较问题转化为在网格上寻找最短路径：
- 从左上角 (0,0) 走到右下角 (N,M)。
- 向右走一格 = 删除左侧文本的一个元素；向下走一格 = 新增右侧文本的一个元素。每步代价为 1。
- 当两个元素相同时，可以沿对角线免费前进。这样连续的对角线段称为 snake。
代价最小的路径就是最短的编辑脚本。Myers 算法依次扩展“代价为 0 能到达的最远位置”“代价为 1 能到达的最远位置”……直到抵达终点为止。每一步只需记住每条对角线上走得最远的位置，因此耗时大致与 (N+M)×D 成正比。两段文本几乎相同时 D 很小，速度非常快；完全不同时则会变慢。
线性内存与 middle snake
要回溯出路径，就得记录每一步的状态，内存可能随 D² 增长。Myers 在同一篇论文中还提出了一种变体：同时从起点正向搜索、从终点反向搜索，找到两者相遇的对角线段（middle snake）。以该点为界把问题拆成两个更小的问题并递归处理，内存用量就只与输入规模成正比。
代价过高时：近似启发式
如果两个输入都有数万行且差异很大，D 也会很大，(N+M)×D 可能达到数十亿。GNU diff 为此设置了一种启发式：当搜索步数超过一定上限时，就在目前推进得最远的对角线处把问题切开。结果仍然是正确的编辑脚本，但不再保证是最短的。GNU diff 和 git 的 --minimal 选项会让它即使多花时间也要找出最小结果。
最小不一定最好读
编辑距离相同的路径可能有好几条。例如在代码中新增一个函数时，右花括号 } 和空行到处都有，算法可能把“新函数的 }”和“原有函数的 }”配成一对。结果虽然是最小的，人看起来却很别扭。这正是 git 默认使用根据缩进移动变更边界的启发式，并提供 patience、histogram 等其他算法的原因。详细比较见 diff 算法比较。
在本工具中
本站的比较引擎用 JavaScript 实现了 Myers 算法的线性内存变体，输入较大时会像 GNU diff 一样改用近似分割。计算在 Web Worker 中进行，即使载入大文件页面也不会卡住。得到按行比较的结果后，会把内容相似的变更行配对并标记为“修改”，再按您选择的单位（词、按空格分段、字符）对其内容做一次比较并高亮显示。
不妨在 文本对比工具 中放入两段文本，切换行内比较单位，看看结果如何变化。如何以 git 格式阅读结果，请参阅 unified diff 阅读指南。