【Algorithms 4】算法（第4版）学习笔记 24 - 5.5 数据压缩

前言

本篇主要内容包括：游程编码、霍夫曼压缩算法、LZW 压缩算法。

建议在学习本篇之前先行学习或回顾 《5.2 单词查找树》的内容。

参考目录

• B站 普林斯顿大学《Algorithms》视频课
  （请自行搜索。主要以该视频课顺序来进行笔记整理，课程讲述的教授本人是该书原版作者之一 Robert Sedgewick。）
• 微信读书《算法（第4版）》
  （本文主要内容来自《5.5 数据压缩》）
• 官方网站
  （有书本配套的内容以及代码）

学习笔记

注1：下面引用内容如无注明出处，均是书中摘录。
注2：所有 demo 演示均为视频 PPT demo 截图。
注3：如果 PPT 截图中没有翻译，会在下面进行汉化翻译，因为内容比较多，本文不再一一说明。

1：介绍

这个世界充满了数据，而能够有效表达数据的算法在现代计算机基础架构中有着重要的地位。压缩数据的原因主要有两点：节省保存信息所需的空间和节省传输信息所需的时间。

对于通用数据压缩：

2：游程编码 run-length encoding

2.1：介绍

将 40 位长的比特字符串拆解可得：15个0，7个1，7个0，11个1（交替出现的 0 和 1）
用 4 位表示长度并以 0 开头，可以得到：15=1111，7=0111，7=0111，11=1011
即：1111011101111011

问题一：用多少比特表示游程长度？
答：用 8 位（但本例中使用 4 位）
问题二：当某个游程的长度超过了能够记录的最大长度时怎么办？
答：当运行长度超过最大值时，插入长度为0的运行进行间隔。

2.2：Java 实现

edu.princeton.cs.algs4.RunLength

edu.princeton.cs.algs4.RunLength#compress

3：霍夫曼压缩 Huffman compression

3.1：变长前缀码 variable-length codes

3.1.1：介绍

根据不同字符采用不同位数进行编码。

Q. 如何避免歧义？
**A. ** 确保任何编码都不作为其他编码的前缀存在。

示例 1. 固定长度编码。
示例 2. 在每个编码字后附加特殊终止字符。
示例 3. 实现通用的前缀码。

3.1.2：前缀码单词查找树

注：建议回顾《5.2 单词查找树》 。

Q. 如何表示前缀码？
A. 单词查找树！

• 字符存储在叶子节点上。
• 每个编码对应从树的根节点到某个叶子节点的一条路径。

压缩：

• 方法1：从叶子节点开始，沿路径向上追溯至根节点，反向输出各节点对应的二进制位。
• 方法2：创建键-值对的符号表。

扩展：

• 从根节点开始。
• 若当前位为 0，则向左子树移动；若为 1，则向右子树移动。
• 若到达叶子节点，则输出该节点所代表的字符，并返回到根节点继续处理下一个位。

3.2：霍夫曼编码

3.2.1：概述

动态模型： 针对每条消息使用自定义的前缀码进行压缩。

压缩过程：

• 读取待压缩的消息。
• 根据消息内容构建最优的前缀码。如何构建？
• 将生成的前缀码（单词查找树）写入文件。
• 利用构建好的前缀码对消息进行压缩。

扩展过程：

• 从文件中读取前缀码（单词查找树）。
• 读取已压缩的消息，并利用单词查找树对其进行扩展还原。

3.2.2：Java 实现：单词查找树节点

edu.princeton.cs.algs4.Huffman.Node

3.2.3：Java 实现：扩展

edu.princeton.cs.algs4.Huffman#expand

3.2.4：Java 实现：单词查找树、编译表

edu.princeton.cs.algs4.Huffman#buildTrie

edu.princeton.cs.algs4.Huffman#buildCode

3.2.5：Java 实现：压缩

edu.princeton.cs.algs4.Huffman#compress

