自适应霍夫曼编码如何工作？

#1 楼

Wikipedia文章使用了一种著名的实现方法Vitter算法，很好地描述了自适应霍夫曼编码过程。如您所述，标准的霍夫曼编码器可以访问其输入序列的概率质量函数，该函数用于为最可能的符号值构造有效的编码。例如，在基于文件的数据压缩的典型示例中，可以通过对输入序列进行直方图计算，计算每个符号值的出现次数（例如，符号可以是1字节序列）来计算此概率分布。该直方图用于生成霍夫曼树，就像这样的树（摘自Wikipedia文章）：



树通过减小权重或出现概率来排列按输入顺序；顶部的叶节点表示最可能的符号，因此在压缩数据流中接收到的符号最短。然后，将树与压缩数据一起保存，随后由解压缩器随后使用，以再次重新生成（未压缩的）输入序列。作为早期的熵代码实现之一，标准的霍夫曼编码非常简单。


自适应霍夫曼编码器的结构非常相似。它使用输入序列统计信息的基于树的相似表示形式，为每个输入符号值选择有效的编码。主要区别在于，作为该算法的流式实现，没有关于输入的概率质量函数的先验知识。序列的统计信息必须即时估算。如果要使用相同的霍夫曼编码方案，则意味着在处理输入流时必须动态构建和维护用于在压缩流中生成每个符号编码的树。

Vitter算法是完成此任务的一种方法；在处理每个输入符号时，将更新树，从而保持其在向下移动树时降低符号出现概率的特性。该算法定义了一组规则，这些规则涉及如何随时间更新树以及如何在输出流中对生成的压缩数据进行编码。随着输入序列的消耗，树的结构应代表对输入概率分布的越来越准确的描述。与标准的霍夫曼编码方法相比，解压缩器没有静态树可用于解码；

总结：自适应霍夫曼编码器的操作与标准算法非常相似；它在压缩过程中必须连续执行相同的树维护功能。但是，不是对整个输入序列的统计信息（霍夫曼树）进行静态测量，而是使用对序列概率分布的动态累积（即从第一个符号到当前符号）的估计来编码（和解码）每个符号。与标准的霍夫曼编码方法相比，自适应霍夫曼算法需要在编码器和解码器上进行此统计分析。