无损数据压缩.ppt

《无损数据压缩.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章无损数据压缩本章学习目标掌握数据压缩的基本概念掌握几种常见的数据压缩方法香农-范诺编码算术编码RLE编码词典编码霍夫曼编码1.1数据压缩基本概念数据压缩基础无损压缩压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。如,磁盘文件的压缩。有损压缩压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。如，图像、声音的压缩。主要介绍目前用得最多和技术最成熟的无损压缩编码技术，包括：香农-范诺

2、和霍夫曼编码算术编码RLE编码词典编码1.1数据压缩基本概念无损数据压缩无损压缩1.2数据压缩方法基本概念：熵编码器信源（消息集）X={x1,…,xn}编码输出集Z={z1,…,zn}符号集Am={a1,…,am}熵(Entropy)的概念熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。某个事件的信息量用表示，其中Pi为第i个事件的概率，0

3、范诺按照香农(Shannon)的理论，信源S的熵定义为即信源X发出的xi共n个随机事件的自信息统计平均（数学期望）其含义：信源X发出任意一个随机变量的平均信息量。其中pi是符号Si在S中出现的概率;log2(1/pi)表示包含在si中的信息量，也就是编码si所需要的位数。Shannon(1948年)、Fano（1949年）采用从上到下的方法进行编码1.按符号出现的频率或概率排序;2.按递归方法分成两部分，每部分具有近似相同的次数;1.2数据压缩方法香农-范诺A15B7C7D6E5按符号出现的频率或概率排序A、B、C、D、E;按递归方法分成两部分，每部分具有近似相同的次

4、数;总位数：2×15＋2×7＋2×7＋3×6+3×5=91压缩比：120/91=1.3:11ABCDE00001111.2数据压缩方法香农-范诺举例例:有一幅40个像素组成的灰度图象，灰度共有5级，分别用符号A，B，C，D，E表示，如果用3个位表示5个等级的灰度值，则编码这幅图像总共需120位。霍夫曼(Huffman)1952年，从下到上的编码方法。1.初始化,根据概率大小由大到小顺序对符号进行排序2.概率最小的两个符号组成节点3.重复步骤24.从根节点到页节点,分别进行编码霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。几个问题值得注意：1.霍夫曼码没有错误

5、保护功能；2.霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码;3.接收端需保存一个与发送端相同的霍夫曼码表。1.2数据压缩方法霍夫曼编码A（0.3846）B（0.1795）C（0.1538）D（0.1538）E（0.1282）010101011.2数据压缩方法霍夫曼编码举例11.初始化，根据概率大小按由大到小的顺序对符号进行排序；2.概率最小的两个符号组成一个节点3.重复步骤2，直到形成一棵完整的数4.从根节点开始分别对数的分枝进行编码（0或1）例：设有7个符号：a1,a2,a3,a4,a5,a6,a7它们出现概率是:0.2,0.19,0.

6、18,0.17,0.15,0.1,0.01a2(0.19)a1(0.2)a3(0.18)a4(0.17)a5(0.15)a6(0.1)0.390.350.110.260.611.010010101010110110000010100110a7(0.01)01111.2数据压缩方法霍夫曼编码举例2每个编码均非其它码的前缀，因此唯一可译(a1=10,a2=11,a3=000,a4=001,a5=010,a6=0110,a7=0111)11010100011011100111a2a5a1a4a1a2a1a7编码方案不唯一，码表必须存储（传输）简单易实现编码效率较高必须预先知

7、道信源的统计特性1.2数据压缩方法霍夫曼编码分析算法思想Huffman编码中每个符号都用整数个bits来表示，影响编码效率。若能把一串符号作为编码单位，则效率还可提高。符号串的区间表示法设符号串为：S1,S2,…Sm则它可以映射成为0..1中的唯一的一个子区间来表示1.2数据压缩方法算术编码思想消息用0到1之间的实数进行编码，两个基本的参数：符号的概率和编码间隔。信源符号的概率决定编码的效率，及信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。步骤：1.在[0,1)之间给每个符号分配一个初始子间隔,其长度为等于它的概