自己来写压缩算法——哈夫曼算法
一般文件的编码都是等长的，一些常用字符的编码与很少用到的等长，可若是编码是变长的呢？无疑可以使整个文件大小减小。为了解码时不遇到任何歧义的问题，则每个有效字符所代表的变长编码不能是其它字符的前缀，这种编码也叫做前缀编码。而如何做到这一点呢，接下的内容会尽可能地讲明白。
哈夫曼算法
若是把等长的编码(一字节)用平衡二叉树来表示，字符共有256个，那么树的深度就有 $\log_{2}{256}=8$ 。
如果变作变长编码，那么所有有儿子（child）的节点（node）都不能用来表示，唯有子叶（leaf，没有儿子的节点）才可以用来表示。这是因为每个有效字符所代表的变长编码不能是其它字符的前缀。而且树结构也不可能是平衡二叉树了，树的深度肯定会大于8。
例如，有一份MIT-LICENCE.txt文件，其中空格' '有163个，而字母'v'却只有一个。那么让' '表示为110,'v'表示为0111011101，那么得省$(8 - 3) \times 163 - (8 - 10) \times 1 = 817$个bit。可见变长编码确确实实能起到压缩的作用。
哈夫曼树
哈夫曼树Huffman Tree，也叫做最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为$0$层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为$\operatorname{WPL}=(W_1 \times L_ 1+W_2 \times L_2+W_3 \times L_3+…+W_n \times L_n)$，$N$个权值$W_i(i=1,2,…n)$构成一棵有$N$个叶结点的二叉树，相应的叶结点的路径长度为$L_i(i=1,2,…n)$。可以证明霍夫曼树的$\operatorname{WPL}$是最小的。
/-40 /-40 /-40
/-| /-| /-|
| \-48 | \-48 | | /-48
--| | | \-|
| /-60 --| /-60 --| \-18
\-| | /-| |
| /-30 | | \-20 | /-60
\-| \-| | /-|
| /-18 | /-30 \-| \-20
\-| \-| |
\-20 \-18 \-30
(0) (1) (2)计算上面三颗树的$\operatorname{WPL}$：
(0) $ 18 \times 3 + 20 \times 3 + 30 \times 2 + 60 \times 1 + 48 \times 1 + 40 \times 1 = 286$
(1) $ 18 \times 2 + 30 \times 2 + 20 \times 2 + 60 \times 2 + 48 \times 1 + 40 \times 1 = 344$
(2) $ 20 \times 2 + 60 \times 2 + 18 \times 2 + 48 \times 2 + 30 \times 1 + 40 \times 1 = 362$
可以看出同样的子叶，构造出来的树(0)的$\operatorname{WPL}$最小。 其实它就是哈夫曼树，可以验证同样的子叶,构造出来树的$\operatorname{WPL}$没有比这更小的了(可以同$\operatorname{WPL}$不同构)。
结论: 权值越大的子叶离根节点越近，即路径长度越短；反之，权值越小的子叶离根节点越远，即路径长度越长。
构造哈夫曼树的算法步骤下：
- 将所有的要添加到哈夫曼树的子叶按从小达到排列
- 找出两个权值最小的节点，拼接成一树结构，父节点的权值为二者之和
父节点为新的节点，加入排列中，重复步骤2
1 /-1 /-3 3 | /-| 2 \-2 /-3 /-3 | | /-1 6 | /-1 6 | /-1 | \-| 3 3 \-| \-| --| \-2 \-2 \-2 | 4 4 4 /-4 | /-4 9 | \-| 5 5 5 \-5 \-5 (0) (1) (2) (3) (4)
哈夫曼编码
从根结点开始，左子树为'0',右子树为'1'，累积到子叶得到的编码就是哈夫曼编码。
| leaf | code |
|------|------|
| 1 | 010 |
| 2 | 011 |
| 3 | 00 |
| 4 | 10 |
| 5 | 11 |哈夫曼编码MIT-LICENCE文件结果
| byte | count | code | | byte | count | code | | byte | count | code |
|------|-------|------------| |------|-------|------------| |------|-------|------------|
| '/' | 1 | 0111011010 | | 'j' | 1 | 0111011011 | | ':' | 1 | 0111011100 |
| 'v' | 1 | 0111011101 | | 'K' | 1 | 0111011110 | | 'X' | 1 | 0111011111 |
| '(' | 2 | 011101000 | | ')' | 2 | 011101001 | | '<' | 2 | 011101010 |
| '>' | 2 | 011101011 | | 'V' | 2 | 011101100 | | '.' | 3 | 01101100 |
| '"' | 4 | 01101101 | | 'B' | 5 | 11110100 | | 'Y' | 6 | 11110101 |
| 'G' | 6 | 0011110 | | '\r' | 7 | 0011111 | | '\n' | 7 | 0100110 |
| 'M' | 7 | 0100111 | | 'P' | 8 | 0110111 | | 'm' | 8 | 0111000 |
| 'U' | 8 | 0111001 | | 'y' | 9 | 1011000 | | 'b' | 9 | 1011001 |
| 'W' | 9 | 1011010 | | 'g' | 10 | 1011011 | | 'w' | 10 | 1110000 |
| 'D' | 10 | 1110001 | | 'C' | 12 | 1111011 | | 'u' | 12 | 000100 |
| 'F' | 12 | 000101 | | 'p' | 13 | 001110 | | 'L' | 14 | 010010 |
| 'f' | 15 | 011010 | | 'c' | 17 | 100010 | | 'l' | 17 | 100011 |
| 'd' | 17 | 101000 | | 'H' | 18 | 101001 | | ',' | 22 | 111001 |
| 'h' | 23 | 111100 | | 'S' | 25 | 00011 | | 'a' | 26 | 00110 |
| 'A' | 28 | 01000 | | 'r' | 29 | 01010 | | 'n' | 30 | 01011 |
| 'N' | 30 | 01100 | | 's' | 34 | 01111 | | 'R' | 34 | 10000 |
| 'E' | 35 | 10010 | | 'I' | 35 | 10011 | | 'O' | 36 | 10101 |
| 'T' | 39 | 10111 | | 'i' | 45 | 11101 | | 'e' | 48 | 11111 |
| 't' | 49 | 0000 | | 'o' | 52 | 0010 | | ' ' | 163 | 110 | /----'t' 49 0000
|
/----0 /----'u' 12 000100
| | /----0
| \----1 \----'F' 12 000101
/----0 |
| | \----'S' 25 00011
| |
| | /----'o' 52 0010
| \----1
| | /----'a' 26 00110
| \----1
| | /----'p' 13 001110
| \----1
| | /----'G' 6 0011110
| \----1
| \----'\r' 7 0011111
|
| /----'A' 28 01000
/----0 /----0
| | | | /----'L' 14 010010
| | | \----1
| | | | /----'\n' 7 0100110
| | /----0 \----1
| | | | \----'M' 7 0100111
| | | |
| | | | /----'r' 29 01010
| | | \----1
| | | \----'n' 30 01011
| | |
| | | /----'N' 30 01100
| | | |
| | | /----0 /----'f' 15 011010
| \----1 | | |
| | | \----1 /----'.' 3 01101100
| | | | /----0
| | | \----1 \----'"' 4 01101101
| | | |
| | | \----'P' 8 0110111
| | |
| | | /----'m' 8 0111000
| | | /----0
| | | | \----'U' 8 0111001
| | | |
| \----1 | /----'(' 2 011101000
| | | /----0
| | /----0 | \----')' 2 011101001
| | | | /----0
| | | | | | /----'<' 2 011101010
| | | | | \----1
| | | | | \----'>' 2 011101011
| | | | |
| | | \----1 /----'V' 2 011101100
--| | | | /----0
| | | | | | /----'/' 1 0111011010
| | | | | \----1
| \----1 | | \----'j' 1 0111011011
| | \----1
| | | /----':' 1 0111011100
| | | /----0
| | | | \----'v' 1 0111011101
| | \----1
| | | /----'K' 1 0111011110
| | \----1
| | \----'X' 1 0111011111
| |
| \----'s' 34 01111
|
| /----'R' 34 10000
| /----0
| | | /----'c' 17 100010
| | \----1
| /----0 \----'l' 17 100011
| | |
| | | /----'E' 35 10010
| | \----1
| | \----'I' 35 10011
| |
| /----0 /----'d' 17 101000
| | | /----0
| | | /----0 \----'H' 18 101001
| | | | |
| | | | \----'O' 36 10101
| | | |
| | \----1 /----'y' 9 1011000
| | | /----0
| | | | \----'b' 9 1011001
| | | /----0
\----1 | | | /----'W' 9 1011010
| \----1 \----1
| | \----'g' 10 1011011
| |
| \----'T' 39 10111
|
| /----' ' 163 110
| |
| | /----'w' 10 1110000
| | /----0
| | /----0 \----'D' 10 1110001
\----1 | |
| /----0 \----',' 22 111001
| | |
| | \----'i' 45 11101
| |
\----1 /----'h' 23 111100
| |
| /----0 /----'B' 5 11110100
| | | /----0
| | \----1 \----'Y' 6 11110101
\----1 |
| \----'C' 12 1111011
|
\----'e' 48 11111压缩实现
知道了如何编码，那怎么应用到压缩上去呢？
压缩
- 把文件分割成一个个字节，统计各个字节（总共256个）的数量
- 根据统计出来的权重，来构造哈夫曼树，得出哈夫曼编码
- 一字节一字节的转换为哈夫曼编码，再保存到新的文件（压缩文件）里
- 再把统计的结果，也存储到文件里，用来解压缩
注意：转换后数据不一定能被8整除，那么保存的结尾就要稍作处理
原文：
b'Copyr……转换：
| b'C' | b'o' | b'p' | b'y' | b'r' | ... |
|---------|------|--------|---------|-------|-----|
| 1111011 | 0010 | 001110 | 1011000 | 01010 | ... |
11110110010001110101100001010……分割成字节：
| 1111 0110 | 0100 0111 | 0101 1000 | 0101 0…… |
|-----------|-----------|-----------|----------|
| 246 | 71 | 88 | …… |
| b'\xf6' | b'G' | b'X' | …… |压缩结果：
b'\xf6GX……这么短短的一段，从5字节压缩成3.6+字节大小
解压
- 读取压缩文件中的统计结果，构造哈夫曼树
- 一比特一比特的用哈夫曼树索引，得到原本的字节，再保存到新文件中
压缩文件字节流：
b'\xf6GX……得到比特流：
| b'\xf6' | b'G' | b'X' | …… |
|-----------|-----------|-----------|----------|
| 246 | 71 | 88 | …… |
| 1111 0110 | 0100 0111 | 0101 1000 | 0101 0…… |根据哈夫曼树，索引出对应的值，'0'进入左子树，'1'进入右子树，直到子叶……
11110110010001110101100001010……
| 1111011 | 0010 | 001110 | 1011000 | 01010 | ... |
|---------|------|--------|---------|-------|-----|
| b'C' | b'o' | b'p' | b'y' | b'r' | ... |原文：
b'Copyr……尾部处理
若结尾出现以下情况
结尾长度小于一字节
压缩 解压 | 0010 | | b'\x02' | |---------| |----------| | 2 | | 2 | | b'\x02' | | 00000010 |结尾长度等于一字节
压缩 解压 | 00000010 | | b'\x02' | |----------| |----------| | 2 | | 2 | | b'\x02' | | 00000010 |
为了避免尾部可能出现的错误，所以将对尾部进行处理：在尾部写入之前，写入尾部的长度数据
压缩 解压
| 0010 | | b'\x04\x02' |
|-------------| |--------------|
| 2 | | 2 |
| b'\x04\x02' | | 0010 |
压缩 解压
| 00000010 | | b'\x08\x02' |
|-------------| |--------------|
| 2 | | 2 |
| b'\x08\x02' | | 00000010 |存储字节统计结果
字符（一字节）字节，字符以一字节来存，最多有256个字符。 还要存储出现次数的字节长度，用来读取。
| for | value | bytes |
|----------------------|---------------|---------------------|
| charNum | 256 - 1 (max) | b'\xff' |
| Count's bytes length | 4 | b'\x04 |
| char | 0 | b'\x00' |
| char Count | 255 | b'\x00\x00\x00\xff' |
| char | 1 | b'\x01' |
| ... | ... | ... |
b'\xff\x04\x00\x00\x00\x00\xff\x01...测试
拿MIT-LICENCE.txt文件来测试：
| before | after |
|-------------|-----------|
| 1,072 bytes | 859 bytes |代码
GIST: Huffman Encoding and Data Compression | linw1995
参考
- 霍夫曼编码 | Wikipedia
- Magnus Lie Hetland.(2015).哈夫曼算法.In Python算法教程,pages 159-164.
