2.常用数据压缩技术

1、常用数据压缩技术n主要内容n香农-范诺编码nHuffman编码n算术编码n行程编码(Run Length Encoding)n词典编码n预测编码n变换编码O、香农-范诺编码n熵(Entropy)的概念n熵是信息量的度量方法，表示一条信息中真正需要熵是信息量的度量方法，表示一条信息中真正需要编码的信息量。编码的信息量。熵的单位是bits。事件发生的可能性越小（数学上就是概率越小），表示某一事件出现的消息越多。n某个事件的信息量用I Ii i -log -log2 2 p pi i 表示， 其中pi 为第 i 个事件的概率， 0 0 p pi i 1 1O、香农-范诺编码n信源S 的熵n按照香农(

2、Shannon)的理论，信源 S S 的熵定义为其中 为符号S i 在S中出现的概率。 表示包含在S i 中的信息量，也就是编码S i 所需要的位数。n按照香农的理论，熵是平稳信源的无损压缩效率的极限。例如，一幅用256级灰度表示的图像，如果每一个像素点灰度的概率均为 pi=1/256，编码每一个像素点就需要8位（比特，bit）。 例例 对下面这条只出现了 a、b、c 三个字符的字符串：aabbaccbaa，字符串长度为 10，字符 a b c 分别出现了 5、3、2 次，则 a、b、c 在信息中出现的概率分别为 0.5 0.3 0.2，他们的熵分别为： Ea = -log2(0.5) = 1

3、 Eb = -log2(0.3) = 1.737 Ec = -log2(0.2) = 2.322整条信息的熵也即表达整个字符串需要的位数为： Ea * 5 + Eb * 3 + Ec * 2 = 14.855 位 如果用计算机中常用的 ASCII 编码，表示上面的字符串需要整整80位！ 信息为什么能被压缩而不丢失原有的信息内容呢？简信息为什么能被压缩而不丢失原有的信息内容呢？简单地讲，用较少的位数表示较频繁出现的符号，这就是数单地讲，用较少的位数表示较频繁出现的符号，这就是数据压缩的基本准则。据压缩的基本准则。 例例 有一幅4040个象素组成的灰度图像，灰度共有5 5级，分别用符号A、B、C、

4、D和E表示，4040个象素中出现灰度A的象素数有1515个，出现灰度B的象素数有7 7个，出现灰度C的象素数有7 7个等等，如表所示。如果用3 3个位表示5 5个等级的灰度值，也就是每个象素用3 3位表示，编码这幅图像总共需要120120位。香农-范诺编码算法步骤n按照符号出现的概率减少的顺序将待编码的符号排成序列。 n将符号分成两组，使这两组符号概率和相等或几乎相等。 n将第一组赋值为0，第二组赋值为1。 n对每一组，重复步骤2、3的操作。01000111ABCDE按照这种方法进行编码得到的总位数为91，实际的压缩比约为120 : 911.3 : 1 一、Huffman编码nHuffman编

5、码属于信息熵编码的方法之一；n信息熵编码又称统计编码,它是根据信源符号出现概率的分布特性而进行的压缩编码；n信息熵编码基本思想: 在信源符号和码字之间建立明确的一一对应关系，以便在恢复时能准确地再现原信号，同时要使平均码长或码率尽量小；n信息熵编码的代表nHuffman编码n算术编码一、 Huffman编码nHuffman编码的理论基础是Huffman定理；nHuffmanHuffman定理（定理（1952年Huffman提出的） 在变长编码中,对出现概率大的信源符号赋于短码字,而对于出现概率小的信源符号赋于长码字。如果码字长度严格按照所对应符号出现概率大小逆序排列,则编码结果平均码字长度一定

6、小于任何其它排列方式。n也称为最佳编码，平均码长最短。Huffman编码步骤(1) 将信源符号按概率递减顺序排列；(2) 把二个最小概率相加作为新符号的概率，并按(1) 重排；(3) 重复(1)、(2)，直到概率为1；(4) 在每次合并信源时，将合并的信源分别赋“0”和“1”(如概率大的赋“0”,概率小的赋“1”)；(5) 寻找从每一信源符号到概率为1处的路径，记录下路径上的“1”和“0”；(6)写出每一符号的“1”、“0”序列(从树根到信源符号节点)。Huffman编码示例n平均码字长度: R=Pii= n该信源的信息熵：H=Pilog2Pi =(i )(Pi)M0M1M2M3M4M5M6M

