Git Diff 算法原理

博途PLC工程智能体 | AI智能体博途网关 | 博途PLC程序知识图谱 | 梯形图转SCL | 自然语言生成梯形图 | 自然语言生成SCL | 逆向生成程序块文档 | 梯形图在线查看 | 博途编程文档MCP | AI模型价格对比 | AI工具导航 | ONNX模型库 | Vibe Coding教程 | PLC在线仿真器 | Tripo 3D | Meshy AI

每个开发者每天都通过 git 使用 diff。但很少有人理解驱动它的算法，更少有人知道为什么不同的 diff 工具对相同的输入产生不同的输出。

diff 问题的正式表述是：给定两个序列，找到最长公共子序列（LCS）。diff 就是不在 LCS 中的所有内容。这在一般情况下是一个 NP 困难问题，但实际算法可以有效地解决文本的 diff。

1、Myers diff 算法

Git 使用 Myers diff 算法（1986 年）的变体。核心思想是找到最短编辑脚本——将序列 A 转换为序列 B 所需的最小插入和删除次数。

Myers 将其建模为图搜索问题。想象一个网格，其中 X 轴表示序列 A 的元素，Y 轴表示序列 B 的元素。向右移动是删除（从 A 中移除）。向下移动是插入（从 B 添加）。对角线移动意味着元素匹配（无需编辑）。

最短编辑脚本是从 (0,0) 到 (N,M) 的路径，该路径最大化对角线移动（匹配）并最小化水平和垂直移动（编辑）。

    c  a  t
  +--------
d | \
o |   \
g |     \

该算法使用广度优先方法，先探索 0 次编辑的路径，然后 1 次编辑，然后 2 次，直到找到完整路径。这保证了最小性。

2、为什么 diff 不同

LCS 并不总是唯一的。两个文本可能有多个相同长度的有效 LCS，产生不同但同样有效的 diff。不同的工具对选择哪个 LCS 有不同的偏好。

考虑：

旧: A B C D
新: B C D A

一个有效的 diff：从位置 0 删除 A，在位置 4 插入 A（1 次删除 + 1 次插入）。 另一个有效的 diff：从位置 0 删除 A，在 A 之前插入 B C D（1 次删除 + 3 次插入）。

两者都是正确的。第一个更短。但有时更长的 diff 更可读，因为它保留了人类期望的视觉结构。

3、行级 vs. 字级 vs. 字符级

大多数 diff 工具在行级别操作。两行要么相同，要么不同。这对代码效果很好，但对散文效果很差。

如果你在一个长段落中更改一个单词，行级 diff 会将整个段落显示为已更改。字级 diff 只突出显示更改的单词。字符级 diff 突出显示特定字符。

实现字级 diff 意味着将行标记为单词，并在单词标记上运行 diff 算法，而不是在行字符串上运行。字符级 diff 是相同概念在更细粒度上的应用。权衡是精确度与噪声——代码上的字符级 diff 在视觉上可能令人不知所措。

最佳方法是分层：先行级 diff，然后在更改的行内进行字级 diff。这就是 GitHub 的 pull request 视图所做的。

4、超越 git 的实际 diff 用途

合同审查。 比较法律文档的两个版本以找到每个更改。字级 diff 在这里至关重要，因为行边界在流畅的散文中没有意义。

配置比较。 比较两个配置文件以找到差异。这在调试特定于环境的问题时很常见。

数据库迁移验证。 将预期模式与实际模式进行 diff 以捕获偏差。

API 响应比较。 在测试中比较预期与实际的 API 响应。理解结构的 JSON diff 工具（例如忽略键排序）比原始文本 diff 更有用。

5、空白和规范化

foo bar（两个空格）应该与 foo bar（一个空格）diff 吗？在代码中，空白通常很重要。在散文中，它通常不重要。Diff 工具需要可配置的空白处理：

• 严格：显示所有空白差异
• 忽略尾随：隐藏尾随空白更改
• 忽略所有空白：隐藏任何空白更改
• 规范化：在比较前将所有空白折叠为单个空格

Git 的 --ignore-space-change 和 --ignore-all-space 标志处理了这个问题，但基于 Web 的 diff 工具通常缺乏这些选项。

原文链接：How Diff Algorithms Actually Work (And Why Yours Might Be Wrong)

汇智网翻译整理，转载请标明出处