无损数据压缩

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

2、： 香农-范诺和霍夫曼编码 算术编码 RLE编码 词典编码,1.1 数据压缩基本概念,无损数据压缩,无损压缩,1.2 数据压缩方法,基本概念：熵,如：一幅用256级灰度表示的图像，如果每一个像素点灰度的概率均为pi1/256，编码每一个像素就需要8位。 log2(1/ pi)= log2256=8,1.2 数据压缩方法,香农-范诺,按照香农(Shannon)的理论，信源S的熵定义为,即信源X发出的xi共n个随机事件的自信息统计平均（数学期望） 其含义：信源X发出任意一个随机变量的平均信息量。其中pi是符号Si在S中出现的概率;log2(1/ pi)表示包含在si中的信息量，也就是编码si所需要

3、的位数。,Shannon(1948年)、Fano（1949年） 采用从上到下的方法进行编码 1.按符号出现的频率或概率排序; 2.按递归方法分成两部分，每部分具有近似相同的次数;,1.2 数据压缩方法,香农-范诺,A15 B7 C7 D6 E5,按符号出现的频率或概率排序A、B、C、D、E; 按递归方法分成两部分，每部分具有近似相同的次数; 总位数：215272736+35=91 压缩比：120/91=1.3:1,1.2 数据压缩方法,香农-范诺举例,例:有一幅40个像素组成的灰度图象，灰度共有5级，分别用符号A，B，C，D，E表示，如果用3个位表示5个等级的灰度值，则编码这幅图像总共需120

4、位。,霍夫曼(Huffman) 1952年，从下到上的编码方法。 1.初始化,根据概率大小由大到小顺序对符号进行排序 2.概率最小的两个符号组成节点 3.重复步骤2 4.从根节点到页节点,分别进行编码 霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。 几个问题值得注意： 1.霍夫曼码没有错误保护功能； 2.霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码; 3.接收端需保存一个与发送端相同的霍夫曼码表。,1.2 数据压缩方法,霍夫曼编码,1.2 数据压缩方法,霍夫曼编码举例1,1.初始化，根据概率大小按由大到小的顺序对符号进行排序；,2.概率最小的两个符号组成

5、一个 节点,3.重复步骤2，直到形成一棵完整的数,4.从根节点开始分别对数的分枝进行编码（0或1）,1.2 数据压缩方法,霍夫曼编码举例2,每个编码均非其它码的前缀，因此唯一可译 ( a1=10,a2= 11, a3= 000, a4= 001, a5= 010, a6= 0110, a7=0111 ) 11 010 10 001 10 11 10 0111 a2 a5 a1 a4 a1 a2 a1 a7 编码方案不唯一，码表必须存储（传输） 简单易实现 编码效率较高 必须预先知道信源的统计特性,1.2 数据压缩方法,霍夫曼编码分析,算法思想 Huffman编码中每个符号都用整数个bits来表

6、示，影响编码效率。 若能把一串符号作为编码单位，则效率还可提高。 符号串的区间表示法 设符号串为：S1, S2, Sm 则它可以映射成为0.1中的唯一的一个子区间来表示,1.2 数据压缩方法,算术编码思想,消息用0到1之间的实数进行编码，两个基本的参数：符号的概率和编码间隔。信源符号的概率决定编码的效率，及信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。 步骤： 1.在0,1)之间给每个符号分配一个初始子间隔,其长度为等于它的概率，初始子间隔的范围用 表示. 2.用二进制表示子边界 如果 不发送任何数据，否则发送二进制符号 3.用递归方法读下一个符号。,1.

7、2 数据压缩方法,算术编码,假设信源符号为00, 01, 10, 11，这些符号的概率分别为 0.1, 0.4, 0.2, 0.3 ，根据这些概率可把间隔0, 1)分成4个子间隔：0, 0.1), 0.1, 0.5), 0.5, 0.7), 0.7, 1)，二进制消息序列的输入为：10 00 11 00 10 11 01,1.2 数据压缩方法,算术编码举例1,1.2 数据压缩方法,算术编码举例2,子区间的大小对应于符号串中各符号概率的乘积大小 子区间的位置对应着 符号串中符号的排列顺序 子区间的头尾均用二进制数表示 该符号串的编码是满足下列条件的、最短的数F: 头 = F 尾 可见： 不同的串

8、，对应着不同的子区间，选择子区间中任意的一个数作为该符号串的代码,则必有不同的编码 选择 子区间中最短的数作为 该符号串的代码 一般而言,子区间越宽,码长越短;子区间越窄,码长越长,1.2 数据压缩方法,算术编码分析,在算术编码中需要注意的几个问题： 1. 由于实际计算机精度不可能无限长，运算中溢出是明显的问题，但多数机器都有16位、32位或者64位的精度，因此可使用比例缩放法解决。 2. 算术编码器对消息只产生一个码字，这个码字是在0, 1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。 3. 算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息

