第十三 压缩

数据压缩是计算机科学中一项核心技术，它通过消除数据中的冗余信息来减少存储空间或传输带宽。从节省手机存储空间的照片压缩，到加速网页传输的 Gzip，再到流式媒体的音视频编码，压缩技术无处不在。本章将介绍压缩的基本原理、经典算法以及在 Rust 中的实践。

一、数据压缩原理

1.1 信息冗余与压缩

数据压缩的本质是消除冗余。冗余是指数据中存在的不必要或可预测的信息。根据信息论，如果某些信息可以通过其他信息推导出来，那么它就是冗余的。

常见的冗余类型：

压缩率的计算：

压缩率 = 压缩后大小 / 压缩前大小 × 100%
压缩比 = 压缩前大小 / 压缩后大小

例如，一个 100KB 的文件压缩后为 25KB，则压缩率为 25%，压缩比为 4:1。

1.2 熵与信息论

香农（Claude Shannon）在 1948 年提出的信息论为数据压缩奠定了理论基础。

信息熵（Entropy） 表示随机变量的不确定性，也代表了数据的最小平均编码长度：

$$H(X) = -\sum_{i=1}^{n} p(x_i) \log_2 p(x_i)$$

其中 $p(x_i)$ 是符号 $x_i$ 出现的概率。熵越大，数据的不确定性越高，可压缩的空间越小；熵越小，数据的规律性越强，可压缩的空间越大。

fn shannon_entropy(data: &[u8]) -> f64 {
    let mut freq = [0usize; 256];
    for &byte in data {
        freq[byte as usize] += 1;
    }

    let len = data.len() as f64;
    let mut entropy = 0.0;

    for &count in &freq {
        if count > 0 {
            let p = count as f64 / len;
            entropy -= p * p.log2();
        }
    }

    entropy
}

fn main() {
    // 高度规律的数据，熵低，可压缩性高
    let repetitive = b"AAAAAAAAAABBBBBBBBBB";
    println!("重复数据熵: {:.4} bits/byte", shannon_entropy(repetitive));

    // 随机数据，熵高，接近 8 bits/byte，难以压缩
    let random = [0x3F, 0xA7, 0x12, 0xE9, 0x55, 0x8C, 0x21, 0x7B];
    println!("随机数据熵: {:.4} bits/byte", shannon_entropy(&random));

    // 英文文本，熵约 4-5 bits/byte
    let text = b"Hello, World! This is a test of entropy calculation.";
    println!("英文文本熵: {:.4} bits/byte", shannon_entropy(text));
}

1.3 压缩算法的分类

二、无损压缩

无损压缩保证压缩后的数据可以完全还原为原始数据，适用于文本、程序代码、可执行文件等对数据完整性要求高的场景。

2.1 Huffman 编码

Huffman 编码是一种经典的熵编码方法，由 David Huffman 于 1952 年提出。其核心思想是：出现频率高的符号使用较短的编码，出现频率低的符号使用较长的编码。

Huffman 编码的构建过程：

1. 统计每个符号的出现频率
2. 将每个符号作为一个叶子节点，构建一个森林
3. 每次取出频率最小的两个节点，合并为一个新节点（频率为两者之和）
4. 重复步骤 3，直到只剩一棵树
5. 从根节点出发，左分支标记 0，右分支标记 1，到达叶子节点的路径即为该符号的编码

use std::collections::{BTreeMap, BinaryHeap};

#[derive(Debug, Clone)]
struct HuffmanNode {
    freq: usize,
    symbol: Option<u8>,
    left: Option<Box<HuffmanNode>>,
    right: Option<Box<HuffmanNode>>,
}

impl HuffmanNode {
    fn new_leaf(symbol: u8, freq: usize) -> Self {
        HuffmanNode {
            freq,
            symbol: Some(symbol),
            left: None,
            right: None,
        }
    }

    fn new_internal(left: HuffmanNode, right: HuffmanNode) -> Self {
        HuffmanNode {
            freq: left.freq + right.freq,
            symbol: None,
            left: Some(Box::new(left)),
            right: Some(Box::new(right)),
        }
    }
}

impl PartialEq for HuffmanNode {
    fn eq(&self, other: &Self) -> bool {
        self.freq == other.freq
    }
}

impl Eq for HuffmanNode {}

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

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

fn build_codes(node: &HuffmanNode, prefix: String, codes: &mut BTreeMap<u8, String>) {
    if let Some(symbol) = node.symbol {
        codes.insert(symbol, if prefix.is_empty() { "0".to_string() } else { prefix });
    } else {
        if let Some(ref left) = node.left {
            build_codes(left, format!("{}0", prefix), codes);
        }
        if let Some(ref right) = node.right {
            build_codes(right, format!("{}1", prefix), codes);
        }
    }
}

