郑合乐、汪骏杰、纪震、王峥、蒋俊杰——香农码、哈夫曼码、算数编码的比较

香农码、哈夫曼码、算数编码的比较"/>

郑合乐、汪骏杰、纪震、王峥、蒋俊杰——香农码、哈夫曼码、算数编码的比较

香农码、哈夫曼码、算数编码的比较

1.香农码

1.1概念：香农编码是是采用信源符号的累计概率分布函数来分配字码的。香农编码是根据香农第一定理直接得出的，指出了平均码长与信息之间的关系，同时也指出了可以通过编码使平均码长达到极限值。香农第一定理是将原始信源符号转化为新的码符号，使码符号尽量服从等概分布，从而每个码符号所携带的信息量达到最大，进而可以用尽量少的码符号传输信源信息。
1.2编码过程：二分法香农-范诺编码方法的步骤如下：
(1)将信源符号按照其出现概率从大到小排序；
(2)从这个概率集合中的某个位置将其分为两个子集合，并尽量使两个子集合的概率和近似相等，给前面一个子集合赋值为0，后面一个子集合赋值为1；
(3)重复步骤(2)，直到各个子集合中只有一个元素为止；
(4)将每个元素所属的子集合的值依次串起来，即可得到各个元素的香农编码。
其香农编码如表所示
平均码长＝1.946
编码效率=1.21
香农编码的效率不高，实用性不大，但对其他编码方法有很好的理论指导意义。一般情况下，按照香农编码方法编出来的码，其平均码长不是最短的，即不是紧致码(最佳码)。只有当信源符号的概率分布使不等式左边的等号成立时，编码效率才达到最高。

2.哈夫曼码

2.1概念:我们都知道使用电报来传递信息在上个世纪来说是很自然的，但是由于技术问题，使得远距离通信的数据传输效率显得极其重要，美国数学家哈夫曼研究出哈夫曼编码能够使得数据传输得到优化。例如我现在要传递信息 “ABBCCCDDDDEEEEE”，如果利用二进制编码来实现的话，就是传递“000 001 001 010 010 010 011 011 011 011 100 100 100 100 100”，有 45 个字符，但是我们观察到这个编码中有 5 个字母，每个字母出现的频率都不一样，这时我们就开始思考了，如果我们用一些其他的编码去组织这 5 种字符，让出现次数较多的字母用简单的代号去表示，这样会不会使得传递较少的数据，传达同样多的消息呢？

如图所示，我们拥有了这么一棵二叉树，我们发现这棵二叉树在两个结点间有个数字，我们用这些数字的组合来构造新密码。

那么“ABBCCCDDDDEEEEE”编码的结果就是“101 100 100 00 00 00 11 11 11 11 01 01 01 01 01”共 33 个字符，相比原来的 45 个字符而言已经有不小的进步了。那么你可能要问了，这么做读取的信息会不会出现二义性呢？答案是不会的，例如我收到了“011100100101”这个编码，你对照上文的二叉树，按照编码顺序从根结点向下解读，读取的结果是“EDCBA”，没有二义性。
这种巧妙的方法就是哈夫曼编码，而我们用来解密的二叉树就被成为哈夫曼树。与编码对应的哈夫曼编码生成的方式是，获取需要编码的字符集，将各个字符在数据中出现的次数整合为一个集合，以字符集作为叶子结点，以对应的频率作为相应叶子结点的权值来构造一棵二叉树，二叉树树的左分支代表 0，右分支代表 1，则从根结点到叶子结点所经过的路径分支组成的 0 和 1 的序列便为该结点应字符的哈夫曼编码。
2.1编码过程:使用需要传送的字符构造字符集C = {c1, c2, … cn}，并根据字符出现的频率构建概率集W = {w1, w2, … wn}。哈夫曼编码的流程如下：
1.将字符集C作为叶子节点；
2.将频率集W作为叶子节点的权值；
3.使用C和W构造哈夫曼树；
4.对哈夫曼树的所有分支，左子树分支编码为0，右子树分支编码为1；
通过上述流程，即完成了哈夫曼编码。
如：首先，设定字符集为C = {T1, T2, T3, T4}，对应的频率集为W = {2, 3, 7, 5}，可以构造出下面的哈夫曼树

构造出哈夫曼树后，只需要将左子树分支编码为0，右子树分支编码为1，即可获得哈夫曼编码如下：

哈夫曼编码示例 ：
编码效率：先求出其平均码长K=先算出平均码字长度K=∑P(ai)*Ki
再可计算其编码效率为η=H（X）/K
如上图中表5-5中
可以算得K=P（x1）*1+P（x2）*2+……+P(x5)*4=2.2
H(X)为提前算出，然后计算η=H（X）/K即可
优点:(1)压缩率高:哈夫曼编码可以在保证编码和解码的正确性的同时，提供较高的压缩率;
(2)解码速度快: 哈夫曼编码的解码过程相对简单，解码速度快;
(3)适用于各种数据: 哈夫曼编码适用于各种类型的数据，包括文本、图像、音频等。
缺点:
(1)压缩和解压缩需要较多的时间: 哈夫曼编码的压缩和解压缩过程相对复杂，需要较多的时间;
(2)不适用于实时数据传输: 由于哈夫曼编码压缩和解压缩的时间较长，不适用于实时数据传输;
(3)不适用于小文件: 哈夫曼编码的压缩效果并不明显，当文件较小时，压缩后的文件可能比原文件还大。

3算数编码

3.1概念：算术编码是图像压缩的主要算法之一。 是一种无损数据压缩方法，也是一种熵编码的方法。算术码即为其中之一，编码的基本思路是，将需要编码的全部数据看成某一L长序列，所有可能出现的L长序列的概率映射到[0，1]区间上，把[0，1]区间分成许多小段，每段的长度等于某一序列的概率。再在段内取一个二进制小数用作码字，其长度可与该序列的概率匹配，达到高效率编码的目的。
3.2编码过程:（1）按照各信源信号好出现的频率，将[0, 1)这个区间分成若干段，每个信号源就会有对应的区间；
（2）将[0, 1)这个区间设置为初始间隔；
（3）按照待处理的信号，一个一个信号源读入，每读入一个信号，就将该信号源在[0, 1)上的范围等比例的缩小到最新得到的间隔中；
（4）依次迭代，不断重复进行步骤3，直到最后信号中的信源信号全部读完为止。
例如：由A、B、C三个符号构成的序列S=AABABCABAB，那么各符号对应的概率为：

算术编码会对[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)
依此类推，重复上面的步骤，直到最后一个字符。
最后按照上述步骤绘制出一张表格：

最终的目标区间为：[0.1686,0.16868)，在这个区间内，任意选一个小数，便可以作为最终的编码小数，为了进行最短压缩，要从 [0.1686, 0.16868) 选一个二进制表示最短的小数。最终选定：0.16864013671875，二进制为：0.00101011001011，去掉整数位 0 以及小数点后，最终的二进制编码为 00101011001011，长度为14。
计算编码效率：

算出平均码长为

该信源的熵为:

编码效率为:

这种编码方法与香农编码法有点类似，只是它们考虑的信源序列对象不同，算术码中的信源序列长度要长得多，或许是欲编码的整个数据文件，而香农码中的序列长度是1。
为了使最终二进制编码更短，就需要使得最终目标区间的范围更大。同时为了使最终目标区间的范围更大，就需要赋予高频字符更大的区间，低频字符更小的区间。