比较 两个文件

“Diffs”是变更的通用语。它们是紧凑的叙述，告诉你一件事物的两个版本之间 什么移动了——源代码、散文、数据集——而无需 强迫你重读所有内容。在那几个符号（+、 -、@@）背后，存在着一个由算法、启发式方法和格式组成的深层堆栈， 它们平衡了最优性、速度和人类理解。本文是diffs从算法到工作流的实践之旅：它们如何计算，如何格式化， 合并工具如何使用它们，以及如何为更好的审查调整它们。在此过程中，我们将把 主张建立在主要来源和官方文档上——因为像空白是否 计数这样的小细节真的很重要。

“diff”到底是什么

形式上，diff描述了一个最短编辑脚本（SES），用于通过插入和删除将“旧”序列转换为“新”序列（有时还包括替换， 可以建模为删除+插入）。在实践中，大多数面向程序员的diff是面向行的，然后为了可读性可选择地细化为单词或字符。 规范的输出是 上下文 和 统一 格式；后者——你通常在代码审查中看到的——用一个简洁的标题 和“hunks”来压缩输出，每个hunk都显示了变更周围的上下文邻域。统一格式 通过-u/--unified选择，是补丁的事实标准； patch通常受益于上下文行 来稳健地应用变更。

GNU diff手册列出了当你想要更少 噪音和更多信号时可以使用的开关——忽略空格、扩展制表符以进行对齐，或者要求一个 “最小”编辑脚本，即使它更慢 (选项参考)。这些选项不会改变两个文件不同的含义；它们改变的是 算法搜索更小脚本的积极程度以及结果如何呈现给人类。

从LCS到Myers：diffs是如何计算的

大多数文本diffs都建立在 最长公共子序列（LCS） 的抽象之上。经典的动态规划在O(mn)时间和空间内解决LCS，但 对于大文件来说太慢且耗费内存。 Hirschberg的算法 展示了如何使用分治法在线性空间（仍然是 O(mn)时间）内计算最优对齐，这是一种影响了 实用diff实现的基本节省空间技术。

在速度和质量方面，突破是 Eugene W. Myers于1986年提出的算法，它在O(ND)时间（N ≈ 总行数，D ≈ 编辑距离） 和近线性空间内找到一个SES。Myers在一个“编辑图”中建模编辑，并沿着最远到达的边界前进，产生的结果在行diff设置中既快又接近 最小。这就是为什么“Myers”在许多工具中仍然是默认设置。

还有 Hunt–Szymanski 家族，当匹配位置很少时，它会加速LCS（通过预先索引匹配并追踪 递增子序列），并且在历史上与早期的diff变体有关。 这些算法揭示了权衡：在匹配稀疏的输入中，它们可以 以亚二次方式运行。有关连接理论和实现的从业者概述，请参阅 Neil Fraser的笔记。

当“最优”不可读时：耐心和直方图策略

Myers旨在实现最小的编辑脚本，但“最小”≠“最可读”。重新排序或复制的大块 可能会欺骗纯粹的SES算法，使其产生尴尬的对齐。进入 patience diff，归功于Bram Cohen：它锚定在独特的、低频的行上以 稳定对齐，通常产生人类认为更清晰的diffs——尤其是在有 移动函数或重组块的代码中。许多工具通过“耐心”选项（例如，diff.algorithm）来暴露这一点。

直方图diff 通过频率直方图扩展了耐心，以更好地处理低出现率的元素，同时 保持快速（在 JGit中普及）。如果你曾发现--histogram为嘈杂的文件产生更清晰的hunks， 那是设计使然。在现代Git上，你可以全局或每次调用时选择算法：git config diff.algorithm myers|patience|histogram或 git diff --patience。

词级清晰度、空白控制和移动代码高亮

行diffs简洁但可能掩盖微小的编辑。 词级diffs (--word-diff)在不淹没审查的情况下为行内变更着色， 非常适合散文、长字符串或单行代码。

重新格式化后，空白可能会淹没diffs。Git和GNU diff都允许你 忽略空格变更 在不同程度上，并且 GNU diff的空白选项 (-b, -w, -B)在格式化程序运行时有帮助；你将看到逻辑编辑而不是对齐噪音。

