哈尔滨工业大学（威海）
自适应霍夫曼编码
信息论论文
隋沛君
10S030092
一、霍夫曼编码概述：
Huffman 算法是一种用于数据压缩的算法，由D.A. Huffman 最先提出。它完全依据字符出现概率来构造平均长度最短的编码，有时称之为最佳编码，一般叫做Huffman编码。频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。
该编码的核心部分为Huffman编码树，一棵满二叉树。所有可能的输入符（通常对应为字节）在Huffman编码树上对应为一个叶节点，叶节点的位置就是该符号的Huffman编码。具体来说，一个符号对应的Huffman 编码就是从根节点开始，沿左字节点0或右子节点1前进，一直找到该符号叶节点为止的路径对应的二进制编码。在Huffman编码树的基础上，该算法的编码部分输入一系列的符号，根据Huffman树对符号进行翻译，以符号在Huffman树上的位置作为编码结果。解码部分反之，根据输入的Huffman编码，通过查询Huffman树翻译回原始符号。
现在使用中的霍夫曼编码大致分为两种：静态霍夫曼编码和自适应霍夫曼编码。
二、 静态霍夫曼编码简介：
编码步骤：
第一，将信源符号按照权重（即该符号出现的概率）递减顺序排序。 第二，取出权重最小的两个集合元素作为叶节点组成一棵子树，子树的根节点权重值为两个叶节点的权重值之和。然后将新产生的子树的根节点元
素替代原两个叶子节点元素放回原来的集合，并保持集合有序。每次形成子树时，将两个叶子节点分别赋予1和0或0和1。
第三，重复上述步骤，直至集合中只剩下一个元素，则 Huffman 编码树构造完成。
第四，对每一个信源符号写出从编码树的根节点到叶子节点的1,0序列。 编码实例： abcddbb
最终编码结果：[1**********]00
三、自适应霍夫曼编码提出的目的和意义：
在静态霍夫曼编码中，要构造编码树必须提前统计被编码对象中的符号出现概率，因此必须对输入符号流进行两遍扫描，第一遍统计符号出现概率并构造编码树，第二遍进行编码，这在很多实际应用的场合中之不能接受的。其次，在存储和传送霍夫曼编码时，必须先存储和传送霍夫曼编码树。再次，静态编码树构造方案不能对输入符号流的局部统计规律变化做出反应。这些问题使得静态霍夫曼编码在实际中并未得到广泛的应用。
为了解决静态Huffman编码的缺点，人们提出了自适应Huffman
编码，
这种方案不需要事先扫描输入符号流，而是随着编码的进行同时构造Huffman树，因此，只需要进行一次扫描即可。在接收端伴随着解码过程同时进行着编码树的构造。自适应霍夫曼编码解决了静态编码树所面临的主要问题，因此在实际领域比如在高质量的图像和视频流传输中中获得了广泛的应用。
四、自适应霍夫曼编码的原理：
这种方案在不需要事先构造 Huffman 树，而是随着编码的进行，逐步构造 Huffman 树。同时，这种编码方案对符号的统计也动态进行，随着编码的进行，同一个符号的编码可能发生改变（变得更长或更短）。
在构造动态霍夫曼编码树的过程中，需要遵循两条重要原则：
（1）权重值大的节点，节点编号也较大。
（2）父节点的节点编号总是大于子节点的节点编号。
以上两点称为兄弟属性（sibling property）。在每一次调整节点权重值时，都需要相应的调整节点编号，以避免兄弟属性被破坏。在对某一个节点权重值进行“加一操作”时，应该首先检查该节点是否具有所在的块中的最大节点编号，如果不是，则应该将该节点与所在块中具有最大节点编号的节点交换位置。然后再对节点的权重值加。这样，由于该节点的节点编号已经处于原来所属块中的最大值，因此权重值加一之后兄弟属性仍然得到满足。最后，由于节点的权重发生了变化，必须递归地对节点的父节点进行加一操作。
初始化编码树时，由于只允许对待编码数据流进行单遍扫描，因此不可能预先知道各种符号的出现频率。为了对所有符号一致对待，编码树的初始
状态只包含一个叶节点，包含符号 NYT（Not Yet Transmitted，尚未传送），权重值为 0。 NYT是一个逸出码（escape code），不同于任何一个将要传送的符号。当有一个尚未包含在编码树中的符号需要被编码时，系统就输出 NYT 编码，然后跟着符号的原始表达。当解码器解出一个 NYT 之后，它就知道下面的内容暂时不再是 Huffman 编码，而是一个从未在编码数据流中出现过的原始符号。这样，任何符号都可以在增加到编码树之前进行传送。
在需要插入一个新符号时，总是先构造一个新的子树，子树包含NYT 符号与新符号两个叶节点，然后将旧的NYT 节点由这个子树替代。由于包含NYT 符号的节点权重值为0，而包含新符号的叶节点的权重值为1，因此最终效果相当于原NYT 节点位置的权重值由0 变为1。因此，下一步将试图对其父节点执行权重值“加一操作”。
对符号编码的方法与静态霍夫曼编码一致，每次符号编码完成以后，也将对包含符号的节点权值进行加一操作。
将一个新的符号插入编码树或者输出某一个已编码符号后，相应的符号的出现次数增加了1，继而编码树中各种符号的出现频率发生了改变，不一定符合兄弟属性，按照上述方法进行调整，使其符合要求。
五、自适应霍夫曼编码流程图：
六、自适应霍夫曼编码实例：
输入序列：abcddbb
步骤一： 初始状态，仅有唯一的YNT节点， 步骤二：
步骤三：
步骤四： 节NYT点的权重为0。 输入符号：a 输出编码：a 使用包含新NYT节点和字符a节点的子树，替换旧的NYT节点。 输入符号：b 输出符号：0b 使用包含新NYT节点和字符b节 点的子树，替换旧的NYT节点。 对51号节点（根节点）执行权重 值加一操作。
输入符号：c
输出编码：00c
使用包含新NYT节点和字符c节
点的子树，替换旧的NYT节点。
步骤五：
将要对49号节点执行权重值加一操 作，但49号节点不具有所在的块中 的最大节点编号，因此需要先与50 号节点进行交换位置操作。
步骤六：
步骤七：
新的50号节点权重值加一。 对51号节点执行权重值加一操作。 输入符号：d 输出编码：100d 使用包含新NYT节点和字符d节点 的子树，替换旧的NYT节点。 将要对47号节点执行权重加一操作，但是47号节点不具有所在块中的最 大节点编号，因此需要先与49号节 点进行交换位置操作。 新的49号节点权重值加一。 对51号节点执行权重值加一操作。
步骤八： 输入符号：d
输出编码：001
将要对44号节点执行权重值加一操 作，但44号节点不具有所在的块中 的最大的节点编号，因此需要先与 48
步骤九：
步骤十：
号节点进行交换位置操作。 新的48号节点权重值加一。 对50号节点执行权重值加一操作。 对51号节点执行权重值加一操作。 输入符号：b 输出编码：001 要对44号节点执行权重值加一操作，但44号节点不具有所在的块中的最 大节点编号，因此需要先与47号节 点进行位置交换操作。
步骤十一：
新的47号节点权重值加一。
对50号节点执行权重值加一操作。 对51号节点执行权重值加一操作。
步骤十二： 输入符号：b
输出编码：10
将要对47号节点执行权重值加一 操作，但47号节点不具有所在块中 的最大节点编号，因此需要先与49 号节点进行交换位置操作。
步骤十三：
新的49号节点权重值加一。 对51号节点执行权重值加一的
操作。
至此编码完成，输出编码为：a0b00c100d00100110
七、自适应霍夫曼编码特征：
通过观察以上步骤，容易发现自适应 Huffman 编码的几个特征：
(1) 在步骤 13 得到的编码树与静态 Huffman 编码树基本相同，除了 NYT 节点和符号 a节点组成的子树替代了静态 Huffman 编码树中的符号 a 的叶节点之外；
(2) 在每一次输入新的符号之前，Huffman 树都处于完整可用的正常状态；
(3) 同一个输入符号，可能产生多种不同的输出。例如三次输入的符号 b，产生的输出分别为 0b、001 和 10；
(4) 同样的输出结果，可能由不同的输入产生。例如第二次输入的符号 d 与第二次输入的符号 b，都产生了 001 作为输出结果。
这些特征首先说明了自适应 Huffman 编码树与静态 Huffman 编码树等同，完全符合Huffman 树的定义。同时，由于每一个输入符号都对编码树产生了影响，因此解码过程无法从 Huffman 编码数据流的某一个中间位置开始进行，而必须从头至尾逐 bit 处理。由于自适应 Huffman 编码算法采用了先编码，后调整编码树的方案，相应的解码算法比较简单。解码算法也使用仅有唯一的 NYT 节点的编码树作为初始状态，然后根据 Huffman编码数据流，对符号进行还原。每次处理完一个符号，就使用这个符号调整编码树。这样，在每一次输入新的符号之前，Huffman 树都处于与进行编码时使用的 Huffman 树完全相同的状态，保证了解码的正确性。
八、总结
自适应霍夫曼编码是一种扩展的熵编码方法，相比于先前的静态霍夫曼编码，自适应霍夫曼编码具有仅需单遍扫描、无需传送编码树、能够对输入符号流的局部统计规律变化做出反应等一系列优点，具有更高的压缩效率。这些优点使得它在一些实时性、可靠性要求比较高的场合得到了广泛的应用，被称为近代压缩算法的灵魂。
九、参考文献
[1] 数据结构与算法分析, Clifford A. Shaffer, 张铭、刘晓丹译, 电子工业出版社, 1998.
[2] Huffman 编码简介,联合程序开发网论坛,2010
[3] Adaptive Huffman Compression, AdaptiveHuff.html, Ze-Nian Li, 2006.
[4] 笨笨数据压缩教程, http://www.contextfree.net/wangyg/a/tutorial/benben. html, 王咏刚, 2003.
哈尔滨工业大学（威海）
自适应霍夫曼编码
信息论论文
隋沛君
10S030092
一、霍夫曼编码概述：
Huffman 算法是一种用于数据压缩的算法，由D.A. Huffman 最先提出。它完全依据字符出现概率来构造平均长度最短的编码，有时称之为最佳编码，一般叫做Huffman编码。频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。
该编码的核心部分为Huffman编码树，一棵满二叉树。所有可能的输入符（通常对应为字节）在Huffman编码树上对应为一个叶节点，叶节点的位置就是该符号的Huffman编码。具体来说，一个符号对应的Huffman 编码就是从根节点开始，沿左字节点0或右子节点1前进，一直找到该符号叶节点为止的路径对应的二进制编码。在Huffman编码树的基础上，该算法的编码部分输入一系列的符号，根据Huffman树对符号进行翻译，以符号在Huffman树上的位置作为编码结果。解码部分反之，根据输入的Huffman编码，通过查询Huffman树翻译回原始符号。
现在使用中的霍夫曼编码大致分为两种：静态霍夫曼编码和自适应霍夫曼编码。
二、 静态霍夫曼编码简介：
编码步骤：
第一，将信源符号按照权重（即该符号出现的概率）递减顺序排序。 第二，取出权重最小的两个集合元素作为叶节点组成一棵子树，子树的根节点权重值为两个叶节点的权重值之和。然后将新产生的子树的根节点元
素替代原两个叶子节点元素放回原来的集合，并保持集合有序。每次形成子树时，将两个叶子节点分别赋予1和0或0和1。
第三，重复上述步骤，直至集合中只剩下一个元素，则 Huffman 编码树构造完成。
第四，对每一个信源符号写出从编码树的根节点到叶子节点的1,0序列。 编码实例： abcddbb
最终编码结果：[1**********]00
三、自适应霍夫曼编码提出的目的和意义：
在静态霍夫曼编码中，要构造编码树必须提前统计被编码对象中的符号出现概率，因此必须对输入符号流进行两遍扫描，第一遍统计符号出现概率并构造编码树，第二遍进行编码，这在很多实际应用的场合中之不能接受的。其次，在存储和传送霍夫曼编码时，必须先存储和传送霍夫曼编码树。再次，静态编码树构造方案不能对输入符号流的局部统计规律变化做出反应。这些问题使得静态霍夫曼编码在实际中并未得到广泛的应用。
为了解决静态Huffman编码的缺点，人们提出了自适应Huffman
编码，
这种方案不需要事先扫描输入符号流，而是随着编码的进行同时构造Huffman树，因此，只需要进行一次扫描即可。在接收端伴随着解码过程同时进行着编码树的构造。自适应霍夫曼编码解决了静态编码树所面临的主要问题，因此在实际领域比如在高质量的图像和视频流传输中中获得了广泛的应用。
四、自适应霍夫曼编码的原理：
这种方案在不需要事先构造 Huffman 树，而是随着编码的进行，逐步构造 Huffman 树。同时，这种编码方案对符号的统计也动态进行，随着编码的进行，同一个符号的编码可能发生改变（变得更长或更短）。
在构造动态霍夫曼编码树的过程中，需要遵循两条重要原则：
（1）权重值大的节点，节点编号也较大。
（2）父节点的节点编号总是大于子节点的节点编号。
以上两点称为兄弟属性（sibling property）。在每一次调整节点权重值时，都需要相应的调整节点编号，以避免兄弟属性被破坏。在对某一个节点权重值进行“加一操作”时，应该首先检查该节点是否具有所在的块中的最大节点编号，如果不是，则应该将该节点与所在块中具有最大节点编号的节点交换位置。然后再对节点的权重值加。这样，由于该节点的节点编号已经处于原来所属块中的最大值，因此权重值加一之后兄弟属性仍然得到满足。最后，由于节点的权重发生了变化，必须递归地对节点的父节点进行加一操作。
初始化编码树时，由于只允许对待编码数据流进行单遍扫描，因此不可能预先知道各种符号的出现频率。为了对所有符号一致对待，编码树的初始
状态只包含一个叶节点，包含符号 NYT（Not Yet Transmitted，尚未传送），权重值为 0。 NYT是一个逸出码（escape code），不同于任何一个将要传送的符号。当有一个尚未包含在编码树中的符号需要被编码时，系统就输出 NYT 编码，然后跟着符号的原始表达。当解码器解出一个 NYT 之后，它就知道下面的内容暂时不再是 Huffman 编码，而是一个从未在编码数据流中出现过的原始符号。这样，任何符号都可以在增加到编码树之前进行传送。
在需要插入一个新符号时，总是先构造一个新的子树，子树包含NYT 符号与新符号两个叶节点，然后将旧的NYT 节点由这个子树替代。由于包含NYT 符号的节点权重值为0，而包含新符号的叶节点的权重值为1，因此最终效果相当于原NYT 节点位置的权重值由0 变为1。因此，下一步将试图对其父节点执行权重值“加一操作”。
对符号编码的方法与静态霍夫曼编码一致，每次符号编码完成以后，也将对包含符号的节点权值进行加一操作。
将一个新的符号插入编码树或者输出某一个已编码符号后，相应的符号的出现次数增加了1，继而编码树中各种符号的出现频率发生了改变，不一定符合兄弟属性，按照上述方法进行调整，使其符合要求。
五、自适应霍夫曼编码流程图：
六、自适应霍夫曼编码实例：
输入序列：abcddbb
步骤一： 初始状态，仅有唯一的YNT节点， 步骤二：
步骤三：
步骤四： 节NYT点的权重为0。 输入符号：a 输出编码：a 使用包含新NYT节点和字符a节点的子树，替换旧的NYT节点。 输入符号：b 输出符号：0b 使用包含新NYT节点和字符b节 点的子树，替换旧的NYT节点。 对51号节点（根节点）执行权重 值加一操作。
输入符号：c
输出编码：00c
使用包含新NYT节点和字符c节
点的子树，替换旧的NYT节点。
步骤五：
将要对49号节点执行权重值加一操 作，但49号节点不具有所在的块中 的最大节点编号，因此需要先与50 号节点进行交换位置操作。
步骤六：
步骤七：
新的50号节点权重值加一。 对51号节点执行权重值加一操作。 输入符号：d 输出编码：100d 使用包含新NYT节点和字符d节点 的子树，替换旧的NYT节点。 将要对47号节点执行权重加一操作，但是47号节点不具有所在块中的最 大节点编号，因此需要先与49号节 点进行交换位置操作。 新的49号节点权重值加一。 对51号节点执行权重值加一操作。
步骤八： 输入符号：d
输出编码：001
将要对44号节点执行权重值加一操 作，但44号节点不具有所在的块中 的最大的节点编号，因此需要先与 48
步骤九：
步骤十：
号节点进行交换位置操作。 新的48号节点权重值加一。 对50号节点执行权重值加一操作。 对51号节点执行权重值加一操作。 输入符号：b 输出编码：001 要对44号节点执行权重值加一操作，但44号节点不具有所在的块中的最 大节点编号，因此需要先与47号节 点进行位置交换操作。
步骤十一：
新的47号节点权重值加一。
对50号节点执行权重值加一操作。 对51号节点执行权重值加一操作。
步骤十二： 输入符号：b
输出编码：10
将要对47号节点执行权重值加一 操作，但47号节点不具有所在块中 的最大节点编号，因此需要先与49 号节点进行交换位置操作。
步骤十三：
新的49号节点权重值加一。 对51号节点执行权重值加一的
操作。
至此编码完成，输出编码为：a0b00c100d00100110
七、自适应霍夫曼编码特征：
通过观察以上步骤，容易发现自适应 Huffman 编码的几个特征：
(1) 在步骤 13 得到的编码树与静态 Huffman 编码树基本相同，除了 NYT 节点和符号 a节点组成的子树替代了静态 Huffman 编码树中的符号 a 的叶节点之外；
(2) 在每一次输入新的符号之前，Huffman 树都处于完整可用的正常状态；
(3) 同一个输入符号，可能产生多种不同的输出。例如三次输入的符号 b，产生的输出分别为 0b、001 和 10；
(4) 同样的输出结果，可能由不同的输入产生。例如第二次输入的符号 d 与第二次输入的符号 b，都产生了 001 作为输出结果。
这些特征首先说明了自适应 Huffman 编码树与静态 Huffman 编码树等同，完全符合Huffman 树的定义。同时，由于每一个输入符号都对编码树产生了影响，因此解码过程无法从 Huffman 编码数据流的某一个中间位置开始进行，而必须从头至尾逐 bit 处理。由于自适应 Huffman 编码算法采用了先编码，后调整编码树的方案，相应的解码算法比较简单。解码算法也使用仅有唯一的 NYT 节点的编码树作为初始状态，然后根据 Huffman编码数据流，对符号进行还原。每次处理完一个符号，就使用这个符号调整编码树。这样，在每一次输入新的符号之前，Huffman 树都处于与进行编码时使用的 Huffman 树完全相同的状态，保证了解码的正确性。
八、总结
自适应霍夫曼编码是一种扩展的熵编码方法，相比于先前的静态霍夫曼编码，自适应霍夫曼编码具有仅需单遍扫描、无需传送编码树、能够对输入符号流的局部统计规律变化做出反应等一系列优点，具有更高的压缩效率。这些优点使得它在一些实时性、可靠性要求比较高的场合得到了广泛的应用，被称为近代压缩算法的灵魂。
九、参考文献
[1] 数据结构与算法分析, Clifford A. Shaffer, 张铭、刘晓丹译, 电子工业出版社, 1998.
[2] Huffman 编码简介,联合程序开发网论坛,2010
[3] Adaptive Huffman Compression, AdaptiveHuff.html, Ze-Nian Li, 2006.
[4] 笨笨数据压缩教程, http://www.contextfree.net/wangyg/a/tutorial/benben. html, 王咏刚, 2003.