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

来源：计算机技术与发展杂志2023年第02期北京时间：

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

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

关键词：Deflate;哈夫曼编码;哈夫曼树;超长 Huffman 码;超长 Huffman 码校正