Diff 算法入门：LCS 与 Myers，以及代码评审中高效读 diff 的技巧Diff Algorithms 101: LCS and Myers, Plus Tricks for Reading Diffs in Code Review

从一行改动到 diff 输出From a one-line change to diff output

最早接触 diff 是在大学做课程项目，队友改了一个变量名，我在终端敲 `git diff`，屏幕上跳出一大片红色和绿色，我以为他重写了整个文件。后来才知道，那是因为他同时用编辑器格式化了代码，缩进从 4 空格变成了 2 空格，diff 把每一行都标记成了"删除+新增"。这个经历让我意识到：diff 不是"智能地告诉你改了什么"，而是"用某种算法算出两组文本的最小差异"，算法不同，输出的差异形态就不同。I first met diff in a university project. A teammate renamed a variable, I ran `git diff`, and the screen lit up with red and green — I thought he had rewritten the whole file. It turned out his editor had also reformatted indentation from 4 spaces to 2, so diff marked every line as delete-plus-add. That taught me: diff does not "intelligently tell you what changed"; it computes a minimal difference between two texts with some algorithm, and different algorithms produce different shapes of change.

一个最朴素的想法是：把两个文件的行对齐，相同的保留，不同的标出来。但问题在于，当中间插入或删除了若干行时，后面的行全部错位，逐行对比会把所有后续行都标成改动。真正的 diff 算法要解决的是"找到最长的公共部分，剩下的就是差异"——这就是最长公共子序列（LCS）的思路。The naive idea is to align lines and mark mismatches. But when lines are inserted or deleted in the middle, everything after shifts, and a line-by-line comparison flags all subsequent lines as changed. A real diff algorithm must "find the longest common part; the rest is the difference" — that is the longest common subsequence (LCS) approach.

LCS：最朴素的最长公共子序列LCS: the naive longest common subsequence

LCS 的定义很直观：两个序列中，按顺序出现但不一定连续的最长公共序列。比如 `ABCBDAB` 和 `BDCAB` 的 LCS 是 `BCAB` 或 `BDAB`，长度 4。把它套到文本 diff 上，把每一行当作一个元素，两个文件的 LCS 就是"不需要改动的行"，剩下的行就是删除或新增。LCS is straightforward: the longest sequence that appears in both inputs in order but not necessarily contiguously. For `ABCBDAB` and `BDCAB`, the LCS is `BCAB` or `BDAB`, length 4. Applied to text diff, treat each line as an element; the LCS of two files is the "unchanged lines", and everything else is a deletion or insertion.

经典实现用动态规划：建一个 `(m+1) × (n+1)` 的二维表，`dp[i][j]` 表示前 i 行和前 j 行的 LCS 长度。如果两行相等，`dp[i][j] = dp[i-1][j-1] + 1`；否则取 `max(dp[i-1][j], dp[i][j-1])`。时间复杂度 O(m×n)，空间也是 O(m×n)。对几百行的小文件没问题，但对几万行的大文件，这个表会占几百 MB，慢得无法接受。The classic implementation uses dynamic programming: build an `(m+1) × (n+1)` table where `dp[i][j]` is the LCS length of the first i and j lines. If the lines match, `dp[i][j] = dp[i-1][j-1] + 1`; otherwise take `max(dp[i-1][j], dp[i][j-1])`. Time and space are both O(m×n). Fine for a few hundred lines, but for tens of thousands of lines the table consumes hundreds of megabytes and becomes unusably slow.

LCS 还有一个工程问题：它找到的"最长公共子序列"不一定是人类觉得最自然的差异。比如在两段相似代码中间插入一行，LCS 可能把后面的行匹配到前面去，产生看起来很奇怪的 diff。这就是为什么实际工具很少用纯 LCS。LCS also has an engineering problem: the "longest common subsequence" it finds is not always the diff a human finds natural. Inserting one line between two similar blocks can make LCS match later lines to earlier ones, producing weird-looking output. That is why real tools rarely use pure LCS.

Myers 算法：为什么 git diff 用它Myers: why git diff uses it