7、710M0M1M2M3M4M5M6M710信源符号信源符号概率概率编码过程编码过程码字码字码长码长(i)x1 x2x3x4x5x6x7x80.40 0.180.10 0.10 0.070.060.050.041 00101100000100010100010 000111 33444550101010.090.130.190.230.370.601010011平均码字长度: R=？该信源的信息熵：H= ？！编程实现Huffman编解码算法R=Pii=0.401+0.183+0.103+0.104+0.074 +0.064+0.055+0.045二、算术编码n20世纪60年代初，Elias提出了

8、算术编码（Arithmetic Coding）的概念。n1976年，Rissanen和Pasco首次介绍了它的实用技术。其基本原理是：将编码的信息表示成实数0和1之间的一个间隔(Interval) ，信息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。n算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而且是一个介于 0 和 1 之间的二进制小数。例如算术编码对某条信息的输出为 1010001111，那么它表示小数 0.1010001111，也即十进制数 0.64。算术编码示例n采用固定模式符号概率分配如下： 字符: a e i o u 概率 范围:0,0.2) 0.

9、2,0.5) 0.5,0.6)0.6,0.8)0.8,1.0)n编码数据串为eai。令high间隔的高端， low为低端，range为间隔的长度， rangelow为编码字符分配的间隔低端， rangehigh为编码字符分配的间隔高端。 n初始high=1，low=0， range=high-low， 一个字符编码后新的low和high按下式计算： low=low+rangerangelow； high=low+rangerangehigh。(1) 在第一个字符e被编码时， e的rangelow=0.2， rangehigh=0.5， 因此： 此时分配给e的范围为0.2， 0.5) (2) 第

10、二个字符a编码时使用新生成范围0.2，0.5)， a的rangelow=0， rangehigh=0.2， 因此： 范围变成0.2， 0.26) (3) 对下一个字符i编号， i的rangelow=0.5，rangehigh=0.6，range=0.06， 则： n结果结果：用0.23， 0.236)表示数据串eai，如果解码器知道最后范围是0.23， 0.236)，它马上可解得一个字符为e， 然后依次得到惟一解a、i， 最终得到eai。 1e 0.5ea 0.26 0.2360.80.60.50.20uoieauoieauoieauoiea 0.2 0.2 0.23eai字符: a e i

11、o u概率范围:0,0.2) 0.2,0.5) 0.5,0.6)0.6,0.8)0.8,1.0)eai算术编码过程表示算术编码过程表示n算术编码的优缺点：n对整个消息只产生一个码字,无需用一个特定的代码替代一个输入符号；n小数的精度不可能无限长，在运算中存在溢出的问题需要解决；n对错误非常敏感；n信源符号概率接近时，建议使用算术编码，这种情况下其效率高于Huffman编码(约5%)。n可以不必预先定义概率模型，自适应模式自适应模式具有独特的优点；！编程实现算术编解码算法三、行程编码n行程编码（RLE， Run Length Encoding）RLE编码的结果是：80315084180压缩比：7

12、3 ：11 7 ：1！编程实现RLE编解码算法三、行程编码nRLE所能获得的压缩比有多大，这主要是取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小。nRLE压缩编码尤其适用于计算机生成的图像，对颜色丰富的自然图像就显得力不从心。n在自然图像的压缩中少不了RLE，但需要和其他的压缩编码技术联合应用。 四、词典编码n词典编码的根据：数据本身包含有重复代码数据本身包含有重复代码 n词典编码的种类：n第一类：查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“