fn huffman_encode(data: &[u8]) -> (BTreeMap<u8, String>, String) {
    // 统计频率
    let mut freq = [0usize; 256];
    for &byte in data {
        freq[byte as usize] += 1;
    }

    // 构建最小堆
    let mut heap = BinaryHeap::new();
    for (symbol, count) in freq.iter().enumerate() {
        if *count > 0 {
            heap.push(HuffmanNode::new_leaf(symbol as u8, *count));
        }
    }

    // 构建 Huffman 树
    while heap.len() > 1 {
        let left = heap.pop().unwrap();
        let right = heap.pop().unwrap();
        heap.push(HuffmanNode::new_internal(left, right));
    }

    // 生成编码表
    let mut codes = BTreeMap::new();
    if let Some(root) = heap.pop() {
        build_codes(&root, String::new(), &mut codes);
    }

    // 编码数据
    let mut encoded = String::new();
    for &byte in data {
        encoded.push_str(codes.get(&byte).unwrap());
    }

    (codes, encoded)
}

fn main() {
    let text = b"this is an example of a huffman tree";
    let (codes, encoded) = huffman_encode(text);

    println!("原文: {}", String::from_utf8_lossy(text));
    println!("原文长度: {} bytes", text.len());
    println!("\nHuffman 编码表:");
    for (symbol, code) in &codes {
        println!("  '{}' => {}", *symbol as char, code);
    }

    println!("\n编码后: {}", encoded);
    println!("编码后长度: {} bits = {:.2} bytes", encoded.len(), encoded.len() as f64 / 8.0);
    println!("压缩率: {:.2}%", (encoded.len() as f64 / 8.0) / text.len() as f64 * 100.0);
}

Huffman 编码的特点：

• 前缀编码：没有任何编码是其他编码的前缀，保证解码的唯一性
• 最优性：对于给定的频率分布，Huffman 编码是最优的前缀编码
• 局限性：需要预先统计频率或动态维护编码表

2.2 LZ77 算法

LZ77（Lempel-Ziv 1977）是一种基于字典的压缩算法，由 Abraham Lempel 和 Jacob Ziv 于 1977 年提出。其核心思想是：用已出现过的字符串的引用（位置和长度）来替换重复出现的字符串。

LZ77 的工作原理：

算法维护一个滑动窗口，包含已处理的数据（搜索缓冲区）和待处理的数据（前瞻缓冲区）。对于前瞻缓冲区中的数据，在搜索缓冲区中寻找最长的匹配字符串，然后用 (偏移量, 长度, 下一个字符) 的三元组替换。

滑动窗口示意：
[已处理数据（搜索缓冲区）| 待处理数据（前瞻缓冲区）]

示例：压缩 "ABABABAB"
已处理: "ABAB"
待处理: "ABAB"
在搜索缓冲区中找到 "AB" 匹配，偏移量为 2，长度为 2
输出: (2, 2, 'A')

LZ77 是后续许多压缩算法的基础，包括 DEFLATE、Gzip、ZIP 等。

2.3 DEFLATE 算法

DEFLATE 是一种结合了 LZ77 和 Huffman 编码的压缩算法，由 Phil Katz 于 1993 年设计，是 ZIP 和 Gzip 的核心算法。

DEFLATE 的两阶段压缩：

1. LZ77 阶段：使用滑动窗口查找重复的字符串，用长度-距离对替换
2. Huffman 编码阶段：对 LZ77 的输出（字面量、长度、距离）进行 Huffman 编码

DEFLATE 支持多种压缩级别，从最快（级别 1）到最优（级别 9），在速度和压缩率之间进行权衡。

三、有损压缩

有损压缩在压缩过程中会丢失部分信息，但力求丢失的是人眼或人耳不敏感的信息，从而在大幅减小文件体积的同时保持可接受的感知质量。

3.1 JPEG 图像压缩原理

JPEG（Joint Photographic Experts Group）是最广泛使用的有损图像压缩标准。

JPEG 压缩的主要步骤：

DCT 变换的核心思想：

DCT（Discrete Cosine Transform，离散余弦变换）将空间域的图像数据转换到频率域。图像的能量主要集中在低频部分，高频部分（代表细节和噪声）可以被大量量化甚至丢弃而不明显影响视觉质量。

#![allow(unused)]
fn main() {
// JPEG 质量因子与压缩率的示意
fn jpeg_compression_info() {
    let qualities = [
        (95, "极佳", "几乎无损"),
        (85, "很好", "标准质量"),
        (75, "好", "Web 常用"),
        (50, "中等", "明显压缩痕迹"),
        (25, "低", "严重失真"),
        (10, "极低", "块状伪影明显"),
    ];

    println!("JPEG 质量设置与效果对照:");
    println!("{:<10} {:<10} {:<20}", "质量因子", "效果", "说明");
    for (q, effect, desc) in &qualities {
        println!("{:<10} {:<10} {:<20}", q, effect, desc);
    }
}
}

