Myers 在论文中，提到了这样一句话： > An edit script for A and B is a set of insertion and deletion commands that transform A into B. 其中有一个概念叫作 edit script，也就是编辑脚本。比如，对于源文本 A 和目标文本 B，我们一定可以通过不断执行删除行和插入行两种操作，使得 A 转化成 B，这样的一系列插入和删除操作的序列就被称作编辑脚本。所以，文本差分算法，可以定义为用于求出输入源文本和目标文本之间的编辑脚本的算法，广泛运用于各种需要进行文本对比的地方。 下面给你一个**快速版**的内容导读，让你能在最短时间内理解整篇文章的核心思想和做法。 --- ## 1. 为什么要了解文本差分算法？ - **Git Diff**：我们每天都会用 `git diff` 来查看修改差异，但很少有人深入思考这个功能底层是怎么做的。 - **算法意义**：文本差分是一个经典且实用的算法问题，能帮助我们更好地理解"最短编辑路径"、"最长公共子序列（LCS）"等概念。 ## 2. 什么是文本差分？ - **编辑脚本（Edit Script）**：把"把 A 转化成 B 所需的插入与删除操作序列"叫做编辑脚本。 - **最短编辑脚本（SES）**：在所有可行的操作序列中，操作（插入+删除）总数最少的那个。 - **和 LCS 的关系**：最短编辑脚本的长度 = m+n−2×LCS长度m + n - 2 \times \text{LCS长度}。两个问题（SES 与 LCS）是对偶的。 ## 3. 如何评价"差分效果"？ 1. **编辑脚本长度**：操作越少越好，这就是我们寻找 SES 的原因。 2. **可读性**：哪怕编辑脚本同样短，但呈现方式也有好坏之分。一般更可读的差分会尽量避免删除和插入的"交叉"出现，保留更多的连续原文本，这样更好理解。 ## 4. Myers 差分算法的核心思路 Myers 算法是 `git diff` 默认使用的文本差分算法，特点是**计算最短编辑脚本 + 追求更好的可读性**。它把文本差分问题巧妙地转化为一个**图搜索 + 动态规划**的问题： ### 4.1 建立"编辑图"(Edit Graph) 1. **坐标含义**：在一个二维网格里，横轴（X 方向）代表源文本 S 的字符序号，纵轴（Y 方向）代表目标文本 T 的字符序号。 2. **移动方式**： - 向右走（从 (x, y) 到 (x+1, y)）代表删除 S 的一个字符； - 向下走（从 (x, y) 到 (x, y+1)）代表插入 T 的一个字符； - 斜线（从 (x, y) 到 (x+1, y+1)）则表示两个字符相同，无需操作，0 成本。 ### 4.2 动态规划（DP）求最短路径 - 在这个网格里，从 (0,0) 走到 (m,n) 的最短路径就对应最短编辑脚本（SES）。 - Myers 引入了几个概念帮助理解： 1. **D-Path**：需要 D 步插入/删除的路径。 2. **Snake**：一次插入或删除之后紧跟着若干条斜线，表示"一个操作 + 一段不需编辑的公共序列"。 3. **k-Line**：网格中所有满足 x - y = k 的点所构成的斜线。 ### 4.3 贪心策略提高可读性 - **先做删除再做插入**，尽量连贯删除或插入，减少插入和删除的"交叉"，形成更直观的差分结果。 - 算法实质上会倾向于"让 x 尽量变大"，也就是优先在源文本上做删除，而后再插入目标文本。 ### 4.4 时间复杂度 - Myers 通过分析可知，整体复杂度为 O(D×(M+N))O(D \times (M+N))，其中 DD 是最短编辑脚本的长度，MM 和 NN 分别是源、目标文本的长度。 --- ## 5. 小结 - **实用性**：Myers 算法广泛用于各种文本差分场景，比如 Git、Android 的 DiffUtil 等。 - **算法与生活**：很多日常工具背后都有成熟、优雅的算法支撑，值得我们思考和学习。 --- ## 6. 作业与思考 - 试着用动态规划做一个最短公共子序列（LCS）的算法，看看能否衍生成一个简易的文本差分算法。 - 若想更深入，可阅读 Myers 原论文，或在自己的项目里尝试实现这个算法，观察和 Git 自带的 Diff 结果有何差异。 --- 这就是这篇文章的**核心要点**。如果你只需要在短时间内掌握重点，可以记住以下关键字： *_"最短编辑脚本"、"编辑图 + 动态规划"、"可读性贪心策略"、"O(D_(M+N)) 复杂度"**。 希望能帮你**快速Get到**这篇文章的精髓！