13、指针” 。四、词典编码n第二类：企图从输入的数据中创建一个“短语词典”，编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。 LZ77LZ77算法n几个术语 n输入数据流(input stream)：要被压缩的字符序列n字符(character)：输入数据流中的基本单元 n编码位置(coding position)：输入数据流中当前要编码的字符位置 n前向缓冲存储器(Lookahead buffer)：存放从编码位置到输入数据流结束的字符序列的存储器 n窗口(window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的

14、字符数n指针(pointer)：指向窗口中的匹配串且含长度的指针 LZ77LZ77算法n编码步骤：n把编码位置设置到输入数据流的开始位置 n查找窗口(最近输入的W个字符)中最长的匹配串n以“(Pointer, Length) Characters”的格式输出，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器不匹配的第1个字符。 1. 如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤2。 位置位置1 12 23 34 45 56 67 78 89 9字符字符 A AA AB BC CB

15、BB BA AB BC C步骤步骤位置位置匹配串匹配串 字符字符 输出输出 1 11 1-A A(0,0) (0,0) A A2 22 2A AB B(1,1) (1,1) B B3 34 4-C C(0,0) (0,0) C C4 45 5B BB B(2,1) (2,1) B B5 57 7A BA BC C(5,2) (5,2) C C待编码的数据流待编码的数据流 编码过程编码过程 LZSSLZSS算法nLZ77通过输出真实字符真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在

16、下一个匹配串中的字符。 nLZSS基本思想：如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字符。LZSSLZSS算法nLZSS编码算法的具体执行步骤如下：1. 把编码位置置于输入数据流的开始位置。2. 在前向缓冲存储器中查找与窗口中最长的匹配串 Pointer：= 匹配串指针。 Length ：= 匹配串长度。3. 判断匹配串长度Length是否大于等于最小匹配串长度，如果“是”：输出指针，然后把编码位置向前移动Length个字符。如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。4. 如果前向缓冲存储器不是空的，就返回到步骤2。 输入数据流输入数据流

17、编码过程编码过程( (MIN_LENGTH MIN_LENGTH = 2)= 2)步骤步骤位置位置 匹配串匹配串输出输出1 11 1-A A2 22 2A AA A3 33 3-B B4 44 4B BB B5 55 5-C C6 66 6B BB B(3,2)(3,2)7 78 8A A BA A B(7,3)(7,3)8 81111C CC C位置位置1 12 23 34 45 56 67 78 89 910101111字符字符 A AA AB BB BC CB BB BA AA AB BC CLZ78算法n几个术语n字符流(Charstream)：要被编码的数据序列，即输入的数据流n字符

18、(Character)：字符流中的基本数据单元 n前缀(Prefix)：在一个字符之前的字符序列 n缀 符串(String)：前缀字符 n码字(Code word)：码字流中的基本数据单元，代表词典中的一串字符 n码字流(Codestream)：码字和字符组成的序列，是编码器的输出 LZ78算法n词典(Dictionary)：缀-符串表。按照词典中的索引号对每条缀 符串(String)指定一个码字(Code word)n当前前缀(Current prefix)：在编码算法中使用，指当前正在处理的前缀，用符号P表示。n当前字符(Current character)：在编码算法中使用，指当前前缀之

19、后的字符，用符号C表示。 n当前码字(Current code word)：在译码算法中使用，指当前处理的码字，用W表示当前码字，表示当前码字的缀 符串。 LZ78算法nLZ78的编码思想编码思想是不断地从字符流中提取新的缀 符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Code word)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Code word)去替换字符流(Charstream)，生成码字流(Codestream)，从而达到压缩数据的目的。 LZ78算法nLZ78 编码的具体算法如下:步骤1： 在开始时，词典和当前前缀 P 都是空的。步骤2：

20、当前字符 C := 字符流中的下一个字符。步骤3： 判断 P+C 是否在词典中： (1) 如果“是”：用C扩展P，让 P := P+C ； (2) 如果“否”： 输出与当前前缀 P 相对应的码字和当前字符 C； 把字符串 P+C 添加到词典中。 令 P :=空值。 (3) 判断字符流中是否还有字符需要编码 如果“是”：返回到步骤2。 如果“否”：若当前前缀 P 不是空的，输出相应于当前前缀 P 的码字， 然后结束编码。 编码字符串编码字符串位置位置1 12 23 34 45 56 67 78 89 9字符字符 A AB BB BC CB BC CA AB BA A编码过程编码过程步骤步骤位置位

21、置 词典词典输出输出 1 11 1A A(0,(0,A)A)2 22 2B B(0,(0,B)B)3 33 3B CB C(2,(2,C)C)4 45 5B C AB C A(3,(3,A)A)5 58 8B AB A(2,(2,A)A)1 D= P= C=A P+C=A N: output (0,A) D1=A P=2 C=B P= P+C=B N: output (0,B) D2=B P=3 C=B P= P+C=B Y: P=P+C=B4 C=C P=B P+C=BC N: output (2,C) D3=BC P=5 C=B P= P+C=B Y: P=P+C=B6 C=C P=B P

