[科普中国]-适应性哈夫曼编码

适应性哈夫曼编码（Adaptive Huffman coding），又称动态哈夫曼编码（Dynamic Huffman coding），是基于哈夫曼编码的适自适应编码技术。它允许在符号正在传输时构建代码，允许一次编码并适应数据中变化的条件，即随着数据流的到达，动态地收集和更新符号的概率（频率）。一遍扫描的好处是使得源程序可以实时编码，但由于单个丢失会损坏整个代码，因此它对传输错误更加敏感。

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

适应性哈夫曼编码是基于哈夫曼编码的特点实现的，哈夫曼树必须具有如下的属性（假设有个叶子结点）：个叶子结点，每个叶子结点的重量都是非负的，并且某个内部结点的重量是其儿子结点重量之和。结点的顺序按照每个结点的重量升序排列，因此第个结点和第个结点是兄弟结点。；某个结点的父结点的结点号一定大于此结点的结点号。动态哈夫曼编码的关键是如何将前个字符的哈夫曼树调整成一颗前个字符的哈夫曼树。为解决上述问题，需分两步走，第一步把个字符的哈夫曼树转换成它的另一种形式，在该树中只需在第二步中简单的把有根到路径上所有结点的重量加1，就可以变成前个字符的哈夫曼树，其过程就是以叶结点为当前结点，重复的将当前结点与具有同样重量序号最大的节点进行交换，并使后者的父结点成为当前结点，直到遇到根结点为止，第一步通过将根到叶结点路径上的所有结点重量加1，就变成了前个字符的哈夫曼树1。

兄弟性质在哈夫曼编码中，有个缺点是除了压缩后的资料外，它还得传送机率表给解码端，否则解码端无法正确地做解码的工作。如果想要压缩好一点，必须有更多的统计资料，但同时必须要送出更多的统计资料到解压缩端。而适应性编码可以利用已经读过的资料机动的调整哈夫曼树。适应性哈夫曼编码中，算法FGK的基本原则是根据兄弟性质（Sibling Property），由Gallager定义。一颗哈夫曼树只是一棵在每个节点，包括树叶与内节点，加上加权值得二叉树，除了树根外，每一个节点都有一个兄弟节点与其共有一个父亲节点。如果每一个节点可以按照加权值从小排列到大且每个节点又再自己的兄弟相邻，称为兄弟性质。修改、或更新一棵哈夫曼树包括两个步骤。第一个步骤是频率次数的增加，先找到该叶子，把频率加一，在往上找他的父亲节点，也跟着加一，直到树根皆照着此步骤。第二个步骤是如果增加加权值的动作使得兄弟性质不再满足时，必须做调整的动作，借由交换叶子改变频率增加的顺序，同时，交换位置后的父亲节点加权值也要跟着更新，以此原则使之再度成为哈夫曼树。

有关算法FGK算法

在算法FGK中，传输端与接收端同时动态的去改变哈夫曼树，最初，解码树由单一叶子组成，称之0端。0端是用来代表未出现过的讯息，当每一个讯息传递后，增加此讯息的出现频率并调整哈夫曼树保持兄弟性质。当有t个讯息传递后，之中有k个不同的讯息，代表此哈夫曼树有k+1的叶子，k个叶子有讯息，1个代表0端。当下次传递新讯息时，此讯息夹带未出现过的资讯，0端的叶子此时分成2片叶子，1片给新讯息，另一片为新的0端。

考虑适应性哈夫曼编码的效能问题，更有效能的方法是确认编码端不会浪费空间在不存在的符号上，一般的哈夫曼编码容易做到是因为在建立哈夫曼树之前，会统计所有的资料，就能先算出各讯息的频率；相反的，适应性编码不一样，并不知资料出现的频率，因此假设所有讯息长度都一样是log_2⁡q个位元，伴随着统计资料的增加，讯息的编码长度会愈来愈短。但此方法有个缺点，在大部分情况会浪费许多空间，尤其在短讯息的情况，大部分未使用的符号会改变整个统计表，使得压缩结果大打折扣。

举例来说，符号源有256个符号，一开始的哈夫曼树就有这256个符号，且加权值设为1，即使连续读进16个e，也仍然需要四个位元以上来编码e，因为其他没出现的255个符号使得哈夫曼树的调整速度变慢。

解决的方法可以一开始统计表都没有东西，当讯息被读进去时在加入到统计表内，假设一开始哈夫曼树只有两个符号，两个符号加权值都是一，且都不改变，一个代表档案结束，另一个符号较特别，如果辨识的符号，哈夫曼树已经有了，就像上述正常的操作，如果哈夫曼树没出现过，先送出此符号，再送出此符号的ASCⅡ码，最后将这个加入哈夫曼树，设定加权值为1，调整哈夫曼树。这种方法，如过讯息是连续16个e，除了第一个e是九个位元，后面的所有15个e都只需要一个位元表示。

Vitter算法

编码一样是用树状结构表示，每个支点都有对应的权重及特定数字，数字从上到下、从左到右排列，权重要遵守兄弟性质，如果A是B的父亲且B是C的父亲，则 。

权重用来计算支点编码及其小孩（底下的支点）的数量，一样权重的胝点会形成一个区块，要得到每个支点的编码，在二进制树上，传输所有从树根到此支点的路径，往右走就写1，往左走就写0。需要有系统且简单的方式去表示还没传递（NYT），可以使用字母去传递二进制数字，编码跟解码都是从一个有最大数字的树根开始，当传递NYT时，必须传递编码到NYT支点，接着是普遍的支点，当每一个符号都完成后，只要传递编码到自己的叶子支点即可。

本词条内容贡献者为:

王慧维 - 副研究员 - 西南大学