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

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