数据结构与算法（一）

第三次翻转课堂内容：前缀码、哈夫曼树与哈夫曼编码

前缀码

术语解释

码字：变换后的各个新符号串A被称为码字。

码长：码字A的长度(符号数)La被称为码长。

码：所有码字的集合称为“码”。

概念

一种编码系统，通常长度可变，其中的元素成为“码字”，并且每个码字都不可作为后面的码字的前缀

譬如，{592,431}可以是前置码，而{1,0,10}不是，因为1、0是10的前缀，换言之，10中同时包含了1和0。同理，{1,0,10,11}也不是，但是{11,00,01,10}是前缀码，因为相互之间没有冲突。

哈夫曼树

哈夫曼树首先是复数颗二叉树组成的集合，我们先定义一个输入的字符串：

this is an example of a huffman tree

不难统计出来：这个字符串有 4 个'a'， 4 个'e'， 3 个'f'， 2 个'h'， 2 个'i'， 1 个'l'， 2 个'm'， 2 个'n'， 1 个'o'， 1 个'p'， 1 个'r'， 2 个's'， 1 个't'， 1 个'u'， 1 个'x'， 7 个'\0'。

这句话中一共出现了 16 种字符，所以这句话可以组成一个这样的前缀码：

{a,e,f,h,i,l,m,n,o,p,r,s,t,u,x,\0}

现在，选取权重最小，也就是出现次数最少的两个字母组成数颗二叉树，其他的字母不断向上递归，挂靠到这些节点的母节点，直到合并为一颗完整的二叉树或者非标准二叉树

此时变成了这个样子（为了方便辨识，一层为一行）：

[
36,
16,20,
8,8,8,12,
'e',4,'a',4,4,4,5,'\0',
NULL,NULL,'n',2,,NULL,NULL,'t','m','i',2,'h','s',2,'f',NULL,NULL,
NULL,NULL,NULL,NULL,NULL,NULL,'o','u',NULL,NULL,NULL,NULL,NULL,NULL,'x','p',NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,'r','l',NULL,NULL,NULL,NULL,NULL,NULL
]

数字则是该节点下所有字母出现频率之和，NULL 表示空节点。

树造好了，但是字母用什么表示呢？毕竟树里面是不能同时存下字符和数字的。因此，哈弗曼创造了哈夫曼编码。

哈弗曼编码

我们知道前缀码中的码字不能存在前缀，同时二叉树有两个子元素。所以哈弗曼规定：树的左分支为 0 ，右分支为 1 ，根节点到每个叶结点所经过的路径组成的 0 、1 序列即为该叶结点对应字符的编码。

理论很空洞，拿上面的例子来解释：

[
36,
16,20,
8,8,8,12,
'e',4,'a',4,4,4,5,'\0',
NULL,NULL,'n',2,,NULL,NULL,'t','m','i',2,'h','s',2,'f',NULL,NULL,
NULL,NULL,NULL,NULL,NULL,NULL,'o','u',NULL,NULL,NULL,NULL,NULL,NULL,'x','p',NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,'r','l',NULL,NULL,NULL,NULL,NULL,NULL
]

把数组转化为树，我们知道字母'e'是根节点的左节点的左节点的左节点，根节点不表示，那么根据定义，“左节点的左节点的左节点”就是000。

那同理，'l'是根节点的右节点的右节点的左节点的左节点的右节点，它的哈弗曼编码就是11001。

通过这种方式，我们可以获得一个表：

字符	编码	字符	编码
a	010	e	000
f	1101	h	1010
i	1000	l	11001
m	0111	n	0010
o	00110	p	10011
r	11001	s	1011
t	0110	u	00111
x	10010	\0	111

这是我们最初的前缀码：

{a,e,f,h,i,l,m,n,o,p,r,s,t,u,x,\0}

把编码代入得到：

{010,000,1101,1010,1000,11001,0111,0010,00110,10011,11001,1011,0110,00111,10010,111}

如此这般，我们形成的对应关系可以将最初的字符串this is an example of a huffman tree转换为编码，能得到：

//每个字符间一个空格，\0为 111
0110 1010 1000 1011 111 1000 1011 111 010 0010 111 000 10010 010 0111 10011 11001 000 111 00110 1101 111 010 111 1010 00111 1101 1101 0111 010 0010 111 0110 11001 000 000
//无空格的版本
011010101000101111110001011111010001011100010010010011110011110010001110011011011110101111010001111101110101110100010111011011001000000

如果计算机需要翻译，那它会进行这样的操作：

读取一个 0/1 并查找表中是否有对应的内容，如果没有找到，就会再纳入一个 0/1 ，并重复查找，直到出现对应的字符。

作用到例子中就是这个流程：

读取 0 ，此时为 0 ，没有结果
读取 1 ，此时为 01 ,没有结果
读取 1 ，此时为 011 ，没有结果
读取 0 ，此时为 0110 ，查询到字符't'，输出结果并清空当前存储的所有 0/1

如此往复，直到所有的字符都被解析

平均编码长度

首先是公式 $$ L(x) = \log_{2}(\frac{1}{p(x)}) $$

$$ H(p) = \sum{x} p(x) \log{2}(\frac{1}{p(x)}) $$

其中，L(x) 为字符所需要的二进制位数，p(x) 为字符'X'出现的概率，H(p) 为平均编码长度

我们回到上面的表：

字符	编码	字符	编码
a	010	e	000
f	1101	h	1010
i	1000	l	11001
m	0111	n	0010
o	00110	p	10011
r	11001	s	1011
t	0110	u	00111
x	10010	\0	111

尽管表是按照字母顺序编排的，但也许有人注意到了：出现次数最多的字符拥有最短的编码，这样的结果便是编码长度得到了大幅度的缩短。

参考来源

wikipedia——霍夫曼编码

oiwiki——霍夫曼树

CelestialCosmic / themeblog