22、+C=BC Y: P=P+C=BC7 C=A P=BC P+C=BCA N: output (3,A) D4=BCA P=8 C=B P= P+C=B Y: P=P+C=BLZW算法nLZW与LZ78 的差别nLZW只输出代表词典中的缀 符串(String)的码字(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root) ；n由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀(one-character prefix)，因此在词典中搜索的第1个缀 符串有两个字符。 LZW算法n编码算法： 步骤步骤1 1

23、: : 开始时的词典包含所有可能的根开始时的词典包含所有可能的根( (RootRoot) )，而当前前而当前前 缀缀 P P 是空的；是空的； 步骤步骤2 2: : 当前字符当前字符( (C C) := ) := 字符流中的下一个字符；字符流中的下一个字符； 步骤步骤3 3: : 判断缀判断缀 符串符串 P+C P+C 是否在词典中是否在词典中 (1) (1) 如果如果“是是”：P P := := P+CP+C / / ( (用用C C扩展扩展P P) ) ； (2) (2) 如果如果“否否” 把代表当前前缀把代表当前前缀 P P 的码字输出到码字流的码字输出到码字流; ; 把缀把缀 符串符串

24、 P+C P+C 添加到词典添加到词典; ; 令令 P P := := C /C /( (现在的现在的P P仅包含一个字符仅包含一个字符C C);); 步骤步骤4 4: : 判断码字流中是否还有码字要译判断码字流中是否还有码字要译 (1) (1) 如果如果“是是”，就返回到步骤，就返回到步骤2 2； (2) (2) 如果如果“否否” 把代表当前前缀把代表当前前缀P P的码字输出到码字流的码字输出到码字流; ; 结束。结束。 被编码的字符串被编码的字符串位置位置1 12 23 34 45 56 67 78 89 9字符字符 A AB BB BA AB BA AB BA AC CLZWLZW的编码

25、过程的编码过程步骤步骤 位置位置 词典词典输出输出(1)(1)A A(2)(2)B B(3)(3)C C1 11 1(4)(4)A BA B(1)(1)2 22 2(5)(5)B BB B(2)(2)3 33 3(6)(6)B AB A(2)(2)4 44 4(7)(7)A B AA B A(4)(4)5 56 6(8)(8)A B A CA B A C(7)(7)6 6-(3)(3)1 P= C=A P+C=A Y: P=P+C=A2 C=B P=A P+C=AB N: output A.w=1 D=D+AB P=B3 C=B P=B P+C=BB N: output B.W=2 D=D+B

26、B P=B4 C=A P=B P+C=BA N: output B.W=2 D=D+BA P=A5 C=B P=A P+C=AB Y: P=P+C=AB 6 C=A P=AB P+C=ABA N: output AB.W=4 D=D+ABA P=A7 C=B P=A P+C=AB Y: P=P+C=AB8 C=A P=AB P+C=ABA Y: P=P+C=ABA9 C=C P=ABA P+C=ABAC N: output ABA.W=7 D=D+ABAC P=Cn译码算法： 步骤步骤1 1: : 在开始译码时词典包含所有可能的前缀根在开始译码时词典包含所有可能的前缀根( (RootRoot)

27、 ) 步骤步骤2 2: : cWcW := := 码字流中的第一个码字码字流中的第一个码字 ； 步骤步骤3 3: : 输出当前缀输出当前缀 符串符串string.cWstring.cW到字到字符符流流 步骤步骤4 4: : 前码字前码字 pWpW := := 当前码字当前码字cWcW 步骤步骤5 5: : 当前码字当前码字 cWcW := := 码字流中的下一个码字码字流中的下一个码字 步骤步骤6 6: : 判断先前缀判断先前缀 符串符串string.cWstring.cW是否在词典中是否在词典中 (1) (1) 如果如果“是是”，则：，则： 把把当当前缀前缀 符串符串string.pWstr

