龙源期刊网httpwwwqika
comc
浅谈无损压缩算法
作者：孔凡龙程思远关迅来源：《电脑知识与技术》2011年第22期
摘要：该文介绍了经典的Huffma
编码和目前压缩比最高的PAQ系列压缩算法，包括Huffma
编码的原型，改进后的自适应Huffma
编码及他们各自的实现方法和优缺点，PAQ系列压缩算法是如何进行上下文建模，预测和编码的。
关键词：无损压缩；Huffma
；PAQ
中图分类号：TP311文献标识码：A文章编号：10093044201122546602
在信息高速发展的今天，人们进行交流沟通的数据量相当的庞大，如何更好，更快的传输和存储数据已成为一个重大的问题，单纯地提高存储容量，并不能从根本解决问题，而数据的压缩是解决这一问题的重要方法。从无损音乐格式ape到文档的存储，数据的无损压缩已广泛应用于各个领域。
1无损压缩概述
数据压缩是按照特定的编码机制用比未经编码少的数据位（或者其它信息相关的单位）表示信息的过程。无损压缩是利用数据的统计冗余进行压缩，可完全回复原始数据而不引起任何失真，但压缩率是受到数据统计冗余度的理论限制，一般为20到50。这类方法广泛用于文本数据，程序和特殊应用场合的图像数据的压缩。
2无损压缩算法Huffma
和PAQ
21基于Huffma
编码的压缩
211静态Huffma
和动态Huffma
编码
Huffma
编码使用变长编码表对源符号进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现次数多的符号使用较短的编码，出现次数少的则使用较长的编码，这便使编码之后的符号串的平均长度降低，从而达到无损压缩数据的目的。Huffma
编码是通过构建最优二叉树即带权路径长度最小的二叉树，来实现对数据的编码。Huffma
编码的过程：
（1）对数据中的源符号的种类和数量进行统计，共有
个源符号，其出现的频率分别为w1w2w
；
f龙源期刊网httpwwwqika
comc
（2）根据得到的
个权值w1w2w
，构成
个二叉树的集合MT1，T2T
，其中每棵二叉树Ti仅有一个带权为wi的根结点，其左右子树都为空；
（3）在M中选取两棵根结点的权值最小的作为左右子树，构造一个新的二叉树，设置新的二叉树的根结点的权值为左右子树根结点权值之和；
（4）在M中删除选中的两棵子树，同生死将新生成的二叉树加入到M中；
（5）重复（3）和（4），直到M中只含有一棵树HTree为止，HTree即为所求的哈弗曼树；
（6）从根结点出发对HTree进行先序遍历（向左记0，向右记1），从根结点到每个叶子结点的路径即为各个源符号所对应的huffma
编码。
这种静态的huffma
算r