第二章 差分算法基础：二进制差异的本质
做差分升级，说白了就是要回答一个问题：两个二进制文件之间，到底差在哪？
我刚开始接触这个领域时，以为差分就是简单的「逐字节比较」。后来才发现，事情远没那么简单。你想想看，一个固件镜像动辄几兆甚至几十兆，如果只是逐字节对比，那跟全量升级有什么区别？
这一章，我们就来拆解二进制差异的本质，以及支撑差分算法的两个核心理论：编辑距离和最长公共子序列。
2.1 二进制差异的本质
两个二进制文件，在计算机眼里就是两串字节序列。差异的本质，就是从一个序列变成另一个序列，需要做哪些操作。
举个例子：
旧文件: 0x01 0x02 0x03 0x04 0x05
新文件: 0x01 0x02 0xFF 0x04 0x05肉眼一看，第三个字节从 0x03 变成了 0xFF。但实际工程中，差异远不止这么简单：
- 插入：新文件多了几个字节
- 删除：旧文件少了几个字节
- 替换：字节内容变了
- 移动：一大段数据换了位置
核心观点：差分算法的目标，就是用最少的操作来描述新旧文件之间的差异。这个「最少操作次数」，就是后面要讲的编辑距离。
我在项目中遇到过一种情况：两个固件版本，功能上只改了一行代码，但编译出来的二进制差异却很大。为什么？因为编译器优化、地址对齐、链接顺序都会导致大量「无关差异」。所以，二进制差异 ≠ 源码差异，这一点必须刻在脑子里。
2.2 编辑距离算法
编辑距离（Edit Distance），也叫 Levenshtein 距离。它衡量的是：把一个字符串变成另一个字符串，最少需要多少次编辑操作。
操作只有三种：
- 插入一个字符
- 删除一个字符
- 替换一个字符
嗯，这里要注意：移动操作在基本编辑距离里不算，它会被拆成删除+插入。
2.2.1 算法原理
编辑距离用动态规划求解。我们定义一个二维数组 dp[i][j]，表示旧序列前 i 个字符变成新序列前 j 个字符的最小编辑距离。
递推公式：
if old[i] == new[j]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(
dp[i-1][j] + 1, # 删除
dp[i][j-1] + 1, # 插入
dp[i-1][j-1] + 1 # 替换
)边界条件：
dp[0][j] = j（从空串插入 j 次）dp[i][0] = i（从 i 个字符删除 i 次）
2.2.2 一个具体例子
假设旧序列是 "ABC"，新序列是 "ABD"。
| A | B | D | ||
|---|---|---|---|---|
| 0 | 1 | 2 | 3 | |
| A | 1 | 0 | 1 | 2 |
| B | 2 | 1 | 0 | 1 |
| C | 3 | 2 | 1 | 1 |
最终 dp[3][3] = 1，只需要一次替换（C→D）。
个人习惯：我在做嵌入式差分时，很少直接用编辑距离算整个固件。因为固件太大了，O(n*m) 的空间复杂度扛不住。但编辑距离的思想是所有差分算法的基础，必须吃透。
2.3 最长公共子序列
最长公共子序列（LCS），跟编辑距离是「表兄弟」。它找的是：两个序列中，按顺序出现的最长公共部分。
注意，子序列不要求连续。比如 "ABC" 和 "ACB" 的 LCS 是 "AB" 或 "AC"，长度是 2。
2.3.1 LCS 与编辑距离的关系
这两者其实可以互相推导：
编辑距离 = m + n - 2 * LCS长度其中 m 和 n 分别是新旧序列的长度。为什么？因为 LCS 是「不用动」的部分，剩下的都要删掉或插入。
我举个例子你就明白了：
- 旧序列 "ABCD"，新序列 "ACED"
- LCS 是 "ACD"，长度 3
- 编辑距离 = 4 + 4 - 2*3 = 2
确实，只需要把 B 删掉，把 E 插进去，两步搞定。
2.3.2 LCS 的 DP 解法
LCS 的递推公式更简单：
if old[i] == new[j]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])边界全是 0。
我曾经踩过的坑：在资源受限的 MCU 上做差分时，直接用二维数组存 DP 表，结果内存爆了。后来改用滚动数组优化，空间从 O(m*n) 降到 O(min(m,n))。这个优化技巧，后面章节会详细讲。
2.4 从理论到工程：差异的表示
理论讲完了，我们看看工程上怎么表示差异。常见的差分格式有两种：
| 格式 | 描述 | 典型算法 | 适用场景 |
|---|---|---|---|
| 编辑脚本 | 记录每一步操作（插入/删除/替换） | 编辑距离回溯 | 小文件、文本差分 |
| 块匹配 | 记录「从哪里复制多少字节到新位置」 | bsdiff、xdelta | 大文件、二进制差分 |
我个人更倾向于块匹配方式。原因很简单：固件升级包要尽量小，而块匹配能利用「重复数据」大幅压缩差异。
2.5 本章知识结构图
下面这张图，把本章的核心概念串起来了：
2.6 小结
这一章我们聊了三件事：
- 二进制差异的本质：就是序列之间的变换操作
- 编辑距离：衡量差异大小的数学工具
- 最长公共子序列：找出「不用动」的部分，反过来就是差异
这些理论看起来有点抽象，但它们是所有差分算法的基石。后面讲 bsdiff、xdelta、HDiffPatch 时，你会发现它们都在用这些思想，只是换了个更高效的工程实现方式。
给你一个思考题：如果旧文件和新文件完全一样，编辑距离是多少？LCS 长度又是多少？想明白了，这两个概念你就真懂了。