赫夫曼编码 Huffman¶

Huffman 在 1952 年根据香农（Shannon）在 1948 年和范若（Fano）在 1949 年阐述的这种编码思想提出了一种不定长编码的方法，也称霍夫曼（Huffman）编码。

这是一个经典的压缩算法。通过 字符出现的频率，优先级，二叉树 进行的压缩算法。

对一个字符串，计算每个字符出现的次数, 把这些字符放到优先队列（priority queue）；这个 priority queue 转出二叉树

需要一个字符编码表来解码,通过二叉树建立 huffman 编码和解码的字典表

举一个例子：

原始串：二级制编码： huffman 编码：

存储结构和基本操作¶

struct node{
    char *huffCode; // 叶子节点的huff编码
    int weight;
    struct node *left,right;
}

原则：出现频率越多的会在越上层，编码也越短，出现频率越少的在越下层，编码也越长。不存在某一个编码是另一个编码的前缀,字符都在叶节点上，所以不会存在一个编码是另一个编码的前缀二叉树每个节点要么是叶子节点，要么是双分支节点 (且左分支编码为 0，右分支编码为 1)

扫描输入文件，统计各个字符出现的次数，对结构排序（hash 统计每个字符出现的次数）
根据排序结构，构建赫夫曼树（贪心策略，每次选频率值最低的 2 个节点合并,需要优先队列帮组 (priority queue，又叫最小堆)）
对树进行遍历（左分支编码为 0，右分支编码为 1），得到各个字符的 huffman 编码，存到 hash 表中（这个就是编解码表，也可直接存储到节点中，如上面的 char *huffCode）
重新对文件扫描，根据 hash 表进行压缩

压缩的文件为了能够解压缩，需要一个文件头，用来重建赫夫曼树，包括：被编码的文本长度 unsigned int size 字符频率表 unsigned char freqs[NUM_CHARS]