0x00 介绍

哈夫曼算法

《数据结构与算法分析》给出定义：

算法对一个由树组成的森林进行。一棵树的权等于它的树叶的频率的和。任意选取最小权的两棵树T₁和T₂，并任意形成以T₁和T₂为子树的新树，将这样的过程进行C - 1次。在算法的开始，存在C棵单节点树——每个字符一棵。在算法结束时得到一棵树，这棵树就是最优哈夫曼编码树。

哈夫曼编码过程
给出n个字符，对这n个字符进行编码。在这里，我们令n等于5，代表的权值分别为0.1、0.2、0.3、0.4和0.5。根据哈夫曼算法，对其进行哈夫曼编码将按照下列方式依次完成：
5个结点，令其名称即为各自权值：
第一步，合并0.1和0.2：
第二步，合并0.3和0.3：
第三步，合并0.4和0.5：
合并0.6和0.9，得到哈夫曼树：
最后，按照左子树为0，右子树为1的编码规则（也可以是左子树为1，右子树为0）对树进行编码：

从而，0.1、0.2、0.3、0.4和0.5的编码分别为010、011、00、10、11
哈夫曼编码的应用
文件压缩；
HTTP数据包压缩；
信源编码等。

0x01 问题分析

对上述哈夫曼编码过程，我们可以用伪代码描述如下：

将n个结点放入集合S
while (S中的结点数 > 1):
    取走S中2个权值最小的结点，计算它们值之和，并加入S
return 集合S剩下的结点 # 剩下的结点就是根结点

为了高效求出集合S中2个权值最小的结点，需要借助二叉堆的数据结构（即优先队列），避免实现堆的细节，可以采用C++ STL中的priority_queue。

0x02 代码实现

要求
现有input.txt文件，存放内容为0.1、0.2、0.3、0.4和0.5，将各自的哈夫曼编码输出到output.txt中

代码

#include <iostream>
#include <queue>
#include <map>
#include <fstream>

typedef double dataType;

typedef struct Node {
    struct Node* lchild;
    struct Node* rchild;
    dataType data;
} Huffman;

struct cmp { /* 规定优先队列的排序规则 */
    bool operator() (Huffman* a, Huffman* b) const
    {
        return (a->data > b->data); /* 小顶堆 */
    }
};

/*
code 变量的初始值是空字符串，采用二叉树后续遍历，如果是非叶子结点，
存在左子树就将code加"0"，存在右子树就将code加"1"，继续递归调用；
如果是叶子结点，就记录到键值对（map）里。
*/
void huffman_code(Huffman* h, std::string code, std::map<double, std::string>& map_huff)
{
    if (!h)
        return;
    if (h->lchild)
        huffman_code(h->lchild, code + "0", map_huff);
    if (h->rchild)
        huffman_code(h->rchild, code + "1", map_huff);
    if (h->lchild == 0 && h->rchild == 0) {
        map_huff[h->data] = code;
        return;
    }
}

void mem_clear(Huffman* p) /* 释放内存 */
{
    if (!p)
        return;
    mem_clear(p->lchild);
    mem_clear(p->rchild);
    delete p;
}

int main()
{
    std::priority_queue<Huffman*, std::vector<Huffman*>, cmp > Q;
    std::map<double, std::string> map_huff;
    std::ifstream fin("input.txt");
    std::string code("");
    std::ofstream fout("output.txt");

    double x;
    while (fin >> x) {
        Huffman* h = new Huffman();
        h->data = x;
        h->lchild = h->rchild = 0;
        Q.push(h);
        map_huff.insert({x, ""});
    }

    Huffman* p;
    while (Q.size() > 1) { /* 如果Q剩余结点大于1，则执行循环体 */
        p = new Huffman();
        Huffman *p1, *p2;
        p1 = Q.top(); /* 依次取出权值最小的两个结点，放入p1和p2 */
        Q.pop();
        p2 = Q.top();
        Q.pop();

        /*
        计算两结点的权值之和，存入p，且因为
        p1->data <= p2->data，可以将权值小
        的结点存入p的左子树，权值大的结点存入p
        的右子树，最后将p放入Q中
        */
        p->data = p1->data + p2->data; 
        p->lchild = p1;
        p->rchild = p2;
        Q.push(p);
    }
    
    huffman_code(p, code, map_huff); /* p就是哈夫曼树的根结点 */
    mem_clear(p);
    
    for (auto& i : map_huff) {
        fout << i.first << "\t" << i.second << std::endl;
    }

    fin.close();
    fout.close();
    return 0;
}

编译环境
g++ -std=c++11
运行结果

0x00 介绍

哈夫曼算法

哈夫曼编码过程

哈夫曼编码的应用

0x01 问题分析

0x02 代码实现