5.5 Data Compression：RLE、Huffman、LZW与可逆证书

5.5 · Data Compression覆盖 6 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

  • 能解释“5.5 · Data Compression”如何以可逆性为主线比较二进制 I/O、游程编码、Huffman 与 LZW 的模型和码流
  • 能逐项核对 数据压缩、二进制输入输出、游程编码、霍夫曼压缩、LZW压缩、压缩极限与错误检测，并区分作者站内容与本页独立补充
  • 能按“Huffman 平均码长满足 H ≤ L < H+1；压缩是否有效还取决于模型和元数据成本”手算一个最小输入，逐步检查“decode(encode(bytes)) 必须逐字节等于原输入，码流边界和 EOF 约定必须唯一”
  • 能注入“Huffman 单字符输入没有生成可消费码字，或 LZW 编解码器的字典新增时点不同步”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“5·5 · Data Compression”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“5·5 · Data Compression”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“5·5 · Data Compression”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：5.5 · Data Compression

  • 1. 数据压缩：在本页通过“读取二进制输入”连接解释、交互状态和练习验收。
  • 2. 二进制输入输出：在本页通过“建立频率或字典模型”连接解释、交互状态和练习验收。
  • 3. 游程编码：在本页通过“发射码字”连接解释、交互状态和练习验收。
  • 4. 霍夫曼压缩：在本页通过“按同一模型解码”连接解释、交互状态和练习验收。
  • 5. LZW压缩：在本页通过“逐字节核对”连接解释、交互状态和练习验收。
  • 6. 压缩极限与错误检测：在本页通过“读取二进制输入”连接解释、交互状态和练习验收。

从“变小不是正确性，可逆才是”开始

数据压缩（data compression）减少存储空间与传输时间，但“输出比输入小”不是correctness contract。Lossless compressor必须满足：

∀x∈D,expand⁡(compress⁡(x))=x\forall x\in D,\qquad \operatorname{expand}(\operatorname{compress}(x))=x

先预测：ABRACADABRA! 的Huffman payload可能远短于12个raw bytes，最终file就一定更短吗？不一定。Decoder还要拿到code trie与original length；短message上header会压过payload savings。LZW也要把每个code按固定width写出并用EOF framing结束。

因此评估同时包含四件事：round trip、format completeness、total encoded bits和malformed input behavior。压缩率只是最后一个指标。

5.5.1 Binary input and output：算法先从bit framing开始

普通text I/O以characters、tokens或lines为单位；压缩器必须读写单个bits和non-byte-width integers。二进制输入输出（binary input and output）由官方BinaryStdIn、BinaryStdOut提供。

若alphabet含R个symbols，fixed-length code至少需要：

W=⌈lg⁡R⌉W=\lceil \lg R\rceil

bits才能区分每个symbol。DNA alphabet ACTG 有R=4，只需2 bits，而extended ASCII的R=256需要8 bits。

BinaryStdOut.write(value, W)写value的W个low-order significant bits，顺序由format约定；最后不足一个byte的buffer在close时补padding。Decoder不能仅凭padding bits判断真实结束位置，所以format必须提供original length、EOF codeword或外层byte length。

BinaryStdOut.write(value, W);       // exactly W bits
int restored = BinaryStdIn.readInt(W);
if (restored != value) throw new IllegalStateException();
BinaryStdOut.close();               // flush final partial byte

5.5.2 Run-length encoding：用run counts替代重复bits

游程编码（run-length encoding）对长重复区特别有效。官方binary RunLength不写每个run的bit value，而约定：

  • First count永远代表0-run。
  • 后续counts交替表示1-run、0-run、1-run。
  • 每个count用8 bits，范围0至255。

所以input以1开头时，stream first count必须是0；例如 1111 编成counts [0,4]。若忘了leading zero，decoder会输出四个0。

char run = 0;
boolean old = false;
while (!BinaryStdIn.isEmpty()) {
    boolean bit = BinaryStdIn.readBoolean();
    if (bit != old) {
        BinaryStdOut.write(run, 8);
        run = 1;
        old = !old;
    } else {
        if (run == 255) {
            BinaryStdOut.write(run, 8);
            BinaryStdOut.write(0, 8);
            run = 0;
        }
        run++;
    }
}
BinaryStdOut.write(run, 8);