当代码整体移动时，Git可以 高亮移动的块 使用--color-moved，在视觉上将“移动”与“修改”分开，这有助于 审查员审计移动是否隐藏了意外的编辑。通过 diff.colorMoved使其持久化。

服务于合并的Diffs：双向与三向和diff3

一个双向diff精确比较两个版本；它无法判断双方是否 编辑了相同的基础行，因此经常过度冲突。 三向合并（由现代VCS使用）计算从共同祖先到每一方的diffs，然后协调两个变更集。这极大地 减少了虚假冲突并提供了更好的上下文。这里的经典算法核心是 diff3，它将变更从“O”（基础）合并到“A”和“B”，并在必要时标记冲突。

学术和工业界的工作继续形式化和改进合并的正确性；例如， 经过验证的三向合并提出了无冲突的语义概念。在日常 Git中，现代的 ort合并策略 建立在diffing和重命名检测之上，以产生更少意外的合并。对于用户来说， 关键提示是：在冲突中显示基础行，使用 merge.conflictStyle=diff3，并经常集成以保持diffs小。

重命名检测及其阈值

传统的diffs无法“看到”重命名，因为内容寻址将文件视为blobs； 它们只看到一个删除和一个添加。 重命名检测启发式 通过比较添加/删除对之间的相似性来弥合这一差距。在Git中，通过-M/--find-renames[=<n>]（默认为~50% 相似性）启用或调整。对于更嘈杂的移动，降低它。你可以 限制候选比较 使用diff.renameLimit（以及合并期间的 merge.renameLimit ）。要跨重命名跟踪历史，请使用 git log --follow -- <path>。最近的Git还执行 目录重命名检测 以在合并期间传播文件夹移动。

二进制和增量diffs：rsync、VCDIFF/xdelta、bsdiff

改变的不仅仅是文本。对于二进制文件，你通常想要 增量编码——发出复制/添加指令以从 源重建目标。 rsync算法 开创了使用滚动校验和在网络上对齐块来高效进行远程差异比较的先河，从而最小化了带宽。

IETF标准化了一个通用的增量格式， VCDIFF (RFC 3284)，描述了ADD、COPY和RUN的字节码， 像 xdelta3 这样的实现用它来进行二进制补丁。对于可执行文件上的紧凑补丁， bsdiff 通常通过后缀数组和压缩产生非常小的增量；当补丁大小 占主导地位且生成可以离线进行时选择它。

超越源代码的文本diffs：模糊匹配和补丁

当你需要面对并发编辑或稍微错位的上下文时进行稳健的补丁——想想编辑器或协作系统——考虑 diff-match-patch。它将Myers风格的差异比较与 Bitap 模糊匹配结合起来，以找到近似匹配并“尽力而为”地应用补丁，外加预diff加速 和后diff清理，这些清理以牺牲一点点最小性为代价换取更美观的人类输出。关于如何在连续同步循环中结合diff和模糊补丁，请参阅Fraser的 差分同步。

结构化数据diffs：表格和树

CSV/TSV上的行diffs很脆弱，因为一个单元格的更改可能看起来像整行编辑。 表格感知的diff工具（daff） 将数据视为行/列，发出针对特定单元格的补丁，并渲染 使添加、删除和修改显而易见的可视化（参见 R小插图）。对于快速检查，专门的CSV差异比较器可以突出显示单元格间的更改和类型 转换；它们在算法上并不奇特，但它们通过 比较你实际关心的结构来增加审查信号。

实用的Git diff调优：审查员清单

• 选择正确的算法：从Myers（默认）开始，如果重新排序或嘈杂的块混淆了输出，请尝试 --patience ，或者对于重复文本上的快速、可读的diffs，请尝试 --histogram 。使用 git config diff.algorithm …设置默认值。
• 减少噪音：对于仅样式的编辑，使用空白标志（-b、 -w、 --ignore-blank-lines）以专注于实质性变更。在Git之外，请参阅 GNU diff的空白控制。
• 查看行内： --word-diff 有助于长行和散文。
• 审计移动的代码： --color-moved （或 diff.colorMoved）将“移动”与“修改”分开。
• 处理重命名：在审查重构时，添加 -M 或调整相似性阈值（-M90%、-M30%）以捕获 重命名；请记住默认值约为50%。对于深层树，设置 diff.renameLimit。
• 跨重命名跟踪历史： git log --follow -- <path>。

