《算法导论》16.3 赫夫曼编码（含C++代码）

一、问题背景

1、赫夫曼算法是一种可以有效压缩数据的算法。假定我们希望压缩一个10万个字符的数据文件。图16-3给出了文件中所出现的字符和它们的出现频率。也就是说，文件中只出现了6个不同字符，其中字符a出现了45 000次。

2、我们有很多方法可以表示这个文件的信息。在这里，我们考虑一种二进制字符编码(或简
称编码)的方法，每个字符用一个唯一的二进制 串表示，称为码字。如果使用定长编码，需要用3位来表示6个字符: a=000， b=001，…，f=101。这种方法需要300 000个二进制位来编码文件。是否有更好的编码方案呢?
变长编码(variable-lengthcode)可以达到比定长编码好得多的压缩率，其思想是赋予高频字
符短码字，赋予低频字符长码字。图16-3显示了本例的一种变长编码: 1位的串0表示a，4位
的串1100表示f。因此，这种编码表示此文件共需

很明显就有所优化。
3、前缀码，即没有任何码字是其他码字的前缀，它可以保证最优的数据压缩率。将abc连接起来等同于上面图中变长码连接起来，即0101100。前缀码是没有歧义的，比如001011101解码只是aabe。
4、截取码字很容易，可以通过二叉树，0意味着转向左孩子，1意味着转向右孩子。

5、文件的最优编码方案总是对应一棵满二叉树， 即每个非叶结点都有两个孩子结点。前文给出的定长编码实例不是最优的，因为它的二叉树表示并非满二叉树，如图16-4(a)所示：它包含以10开头的码字，但不包含以11开头的码字。现在我们可以只关注满二叉树了，因此可以说，若C为字母表且所有字符的出现频率均为正数，则最优前缀码对应的树恰有|C|个叶结点，每个叶结点对应字母表中一个字符，且恰有|C|-1 个内部结点。

二、构造赫夫曼编码

在下面给出的伪代码中，我们假定C是一个n个字符的集合，而其中每个字符c∈C都是一个对象，其属性c.freq给出了字符的出现频率。算法自底向上地构造出对应最优编码的二叉树T。它从|C|个叶结点开始，执行|C|-1个“合并”操作创建出最终的二叉树。
算法使用一个以属性freq为关键字最小优先队列Q，以识别两个最低频率的对象将其合并（可以观察图16-4的b图，最末端的叶结点一定是最小的两个频率）。当合并两个对象时，得到的新对象的频率设置为原来两个对象的频率之和。

HUFFMAN(C)
n = |C|
Q = C	//用C中字符初始化最小优先队列
for i = 1 to n-1	//n-1次合并频率最小的两个元素
	allocate a new node z
	z.left = x = EXTRACT-MIN(Q)		//xy作为左右孩子顺序是任意的
	z.right = y = EXTRACT-MIN(Q)
	z.freq = x.freq + y.freq	
	INSERT(Q,z)
return EXTRACT-MIN(Q)
1
2
3
4
5
6
7
8
9
10

三、验证算法正确性（拓展一下，姑且截图）

四、C++代码

#include 
using namespace std;
#include 
#include 
//代表赫夫曼树结点的结构体
struct HTNode
{
    int weight;
    int parent;
    int lchild, rchild;
    HTNode(int val = 0) : weight(val)
    {
        parent = 0;
        lchild = -1;
        rchild = -1;
    }
};
struct Elem
{
    char ch;   //存储字符
    int frequence; //出现的频率
};

//计算每个字符出现的频率
vector<Elem> CntFrequenceOfLetter(string str)
{
    vector<Elem> InfoList; //存储字符频率信息
    if (str.size() == 0)
        return InfoList;
    sort(str.begin(), str.end());//排序字符串
    char s = str[0];
    int frequence = 0;
    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] != s)
        {
            //将统计的信息存入结构体
            Elem letter;
            letter.ch = s;
            letter.frequence = frequence;
            InfoList.push_back(letter);     //将元素存入数组中
            //开始统计下一个字符
            s = str[i];
            frequence = 1;
        }
        else
        {
            frequence++;
        }
        //如果为最后一个字符，不管是和前面一个字符相同还是不相同，都进行收尾
        if (i == str.size() - 1)
        {
            //将统计的信息存入结构体
            Elem letter;
            letter.ch = s;
            letter.frequence = frequence;
            InfoList.push_back(letter);
        }
    }
    return InfoList;
}

//从森林中选择权重最小的两棵树
void SelectTree(vector<HTNode>& T, int* s1, int* s2)
{
    int min = INT_MAX;
    //选出第一小的
    for (int i = 0; i < T.size(); i++)
    {
        if (T[i].parent == 0 && T[i].weight <= min)
        {
            min = T[i].weight;
            *s1 = i;
        }
    }
    min = INT_MAX;  //MAX为全局变量
    //选出第二小的
    for (int i = 0; i < T.size(); i++)
    {
        if (T[i].parent == 0 && T[i].weight < min && *s1 != i)
        {
            min = T[i].weight;
            *s2 = i;
        }
    }
}

//构造赫夫曼树
vector<HTNode> CrtHuffmanTree(vector<Elem> InfoList)
{
    vector<HTNode> HTNodeList(InfoList.size());
    if (HTNodeList.size() == 0) {
        return HTNodeList;
    }
    else
    {
        for (int i = 0; i < InfoList.size(); i++)
        {
            HTNodeList[i].weight = InfoList[i].frequence;
        }
        for (int j = InfoList.size(); j < 2 * InfoList.size() - 1; j++)
        {
            int s1 = 0, s2 = 0;
            //找到森林中权重最小的树
            SelectTree(HTNodeList, &s1, &s2);
            //cout << s1 << " " << s2 << endl;
            //合并成新结点
            HTNode NewNode(HTNodeList[s1].weight + HTNodeList[s2].weight);  //权重更新
            NewNode.lchild = s1;    //父子关系创建
            NewNode.rchild = s2;
            HTNodeList[s1].parent = HTNodeList.size();  //通过size确认父结点的下标，如第一次循环（6种元素），那么父结点刚好变成list[6]
            HTNodeList[s2].parent = HTNodeList.size();
            //cout <<"HTNodeList.size:" << HTNodeList.size() << endl;
            HTNodeList.push_back(NewNode);
        }
    }
    return HTNodeList;
}

//生成赫夫曼编码
void CrtHuffmanCode(vector<Elem> list1, vector<HTNode> list2)
{
    vector<int> code;
    for (auto i = 0; i < list1.size(); i++)
    {
        cout << list1[i].ch << ": ";
        auto crr = i;   //crr的作用是记录i，从而在list2先从最底层的结点开始遍历
        while (list2[crr].parent != 0)
        {
            auto parent = list2[crr].parent;    //将parent赋值为该结点的parent
            if (crr == list2[parent].lchild)
                code.push_back(0);
            else if (crr == list2[parent].rchild)
                code.push_back(1);
            crr = list2[crr].parent;    //crr更新成父结点
        }
        //反向遍历容器
        for (auto it = code.rbegin(); it != code.rend(); ++it)
        {
            cout << *it << " ";
        }
        cout << endl;
        code.clear();
    }
}

int main()
{
    string s = "AAABBBBCCCCCCCCCCDDDDDDDDEEEEEEFFFFF";// 3 4 10 8 6 5
    auto list = CntFrequenceOfLetter(s);    //先算出对应元素的频率，返回一个数组
    auto TreeList = CrtHuffmanTree(list);
    CrtHuffmanCode(list, TreeList);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153