/**
     * Reads a sequence of 8-bit bytes from standard input; compresses them
     * using Huffman codes with an 8-bit alphabet; and writes the results
     * to standard output.
     * 从标准输入中读取8位字节序列; 使用具有8位字母的霍夫曼代码对其进行压缩; 并将结果写入标准输出。
     */
    public static void compress() {
        // read the input
        String s = BinaryStdIn.readString();
        char[] input = s.toCharArray();

        // tabulate frequency counts
        int[] freq = new int[R];
        for (int i = 0; i < input.length; i++)
            freq[input[i]]++;

        // build Huffman trie
        Node root = buildTrie(freq);

        // build code table
        String[] st = new String[R];
        buildCode(st, root, "");

        // print trie for decoder
        writeTrie(root);

        // print number of bytes in original uncompressed message
        BinaryStdOut.write(input.length);

        // use Huffman code to encode input
        for (int i = 0; i < input.length; i++) {
            String code = st[input[i]];
            for (int j = 0; j < code.length(); j++) {
                if (code.charAt(j) == '0') {
                    BinaryStdOut.write(false);
                }
                else if (code.charAt(j) == '1') {
                    BinaryStdOut.write(true);
                }
                else throw new IllegalStateException("Illegal state");
            }
        }

        // close output stream
        BinaryStdOut.close();
    }

3.3：demo 演示

• 计算输入字符的频率。

• 从每个字符开始，对应创建一个节点，并赋予其权重等于该字符的出现频率。（按照权重排序）

• 找到最小权重的两个。
• 合并成一个累计权重的单词查找树。

将新的树放回原本的队列中，按照权重排序。

重复以上的构建步骤，具体过程如下：

最终构建结果：

3.4：小结

Q. 如何找到最佳的前缀码？

霍夫曼算法：

• 计算输入字符串中每个字符 i 的出现频率 freq[i]。
• 针对每个字符 i，初始化一个节点，节点的权重设置为其频率 freq[i]。
• 重复以下过程直到形成一个单一的单词查找树：
  • 选择两个具有最小权重 freq[i] 和 freq[j] 的节点。
  • 将这两个节点合并成为一个新节点，新节点的权重为原两个节点权重之和 freq[i] + freq[j]。

对应书本命题 U：

4：LZW 压缩算法

4.1：统计方法

静态模型： 应用于所有文本的固定模型。

• 速度快。
• 不是最优：因为各类文本具有各自的统计特征差异。
• 示例：ASCII码、摩尔斯电码。

动态模型： 根据文本内容动态生成压缩模型。

• 需要先进行一次预处理遍历来建立模型。
• 在传输压缩数据时，必须同时发送模型信息。
• 示例：霍夫曼编码。

适应性模型： 在读取文本过程中不断学习和更新模型。

• 精确的模型构建可带来更高的压缩率。
• 解压时需从起始位置开始解码整个文件。
• 示例：LZW算法。

4.2：LZW 压缩

demo 演示：

压缩：

LZW压缩：

• 创建一张关联 W 位长度编码值和字符串的符号表。
• 初始化 ST，其中包含单个字符键对应的码字。
• 在输入未扫描部分中查找 ST 中最长的字符串 s，该字符串是输入的一个前缀。
• 写出与字符串s关联的W位码字。
• 将 s 与输入中的下一个字符 c 拼接起来，形成新的字符串，并将其添加到 ST 中。

Q. 如何表示 LZW 压缩的码表？
A. 使用一个单词查找树（Trie）结构来支持最长前缀匹配。

4.3：LZW 扩展

demo 演示：

扩展：

LZW 扩展：

• 创建一个符号表，用于关联 W 位宽的码键与对应的字符串值。
• 初始化 ST，填充所有可能的单字符解码结果。
• 读取一个 W 位码键。
• 在 ST 中查找与该码键关联的字符串值并输出。
• 更新ST。

Q. 如何表示 LZW 解压缩的码表？
A. 使用大小为 2^W 的数组来表示。

4.4：特殊情况

4.5：Java 实现

edu.princeton.cs.algs4.LZW

edu.princeton.cs.algs4.LZW#compress

edu.princeton.cs.algs4.LZW#expand

4.6：小结

无损压缩：

• 使用变长编码表示固定长度的符号。[霍夫曼编码]
• 使用固定长度的编码表示变长的符号。[LZW 编码]

有损压缩： [本课程未涵盖]
· JPEG、MPEG、MP3等。
· FFT（快速傅里叶变换）、小波分析、分形等技术。

压缩的理论极限： 香农信息熵。

压缩实践： 尽可能利用所有可利用的信息。

（完）