基于上下文模型的超长哈夫曼码校正算法

作者：张永兴^*; 吴睿振; 贾晓龙; 陈静静; 孙华锦

来源：计算机技术与发展, 2023, 33(02): 92-104.

• Deflate
• 哈夫曼编码
• 哈夫曼树
• 超长Huffman码
• 超长Huffman码校正

常见的Gzip、Zlib数据压缩标准都采用Deflate协议压缩封装数据，Deflate协议中采用哈夫曼码编码源符号(Source symbols)。哈夫曼编码算法通过构建哈夫曼树生成哈夫曼码，Deflate协议限定源符号的哈夫曼码的码长不能超过最大值。源符号的哈夫曼码长最大值等于哈夫曼树的高度，因此当哈夫曼树的高度超过限定值时，需要先把哈夫曼树进行“校正”,随后再为每个符号分配。Gzip、Zlib软件参考代码中使用的基于二叉树搜索的“校正”算法，校正时需要遍历搜索哈夫曼树，寻找嫁接“节点”。校正流程时间消耗非常大，而且硬件实现难度较大。该文探索一种基于上下文模型校正超长哈夫曼树的算法，与参考二叉树搜索算法相比：该算法可以快速校正超长哈夫曼树，将校正的时间消耗降至为0,而且对压缩效果几乎没有影响(压缩比平均下降率仅为0.372%)。该算法也易于硬件化实现，可以实时校正超长哈夫曼码。