文本对比看起来只是"把不一样的地方标红标绿"，但真正难的是：插入一行后，后面所有行都往下挪了，怎么知道它们没变、只是位置偏了？ diff 算法的核心不是逐字符比，而是求一条"从 A 改到 B 代价最小的编辑路径"。
diff 到底在求解什么问题？
diff 的本质是求从文本 A 变成文本 B 的最短编辑序列：用最少的"插入"和"删除"操作把 A 改成 B。为什么不逐字符比？因为逐位比对遇到"在第 3 行插入一行"会彻底错乱——从插入点往后每一行都和原来对不齐，朴素比对会把它们全判成"改了"，而人眼一看就知道只是整体下移、内容没变。
把它建模成"最少编辑操作"后，算法就能识别出"这些行其实没变，只是被插入的新行顶下去了"。这与最长公共子序列（LCS） 是同一枚硬币的两面：A 和 B 的 LCS 越长，需要增删的部分就越少，两者一一对应。
最长公共子序列（LCS）是怎么定位"没变的部分"的？
LCS 指两段文本中按原顺序都出现、但不要求连续的最长子序列。它代表 A 和 B 共有、未被改动的内容；剩下的部分，A 里独有的就是"删除"，B 里独有的就是"新增"。经典解法是动态规划：
- 用一个二维表
dp[i][j]表示 A 前 i 个单位与 B 前 j 个单位的 LCS 长度； - 当前两个单位相同则
dp[i][j] = dp[i-1][j-1] + 1，否则取上方与左方的较大值； - 回溯这张表即可还原出哪些是公共的、哪些是增删。
它直观、好实现，但时间和空间都是 O(N×M)，N、M 是两段文本长度。文本一大，二维表就吃内存，这是它的硬伤。
Myers 算法为什么更快、更常用？
Myers 算法把 diff 看成"在编辑图里找最短路径"，在差异较小时远快于朴素 DP，这也是 Git 默认用它的原因。它的关键洞察是：实际场景里两个版本往往只差几处，差异数 D 很小。Myers 的复杂度约 O(ND)（N 为总长度，D 为编辑距离），当 D 远小于 N 时几乎线性。
| 维度 | LCS 动态规划 | Myers (O(ND)) |
|---|---|---|
| 思路 | 填二维表求最长公共子序列 | 编辑图上找最短编辑路径 |
| 时间复杂度 | O(N×M) | 约 O(ND)，D 为差异数 |
| 空间 | O(N×M)（可优化到 O(N)） | 线性空间变体 O(N) |
| 差异很小时 | 仍要填满整张表 | 极快（接近线性） |
| 差异很大时 | 稳定但慢 | 退化到接近 O(N²) |
| 典型采用 | 教学、短文本 | Git、多数 diff 工具 |
结论很实际：差异小用 Myers 占尽便宜，差异极大时两者都难免变慢。
行级 diff 和字符级 diff 该怎么选？
diff 的"比对单位"可大可小，单位选错会让结果难读。常见三档：
- 行级：以整行为单位比对，最常用。代码、配置、日志天然按行组织，结果干净；但只能告诉你"这一行变了"，不告诉你行里改了哪个字符。
- 词级：以单词/分词为单位，适合自然语言文本，能标出改了哪个词。
- 字符级：以单个字符为单位，最细，但对长文本会产生大量琐碎的增删片段，反而看不清。
工程上的常见做法是分层：先按行 diff 抓住宏观结构，再对"看起来是修改"的行对做更细粒度的二次 diff。
"行内高亮"是怎么实现的？
行内高亮（标出某一行里具体改了哪几个字符）通常是两级 diff 的结果。第一级做行级 diff，会得到一串"删除某行 + 新增某行"的操作；当一个删除行和一个新增行在位置上配对、且内容相似度足够高时，就把它们判定为"这一行被修改了"。第二级再对这一对行单独跑一次字符级或词级 diff，把行内真正变化的片段精确标出。
所以行内高亮并不是另一套魔法，而是在更细的粒度上重复同样的算法——这也解释了为什么它比纯行级 diff 更耗算力：每一对修改行都要再算一次。
能力边界与已知限制
diff 算法不是万能的，几个常见边界值得知道：
- 差异极大时退化：当两段文本几乎完全不同（D 接近 N），Myers 会退化到接近 O(N²)，超大文本可能明显卡顿；
- "语义等价"识别不了：算法只看字符序列，识别不了"变量重命名后逻辑没变"或"代码块整体搬家"这类语义层面的等价，搬家会被记成一删一增；
- 行尾与空白干扰：CRLF/LF 换行差异、行尾空格、缩进 tab/空格混用，都会被算成差异，对比前常需归一化；
- 比对单位影响可读性：字符级 diff 在长段落上会碎成大量小片段，可读性反而不如词级或行级。
判断一个 diff 结果好不好用，关键看比对单位是否匹配文本类型、以及是否对换行/空白做了合理归一化，而不只是算法本身快不快。
小结
文本对比的核心不是"逐字比对"，而是求最短编辑路径：LCS 找出未变的公共部分，Myers 用编辑图最短路径在差异小时做到接近线性。行级、词级、字符级是不同的比对粒度，行内高亮则是"先行级、再对修改行做字符级"的两级 diff。理解了"最短编辑序列 + 比对粒度 + 归一化"这三件事，就能判断一类 diff 实现适合什么样的文本与规模。