1986 年 Eugene Myers 提出了一个更聪明的算法，核心思想是把 diff 问题转化为"在编辑图上找最短路径"。想象一个网格，横轴是原文件的行，纵轴是新文件的行，从左上角走到右下角，向右走一步表示删除一行，向下走一步表示新增一行，对角线表示两行相同。Myers 算法用贪心策略，优先走对角线（匹配），在无法匹配时才做删除或新增，并且用"蛇形"（snake）的概念一次吃掉尽可能多的匹配。In 1986 Eugene Myers proposed a smarter algorithm that reframes diff as "finding the shortest path on an edit graph". Picture a grid: the x-axis is the original file's lines, the y-axis is the new file's lines. Starting at the top-left and moving to the bottom-right, a step right deletes a line, a step down inserts a line, and a diagonal means the lines match. Myers uses a greedy strategy — prefer diagonals (matches), only delete or insert when forced — and the concept of a "snake" to consume as many matches as possible at once.

它的时间复杂度是 O((m+n)×D)，其中 D 是差异的数量（编辑距离）。当两个文件差异不大时，D 很小，算法极快；即使差异大，也比 O(m×n) 好得多。空间上 Myers 用了线性空间的变种（Hunt–McIlroy 或 Myers 自己的线性空间改进），不会爆内存。Git 默认使用的就是 Myers 算法的一个变体，`git diff --histogram` 则是在 Myers 基础上做了优化，对大文件和重复行多的文件效果更好。Its time complexity is O((m+n)×D), where D is the number of differences (edit distance). When two files are similar, D is small and the algorithm is extremely fast; even with large differences, it beats O(m×n). For space, Myers uses a linear-space variant, so memory never explodes. Git defaults to a Myers variant, and `git diff --histogram` builds on Myers with optimisations that work better for large files and files with many repeated lines.

我自己在实现一个轻量文本对比工具时，最初用了朴素 LCS，测一个 3000 行的日志文件对比花了 8 秒还占了 200MB 内存。换成 Myers 后，同样的对比在 80 毫秒内完成，内存可以忽略。这个差距让我真切体会到算法选型的重要性。When I built a lightweight text diff tool, I started with naive LCS. Comparing two 3,000-line log files took 8 seconds and 200 MB of memory. Switching to Myers brought the same comparison under 80 milliseconds with negligible memory. That gap drove home how much algorithm choice matters.

代码评审中高效读 diff 的技巧Tricks for reading diffs in code review

算法懂了，回到日常工作。我做代码评审时积累了几个提效的习惯。第一，先看 diffstat 或文件列表，判断改动范围：是改了一个函数还是动了 20 个文件？范围决定了评审策略。第二，忽略纯格式化噪音：`git diff -w` 忽略空白变化，`--ignore-space-at-eol` 忽略行尾空白，能把"重命名变量+格式化"这种改动还原成真实的逻辑变更。第三，用 `git diff --word-diff` 看行内差异，长字符串或配置项改动时比逐行对比清晰得多。With the algorithms understood, back to daily work. I have picked up several habits for efficient review. First, check diffstat or the file list to gauge scope: one function or twenty files? Scope decides the review strategy. Second, ignore formatting noise: `git diff -w` ignores whitespace, `--ignore-space-at-eol` ignores trailing whitespace, which restores real logic changes from "rename plus reformat" commits. Third, use `git diff --word-diff` for inline differences — much clearer than line-by-line for long strings or config changes.

第四，对大段重构，不要硬读 diff，改用 `git log -p -L` 跟踪某个函数的历史，或者用 `git range-diff` 对比两个分支的差异集。第五，善用语义 diff 工具：传统 diff 是基于行的，而 `difftastic`、`semanticdiff` 这类工具基于语法树，能识别"函数只是移动了位置"而非"删除+新增"，对重构评审帮助极大。Fourth, for large refactors, do not force-read the diff. Use `git log -p -L` to trace a function's history, or `git range-diff` to compare two branches' change sets. Fifth, use semantic diff tools: traditional diff is line-based, while tools like difftastic and semanticdiff understand syntax trees and recognise "function moved" rather than "delete plus add" — a huge help for refactoring reviews.

最后一个建议：评审时不要只看 diff，还要看上下文。diff 只展示改动行附近的几行，很多 bug 藏在改动影响到的远处逻辑里。我通常会把改动文件完整打开，结合 diff 一起读。本站的文本对比工具支持并排视图、忽略空白和行内高亮，适合快速对比两段配置或代码片段，是命令行之外的一个轻量补充。One last tip: do not read only the diff; read the context too. Diff shows only a few lines around each change, and many bugs hide in distant logic affected by the change. I usually open the full file alongside the diff. Our text diff tool supports side-by-side view, whitespace ignoring and inline highlighting, handy for quickly comparing config snippets or code fragments as a lightweight supplement to the command line.