3.2 MP3 音频压缩原理

MP3（MPEG-1 Audio Layer III）是最流行的有损音频压缩格式。

MP3 压缩的核心技术：

MP3 压缩流程：

1. 将音频信号分帧（每帧约 26ms）
2. 对每帧进行改进的离散余弦变换（MDCT）
3. 应用心理声学模型，计算每个频带的掩蔽阈值
4. 根据掩蔽阈值分配比特，量化频谱系数
5. 使用 Huffman 编码压缩量化后的系数
6. 添加帧头和辅助信息，形成 MP3 比特流

比特率与音质：

四、Rust 压缩库实践

Rust 生态提供了丰富的压缩库，可以方便地进行数据压缩和解压操作。

4.1 使用 flate2 进行 Gzip 压缩

flate2 是 Rust 中最流行的 DEFLATE 压缩库，支持 Gzip 和 Zlib 格式。

Cargo.toml 依赖：

[dependencies]
flate2 = "1.0"

Gzip 压缩与解压：

use flate2::write::{GzEncoder, GzDecoder};
use flate2::Compression;
use std::io::{self, Write};

fn gzip_compress(data: &[u8]) -> io::Result<Vec<u8>> {
    let mut encoder = GzEncoder::new(Vec::new(), Compression::default());
    encoder.write_all(data)?;
    encoder.finish()
}

fn gzip_decompress(data: &[u8]) -> io::Result<Vec<u8>> {
    let mut decoder = GzDecoder::new(Vec::new());
    decoder.write_all(data)?;
    decoder.finish()
}

fn main() -> io::Result<()> {
    let original = b"Rust is a systems programming language that runs blazingly fast, \
                      prevents segfaults, and guarantees thread safety. \
                      Rust is also a great language for web development, \
                      with frameworks like Actix and Axum providing high-performance \
                      HTTP servers. The Rust ecosystem is growing rapidly, \
                      with thousands of crates available on crates.io.";

    println!("原始数据大小: {} bytes", original.len());

    // 压缩
    let compressed = gzip_compress(original)?;
    println!("压缩后大小: {} bytes", compressed.len());
    println!("压缩率: {:.2}%", compressed.len() as f64 / original.len() as f64 * 100.0);

    // 解压
    let decompressed = gzip_decompress(&compressed)?;
    println!("解压后大小: {} bytes", decompressed.len());
    println!("数据一致性: {}", original.to_vec() == decompressed);

    // 不同压缩级别对比
    println!("\n不同压缩级别对比:");
    for level in [Compression::none(), Compression::fast(), Compression::default(), Compression::best()] {
        let mut encoder = GzEncoder::new(Vec::new(), level);
        encoder.write_all(original)?;
        let result = encoder.finish()?;
        println!("级别 {:?}: {} bytes", level.level(), result.len());
    }

    Ok(())
}

使用 BufReader/BufWriter 进行流式压缩：

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

fn compress_file(input_path: &str, output_path: &str) -> io::Result<()> {
    let input = File::open(input_path)?;
    let output = File::create(output_path)?;

    let mut reader = BufReader::new(input);
    let mut encoder = GzEncoder::new(BufWriter::new(output), Compression::default());

    let mut buffer = [0u8; 8192];
    loop {
        let n = reader.read(&mut buffer)?;
        if n == 0 {
            break;
        }
        encoder.write_all(&buffer[..n])?;
    }

    encoder.finish()?;
    Ok(())
}

fn decompress_file(input_path: &str, output_path: &str) -> io::Result<()> {
    let input = File::open(input_path)?;
    let output = File::create(output_path)?;

    let mut decoder = GzDecoder::new(BufReader::new(input));
    let mut writer = BufWriter::new(output);

    let mut buffer = [0u8; 8192];
    loop {
        let n = decoder.read(&mut buffer)?;
        if n == 0 {
            break;
        }
        writer.write_all(&buffer[..n])?;
    }

    writer.flush()?;
    Ok(())
}
}

4.2 使用 zip 库处理 ZIP 文件

zip 库提供了在 Rust 中创建和读取 ZIP 压缩文件的能力。

Cargo.toml 依赖：

[dependencies]
zip = "0.6"

创建 ZIP 压缩文件：

use std::fs::File;
use std::io::{self, Read, Write};
use zip::write::FileOptions;
use zip::CompressionMethod;

fn create_zip_archive(output_path: &str, files: &[(&str, &[u8])]) -> io::Result<()> {
    let file = File::create(output_path)?;
    let mut zip = zip::ZipWriter::new(file);

    let options = FileOptions::default()
        .compression_method(CompressionMethod::Deflated)
        .unix_permissions(0o755);

    for (name, content) in files {
        zip.start_file(*name, options)?;
        zip.write_all(content)?;
    }

    zip.finish()?;
    println!("ZIP 文件已创建: {}", output_path);
    Ok(())
}