连续run超过255时输出255,0：第一个count结束current bit，zero-length opposite run让decoder toggle两次，再继续同一种bit。这个0不是无用padding，而是保持implicit alternating parity的format token。

若input有r个encoded runs，compressed size为 (8r) bits。Raw input有N bits，因此只有：

8r<N8r\lt N

时该format真正缩小。Alternating bits使r接近N，RLE会膨胀约8倍；黑白扫描图、sparse bitmap或preprocessed runs才适合。

Expand从bit false开始，对每个8-bit count输出对应数量，再toggle：

boolean bit = false;
while (!BinaryStdIn.isEmpty()) {
    int run = BinaryStdIn.readInt(8);
    for (int i = 0; i < run; i++) BinaryStdOut.write(bit);
    bit = !bit;
}

Certificate要覆盖empty input、starts-with-one、zero-length run、exact 255、more-than-255和alternating worst case。

5.5.3 Variable-length codes：必须能唯一切分

频繁symbol应使用short codeword，稀有symbol使用long codeword。但variable-length payload没有分隔符，必须保证unique decoding。Prefix-free code提供instantaneous decoding。

若A编码为0而B编码为01，读到0时decoder不知道应立即输出A还是等待1形成B。Prefix-free code消除这种歧义。Codeword lengths (l_1,\ldots,l_R) 必须满足Kraft-McMillan inequality：

∑i=1R2−li≤1\sum_{i=1}^{R}2^{-l_i}\le 1

Binary trie的leaf就是codeword；leaf不能有descendant，所以结构天然prefix-free。Fixed-length code也是prefix-free，但没有利用frequency。

给定symbol i出现frequency (f_i)，code trie T的payload bits是weighted external path length：

B(T)=∑ifi dT(i)B(T)=\sum_i f_i\,d_T(i)

Huffman要在所有prefix-free binary tries中最小化这个值。

5.5.4 Huffman compression：反复合并两个最小frequency tries

霍夫曼压缩（Huffman compression）先统计8-bit alphabet frequencies，再为每个nonzero symbol创建single-node trie。Priority queue每次取two minimum roots，合成weight sum的新parent，直到只剩一棵tree。

MinPQ<Node> pq = new MinPQ<>();
for (char c = 0; c < R; c++)
    if (freq[c] > 0) pq.insert(new Node(c, freq[c], null, null));
 
while (pq.size() > 1) {
    Node left = pq.delMin();
    Node right = pq.delMin();
    pq.insert(new Node('\0', left.freq + right.freq, left, right));
}
Node root = pq.delMin();

给left edge标0、right edge标1，root-to-leaf path就是code。最小frequency symbols被放到deep positions。Optimality可用greedy exchange与induction：

  1. 某棵optimal full trie可把two least-frequent symbols交换到maximum-depth sibling leaves而不增加cost。
  2. 合并这两个leaves为weight sum的pseudo-symbol，得到smaller optimal subproblem。
  3. Huffman反复执行同一choice，因此得到minimum weighted path length。

Tie breaking可能产生不同code table，但payload total bits仍可相同；encoder与decoder通过serialized trie共享exact choice。

Stream format不是只有payload

官方compress依次写：

  1. Preorder trie：internal node写0，leaf写1再写8-bit symbol。
  2. Original byte length：32-bit integer。
  3. 每个input symbol的variable-length code bits。

有R个distinct symbols时，full binary trie有R leaves和R-1 internal nodes，所以tree header需要：

Btrie=(2R−1)+8R=10R−1B_{\mathrm{trie}}=(2R-1)+8R=10R-1

bits。Total是tree header、32-bit length和payload之和。

Decoder先递归恢复trie，再读length；每个output symbol从root读bits直到leaf。Length不是可选优化：它告诉decoder应输出多少bytes，也处理最后byte padding。Official code对empty input没有独立format branch，production wrapper必须定义empty-stream representation；single-symbol tree也要保证decoder按length重复leaf symbol。

5.5.5 LZW compression：固定宽code描述可变长phrases

LZW压缩（LZW compression）与Huffman方向相反：

  • Huffman：variable-length codewords表示fixed-length symbols。
  • LZW：fixed-length codewords表示variable-length strings。

