第二十一章 打包/拆包 压缩/解压

21.1 概述

一般而言，数据越小在存储时占用的空间更小、在传输时速度更快、在处理时耗时更少。 在大数据时代，海量数据的存储、传输、处理都将耗费巨额的成本。为了减少成本， 对数据采用恰当的编码算法进行压缩变得十分重要。AWS 压缩算法从 gzip 切换到 zstd，节约 30% 存储空间

为什么要压缩

• 存储成本：数据量越大，存储介质的采购和维护成本越高。压缩可以显著降低存储需求。
• 传输速度：网络带宽是有限资源，压缩后的数据传输更快，用户体验更好。
• 处理效率：更小的数据意味着更少的 I/O 操作和内存占用，处理速度更快。

压缩的本质：消除冗余

数据压缩的核心思想是消除冗余。现实世界中的数据往往存在大量重复模式和可预测的结构， 例如文本中高频出现的字符、图像中大面积相同颜色的区域、音频中的静音段等。 压缩算法通过识别这些冗余并用更紧凑的方式表示它们来实现数据缩减。

信息论基础

压缩的理论极限由**香农熵（Shannon Entropy）**给出。对于离散随机变量 $X$，其熵定义为：

$$H(X) = -\sum_{x \in X} p(x) \log_2 p(x)$$

其中 $p(x)$ 是符号 $x$ 出现的概率。香农熵的单位是比特（bit），表示编码每个符号所需的平均最小比特数。

关键结论：

• 任何无损压缩算法的平均编码长度不可能小于信源的香农熵。
• 当数据中各符号等概率分布时，熵最大，压缩效果最差。
• 当数据中存在大量重复符号时，熵较小，压缩空间大。

例如，对于只包含字符 A 和 B 的字符串：

• 若 A 出现概率为 0.9，B 为 0.1，则 $H(X) = -(0.9 \log_2 0.9 + 0.1 \log_2 0.1) \approx 0.469$ bit/符号
• 若 A 和 B 各出现概率 0.5，则 $H(X) = 1.0$ bit/符号

常用场景

• 文件、日志归档
• 网络传输
• 数据存储
• 敏感数据加密前先压缩

21.2 压缩算法分类

无损压缩 vs 有损压缩

本章重点讨论无损压缩，因为它是系统编程和数据处理中最常用的压缩方式。

通用压缩 vs 专用压缩

例如：

• 通用压缩：gzip、zstd、LZ4 可压缩任意二进制或文本数据
• 专用压缩：PNG（图像）、FLAC（音频）、VP9（视频）针对特定数据类型优化

压缩算法全景

21.3 经典压缩算法原理

21.3.1 哈夫曼编码（Huffman Coding）

哈夫曼编码是一种变长编码方案，由 David Huffman 于 1952 年提出。其核心思想是： 频率高的字符使用较短的编码，频率低的字符使用较长的编码，从而最小化整体编码长度。

构建哈夫曼树

1. 统计每个字符的出现频率
2. 将每个字符作为一个叶子节点，放入优先队列（按频率排序）
3. 每次取出频率最低的两个节点，合并为一个新的内部节点（频率为两者之和）
4. 将新节点放回优先队列
5. 重复步骤 3-4，直到只剩一个根节点
6. 从根节点到叶子节点的路径即为该字符的编码（左分支为 0，右分支为 1）

编码示例

假设文本为 BCAADDDCCACACAC，字符频率统计：

构建哈夫曼树后，可能的编码结果：

总比特数 = 6 + 10 + 9 + 3 = 28 bit，而固定长度编码需要 $15 \times 2 = 30$ bit（4个字符需要2 bit编码）。

Rust 实现哈夫曼编码

