这是第一次在CSDN上写blog，想写很久了，一直因为忙耽搁了，放假了，打算整理一下这学期的一些代码和实验写blog。 本文主要根据我信息论课程的信源编码大作业报告所写，相关代码放在我的GitHub上，初次在CSDN发blog，小小紧张哈哈哈。

本文主要实现了哈夫曼编码，且性能较为优秀。另外还拓展实现了LZ编码和算数编码，并在将哈夫曼和LZ-78两种编码方式的cpp文件通过统一的main.cpp文件整合在一起，可以通过运行project来选择希望的编码方式对目标文件进行编码。

另外，本文的实验中，也出现了一些编译器的问题，例如Visual Studio下和Mac下存在着一定的优劣对比。

本文中给出了一些实现的部分代码，完整代码见GitHub： https://github.com/YZ-WANG/Three-methods-for-source-encoding

本文的实验实现了三种编码方式：哈夫曼编码、LZ编码和算数编码。下面分析其各自基本原理。

哈夫曼编码是是一种可变长的分组编码，完全依据各字符出现的概率来构造码字。二进制的哈夫曼编码是基于二叉树的编码思想，所有可能的输入符号在哈夫曼树上对应为一个节点，结点的位置就是该符号的哈夫曼编码。为了构造出唯一可译码，这些节点都是哈夫曼树上的终极结点（即叶子结点），不再延伸，不会出现前缀码。具体编码方法如下：

特别地，有时为了得到最短平均码长，尽量减少赋长码的信源符号，需要在编码前对信源符号作添加，使得信源的符号数量满足 M(N-1)+1，其中M为正整数，N为进制，这样在多次合并后就能充分利用短码，以便降低平均码长。

此外，哈夫曼编码方法所得到的码并非是唯一的，造成非唯一的原因如下：

哈夫曼编码的特点：

哈夫曼码的编码效率是非常高的，它可以单个信源符号编码或用L较小的信源序列编码，对编码器的设计来说也将简单得多。但是应当注意，要达到很高的效率仍然需要按长序列来计算，这样才能使平均码字长度降低。 哈夫曼编码的解码则在识别出一个个叶子结点后按照叶子结点对应的原信源符号译码。

哈夫曼编码虽然效率出众，但仍然存在一些分组码所具有但缺点。例如概率特性必须精确测定，以此来编织码表，若略有变化，还需要更换码表。故实际编码过程中需要对原始数据扫描两遍，第一遍用来统计原始数据中各字符出现的概率，创建码表存放起来，第二遍则依据码表在扫描的同时进行编码，才能传输信息。如果将这种编码放在网络通信中，两遍扫描会引起较大的时延；如果用于数据压缩，则会降低速度。因此，出现了自适应哈夫曼编码方法，其码表不是实现构造，而是随着编码的进行，不断动态构造、调整。

由于在使用分组码对信源单符号进行编码时，没有将符号间的相关性纳入考虑之中：若将m个符号合起来进行编码则会增加设备复杂度，且组间符号的相关性还是无法纳入考虑。这就使得信源编码的匹配原则不能充分满足，编码效率有所损失。

为了克服这种局限性，一种基于非分组码的编码方法——算数编码应运而生。编码的基本思路是：将需要编码的全部数据看成某一 L L L 长序列，所有可能出现的L长序列的概率映射到 [ 0 , 1 ] [0,1] [0,1] 的区间上，把 [ 0 , 1 ] [0,1] [0,1] 区间分成许多小段，每段长度等于某一序列的概率。再在段内取一个二进制小数用作码字，其长度可与该序列的概率匹配，达到高效率编码的目的。

算数编码实际的编译码过程比较复杂，但在性能上具有许多优点，特别是所需要的参数很少，不像哈夫曼编码那样需要一个很大的码表。从理论上说，只要已知信源符号集及其符号概率，算数编码的平均码长可以接近符号熵。

具体编码方法如下：

LZ编码是由以色列研究者齐夫和伦佩尔完全脱离哈夫曼码和算术编码的设计思路，设计出的一系列比哈夫曼编码更有效、比算术编码更快捷的通用压缩算法。将这些算法统称为LZ系列算法。LZ系列算法利用一种巧妙的方式将字典技术应用于通用数据压缩领域，而且，可以从理论上证明LZ系列算法同样可以逼近信息熵的极限。

实验采用的 LZ-78编码 的编码过程如下：