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

摘要：

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

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

所属期刊栏目：33

分类号：TP309.3(计算技术、计算机技术)

在线出版日期：2023-03-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：92-98,104