一. 哈夫曼编码

1. 哈夫曼编码思想

哈夫曼编码思想: 对于更高频的符号，使用更短的编码。这样在对整个信息进行编码时，就可以进行大幅度压缩。

比如一段英文字符: AABABCABAB, A出现了5次， B出现了4次， C出现1次。

如果我们使用定长编码来进行信息编码，那么每个符号至少需要2个bit来表示:

A: 01, B: 10, C: 11

那么字符的编码长度就是: 5*2 + 4*2 + 1*2 = 20 bit

但如果采用哈夫曼编码，对于出现频次更好的A，可以使用更短的编码。这里通过构造哈夫曼树来生成码字：

image.png

A: 0, B: 10, C:11

整段字符的编码长度为: 5*1 + 4 *2 + 1*2 = 15 bit

可以看见采用哈夫曼编码后，有效的对信息进行了压缩。

2. 哈夫曼编码不足

哈夫曼编码确实可以对数据进行压缩，但无法逼近香农定理的熵极限.

信道的香农极限指的是在会随机发生误码的信道上进行无差错传输的最大传输速率。它的存在是香农定理在带宽有限的信道上的一个结论。

对于上面提出的【A出现5次，B出现4次，C出现1次】这种情况，每种符号出现的概率如下:

P(A) = 0.5; P(B) = 0.4; P(c) = 0.1

按照香农的熵计算公式，整个信息熵应该是:

image.png

H(X) = -( 0.5 * log2(0.5) + 0.4 * log2(0.4) + 0.1 * log2(0.1) ) = 1.361

也就是这段字符的压缩极限为,平均每个符号用1.361个bit来表示。整段字符一个10个字母，压缩极限是10*1.361=13.61个bit，约等于14个bit。而采用哈夫曼编码只能压缩到15个bit。

为什么会这样，是因为哈夫曼编码采用整数进行符号编码，不够精准，比如B和A，它们出现的概率分别为0.4和0.1，但是对于它们，哈夫曼却采用了相同的编码。

为什么B，不采用1表示，而是采用10表示，也就是A:0, B: 1, C: 10，这样整段字符的编码长度不就是51 + 41 + 1*2 = 11 bit，可变字长编码VLC的其中一个性质就是: 前缀性质， 也就是任何字符，都不能成为其他字符的前缀子集，按照上面的编码，B就成了C的前缀子集，解码的时候，遇到1010的序列，就无法判断第一个字符到底是B还是C，解码就具有二义性。

二. 算术编码

1. 算术编码过程

算术编码的本质思想也是对于高频字符进行短编码。

对于上面这段字符: AABABCABAB

P(A) = 0.5, P(B) = 0.4, P(C) = 0.1

那么算术编码会对0-1进行区间划分:

A: [0, 0.5], B:[0.5, 0.9], C:[0.9, 1]

AABABCABAB的第1个字符为: A， 那么我们选中了A的区间[0, 0.5]作为新的目标区间。

我们对新目标区间，再按照ABC的概率占比进行划分。

A:[0, 0.25], B: [0.25, 0.45], C:[0.45, 0.5]

AABABCABAB的第2个字符仍然是:A，那么我们再选中A的区间[0, 0.25]作为新的目标区间。

我们对新的目标区间，再按照ABC的概率占比进行划分。

A:[0, 0.125], B:[0.125, 0.225], C:[0.225, 0.25]

AABABCABAB的第3个字符是: B, 这次我们选中的是B的区间[0.125, 0.225]作为新的目标区间。

我们对新的目标区间，再按照ABC的概率占比进行划分.

A:[0.125, 0.175], B: [0.175, 0.215], C:[0.215, 0.225]

AABABCABAB的第4个字符是: A, 那么我们再选中A的区间[0.125, 0.175]作为新的目标区间。

我们重复上面的操作，一直到最后的一个字符:

image.png

完成上面的操作后，最终的目标区间为: [0.1686, 0.16868],我们在这个区间内，任意选一个小数，便可以作为最终的编码小数，但是计算机只能识别0和1，所以我们再将小数转成二进制。

我们的诉求是进行最短压缩，所以我们要从[0.1686, 0.16868]选一个二进制表示最短的小数。这里我们选定0.16864， 二进制为:0.00101011001011,去掉整数位0以及小数点后，最终的二进制编码为00101011001011bit长度为14位，比哈夫曼编码要更1位。

2. 算术解码过程

理解算术编码过程，解码过程相对也容易理解，比如上面最终二进制编码为00101011001011, 加上小数点后还原为0.00101011001011，对应的十进制编码小数是0.16864013671875。

我们从初始区间中定位第一个字符:

A: [0, 0.5), B: [0.5, 0.9), C: [0.9, 1)

0.16864013671875位于A区间，所以第一个字符为A， 我们接着对A: [0, 0.5)再进行划分。

A: [0, 0.25), B:[0.25, 0.45), C:[0.45, 0.5)

0.16864013671875仍然位于A区间，所以第二个字符仍然为A。我们接着对A: [0, 0.25)再进行划分.

A: [0, 0.125), B:[0.125, 0.225), C:[0.225, 0.25)

0.16864013671875位于B区间，所以第三个字符为B

依此类推，就可以将整个字符解码出来。

3. 算术编码为什么可以压缩数据

算术编码的压缩本质，就是保留字符排列顺序的同时，对于更高频出现的字符，也就是概率更大，赋予更大的小数区间。

为什么要这样划分区间呢？因为算术编码的目的，是要在最终的目标区间内，找一个二进制最短的小数作为最终编码。

那怎么去找到这样一个目标区间呢？最终目标区间的范围更大，可容纳的小数精度就越低，意味着我们最终的二进制编码就更短。比如在低精度的[0.1, 0.2)和高精度的[0.1111111111, 0.1111111112)之间各找一个最短编码的二进制进行比较，肯定是在[0.1, 0.2)中找到的最短二进制编码更短。

所以算术编码的实现途径就是: 尽量使最终目标区间的范围更大。

三. 总结

通过上面的例子，我们就清楚了算术编码的原理:

1. 为了使最终二进制编码更短，就需要使得最终目标区间的范围更大。

2. 为了使最终目标区间范围更大，就需要赋予高频字符更大的区间，底部字符更小的区间。