文档介绍：浅谈无损压缩算法摘要:该文介绍了经典的Huffman编码和目前压缩比最高的PAQ系列压缩算法,包括Huffman编码的原型,改进后的自适应Huffman编码及他们各自的实现方法和优缺点,PAQ系列压缩算法是如何进行上下文建模,预测和编码的。关键词:无损压缩;Huffman;PAQ 中图分类号:TP311文献标识码:A文章编号:1009-3044(2011)22-5466-02 在信息高速发展的今天,人们进行交流沟通的数据量相当的庞大,如何更好,更快的传输和存储数据已成为一个重大的问题,单纯地提高存储容量,并不能从根本解决问题,而数据的压缩是解决这一问题的重要方法。从无损音乐格式ape到文档的存储,数据的无损压缩已广泛应用于各个领域。 1无损压缩概述数据压缩是按照特定的编码机制用比未经编码少的数据位(或者其它信息相关的单位)表示信息的过程。无损压缩是利用数据的统计冗余进行压缩,可完全回复原始数据而不引起任何失真,但压缩率是受到数据统计冗余度的理论限制,一般为20%到50%。这类方法广泛用于文本数据,程序和特殊应用场合的图像数据的压缩。 2无损压缩算法Huffman和PAQ Huffman编码使用变长编码表对源符号进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现次数多的符号使用较短的编码,出现次数少的则使用较长的编码,这便使编码之后的符号串的平均长度降低,从而达到无损压缩数据的目的。Huffman编码是通过构建最优二叉树即带权路径长度最小的二叉树,来实现对数据的编码。Huffman编码的过程: (1)对数据中的源符号的种类和数量进行统计,共有n个源符号,其出现的频率分别为w1,w2...wn; (2)根据得到的n个权值{w1,w2...wn},构成n个二叉树的集合M={T1,T2...Tn},其中每棵二叉树Ti仅有一个带权为wi的根结点,其左右子树都为空; (3)在M中选取两棵根结点的权值最小的作为左右子树,构造一个新的二叉树,设置新的二叉树的根结点的权值为左右子树根结点权值之和; (4)在M中删除选中的两棵子树,同生死将新生成的二叉树加入到M中; (5)重复(3)和(4),直到M中只含有一棵树HTree为止,HTree即为所求的哈弗曼树; (6)从根结点出发对HTree进行先序遍历(向左记0,向右记1),从根结点到每个叶子结点的路径即为各个源符号所对应的huffman编码。这种静态的huffman算法实质是统计源符号,然后对其编码,这样需要对数据进行扫描统计和编码压缩两次操作,压缩速度较慢,实际运用不广泛。为了解决静态Huffman编码的缺点,产生了动态Huffman编码(又称自适应Huffman编码),它只需要对数据进行一次扫描,不需要事先构造Huffman树,而是随着编码的进行逐步构建Huffman树,随着编码的进行同一字符的编码也会随之发生变化。动态Huffman编码流程: (1)初始化编码树,仅含有一个结点,包含符号NYT(NYT是逸出码,不同于任何一个传送的符号,当有一个尚未在编码树中的符号需要被编码时,输出NYT编码,然后跟着符号的原始表达式),权值为0,符号集合M为空; (2)扫描符号fi,如果fi?埸M,将fi加入到M中,用