fn main() -> io::Result<()> {
    let files = [
        ("readme.txt", b"This is a README file.\n" as &[u8]),
        ("data.json", b"{\"name\": \"Rust\", \"version\": \"1.70\"}\n" as &[u8]),
        ("hello.rs", b"fn main() { println!(\"Hello, Rust!\"); }\n" as &[u8]),
    ];

    create_zip_archive("archive.zip", &files)?;

    Ok(())
}

读取 ZIP 压缩文件：

use std::fs::File;
use std::io::{self, Read};
use zip::ZipArchive;

fn read_zip_archive(path: &str) -> io::Result<()> {
    let file = File::open(path)?;
    let mut archive = ZipArchive::new(file)?;

    println!("ZIP 文件包含 {} 个条目:", archive.len());
    println!("{:<20} {:<10} {:<10}", "文件名", "压缩后", "原始大小");
    println!("{}", "-".repeat(45));

    for i in 0..archive.len() {
        let mut file = archive.by_index(i)?;
        let name = file.name();
        let compressed = file.compressed_size();
        let size = file.size();

        println!("{:<20} {:<10} {:<10}", name, compressed, size);

        // 读取文件内容
        let mut contents = String::new();
        file.read_to_string(&mut contents)?;
        println!("  内容预览: {}", &contents[..contents.len().min(50)]);
    }

    Ok(())
}

fn main() -> io::Result<()> {
    read_zip_archive("archive.zip")?;
    Ok(())
}

4.3 压缩算法选择指南

在实际项目中，应根据数据类型和需求选择合适的压缩方案：

不同压缩算法的对比：

#![allow(unused)]
fn main() {
fn compression_comparison() {
    let algorithms = [
        ("Gzip (flate2)", "通用，兼容性好", "中等", "高"),
        ("LZ4", "极速压缩解压", "低", "很高"),
        ("Zstd", "Facebook 开发，压缩率和速度均衡", "高", "高"),
        ("LZMA/XZ", "极高压缩率", "很高", "中等"),
        ("Brotli", "Google 开发，Web 优化", "高", "高"),
    ];

    println!("{:<15} {:<30} {:<10} {:<10}", "算法", "特点", "压缩率", "速度");
    println!("{}", "-".repeat(70));
    for (name, feature, ratio, speed) in &algorithms {
        println!("{:<15} {:<30} {:<10} {:<10}", name, feature, ratio, speed);
    }
}
}

4.4 内存中的压缩与解压示例

use flate2::{read::ZlibDecoder, write::ZlibEncoder, Compression};
use std::io::{self, Read, Write};

fn zlib_roundtrip(data: &[u8]) -> io::Result<bool> {
    // 压缩
    let mut encoder = ZlibEncoder::new(Vec::new(), Compression::default());
    encoder.write_all(data)?;
    let compressed = encoder.finish()?;

    // 解压
    let mut decoder = ZlibDecoder::new(&compressed[..]);
    let mut decompressed = Vec::new();
    decoder.read_to_end(&mut decompressed)?;

    Ok(data == decompressed.as_slice())
}

fn main() -> io::Result<()> {
    let test_data = [
        b"Short text".to_vec(),
        vec![0u8; 1000],           // 全零数据（高度可压缩）
        (0..=255).collect(),       // 均匀分布数据（难以压缩）
        "Rust ".repeat(100).into_bytes(),  // 重复数据
    ];

    for (i, data) in test_data.iter().enumerate() {
        let mut encoder = ZlibEncoder::new(Vec::new(), Compression::default());
        encoder.write_all(data)?;
        let compressed = encoder.finish()?;

        let ratio = compressed.len() as f64 / data.len() as f64;
        let ok = zlib_roundtrip(data)?;

        println!(
            "测试 {}: 原始 {} bytes, 压缩后 {} bytes, 比率 {:.2}%, 一致性 {}",
            i + 1,
            data.len(),
            compressed.len(),
            ratio * 100.0,
            ok
        );
    }

    Ok(())
}

五、总结

练习建议：

1. 实现一个简单的 Run-Length Encoding（RLE，游程编码）算法，测试其对不同类型数据的压缩效果
2. 使用 flate2 编写一个命令行工具，支持对文件进行 Gzip 压缩和解压（类似 gzip 命令）
3. 对比 flate2 的不同压缩级别（none/fast/default/best）在速度和压缩率上的表现
4. 使用 zip 库编写一个程序，递归地将一个目录打包为 ZIP 文件
5. 统计一段文本中各字符的出现频率，计算其信息熵，并与 Huffman 编码后的平均码长进行比较
6. 尝试用 reqwest 下载一个网页，并用 flate2 压缩其 HTML 内容，观察压缩率