9、译错。,1.2 数据压缩方法,算术编码注意点,信源符号及其概率如下: 求输入串ABBA的算术二进制编码(赋予大概率为右区间)，并求最短编码。,1.2 数据压缩方法,算术编码思考,1/4(0.25),A,B,B,A,0,1/4(0.01),1,0,1/4(0.01),1/16(0.0001),1/16,1/4(0.01),7/64(0.000111),7/64(0.000111),37/256(0.00100101),ABBA符号串对应的区间为7/64，37/256）, 即对应的二进制区间为0.000111,0.00100101 ）, 取最短二进制编码为：0.001,1.2 数据压缩方法,算术编

10、码思考答案,RLE(run length encoding）编码的概念,用RLE编码方法得到的代码为：80315084180。代码中用黑体表示的数字是行程长度，黑体字后面的数字代表象素的颜色值。例如黑体字50代表有连续50个象素具有相同的颜色值，它的颜色值是8。,译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。,1.2 数据压缩方法,RLE编码,词典编码的思想,第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。,1.2 数据压缩方法,第一类词典编码思想

11、,第二类算法的想法是企图从输入的数据中创建一个“短语词典 (dictionary of the phrases)”，这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。,1.2 数据压缩方法,第二类词典编码思想,核心：查找从前向缓冲存储器开始的最长的匹配串,1. 输入数据流：要被压缩的字符序列 2. 字符：输入数据流的基本单元 3. 编码位置：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符 4. 前向缓冲存储器：存放从编码位置到输入数据流结束的字符序列的存储器。 5. 窗口：指包含W个字符的窗

12、口 6. 指针：指向窗口中的匹配串且含长度的指针。,1.2 数据压缩方法,第一类词典编码:LZ77,1.2 数据压缩方法,第一类词典编码:LZ77举例,LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。,1.2 数据压缩方法,第一类词典编码:LZ77分析,LZSS算法以比较有效的方法解决这个问题，它的思想是如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字符。,1.2 数据压缩方法,第一类词典编码:LZSS,MIN_LENGTH2,L

13、ength MIN_LENGTH ？,1.2 数据压缩方法,第一类词典编码:LZSS举例,第二类算法的想法是企图从输入的数据中创建一个“短语词典 (dictionary of the phrases)”，这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。,1.2 数据压缩方法,第二类词典编码思想,术语： 1. 字符流(input stream)：要被编码的数据序列。 2. 字符(character)：输入数据流中的基本单元。 3. 前缀（prefix）：在一个字符之前的字符序列 4. 缀-符串(String

14、) ：前缀+字符 5. 码字(code word):码字流中的基本数据单元,代表词典中的一串字符 6. 码字流(codestream) ：码字和字符组成的序列,是编码器的输出 7. 词典(dictionary):缀-符串表 8. 当前前缀(current prefix):当前正在处理的前缀(P) 9. 当前字符(current character):当前前缀之后的字符(C) 10.当前码字(current code word):当前处理的码字(W),1.2 数据压缩方法,第一类词典编码:LZ78,LZ78的编码思想是不断地从字符流中提取新的缀-符串(String)，通俗地理解为新“词条”，然后

15、用“代号”也就是码字(Code word)表示这个“词条”。这样，对字符流的编码就变成了用码字(Code word)去替换字符流(Char stream)，生成码字流(Code stream)，从而达到压缩数据的目的。 LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的缀-符串(String)用字符C进行扩展生成新的缀-符串(String)，然后添加到词典中。,1.2 数据压缩方法,第二类词典编码:LZ78,1.2 数据压缩方法,第二类词典编码:LZ78举例,LZW编码是围绕称为词典的转换表来完成的。,在编码原理上，LZW与LZ78相比有如下差别： LZW只

16、输出代表词典中的缀-符串(String)的码字(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root)。 由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀(one-character prefix)，因此在词典中搜索的第1个缀-符串有两个字符。,J.Ziv和A.Lempel在1978年首次发表了介绍上述第二类编码方法的文章。在他们的研究基础上，Terry A.Welch在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为LZW(Lempel-Ziv Walch)压缩编码，,1.2 数据压缩方法,第二类词典编码:LZW,LZW编码器使用了一种很实用的分析(parsing)算法，称为贪婪分析算法(greedy parsing algorithm)。在贪婪分析算法中，每一次分析都要串行地检查来自字符流(Charstream)的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀(Prefix)。用已知的前缀(Prefix)加上下一个输入字符C也就是当前字符(Current character)作为该前缀的扩展字符，形成新的扩展字符串缀-符串(String)：Prefix.C。这个新的缀-符串(String)是否要加到词典中，还要看词典中是否存有和它