我对2-Byte Deltas着迷，打造了一个真正能利用它们的Delta Compressor
Source: Dev.to
TL;DR
需要为加密文档格式生成极小的增量。xdelta3 对于简单编辑就要占用 40 多个字节。于是我构建了 xpatch，它包含 7 种专用算法以及一个引用旧版本的标签系统。结果：在真实代码仓库（对 120 万条真实世界的变更进行测试）中，增量的中位数只有 2 字节。它既快又真的能用。
中位数增量是 2 字节。不是打错——这正好是一个 uint16：头部加上几乎什么也没有，因为被比较的文件是完全相同的，算法只会说 “嘿，去看第 5 版吧，它们是一样的”。
让我抓狂的问题
我在构建一种文档格式，需求清单包括：端到端加密、实时协作、完整的版本历史、离线优先同步，并且不依赖专门的服务器集群。
关键点在于：加密后就不能再压缩。一旦增量被加密，就没有压缩的余地，所以每个增量必须非常小，否则存储成本会把产品压垮。
- Myers diff – 经典且经过充分验证，但对每 500 ms 捕获的微小编辑来说太冗长。记录 “用户添加了 5 个字符”就要占用数十字节。
- xdelta3 – 对大幅更改更友好，但仅仅编码 “hello” → “hello world” 就要消耗 40 多个字节（相当于 6 字节改动的 8 倍开销）。
- gdelta – 2021 年的有前景的研究论文，针对小文件提供快速压缩，但唯一的实现是三年前的研究代码，只有 Python 绑定，几乎编不成功。
我把 gdelta 用 Rust 重写了一遍（见仓库）。它快且高效，但对简单编辑仍会产生约 20 字节的增量。我一直在自问：为什么要用 20 字节来记录一次 “hello” 的敲入？
改变一切的领悟
大多数文档编辑遵循可预测的模式：
- 添加文本 – “hello” → “hello world”
- 删除文本 – “hello world” → “hello”
- 回滚更改 – “hello” → “hello world” → “hello”
- 重复模式 – “test test test”、缩进、装饰器
- 复杂结构性更改 – 其余所有情况
通用算法（如 xdelta3 或 gdelta）试图用单一方法处理所有情况，并为最坏情况（任意二进制更改）进行优化。
如果我们不需要为所有情况准备同一个算法会怎样？如果我们为每种模式尝试几种专用算法，并挑选最小的结果会怎样？这个想法催生了 xpatch。
构建过程：先做最简单的部分
Algorithm 1: Just Store The Damn Characters
最常见的情况是添加文本，所以我们直接存储字符。
fn encode_add(position: usize, data: &[u8]) -> Vec<u8> {
let mut encoded = encode_varint(position);
encoded.extend_from_slice(data);
encoded
}Position（可变长整数）+ 原始字符。把 “world” 插入到位置 6 大约只需要 6 字节，已经优于 gdelta 的 20 + 字节。
Algorithm 2: Deletion Is Even Simpler
fn encode_remove(start: usize, end: usize) -> Vec<u8> {
let mut encoded = encode_varint(start);
encoded.extend(encode_varint(end - start));
encoded
}两个数字：删除起始位置以及要删除的字节数。典型开销约为 3 字节。
Algorithm 3: Wait, What If We Tokenize This?
文本不是随机的，它由单词组成。通过对常见单词进行标记化，我们可以用小的 ID 替代它们。
- 标记表：2¹⁴ = 16 384 个标记（适合 varint；大多数 ID 能放在一个字节内）。
- 标记按出现频率排序，常用词获得最小的 ID。
- 在大语料库（例如 Wikipedia）上训练，以构建词汇表。
标记器使用带数组索引子节点的 trie，实现 O(1) 的每字节查找：
struct TrieNode {
token_id: Option<u16>,
children: [Option<Box<TrieNode>>; 256],
}
impl TrieNode {
fn find_longest_match(&self, text: &[u8], start: usize) -> Option<(usize, u16)> {
let mut node = &self;
let mut last_match = None;
let mut pos = start;
while pos < text.len() {
let byte = text[pos];
match &node.children[byte as usize] {
Some(child) => {
node = child;
if let Some(id) = node.token_id {
last_match = Some((pos + 1, id));
}
pos += 1;
}
None => break,
}
}
last_match
}
}Choosing the Best Algorithm
enum Algorithm {
Chars,
Tokens,
GDelta,
}
fn encode_delta(base: &[u8], new: &[u8]) -> (Algorithm, Vec<u8>) {
// Start with simple character encoding
let mut best_algo = Algorithm::Chars;
let mut best_data = encode_add(0, new); // placeholder for actual diff
// Try tokenization – might be smaller
if let Ok(token_data) = encode_tokens(0, new) {
if token_data.len() < best_data.len() {
best_algo = Algorithm::Tokens;
best_data = token_data;
}
}
// Fallback to gdelta for anything not covered above
let gdelta_data = gdelta_encode(base, new);
if gdelta_data.len() < best_data.len() {
best_algo = Algorithm::GDelta;
best_data = gdelta_data;
}
(best_algo, best_data)
}编码器始终返回给定更改的最小可能增量，利用专用算法在它们占优势时进行压缩，并在必要时优雅地回退到功能强大的通用压缩器。