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

Correction Algorithm for Ultra-long Huffman Codes Based on Context Model

作　　者：张永兴 吴睿振 贾晓龙 陈静静 孙华锦 ZHANG Yong-xing;WU Rui-zhen;JIA Xiao-long;CHEN Jing-jing;SUN Hua-jin(Inspur Artificial Intelligence Research Institute Co.,Ltd.,Xi’an 710077,China)

机构地区：[1]浪潮人工智能研究院有限公司,陕西西安710077

出　　处：《计算机技术与发展》2023年第2期92-98,104,共8页Computer Technology and Development

摘　　要：常见的Gzip、Zlib数据压缩标准都采用Deflate协议压缩封装数据,Deflate协议中采用哈夫曼码编码源符号(Source symbols)。哈夫曼编码算法通过构建哈夫曼树生成哈夫曼码,Deflate协议限定源符号的哈夫曼码的码长不能超过最大值。源符号的哈夫曼码长最大值等于哈夫曼树的高度,因此当哈夫曼树的高度超过限定值时,需要先把哈夫曼树进行“校正”,随后再为每个符号分配。Gzip、Zlib软件参考代码中使用的基于二叉树搜索的“校正”算法,校正时需要遍历搜索哈夫曼树,寻找嫁接“节点”。校正流程时间消耗非常大,而且硬件实现难度较大。该文探索一种基于上下文模型校正超长哈夫曼树的算法,与参考二叉树搜索算法相比:该算法可以快速校正超长哈夫曼树,将校正的时间消耗降至为0,而且对压缩效果几乎没有影响(压缩比平均下降率仅为0.372%)。该算法也易于硬件化实现,可以实时校正超长哈夫曼码。Common data compression standards such as Gzip and Zlib compress and encapsulate data with the Deflate format.In Deflate protocol,Source symbols are encoded with Huffman codes that are distributed by constructing the Huffman tree.In the"Deflate"protocol,the Huffman codes for the various alphabets must not exceed certain maximum code lengths.Therefore,if the height of First Huffman tree was greater than the maximum value,First Huffman tree needs to be"corrected"before generating Huffman code.The current"correction"algorithm based on the binary tree consumes a lot of time in the correction process and is difficult to implement in hardware.We explore an algorithm to quickly correct ultra-long Huffman trees based on context models.Compared to exist correcting algorithm,the ultra-long Huffman trees could be quickly corrected with a consuming time of nearly 0.Moreover,mean compression ratio is only reduced by 0.372%.The proposed algorithm is suitable for hardware implementation and can correct ultra-long Huffman codes in real time.

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

分 类 号：TP309.3[自动化与计算机技术—计算机系统结构]