外观
4.11 哈夫曼树和哈夫曼编码
一段文字要多少位
计算机里,每个字符都要写成一串0和1。同样一段文字,用的位越少,存起来越省地方,传出去也越快。想办法少用几位,就是压缩。
本节问题把ABRACADABRA存起来,最少要多少位?
数一数。11个字符,只有5种:A出现5次,B、R各2次,C、D各1次。
定长编码。5种字符,每种要一个不同的编码。2位只有00、01、10、11四种,不够;3位有8种,够了。每个字符都用3位:A=000,B=001,R=010,C=011,D=100。开头的ABR写成9位:
11个字符,每个3位,一共11 × 3 = 33位。
定长编码的好处是解码简单:每3位一切,查一下是哪个字符就行。
常用的字用短码
A出现了5次,C、D只出现1次,可它们都占3位。要是让常用的字符用短编码、少用的用长编码,总数就能少下来。先试一个最短的方案:
一个最短的方案。A=0,B=1,剩下三个用两位:R=00,C=01,D=10。出现5次的A,每次省下2位。
可是读不回来。收到一串010。它可以读成A、B、A,也可以读成C、A,还可以读成A、D。同一串位,三种读法。
毛病出在:A的编码0,是C的编码01的开头。读到一个0时,不知道该停下来当成A,还是接着往下读。
前缀编码
要读得回来,就得避开这个毛病:任何一个字符的编码,都不是另一个字符编码的开头。这样的编码叫前缀编码。
一个前缀编码。A=00,B=01,R=10,C=110,D=111。挨个比一比:没有一个编码是另一个的开头。
读得回来。从头读,读出的几位一旦正好是某个编码,就是这个字符,接着往下读。比如0110:读到01是B,再读到10是R,不会有第二种读法。
算一算总数:A 5次 × 2位,B、R各2次 × 2位,C、D各1次 × 3位,10 + 4 + 4 + 3 + 3 = 24位。比定长编码少了9位。
前缀编码有很多种,哪一种最短?要回答它,先换个角度看前缀编码。
前缀编码就是一棵二叉树
把编码画成一棵二叉树:从根出发,读到0往左走,读到1往右走。一个编码走完,停在哪个结点,就把字符放在那里。图里每条边旁写着它代表的0或1:
画出刚才的编码。A=00是左、左;B=01是左、右;R=10是右、左;C、D多走一步。
字符都在叶子上。从根走到一个字符,路上不会经过别的字符。所以一个编码不会是另一个的开头,前缀编码的条件自动满足。
反例:字符不在叶子上。上一页失败的方案画出来,A=0在根的左孩子,C=01在A的下面。从根走到C要经过A,A的编码就成了C的开头。
反过来,任意一棵字符都在叶子上的二叉树,读出来都是前缀编码。找前缀编码,就是找这样一棵二叉树。
总长度就是带权路径长度
一个字符的编码长度,就是从根走到它要经过几条边。从根到一个结点经过的边,叫这个结点的路径;边的条数,叫路径长度。路径长度按边数算,比4.1节的层次少1:第3层的结点,路径长度是2。
一个字符出现的次数,写在它的叶子上,叫这个叶子的权。权乘以路径长度,是这个叶子的带权路径长度。所有叶子的带权路径长度加起来,叫这棵树的带权路径长度,记作WPL。
定长编码的树。每个字符的路径长度都是3。WPL = (5 + 2 + 2 + 1 + 1) × 3 = 33,正好是定长编码的总位数。
刚才的前缀编码。A、B、R的路径长度是2,C、D是3。WPL = 5 × 2 + 2 × 2 + 2 × 2 + 1 × 3 + 1 × 3 = 24。
编码的总位数,就是这棵树的WPL。要压缩得最多,就要找一棵字符都在叶子上、WPL最小的二叉树。
哈夫曼的办法:每次合并最小的两个
WPL最小的二叉树,叫哈夫曼树,也叫最优二叉树。哈夫曼想出了构造它的办法。
出现最少的两个字符,编码应该最长,放在最下面,做一对兄弟。把它们合成一个结点,这个结点的权是两个权之和。这样问题就少了一个字符,再做同样的事:
一开始。五个字符各是一棵只有根的树,权写在旁边。
合并C和D。最小的是C、D,都是1。合成一个结点,权是1 + 1 = 2。
合并B和R。现在最小的有三个2:B、R,还有刚合出来的结点。挑哪两个都可以,这里挑B和R,合出4。
合并2和4。剩下5、2、4,最小的是2和4,合出6。
合并A和6。只剩5和6,合出11。只剩一棵树了,它就是哈夫曼树。
每合并一次,就少一棵树。5个字符合并4次,只剩一棵。根的权11,正好是字符的总个数。
为什么这样合出来的WPL最小,可以严格证明,本书不展开。直觉是:越少用的字符放得越深,越常用的放得越浅。
哈夫曼编码
在哈夫曼树上,左边记0、右边记1,读出的编码叫哈夫曼编码。
读出编码。A=0,C=100,D=101,B=110,R=111。出现5次的A只用1位,只出现1次的C、D用3位。
一共23位。WPL = 5 × 1 + 2 × 3 + 2 × 3 + 1 × 3 + 1 × 3 = 23。
解码:读到B。收到的位以110开头。从根出发,1往右,1往右,0往左,走到叶子B。写下B,回到根。
解码:读到A。下一位是0,从根往左一步,就到叶子A。写下A,再回到根。
整段ABRACADABRA编成0 110 111 0 100 0 101 0 110 111 0,一共23位。
回到本节问题。定长编码33位,手排的前缀编码24位,哈夫曼编码23位。哈夫曼树的WPL最小,用它编码,总位数最少。
数一数这棵哈夫曼树:5个叶子,合并4次合出4个结点,一共9个,是2 × 5 − 1。合出来的结点都有两个孩子,没有度为1的结点。叶子5个、度为2的4个,5 = 4 + 1,正是4.6节的性质。
写成函数
教材用一个数组存整棵哈夫曼树。n个叶子放在前n格,合出来的n − 1个结点依次放在后面,一共2n − 1格。每个结点记下权、双亲、左右孩子的下标。下标从1开始,0表示"没有",所以0号格不用:
c
typedef struct {
int weight; /* 权:出现的次数 */
int parent, lchild, rchild; /* 双亲、左右孩子的下标,0表示没有 */
} HTNode;每合并一次,要挑出两个"还没有双亲、权最小"的结点。没有双亲,说明它还是一棵树的根:
c
/* 在HT[1..k]里,挑出没有双亲、权最小的两个:s1最小,s2第二小 */
void Select(HTNode HT[], int k, int *s1, int *s2) {
*s1 = 0;
for (int i = 1; i <= k; i++)
if (HT[i].parent == 0 && (*s1 == 0 || HT[i].weight < HT[*s1].weight)) *s1 = i;
*s2 = 0;
for (int i = 1; i <= k; i++)
if (HT[i].parent == 0 && i != *s1 && (*s2 == 0 || HT[i].weight < HT[*s2].weight)) *s2 = i;
}合并就是填一格:两个孩子的双亲改成它,它的孩子是这两个,权是两者之和。
c
/* n个叶子放在HT[1..n],合出来的结点依次放在HT[n+1..2n-1] */
void CreateHuffmanTree(HTNode HT[], int w[], int n) {
for (int i = 1; i <= 2 * n - 1; i++) {
HT[i].weight = i <= n ? w[i] : 0;
HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
}
for (int i = n + 1; i <= 2 * n - 1; i++) {
int s1, s2;
Select(HT, i - 1, &s1, &s2); /* 挑最小的两个 */
HT[s1].parent = HT[s2].parent = i; /* 合成第i个结点 */
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}读编码时,从叶子顺着parent往上走:自己是双亲的左孩子记0,右孩子记1,走到根为止。这样得到的位是倒着的,最后再翻过来。
完整程序算出ABRACADABRA每个字符的编码和总位数:
c
#include <stdio.h>
#define N 5 /* 字符有几种 */
typedef struct {
int weight; /* 权:出现的次数 */
int parent, lchild, rchild; /* 双亲、左右孩子的下标,0表示没有 */
} HTNode;
/* 在HT[1..k]里,挑出没有双亲、权最小的两个:s1最小,s2第二小 */
void Select(HTNode HT[], int k, int *s1, int *s2) {
*s1 = 0;
for (int i = 1; i <= k; i++)
if (HT[i].parent == 0 && (*s1 == 0 || HT[i].weight < HT[*s1].weight)) *s1 = i;
*s2 = 0;
for (int i = 1; i <= k; i++)
if (HT[i].parent == 0 && i != *s1 && (*s2 == 0 || HT[i].weight < HT[*s2].weight)) *s2 = i;
}
/* n个叶子放在HT[1..n],合出来的结点依次放在HT[n+1..2n-1] */
void CreateHuffmanTree(HTNode HT[], int w[], int n) {
for (int i = 1; i <= 2 * n - 1; i++) {
HT[i].weight = i <= n ? w[i] : 0;
HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
}
for (int i = n + 1; i <= 2 * n - 1; i++) {
int s1, s2;
Select(HT, i - 1, &s1, &s2); /* 挑最小的两个 */
HT[s1].parent = HT[s2].parent = i; /* 合成第i个结点 */
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
/* 从叶子i往上走到根,是左孩子记0、右孩子记1,倒着写进code */
void GetCode(HTNode HT[], int i, char code[]) {
char tmp[N];
int len = 0;
for (int c = i, p = HT[i].parent; p != 0; c = p, p = HT[p].parent)
tmp[len++] = HT[p].lchild == c ? '0' : '1';
for (int k = 0; k < len; k++) code[k] = tmp[len - 1 - k];
code[len] = '\0';
}
int main(void) {
char ch[N + 1] = { ' ', 'A', 'B', 'R', 'C', 'D' };
int w[N + 1] = { 0, 5, 2, 2, 1, 1 }; /* ABRACADABRA里的次数 */
HTNode HT[2 * N]; /* HT[0]不用 */
CreateHuffmanTree(HT, w, N);
int total = 0;
for (int i = 1; i <= N; i++) {
char code[N];
GetCode(HT, i, code);
printf("%c 出现%d次,编码%s\n", ch[i], w[i], code);
int len = 0;
while (code[len] != '\0') len++;
total += w[i] * len;
}
printf("总位数:%d\n", total);
return 0;
}text
A 出现5次,编码0
B 出现2次,编码110
R 出现2次,编码111
C 出现1次,编码100
D 出现1次,编码101
总位数:23Select遇到权相等时,挑下标小的那个,所以第二次合并挑的是B和R,和前一页画的一样。
练习1:算WPL
填空
4个叶子的权是1、2、3、4,构造哈夫曼树:
- 第一次合并,得到的结点权是
- 权为4的叶子,路径长度是
- 这棵哈夫曼树的WPL是
先合并1和2得3;剩下3、3、4,合并两个3得6;最后4和6合出10。权4的叶子在根下面,路径长度1;权3的是2;权1、2的是3。WPL = 4 × 1 + 3 × 2 + 1 × 3 + 2 × 3 = 19。10是根的权,不是WPL。
练习2:哪个是前缀编码
单选
下面哪一组编码是前缀编码?
A
A=0,B=10,C=11
没有一个编码是另一个的开头。
B
A=0,B=01,C=11
A的0是B的01的开头。
C
A=1,B=10,C=00
A的1是B的10的开头。
D
A=00,B=0,C=11
B的0是A的00的开头。
判断的办法:拿每个编码,看它是不是别的编码的开头。
练习3:挑别的两个合并
填空
构造ABRACADABRA的哈夫曼树时,第二次合并遇到三个2。要是挑B和C、D合出的那个结点,合成4;再把R和这个4合成6;最后A和6合成11:
- R的编码长度是
- C的编码长度是
- 总位数是
A的路径长度是1,R是2,B是3,C、D是4。总位数5 × 1 + 2 × 2 + 2 × 3 + 1 × 4 + 1 × 4 = 23,和前面那棵一样。权相等时挑法不同,树的样子不同,WPL都是最小的那个值。
到这里你有了压缩的问题:定长编码简单但浪费;变长编码要能读回来,就得是前缀编码。前缀编码就是字符都在叶子上的二叉树,左0右1;总位数就是这棵树的带权路径长度WPL。哈夫曼树是WPL最小的二叉树,构造办法是每次合并权最小的两个。n个字符的哈夫曼树有2n − 1个结点,没有度为1的结点。下一步除了根放在前、中、后,还能一层一层地走;递归也能换成自己用栈。