> ## Content Index
> Fetch the complete content index at: https://www.hubwiz.com/blog/llms.txt
> Use this file to discover other available public pages before exploring further.

# Git Diff 算法原理
- URL: https://www.hubwiz.com/blog/how-git-diff-algorithms-work/
- Published: 2026-09-12T04:00:23.000Z
- Updated: 2026-09-12T04:00:23.000Z
- Description: diff 问题的正式表述是：给定两个序列，找到最长公共子序列（LCS）。diff 就是不在 LCS 中的所有内容。这在一般情况下是一个 NP 困难问题，但实际算法可以有效地解决文本的 diff。
- Author: admin
- Tags: ALGORITHM, #Import 2026-10-14 14:41

每个开发者每天都通过 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)](https://dev.to/alphashark/how-diff-algorithms-actually-work-and-why-yours-might-be-wrong-3c74?ref=hubwiz.com)

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