Huffman 压缩主要是通过 Huffman 编码来代替 ASCII 重新表示字符,使得出现频率高的字符编码短,出现少的字符编码长。

注:以下代码仅用于理解,无法编译成功。如需要编译成功的代码,请查看 Huffman Compression 哈夫曼压缩实现

什么是压缩

压缩是一种通过特定的算法来减小计算机文件大小的机制。这种机制是一种很方便的发明,尤其是对网络用户,因为它可以减小文件的字节总数,使文件能够通过较慢的互联网连接实现更快传输,此外还可以减少文件的磁盘占用空间。[1]

但是,所有的压缩都能使得文件变小吗?

压缩的极限

因为所有的文件都是由二进制来存储的,让我们考虑一个长度为 n 的字符串,我们可以知道总共有 2n2^n 个长度为 n 的二进制字符串。

接着,由于以下的公式

20+21+22+...+2n1=2n12^0 + 2^1 + 2^2 + ... + 2^{n-1} = 2^n - 1

我们可以知道,总共有 2n12^n - 1 个长度小于 n 的字符串。既然我们要使得压缩后的文件比源文件小,那么这就意味着压缩算法需要将长度为 n 的字符串变成任何小于 n 的字符串。但是,因为压缩函数是一个双射函数,这就意味着每一个长度为 n 的字符串只能被压缩成一个 unique 的长度小于 n 的字符串。

但是,小于 n 的字符串只有 2n12^n - 1 个,但这导致了一个矛盾:我们要把 2n2^n 个长度为 n 的字符串放进 2n12^n - 1 个长度小于 n 的字符串,但是这会导致有两个不同的长度为 n 的字符串被压缩成了同一个长度小于 n 的字符串。很明显,这是不可能的(这样会导致无法解压;到底是解压成文件 A 还是文件 B?),所以,不存在一种完美的压缩算法能够将所有的文件都压缩成比自己小的文件

哈夫曼编码

虽然说没有方法能够把文件完美的压缩,但是大多数情况下我们还是有方法能够尽可能的压缩文件的。

众所周知,我们使用 ASCII 来表示字符,比如:

Hello World 就可以用 ASCII 表示成如下的字符:

01001000 01100101 01101100 01101100 01101111 00100000 01010111 01101111 01110010 01101100 01100100

但是我们可以发现,Hello World 用 ASCII 表示会产生很多无用的二进制位,比如 01001000 01100101开头的 0 貌似看起来没有太多用处。

所以,我们能不能设计自己的一个编码,然后根据这种编码来进行压缩呢?这就是哈夫曼编码的来源。

Prefix Code

假设我们采用如下的编码方式来表示 Hello World

字符编码
H0
e1
l00
o01
[空格]10
W11
r100
d101

我们可以得到:0 1 00 00 01 10 11 01 100 00 101.

乍一看,这个压缩之后的字符明显比原先的用 ASCII 表示的 Hello World 小了很多。但是这里存在一个问题,我们如何怎么划分这个二进制字符串呢,同一个字符串我们可以这么读:
01 00 00 01 101 101 100 00 10 1,这样压缩出来就变成了 olloddrl e. 但这并不是我们想要的字符串。

为了解决这个问题,我们就引入了 Prefix Code 前缀码,这种方式保证了我们对每一个字符的 Code 都不是另外一个字符的 Code 的前缀。

前缀码 - 编码

让我们考虑如上的编码,我们可以把 Hello World 表示为:

000 001 010 010 011 100 101 011 110 010 111

虽然这看起来比之前的编码长一些,但是可以看出来,针对这个二进制编码,没有其它的解读方法。这种编码方式有这种特性的原因就是因为,我们把所有的字母都放在了树的叶结点上,这样保证了没有一个字符会使用另一个字符的编码作为开头

哈夫曼树

有了前缀码的基础之后,我们需要解决的就是另外一个问题:我们如何能够保证我们能尽可能的压缩这个 Hello World 这个字符串呢?

换言之,这个问题就是我们如何能够构造出一个最优的树,使当我们用这棵树作为编码方式时,能把 Hello World 压缩成最小。这颗最小的树就是哈夫曼树。