官方实现使用extended ASCII：

  • Codes 0至255：single-character strings。
  • Code 256：EOF。
  • Next available code从257开始。
  • W=12 bits，所以最多L=4096 entries。

Encoder在remaining input中找dictionary longest prefix s，写出s的12-bit code；若还有next character且dictionary未满，加入 s + nextCharacter。

while (input.length() > 0) {
    String s = st.longestPrefixOf(input);
    BinaryStdOut.write(st.get(s), 12);
    int t = s.length();
    if (t < input.length() && code < 4096)
        st.put(input.substring(0, t + 1), code++);
    input = input.substring(t);
}
BinaryStdOut.write(256, 12);

Decoder不接收dictionary；它从same 256 single-character entries开始。输出previous phrase val 后读next codeword，加入 val + firstChar(nextPhrase)，因此与encoder lockstep。

String val = st[BinaryStdIn.readInt(12)];
while (true) {
    BinaryStdOut.write(val);
    int codeword = BinaryStdIn.readInt(12);
    if (codeword == 256) break;
    String s = st[codeword];
    if (codeword == nextCode) s = val + val.charAt(0);
    if (nextCode < 4096) st[nextCode++] = val + s.charAt(0);
    val = s;
}

codeword == nextCode 是关键special case：encoder刚加入的phrase尚未在decoder table中出现，但它必然是 val + val.firstChar。忽略它会让 ABABABA 或repetitive patterns解码失败。

Official fixed-width stream的codeword count为C时，总payload为 (12C) bits。Dictionary满后停止增长，不reset；实际formats可能动态增宽、clear或freeze，但encoder/decoder必须使用相同policy。当前Java代码反复substring，在现代Java可能产生quadratic copying；production实现应以cursor或streaming trie扫描，而不是把此API成本误当LZW理论成本。

5.5.6 Workload决定谁能压缩

  • RLE利用long same-bit runs。
  • Huffman利用single-symbol frequency skew，但不建模symbol order。
  • LZW利用repeated phrases与context，frequency相同的strings也可能有不同ratio。
  • Already-compressed、encrypted或random-like data通常无可利用redundancy，header只会膨胀。

Benchmark应报告raw bits、header bits、payload bits、total bits、compress/expand throughput、peak memory和round-trip result。不能只挑最适合某算法的一条sample。

Pipeline可组合transform，例如先把image pixels变成differences，再RLE或dictionary-code；但每一步都要versioned framing。Repeated compression不保证继续变小。

5.5.7 Compression limits：不存在让所有files都严格变小的lossless算法

压缩极限与错误检测（compression limits and error detection）首先要区分两件事：压缩利用source redundancy；错误控制增加redundancy来发现或纠正channel damage。它们目标相反但都依赖明确bit model。

对所有n-bit strings，inputs数量是 (2^n)。所有length小于n的bitstrings总数：

∑k=0n−12k=2n−1\sum_{k=0}^{n-1}2^k=2^n-1

若lossless compressor让每个n-bit input都变短，就要把 (2^n) 个inputs injectively映射到只有 (2^n-1) 个outputs，违反pigeonhole principle。因此至少一个input不能缩短；考虑all lengths与self-delimiting format时，一些inputs必然膨胀。

这个论证不否认useful compression。Real workloads不是uniform all bitstrings；text、images和telemetry有统计结构。Compressor把common inputs缩短，代价是rare/incompressible inputs不变或变长。

5.5.8 Error detection：round trip不能证明stored stream未损坏

Compression/decompression在clean channel上的round trip只证明codec互逆。Bit flip可能：

  • 改变Huffman trie，使后续payload全部错位。
  • 改变original length，导致truncation或overrun。
  • 改变LZW codeword，使dictionary从该点永久不同步。
  • 在RLE中把一个count变成很大run。

最简单even parity能检测odd number of bit flips，不能检测even flips，也不能纠正位置。若每bit以three copies发送、channel独立flip probability为p，majority decoder错误概率：

Pwrong=3p2(1−p)+p3=3p2−2p3P_{\mathrm{wrong}}=3p^2(1-p)+p^3=3p^2-2p^3