28、ing.pW输出到字符流。输出到字符流。 当前前缀当前前缀 P P := := 先前缀先前缀 符串符串string.pWstring.pW。 当前字符当前字符 C C := := 当前前缀当前前缀 符串符串string.cWstring.cW的第一个字符。的第一个字符。 把缀把缀 符串符串 P+C P+C 添加到词典。添加到词典。 (2) (2) 如果如果“否否”，则：，则： 当前前缀当前前缀 P P := :=先前缀先前缀 符串符串string.pWstring.pW。 当前字符当前字符 C C := :=当前缀当前缀 符串符串string.cWstring.cW的第一个字符。的第一个字符。

29、 输出缀输出缀 符串符串 P+C P+C 到字符流，然后把它添加到词典中。到字符流，然后把它添加到词典中。 步骤步骤7 7：判断码字流中是否还有码字要译判断码字流中是否还有码字要译 (1) (1) 如果如果“是是”，就返回到步骤，就返回到步骤4 4。 (2) (2) 如果如果“否否”, ”, 结束。结束。 步骤步骤代码代码词典词典输出输出(1)A(2)B(3)C1(1)-A2(2)(4)ABB3(2)(5)BBB4(4)(6)BAAB5(7)(7)ABAABA6(3)(8)ABACCLzwLzw的译码过程的译码过程1 cW=1 out 1.S=A2 pW=1 cW=2 Y: out 2.S=B

30、 P=1.S=A C=2.S=B D=D+AB3 pW=2 cW=2 Y: out 2.S=B P=2.S=B C=2.S=B D=D+BB4 pW=2 cW=4 Y: out 4.S=AB P=2.S=B C=4.S=A D=D+BA5 pW=4 cW=7 N: P=4.S=AB C= A out ABA D=D+ABA6 pW=7 cW=3 Y: out 3.S=C P=7.S=ABA C= C D=D+ABAC五、预测编码n预测编码n基本原理是基于图像中相邻像素之间具有较强的相关性。每个像素可根据已知的前几个像素来作预测。因此在预测编码中，编码和传输的并不是像素采样值本身，而是这个采样值

31、的预测值与其实际值之间的差值。五、预测编码n分类n线性预测n差分脉冲编码调制DPCM（Differential Pulse Code Modulation）典型代表n增量调制（DM）n自适应增量调制（ADM）n自适应脉冲编码调制（APCM）n自适应差分脉冲编码调制（ADPCM）n非线性预测（不讨论）DPCMn在PCM系统中，原始的模拟信号经过采样后得到的每一个样值都被量化成为数字信号。n为了压缩数据，可以不对每一样值都进行量化，而是预测下一样值，并量化实际值与预测值之间的差值，这就是DPCM（Differential Pulse Code Modulation，差分脉冲编码调制）。DPCM系统

32、原理框图n差分信号是离散输入信号和预测器输出的估算值之差。nDPCM系统是一个负反馈系统，采用这种结构可以避免量化误差的积累。nDPCM适用于图像和语音数据n例子： 23 45 48 52 60 76 89 90 95 23 22 3 4 8 16 13 1 5) 1()()(kskskde自适应脉冲编码调制(APCM) n自适应脉冲编码调制(a adaptive p pulse c code m modulation，APCM)是根据输入信号幅度大小来改变量化阶大小的一种波形编码技术。这种自适应可以是瞬时自适应，即量化阶的大小每隔几个样本就改变，也可以是音节自适应，即量化阶的大小在较长时间周

33、期里发生变化。 自适应差分脉冲编码调制(ADPCM) n自适应脉冲编码调制（ADPCM）基本思想：n利用自适应的思想改变量化阶的大小，即使用小的量化阶(step-size)去编码小的差值，使用大的量化阶去编码大的差值；n使用过去的样本值估算下一个输入样本的预测值，使实际样本值和预测值之间的差值总是最小。 增量调制DM（调制）n是PCM编码的一种变形。PCM是对每个采样信号的整个幅度进行量化编码，因此它具有对任意波形进行编码的能力；DM是对实际的采样信号与预测的采样信号之差的极性进行编码，将极性变成“0”和“1”这两种可能的取值之一。如果实际的采样信号与预测的采样信号之差的极性为“正”，则用“1”表示；相反则用“0”表示，或者相反。由于DM编码只须用1位对话音信号进行编码，所以DM编码系统又称为“1位系统”。增量调制DM（调制）在输入信号变化快的区域，斜率过载是关心的焦点，而在输入信号变化慢的区域，关心的焦点是粒状噪声。为了尽可能避免出现斜率过载