下面就是生成哈夫曼树的步骤:

  • 建立一个频率表,统计文本中每个字符出现的次数
  • 初始化一个空的优先队列,该队列存储树节点(用TreeNode*表示)
  • 为输入字符串中的每个不同字符创建一个叶子节点。将每个新的叶子节点添加到优先队列中。该叶子的权重是该字符的频率
  • 当优先级队列中有两棵或更多树时
    • Dequeue 两个最低优先级的树
    • 将这两棵树合并在一起形成一棵新树,其权重为两棵树的权重之和
    • 然后,再将该树加回优先级队列。

如果不知道什么是优先队列,可以查看这篇文章.

哈夫曼压缩

接下来我们就要来实现哈夫曼压缩。

在接下来的代码里,可以假设如下的结构体 & 类存在:

struct EncodingTreeNode {

    char ch;
    EncodingTreeNode* zero;
    EncodingTreeNode* one;

    EncodingTreeNode(char c) {
        ch = c;
        zero = one = nullptr;
    }

    EncodingTreeNode(EncodingTreeNode* z, EncodingTreeNode* o) { 
        zero = z;
        one = o;
    }
};

class Bit {
public:
    Bit() = default;
    Bit(int value);

    friend bool operator== (Bit lhs, Bit rhs);
    friend bool operator!= (Bit lhs, Bit rhs);
    friend std::ostream& operator<< (std::ostream& out, Bit bit);

private:
    bool _value;
};

struct EncodedData {
    Queue<Bit>  treeBits;
    Queue<char> treeLeaves;
    Queue<Bit>  messageBits;
};

注:Bit 结构保证了我们存储的整数只能为 0 或 1

哈夫曼树的构建 & 字符频率

EncodingTreeNode* buildHuffmanTree(string text) {
    Map<char, double> m;
    EncodingTreeNode* tree;

    // Generate frequency table
    for(char c : text){
        m[c] += 1;
    }

    if(m.size() < 2){
        error("The input text does not contain at least two distinct characters");
    }

    PriorityQueue<EncodingTreeNode*> q;

    // Initialize a priority queue
    for(char key : m){
        EncodingTreeNode* tmp = new EncodingTreeNode(key);
        q.enqueue(tmp, m[key]);
    }

    // Merge Tree
    while(!q.isEmpty()){
        double priorityFirst = q.peekPriority();
        EncodingTreeNode* first = q.dequeue();

        double prioritySecond = q.peekPriority();
        EncodingTreeNode* second = q.dequeue();

        EncodingTreeNode* tmp = new EncodingTreeNode(first, second);

        if(q.isEmpty()){
            tree = tmp;
            break;
        }
        q.enqueue(tmp, priorityFirst + prioritySecond);
    }

    return tree;
}

压缩字符

为了避免我们每次遇到一个字符都需要遍历树去查找这个字符,我们可以为树里的每一个字符都构建一个 Map

Queue<Bit> encodeText(EncodingTreeNode* tree, string text) {
    Map<char, Vector<Bit>> m;
    Queue<Bit> b;

    generateMapForEachCharacter(tree, {}, m);

    for(char c : text){
        Vector<Bit> bitString = m[c];
        for(Bit bit : bitString){
            b.enqueue(bit);
        }
    }

    return b;
}

Flatten Huffman Tree

为了使得其它的电脑能够解压我们的文件,我们需要一种方法存储我们的哈夫曼树。这就是 Flatten a tree.

One of the practical concerns of Huffman coding is the compressed data has to include information about the encoding tree used. It is not possible to decode the bit sequences back to the original characters without knowledge of the original encoding tree.
We want to write the Huffman tree into the compressed file, but it isn't possible to write a tree directly. Therefore, we must come up with a way to "flatten" the tree into a form that records the data and structure of the tree and allows you to later reconstruct the tree.
There are many ways to do this, but one very space-efficient approach is to flatten the tree into two sequences: a sequence of bits that gives the shape of the tree and a sequence of characters from the leaves.

