霍夫曼编码及其改进
在通信中，为了提高信息传输效率，得到或接近信息熵的最小信息率，我们需要解决信源编码的问题。

在信源编码中，我们试图让信源编码的平均码长尽可能缩短，减少冗余度,从而提高编码效率。

信源编码又分为无失真信源编码和限失真信源编码。

哈夫曼编码(Huffman Coding)是一种无失真编码方式，是可变字长编码(VLC)的一种，由Huffman于1952年提出，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。

哈夫曼编码是一种最优的前缀编码技术。

对于多元独立信源，哈夫曼编码为最佳编码，之所以称之为最佳编码，因为其拥有以下特性：(1) 保证概率大的对应短码，概率小的对应长码，即短码得到充分利用；(2) 每次缩减信源的最后两个码字，总是最后面的一个码元不同，而前面的各个码元相同；(3) 每次缩减信源的最长两个码字有相同的码长。

平均码长n=2×10+8
38+3×7+6+3
38
+4×2
38
+5×1+1
38
=2.68
冗余度
哈夫曼编码是一种非唯一性编码，其编码方式并不唯一。

首先，因为对缩减信源最后两个概率小的符号用0和1码的赋予可以是任意的，故可以得到不同的码，但是它们只是码的具体形式不同。

其码长n不变，平均码长ñ也不变，所以没有本质区别。

其次，若当缩减信源中合并后的符号概率与其他信源符号概率相同时，从编码方法上说哪个在上面哪个在下面是没有本质区别的，但是得到的码是不相同的对这两种不同的码，它们的码长n不同，但是平均码长ñ是相同的。

为了克服哈夫曼编码方式存在的问题，提高哈夫曼编码的可用性，我们需要设法降低哈夫曼编码树的存储空间。

在数据特定的情况下，我们可以让编码器和解码器使用事先约定的编码树，如此可以消除哈夫曼树生成和传输储存的时间，但是当信源变化，此种方法就不再适用，不具备通用性。

自适应哈夫曼编码技术
Faller[1973]提出了一种自适应哈夫曼编码技术，它可以使哈夫曼编码树的存储空间降为零，即在使用某种约定的情况下，解码器能动态地重构出和编码器同步的哈夫曼编码树，而不需要任何附加数据。

它对数据编码的依据是动态变化的哈夫曼树，也就是说，对第t+1个字符编码是根据原始数据中前t个字符得到的哈夫曼树来进行的.压缩和解压子程序具有相同的初始化树，每处理完一个字符，压缩和解压方使用相同的算法修改哈夫曼树，因而该方法不需要为解压而保存树的有关信息。

压缩和解压一个字符所需的时间与该字符的编码长度成正比，因而该过程可以实时进行。

其算法如下：
这样做的代价便是时间开销的增大。

范式哈夫曼编码技术。