哈夫曼编码方法的选择及其Python的实现

西北民族大学电气工程学院 冯兴民

随着人们对图像和视频的压缩存储和传输的要求越来越高，如何提高传输速率和如何节省存储空间显得更加重要，解决这两个问题的最根本途径就是采用图像压缩技术。本科课程《信息论与编码》中指出图像压缩的具体实现技术就是压缩编码，通过编码可以减少信息的冗余度从而提高传输速率和节省存储空间。在音视频编解码技术快速发展的今天，其实已经有很多的编码方法。通过实际应用发现，哈夫曼编码在编码效率与平均码长方面都是较好的。本文主要研究哈夫曼编码及其Python的实现。

1 哈夫曼编码

哈夫曼编码是一种典型的无失真编码，哈夫曼编码所采用的编码原理是最佳编码定理。最佳编码定理指出，在信息编码的过程中对于信源符号，如果分配短字长的码字给出现概率小的信源符号，分配长字长的码字给出现概率大的信源符号，那么编码结束之后所得到的平均码长一定是小于其他任何一种编码方法所得到的平均码长的，也就是每个信源符号所得到的码字长度是严格按照符号概率大小的相反顺序所排列。

哈夫曼编码具体步骤如下：

（1）将n个信源符号按其概率大小进行降序排序，即：

（2）取两个概率最小的信源符号分别配以1和0两个码元，然后将这两个信源符号概率相加作为一个新符号的概率，与未分配的二进符号重新进行降序排序。

（3）对重排后的序列重复（2）过程，直到只有两个信源符号为止，再把这两个信源符号分别配以1和0即可。……