它在 0<p<1/20\lt p\lt 1/2 时低于p，但传输率降为one third。Checksums/CRC用于检测，Reed-Solomon等error-correcting codes加入结构化冗余用于burst errors。Compression format至少应有length bounds、checksum或外层authenticated framing，且decoder必须限制allocation和expansion ratio。

5.5.9 Independent certificate：可逆、完整、受限

压缩器的独立证书不能由candidate decoder单独自证。至少包括：

  1. Byte-exact round trip：referenceExpand(candidateCompress(x))与x完全相等。
  2. Cross implementation：candidate encoder与reference decoder、reference encoder与candidate decoder交叉。
  3. Framing：tree/length/EOF/padding都存在且consume exactly expected bits。
  4. Malformed streams：truncated header、impossible code、oversized length、missing EOF必须拒绝。
  5. Size accounting：ratio包含headers，不只payload。
  6. Resource bounds：declared length与expansion work有上限，避免decompression bomb。
for (const input of corpus) {
  const stream = candidate.compress(input);
  assertBytesEqual(reference.expand(stream), input);
  assert(stream.totalBits === stream.headerBits + stream.payloadBits);
}
for (const mutation of malformedStreams)
  assertRejects(() => candidate.expand(mutation));

Corpus要含empty、one symbol、all 256 byte values、long runs、alternating bits、repeated phrases、random-like bytes和large input。Mutation应命中每个field boundary，而不是只随机flip。

5.5.10 逐步运行路线

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“5.5 · Data Compression”的两个最小情境间切换，再逐项选择正式概念。预测“Huffman 平均码长满足 H ≤ L < H+1；压缩是否有效还取决于模型和元数据成本”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

5.5 · Data Compression：对象、操作与不变量

以可逆性为主线比较二进制 I/O、游程编码、Huffman 与 LZW 的模型和码流

选择最小情境

切换正式概念

输入合同操作证书algs4-5.5 · 先给前提，再执行，再验收当前概念：1/6
偏斜频率
AAAAABBC 的字符频数
当前观察
data compression：Huffman 给高频 A 较短码，并保留无前缀歧义
Huffman 平均码长满足 H ≤ L < H+1；压缩是否有效还取决于模型和元数据成本

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

  • 数据压缩：在实验 1 中指出对应状态，并写出一个通过条件。
  • 二进制输入输出：在实验 2 中指出对应状态，并写出一个通过条件。
  • 游程编码：在实验 3 中指出对应状态，并写出一个通过条件。
  • 霍夫曼压缩：在实验 1 中指出对应状态，并写出一个通过条件。
  • LZW压缩：在实验 2 中指出对应状态，并写出一个通过条件。
  • 压缩极限与错误检测：在实验 3 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“Huffman 平均码长满足 H ≤ L < H+1；压缩是否有效还取决于模型和元数据成本”不是孤立结论？

问题 3：故障恢复。 怎样证明“Huffman 单字符输入没有生成可消费码字，或 LZW 编解码器的字典新增时点不同步”已经修复？

小结

  • Data compression的首要contract是lossless byte-exact round trip，而不是输出总比输入小。
  • Binary input and output按bit和fixed-width fields工作；length、EOF、padding与model属于format。
  • Run-length encoding隐含0/1交替并用8-bit counts；leading zero run与255 overflow的zero count不可漏。
  • Prefix-free code允许沿trie即时切分；Huffman compression最小化frequency-weighted code length。
  • Huffman stream必须携带preorder trie、original length和payload，header需计入ratio。
  • LZW compression以12-bit codes表示variable-length phrases，encoder/decoder同步建dictionary并处理next-code special case。
  • Counting argument证明universal strict compression不可能；workload redundancy决定收益。
  • Error detection与compression责任不同；损坏可放大，需checksum/CRC或更强外层integrity。
  • Independent certificate检查cross-decoding、framing、malformed rejection、total size与resource bounds。

资料与写作方式声明

本章以Algorithms, Fourth Edition的合法公开试读核定可见范围，并以目录限定未公开部分，并结合正文列出的技术资料独立重写；不宣称复现原书正文，也不沿用原作表述。

原作版权归作者与出版社所有；本站原创教学结构与表述仅供学习交流。

讨论

评论区加载中…