合并实际上如何消耗diffs（以及当它们不消耗时该怎么办）

合并计算两个diffs（BASE→OURS, BASE→THEIRS）并尝试将两者都应用于BASE。 像 ort 这样的策略在规模上协调这一点，包括重命名检测（包括目录规模的移动）和 最小化冲突的启发式方法。当冲突发生时， --conflict=diff3 用基础上下文丰富标记，这对于理解 意图是无价的。Pro Git关于 高级合并 的章节介绍了解决模式，Git的文档列出了像 -X ours和-X theirs这样的旋钮。为了在重复的冲突上节省时间，启用 rerere 来记录和重播你的解决方案。

超越文件：远程和增量场景

如果你正在通过网络同步大型资产，你更接近 rsync 世界而不是本地diff。Rsync计算滚动校验和以远程发现匹配的块， 然后只传输必要的内容。对于打包的增量， VCDIFF/xdelta 为你提供了一个标准的字节码和成熟的工具；当你同时控制编码器和 解码器时选择它。如果补丁大小至关重要（例如，无线固件）， bsdiff 在构建时用CPU/内存换取非常小的补丁。

关于“模糊”和“友好”的简短说明

像 diff-match-patch 这样的库接受，在现实世界中，你正在打补丁的文件可能已经发生了变化。通过将 一个坚实的diff（通常是Myers）与模糊匹配 (Bitap)和可配置的清理规则相结合，它们可以找到正确的位置来应用补丁并 使diff更具可读性——这对于协作编辑和同步至关重要。

你应该内化的“赌桌筹码”

1. 了解你的格式。统一diffs (-u/-U<n>)紧凑且对补丁友好；它们是代码审查和CI所期望的 (参考)。
2. 了解你的算法。Myers用于快速最小编辑 (论文); 耐心/直方图用于在重新排序或嘈杂块上的可读性 (耐心, 直方图); Hirschberg用于线性空间技巧 (论文); Hunt–Szymanski用于稀疏匹配加速 (论文)。
3. 了解你的开关。空白控制、词diff和颜色移动是 审查的倍增器 (git diff文档; GNU空白选项)。
4. 了解你的合并。三向与 diff3 风格不那么混乱； ort 加上重命名检测减少了流失； rerere 节省时间。
5. 为数据选择正确的工具。对于CSV/表格，使用 daff；对于二进制文件，使用 VCDIFF/xdelta 或 bsdiff。

附录：小型命令食谱

因为肌肉记忆很重要：

# 显示带有额外上下文的标准统一diff
  git diff -U5
  diff -u -U5 a b
  
  # 为长行或散文获取词级清晰度
  git diff --word-diff
  
  # 重新格式化后忽略空白噪音
  git diff -b -w --ignore-blank-lines
  diff -b -w -B a b
  
  # 在审查期间高亮移动的代码
  git diff --color-moved
  git config --global diff.colorMoved default
  
  # 用重命名检测驯服重构并跨重命名跟踪历史
  git diff -M
  git log --follow -- <file>
  
  # 为可读性优先选择算法
  git diff --patience
  git diff --histogram
  git config --global diff.algorithm patience
  
  # 在冲突标记中查看基础行
  git config --global merge.conflictStyle diff3

结束语

伟大的diffs与其说是为了证明最小性，不如说是为了在最小的认知成本下 最大化审查员的理解。这就是为什么 生态系统发展了多种算法（Myers、patience、histogram）、多种表示方法 （统一、词diff、颜色移动）和领域感知工具（用于表格的daff、用于二进制文件的xdelta/bsdiff） 。学习权衡，调整旋钮，你将花更多的时间来推理意图，而不是从红绿线中重新组装上下文。