The shape of the tree is flattened into a sequence of bits as follows:
If the root of the tree is a leaf node, it’s represented by the bit 0.
If the root of the tree is not a leaf node, it’s represented by a 1 bit, followed by the encoding of its zero (left) subtree, followed by the encoding of its one (right)
subtree.
In this way, the first sequence of bits describes the node structure in the order that the nodes are visited in a pre-order traversal of the tree.
Then, the characters of the tree are flattened into a second sequence that contains the characters from the leaf nodes in the order they are visited during an in-order traversal of the tree.
Together the two flattened sequences describe the tree shape and data in a way that
allows us to recreate that exact tree later.
For example, here are two encoding trees and how they’d be flattened to a sequence of
bits and a sequence of characters:[2]

Flatten Tree Example
void generateTreeLeaves(EncodingTreeNode* tree, Queue<char>& treeLeaves){
    if(tree->one == nullptr){
        treeLeaves.enqueue(tree->ch);
        return;
    }

    generateTreeLeaves(tree->zero, treeLeaves);
    generateTreeLeaves(tree->one, treeLeaves);
}

void generateTreeBits(EncodingTreeNode* tree, Queue<Bit>& treeBits){
    if(tree->one == nullptr){
        treeBits.enqueue(0);
        return;
    }

    treeBits.enqueue(1);

    generateTreeBits(tree->zero, treeBits);
    generateTreeBits(tree->one, treeBits);
}

void flattenTree(EncodingTreeNode* tree, Queue<Bit>& treeBits, Queue<char>& treeLeaves) {
    // Generate treeLeaves
    generateTreeLeaves(tree, treeLeaves);

    // Generate treeBits
    generateTreeBits(tree, treeBits);
}

压缩

完成了以上的步骤,就是我们把它整合起来的时候:

EncodedData compress(string messageText) {
    EncodedData e;

    EncodingTreeNode* tree = buildHuffmanTree(messageText);

    Queue<Bit> encodedString = encodeText(tree, messageText);

    Queue<Bit> treeBits;
    Queue<char> treeLeaves;

    flattenTree(tree, treeBits, treeLeaves);

    e.treeBits = treeBits;
    e.treeLeaves = treeLeaves;
    e.messageBits = encodedString;

    deallocateTree(tree);

    return e;
}

哈夫曼解压

哈夫曼树还原

知道了我们如何使得一个树扁平化,我们也可以知道如何复原这棵树:

EncodingTreeNode* unflattenTreeHelper(EncodingTreeNode*& tree, Queue<Bit>& treeBits, Queue<char>& treeLeaves){
    Bit i = treeBits.dequeue();

    if(i == 0){
        if(tree == nullptr){
            tree = new EncodingTreeNode(nullptr, nullptr);
        }
        tree->ch = treeLeaves.dequeue();
        return tree;
    }

    if(tree == nullptr){
        tree = new EncodingTreeNode(nullptr, nullptr);
    }

    EncodingTreeNode* leftSubtree = unflattenTreeHelper(tree->zero, treeBits, treeLeaves);
    EncodingTreeNode* rightSubtree = unflattenTreeHelper(tree->one, treeBits, treeLeaves);

    tree->zero = leftSubtree;
    tree->one = rightSubtree;

    return tree;
}

EncodingTreeNode* unflattenTree(Queue<Bit>& treeBits, Queue<char>& treeLeaves) {
    EncodingTreeNode* tree = nullptr;

    unflattenTreeHelper(tree, treeBits, treeLeaves);
    return tree;
}

解码字符串

string decodeText(EncodingTreeNode* tree, Queue<Bit>& messageBits) {
    EncodingTreeNode* tmp = tree;
    string result = "";

    while(!messageBits.isEmpty()){
        while(tmp->one != nullptr){ // if it's an optimal Haffman tree, the point doesn't contain "one" child will definitely doesn't contain "zero".
            Bit i = messageBits.dequeue();
            if(i == 0){
                tmp = tmp->zero;
            }else{
                tmp = tmp->one;
            }
        }
        result += tmp->ch;
        tmp = tree;
    }

    return result;
}

解压

string decompress(EncodedData& data) {
    EncodingTreeNode* tree = unflattenTree(data.treeBits, data.treeLeaves);
    string s = decodeText(tree, data.messageBits);

    deallocateTree(tree);

    return s;
}

  1. From Baidu Baike ↩︎

  2. From Stanford CS106 ↩︎