#![allow(unused)]
fn main() {
use std::collections::{BinaryHeap, HashMap};
use std::cmp::Ordering;

#[derive(Debug, Eq, PartialEq)]
struct HuffmanNode {
    freq: usize,
    char: Option<char>,
    left: Option<Box<HuffmanNode>>,
    right: Option<Box<HuffmanNode>>,
}

impl Ord for HuffmanNode {
    fn cmp(&self, other: &Self) -> Ordering {
        other.freq.cmp(&self.freq) // 最小堆
    }
}

impl PartialOrd for HuffmanNode {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl HuffmanNode {
    fn leaf(freq: usize, c: char) -> Self {
        HuffmanNode { freq, char: Some(c), left: None, right: None }
    }

    fn internal(freq: usize, left: Box<HuffmanNode>, right: Box<HuffmanNode>) -> Self {
        HuffmanNode { freq, char: None, left: Some(left), right: Some(right) }
    }
}

fn build_huffman_tree(freq_map: &HashMap<char, usize>) -> Option<HuffmanNode> {
    let mut heap: BinaryHeap<HuffmanNode> = freq_map
        .iter()
        .map(|(&c, &f)| HuffmanNode::leaf(f, c))
        .collect();

    while heap.len() > 1 {
        let left = heap.pop().unwrap();
        let right = heap.pop().unwrap();
        let parent = HuffmanNode::internal(left.freq + right.freq, Box::new(left), Box::new(right));
        heap.push(parent);
    }

    heap.pop()
}

fn generate_codes(node: &HuffmanNode, prefix: String, codes: &mut HashMap<char, String>) {
    match (&node.left, &node.right) {
        (None, None) => {
            if let Some(c) = node.char {
                codes.insert(c, prefix);
            }
        }
        _ => {
            if let Some(left) = &node.left {
                generate_codes(left, format!("{}0", prefix), codes);
            }
            if let Some(right) = &node.right {
                generate_codes(right, format!("{}1", prefix), codes);
            }
        }
    }
}

fn huffman_encode(text: &str) -> (String, HashMap<char, String>) {
    // 统计频率
    let mut freq_map = HashMap::new();
    for c in text.chars() {
        *freq_map.entry(c).or_insert(0) += 1;
    }

    // 构建哈夫曼树
    let root = build_huffman_tree(&freq_map).unwrap();

    // 生成编码表
    let mut codes = HashMap::new();
    generate_codes(&root, String::new(), &mut codes);

    // 编码文本
    let encoded: String = text.chars().map(|c| codes.get(&c).unwrap()).collect();
    (encoded, codes)
}

#[test]
fn test_huffman() {
    let text = "BCAADDDCCACACAC";
    let (encoded, codes) = huffman_encode(text);

    println!("编码表: {:?}", codes);
    println!("原始文本: {} ({} 字符)", text, text.len());
    println!("编码结果: {} ({} bit)", encoded, encoded.len());
    println!("固定编码: {} bit", text.len() * 2);
}
}

21.3.2 LZ77 / LZ78 算法

LZ77 和 LZ78 是由 Abraham Lempel 和 Jacob Ziv 于 1977 年和 1978 年提出的两种字典压缩算法， 是现代压缩技术的基石。

LZ77：滑动窗口算法

LZ77 使用一个**滑动窗口（Sliding Window）**在已处理的输出中查找与当前输入匹配的内容。 其核心思想是：用 (距离, 长度) 对来替代重复出现的字符串。

工作原理：

1. 维护一个固定大小的滑动窗口（通常 4KB ~ 64KB）
2. 从当前位置向前搜索窗口内是否有匹配的字符串
3. 如果找到匹配（长度 >= 最小匹配长度），输出 (距离, 长度) 对
4. 如果未找到匹配，输出原始字符

编码格式：(offset, length, next_char)

• offset：匹配位置相对于当前位置的偏移量
• length：匹配的长度
• next_char：匹配后的下一个字符

示例：

文本 AABAABAAAAB 的 LZ77 编码过程（窗口大小为 6）：

LZ78：显式字典算法

LZ78 与 LZ77 不同，它维护一个显式字典，将新发现的短语逐步加入字典中。 每次编码时，在字典中查找最长匹配，然后输出字典索引和下一个字符。

21.3.3 DEFLATE 算法

DEFLATE 是 LZ77 与 Huffman 编码的结合体，由 Phil Katz 于 1993 年设计， 广泛应用于 gzip、zip、PNG 等格式中。

DEFLATE 的工作流程：

1. LZ77 阶段：使用滑动窗口消除重复字符串，生成字面量和 (距离, 长度) 对的序列
2. Huffman 编码阶段：对 LZ77 的输出进行 Huffman 编码，进一步压缩

原始数据 → LZ77编码（消除重复）→ Huffman编码（消除统计冗余）→ 压缩数据

gzip 就是基于 DEFLATE 算法，额外添加了文件头、CRC32 校验等元数据。

常见压缩算法学习

21.4 现代压缩算法

21.4.1 Snappy

Snappy 是 Google 开发的压缩库， formerly known as Zippy。其设计目标是速度优先， 在牺牲一定压缩率的前提下追求极致的压缩和解压速度。

特点：

• 压缩速度约 250 MB/s，解压速度约 500 MB/s
• 压缩率适中（通常 1.5x ~ 2x）
• 不追求最大压缩率，适合实时场景
• 广泛应用于 LevelDB、Cassandra、Hadoop 等系统

21.4.2 LZ4

LZ4 由 Yann Collet 开发，以极快的压缩和解压速度著称。

特点：

• 解压速度可达数 GB/s（接近内存带宽极限）
• 压缩速度约 400 MB/s
• 压缩率适中
• 提供 LZ4 block format 和 LZ4 frame format 两种模式
• 适用于实时压缩、缓存、内存数据库等场景

21.4.3 Zstandard（zstd）

Zstandard（简称 zstd）由 Facebook（现 Meta）的 Yann Collet 开发， 目标是提供速度与压缩率的最佳平衡。zstd 于 2016 年开源，已被 RFC 8878 标准化。

特点：

• 提供 1-22 级压缩级别，灵活调节速度与压缩率
• 默认级别 3 的速度与 gzip 相当，但压缩率更高
• 级别 19+ 可提供接近 LZMA 的压缩率
• 支持流式压缩和字典压缩
• 小数据压缩表现优异

压缩级别说明：

速度快，性能好！压缩神器 zstd

Rust 中使用 zstd

use std::fs::File;
#[cfg(target_os = "windows")]
use std::os::windows::prelude::MetadataExt;
#[cfg(target_os = "linux")]
use std::os::linux::fs::MetadataExt;
use zstd::stream;

fn main() -> std::io::Result<()> {
    // 压缩文件
    let source = File::open("C:\\data\\movies.json")?;
    let destination = File::create("C:\\data\\movies.zst")?;
    match stream::copy_encode(&source, &destination, 7) {
        Ok(_) => {
            let metadata1 = source.metadata()?;
            let metadata2 = destination.metadata()?;
            println!(
                "compress success: {} => {}",
                metadata1.file_size(),
                metadata2.file_size()
            )
        }
        Err(e) => println!("{}", e),
    }

    // 解压文件
    let destination = File::open("why-rust.zst")?;
    let bytes = stream::decode_all(destination).unwrap();
    println!("{}", String::from_utf8_lossy(&bytes));
    Ok(())
}

Cargo.toml 依赖：

[dependencies]
zstd = "0.13"

zstd github

21.4.4 Brotli

Brotli 是 Google 开发的压缩算法，专为 HTTP 内容压缩优化， 已被 RFC 7932 标准化。 现代浏览器（Chrome、Firefox、Edge 等）均支持 Brotli 压缩。

特点：

• 使用 LZ77 + Huffman + 上下文建模的组合
• 压缩率通常比 gzip 高 15-25%
• 支持预定义字典（针对 HTML、CSS、JavaScript 等优化）
• 解压速度与 gzip 相当，压缩速度较慢
• 适用于 Web 服务器静态资源压缩

Brotli程序库 Brotli rust-brotli

21.4.5 各算法性能对比

注意：以上数据为相对比较，实际性能受硬件、数据类型和压缩级别影响。 压缩率通常以文本数据为基准，二进制数据（如已压缩的媒体文件）压缩效果较差。

21.5 打包与归档

tar 格式

tar（Tape Archive）是一种打包（归档）格式，其作用是将多个文件和目录合并为一个文件。 需要注意的是：tar 本身不进行压缩，仅负责将多个文件合并为一个归档文件。

tar 文件通常与压缩算法配合使用，常见的组合：

文件打包（tar + zstd 压缩）

为了方便管理，先使用 tar 将多个文件打包成一个 tar 文件，然后使用 gzip、lz4、zstd 等压缩算法压缩 tar 文件。 而当我们需要使用文件时，则先解压后拆包得到原先的文件。

#![allow(unused)]
fn main() {
use std::fs::File;
use tar::Builder;
use zstd::stream;

#[test]
fn archive_encode() {
    // 打包
    let file = File::create("examples/file/foo.tar").unwrap();
    let mut a = Builder::new(file);
    a.append_path("why-rust.txt").unwrap();
    a.append_path("sensitive-words.txt").unwrap();
    a.append_path("large_file.txt").unwrap();

    // 压缩
    let source = File::open("examples/file/foo.tar").unwrap();
    let destination = File::create("examples/file/foo.tar.zst").unwrap();
    match stream::copy_encode(&source, &destination, 7) {
        Ok(_) => {
            let metadata1 = source.metadata().unwrap();
            if let Ok(metadata2) = destination.metadata() {
                let size = metadata2.file_size();
                println!("compress success: {} => {}", metadata1.file_size(), size);
            }

            if let Ok(metadata) = fs::metadata("examples/file/foo.tar.zst") {
                println!(
                    "{:?},{},{:?}",
                    metadata.file_type(),
                    metadata.len(),
                    metadata.created().unwrap()
                );
            }
        }
        Err(e) => println!("copy_encode : {}", e),
    }
}
}

文件拆包（解压 + tar 拆包）

#![allow(unused)]
fn main() {
use std::fs::File;
use std::io::Read;
use tar::Archive;
use zstd::stream;

#[test]
fn decode_unpackage() {
    // 解压 zst 文件
    if let Ok(source) = File::open("examples/file/github_users_sample_set.tar.zst") {
        if let Ok(destination) = File::create("examples/file/github_users_sample_set.tar") {
            stream::copy_decode(source, destination);
        }
    }

    // 拆包 tar 文件
    let file = File::open("examples/file/github_users_sample_set.tar").unwrap();
    let mut a = Archive::new(file);

    for file in a.entries().unwrap() {
        // Make sure there wasn't an I/O error
        let mut file = file.unwrap();

        // Inspect metadata about the file
        println!("{:?}", file.header().path().unwrap());
        println!("{}", file.header().size().unwrap());

        // files implement the Read trait
        let mut s = String::new();
        file.read_to_string(&mut s).unwrap();
        println!("{}", s);
    }
}
}

Linux 相关命令

# 打包压缩
tar -zcvf destination.tar.gz source          # gzip 压缩
tar -jcvf destination.tar.bz2 source          # bzip2 压缩
tar -Jcvf destination.tar.xz source           # xz 压缩
tar --zstd -cvf destination.tar.zst source     # zstd 压缩

# 解压拆包
tar -zxvf destination.tar.gz                  # gzip 解压
tar -jxvf destination.tar.bz2                 # bzip2 解压
tar -Jxvf destination.tar.xz                  # xz 解压
tar --zstd -xvf destination.tar.zst           # zstd 解压

编码知识补充：base64 编码将 3 字节映射为 4 字符（膨胀 33%），hex 编码将 1 字节映射为 2 字符（膨胀 100%）。 这两种编码的目的不是压缩，而是将二进制数据转换为文本安全格式。

21.6 压缩与加密的顺序

压缩一定在加密之前。 因为加密以后，比特序列的冗余性消失，基本上无法再压缩了。 在加密前进行压缩的做法不仅仅限于混合密码系统，而是对所有密码都适用。

为什么加密后无法压缩

加密算法（如 AES）的设计目标是将数据随机化，使得密文在统计上与随机数据不可区分。 这意味着：

1. 加密后的数据熵接近最大值（每个比特等概率为 0 或 1）
2. 没有任何重复模式可以利用
3. 压缩算法无法找到可消除的冗余

从信息论角度看，加密后数据的熵为 $H(X) = n$（$n$ 为比特数），即每个比特携带 1 bit 信息， 已经达到理论极限，无法进一步压缩。

正确的处理顺序

原始数据 → 压缩 → 加密 → 传输/存储

接收数据 → 解密 → 解压 → 原始数据

Shell 命令示例

# 正确顺序：先压缩，再加密
tar -zcvf destination.tar.gz source
gpg -c destination.tar.gz

# 解密后解压
gpg -d destination.tar.gz.gpg | tar -zxvf -

21.7 Rust 中的压缩库

Rust 生态中拥有丰富的压缩/解压库，以下列出常用的库及其用途：

核心压缩库

相关资源链接

• snappy - Snappy is a compression/decompression library.
• rust-snappy
• zstd github - Zstandard - Fast real-time compression algorithm
• RFC 8878 - Zstandard 压缩算法规范
• Brotli - Google Brotli 压缩库
• rust-brotli - Brotli 的 Rust 实现
• RFC 7932 - Brotli 压缩算法规范
• LZ4 - LZ4 极速压缩库
• orz - 基于 LZ77 的列式压缩库

Cargo.toml 依赖示例

[dependencies]
# gzip / deflate / zlib 压缩
flate2 = "1"

# ZIP 压缩包读写
zip = "2"

# tar 归档
tar = "0.4"

# zstd 压缩
zstd = "0.13"

# LZ4 压缩
lz4_flex = "0.11"

# Brotli 压缩
brotli = "7"

# Snappy 压缩
snap = "1"

flate2 使用示例（gzip 压缩）

#![allow(unused)]
fn main() {
use flate2::write::GzEncoder;
use flate2::read::GzDecoder;
use flate2::Compression;
use std::fs::File;
use std::io::{Write, Read};

fn compress_gzip(input_path: &str, output_path: &str) -> std::io::Result<()> {
    let input = File::open(input_path)?;
    let output = File::create(output_path)?;
    let mut encoder = GzEncoder::new(output, Compression::default());
    std::io::copy(&mut input.take(0), &mut encoder)?;
    encoder.finish()?;
    Ok(())
}

fn decompress_gzip(input_path: &str, output_path: &str) -> std::io::Result<()> {
    let input = File::open(input_path)?;
    let mut decoder = GzDecoder::new(input);
    let mut output = Vec::new();
    decoder.read_to_end(&mut output)?;
    std::fs::write(output_path, output)?;
    Ok(())
}
}

21.8 总结

压缩算法对比总览

场景选择建议

关键要点

1. 压缩的本质是消除冗余，理论上限由香农熵决定
2. 没有万能的压缩算法，需要根据场景在速度、压缩率、内存占用之间权衡
3. 先压缩，后加密，加密后的数据无法再压缩
4. tar 只打包不压缩，需要配合压缩算法使用
5. zstd 是当前最推荐的通用压缩算法，在速度和压缩率之间取得了优秀的平衡

21.9 练习题

练习 1：计算字符串 "aabbbccccddddd" 的香农熵 $H(X)$，并解释为什么该字符串具有较好的可压缩性。

练习 2：使用 Rust 的 flate2 库实现对一个文本文件的 gzip 压缩和解压，并比较压缩前后的文件大小。

练习 3：手动构建字符串 "ABRACADABRA" 的哈夫曼树，写出每个字符的编码，并计算编码后的总比特数。

练习 4：对字符串 "ABCABCABCABC" 进行 LZ77 编码（假设窗口大小为 9），写出每一步的编码结果。

练习 5：使用 Rust 的 tar 和 zstd 库，编写一个函数将指定目录下的所有 .log 文件打包并压缩为 .tar.zst 格式。

练习 6：为什么加密后的数据几乎无法再压缩？请从信息论的角度给出解释。

练习 7：分别使用 zstd 的压缩级别 1、3、10、19 压缩同一个大文件（>100MB），记录每种级别的压缩时间和压缩后文件大小，绘制速度-压缩率曲线并分析。

练习 8：在一个 Web 服务项目中，分别使用 gzip 和 Brotli 压缩 JSON API 响应数据，比较压缩率和响应时间，给出你的选型建议。