第四章 无损数据压缩

第4章无损数据压缩

4.1仙农-范诺与霍夫曼编码4.2算术编码4.3RLE编码4.4词典编码第4章无损数据压缩数据压缩可分成两种类型，一种叫做无损压缩，另一种叫做有损压缩。

无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同

有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同本章主要介绍目前用得最多和技术最成熟的无损压缩编码技术。

第4章无损数据压缩在数据压缩技术中,编码技术可分成三种类型:

熵编码：不考虑数据源的无损数据压缩技术,它把数据都看作“符号”，其核心思想是按照符号出现的概率大小给符号分配长度合适的代码。概率大的代码长度长，概率小的代码长度短。

源编码：编码时考虑数据信号源的特性和信号的内容。通常为有损编码技术。混合编码：组合源编码和熵编码的数据有损压缩技术。2.1数据冗余一、冗余的概念数据能被压缩的依据是数据本身存在冗余。冗余有：人为冗余视听冗余数据冗余2.1数据冗余二、决策量在有限数目的互斥事件集合中，决策量是事件数的对数值，即

H0=log(n)对数的底数决定决策量的单位，sh(2)、Nat(e)、Hart(10)。2.1数据冗余三、信息量信息量是具有确定概率事件的信息的定量度量，定义为：

I(x)=log2(1/p(x))=-log2p(x)对一个等概率事件的集合，每个事件的信息量等于该集合的决策量。四、熵按照仙农(Shannon)的理论，信源S的熵定义为

其中pi是符号si在S中出现的概率；log(1/pi)表示包含在si中的信息量，H(s)为事件的信息量的平均值，也称为事件的平均信息量。2.1数据冗余五、数据冗余量数据的冗余量(R)定义为决策量(H0)超过熵的量，即为：

R=H0-H(S)2.1数据冗余4.1仙农-范诺与霍夫曼编码

[例4.1]有一幅40个像素组成的灰度图像，灰度共有5级，分别用符号A、B、C、D和E表示,各符号在图像中出现的数目见下表符 号

ABCDE出现的次数

157765如果用3个比特表示5个等级的灰度值，也就是每个像素用3比特表示，编码这幅图像总共需要120比特。

一、仙农-范诺编码4.1仙农-范诺与霍夫曼编码按照仙农理论，这幅图像的熵为

H(S)=(15/40)

log2(40/15)+(7/40)

log2(40/7)+

+(5/40)

log2(40/5)=2.196

即每个符号用2.196比特表示，40个像素需用87.84比特。

4.1仙农-范诺与霍夫曼编码仙农-范诺(Shannon-Fano)算法采用从上到下的方法进行编码。首先按照符号出现的频度或概率排序，例如A，B，C，D和E。然后使用递归方法分成两个部分，每一部分具有近似相同的次数，如图所示。按照这种方法进行编码得到的总比特数为91，实际的压缩比约为1.3:1。A:2位X15B:2位X7C:2位X7D:3位X6E:3位X54.1仙农-范诺与霍夫曼编码二、霍夫曼编码

霍夫曼(Huffman)则采用从下到上的编码方法，仍以刚才的例子说明它的编码步骤：

①初始化，根据符号概率的大小按由大到小顺序对符号进行排序4.1仙农-范诺与霍夫曼编码②把概率最小的两个符号组成一个节点，如P1。

③重复步骤2，得到节点P2、P3和P4，形成一棵“树”。④从根节点P4开始到相应于每个符号的“树叶”，从上到下标上“0”(上枝)或者“1”(下枝)

。⑤从根节点P4开始顺着树枝到每个叶子分别写出每个符号的代码。

P1P2P3P40101100101001011101114.1仙农-范诺与霍夫曼编码

⑥按照仙农理论，这幅图像的熵为

H(S)=(15/39)

log2(39/15)+(7/39)

log2(39/7)+

+(5/39)

log2(39/5)=2.1859

压缩比1.37:1

Huffman编码需要各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行译码。4.1仙农-范诺与霍夫曼编码编码原理——对出现频率高的信源编码长度短，而对出现频率低的信源编码长度长。其编码步骤如下：

[1]信号源的数据按照出现概率递减的顺序排列

[2]合并两个最小出现概率，作为新数据出现概率

[3]重复进行[1][2]，直至概率相加为1为止

[4]合并运算时，概率大者取0，概率小者取1(或相反）

[5]记录概率为1处到各信号源的0、1序列，则得到相应的Huffman编码。4.1仙农-范诺与霍夫曼编码

编码特点

[1]编码长度可变，压缩与解压缩较慢

[2]硬件实现困难

[3]编码效率取决于信号源的数据出现概率

[4]霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪怕仅仅是1位出现错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套，这种现象称为错误传播(errorpropagation)4.2算术编码

算术编码把一个信源集合表示为实数线上的0到1之间的一个区间。这个集合中的每个元素都要用来缩短这个区间。信源集合的元素越多，所得到的区间就越小，当区间变小时，就需要一些更多的数位来表示这个区间，这就是区间作为代码的原理。算术编码首先假设一个信源的概率模型，然后用这些概率来缩小表示信源集的区间。消息的编码输出可以是最后一个间隔中的任意数。

4.2算术编码[例4.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)，其中表示半开放间隔，即包含不包含。上面的信息可综合在表中。符号00011011概率0.10.40.20.3初始编码间隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)4.2算术编码现对输入的二进制消息序列10001100101101进行编码。新子区间的起始位置＝ 前子区间的起始位置＋ 当前符号的区间左端×前子区间长度新子区间的长度＝ 前子区间的长度×

当前符号的概率（等价于范围长度）算术编码过程举例

4.2算术编码4.2算术编码步骤间隔译码符号译码判决1[0.5,0.7)100.51439在间隔[0.5,0.7)2[0.5,0.52)000.51439在上一间隔的第1个1/10

3[0.514,0.52)110.51439在上一间隔的第7个1/104[0.514,0.5146)000.51439在上一间隔的第1个1/10

5[0.5143,0.51442)100.51439在上一间隔的第5个1/106[0.514384,0.51442)110.51439在上一间隔的第7个1/107[0.5143876,0.5144402)010.51439在上一间隔的第2个1/104.2算术编码编码过程：考虑一个有M个符号的字符表集ai=(1,2,…,M)，假设概率p(ai)=pi，而。输入符号用xn

=ai表示，第n个子间隔的范围用表示。其中l0=0，d0=1和p0=0，ln表示间隔左边界的值,rn表示间隔右边界的值，dn=rn-ln表示间隔长度。编码步骤如下：4.2算术编码步骤1：首先在1和0之间给每个符号分配一个初始子间隔，子间隔的长度等于它的概率，初始子间隔的范围用I1=[l1,r1)=[,)表示。令d1=r1-l1，L=l1和R=r1

。步骤2：L和R的二进制表达式分别表示为： 和

其中uk和vk等于“1”或者“0”。4.2算术编码比较u1和v1：①如果u1≠v1，不发送任何数据，转到步骤3；②如果u1=v1

，就发送二进制符号u1。比较u2和v2：①如果u2≠v2

，不发送任何数据，转到步骤3；②如果u2=v2

，就发送二进制符号u2。…这种比较一直进行到两个符号不相同为止，然后进入步骤3，

4.2算术编码步骤3：n加1，读下一个符号。假设第n个输入符号为xn=ai，按照以前的步骤把这个间隔分成如下所示的子间隔：

令dn=rn-ln，L=ln和R=rn

，然后转到步骤2。4.2算术编码发送1算术编码概念

发送0发送011例：对序列a2,a1,a3编码过程：4.2算术编码接受的数字间隔译码输出1[0.5,1)-0[0.5,0.75)0[0.5,0.625)1[0.5625,0.625)-1[0.59375,0.609375)………a2a1a3译码过程4.2算术编码在算术编码中需要注意的几个问题：

①由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。

②算术编码器对整个消息只产生一个码字，这个码字是在间隔[0,1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。

③算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。4.2算术编码算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，在编码期间估算信源符号概率的过程叫做建模。

现实中有许多这样的图像，在一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的像素都具有相同的颜色值。在这种情况下就不需要存储每一个像素的颜色值，而仅仅存储一个像素的颜色值，以及具有相同颜色的像素数目就可以，或者存储一个像素的颜色值，以及具有相同颜色值的行数。这种压缩编码称为行程编码(runlengthencoding，RLE)，具有相同颜色并且是连续的像素数目称为行程长度。

4.3RLE编码

例如对下面一行图像数据：用RLE编码方法得到的代码为：80315084180。代码中用黑体表示的数字是行程长度，黑体字后面的数字代表像素的颜色值。

4.3RLE编码4.3RLE编码

RLE是一种无损压缩技术。尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。然而，RLE对颜色丰富的自然图像就显得力不从心。4.4词典编码

一、词典编码的思想

词典编码(dictionaryencoding)的根据是数据本身包含有重复代码这个特性。它可分为两类：

4.4词典编码第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。如LZ77和LZSS算法。

4.4词典编码第二类算法的想法是企图从输入的数据中创建一个“短语词典(dictionaryofthephrases)”，短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。如LZW压缩编码。

4.4词典编码二、LZ77算法

算法中用到的几个术语：

(1)输入数据流(inputstream)：要被压缩的字符序列。

(2)字符(character)：输入数据流中的基本单元。

(3)编码位置(codingposition)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。

(4)前向缓冲存储器(Lookaheadbuffer)：存放从编码位置到输入数据流结束的字符序列的存储器。

4.4词典编码(5)窗口(window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。

(6)指针(pointer)：指向窗口中的匹配串且含长度的指针。

4.4词典编码LZ77编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执行步骤如下：(1)把编码位置设置到输入数据流的开始位置。(2)查找窗口中最长的匹配串。(3)以“(Pointer,Length)Characters”的格式输出，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个字符。(4)如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤2。4.4词典编码

位置123456789字符AABCBBABC步骤位置匹配串字符输出11--A(0,0)A22AB(1,1)B34--C(0,0)C45BB(2,1)B57ABC(5,2)C4.4词典编码三、LZSS算法

LZSS算法的思想是如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字符。由于输出的压缩数据流中包含有指针和字符本身，为了区分它们就需要有额外的标志位，即ID位。4.4词典编码LZSS编码算法的具体执行步骤如下：(1)把编码位置置于输入数据流的开始位置。(2)在前向缓冲存储器中查找与窗口中最长的匹配串

①Pointer

：=匹配串指针。

②Length：=匹配串长度。(3)判断匹配串长度Length是否大于等于最小匹配串长度(Length

MIN_LENGTH)，

如果“是”：输出指针，然后把编码位置向前移动Length个字符。

如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。(4)如果前向缓冲存储器不是空的，就返回到步骤2。4.4词典编码步骤位置匹配串输出11--A22AA33--B44BB55--C66BB(3,2)78AAB(7,3)811CC位置123456789字符AABBCBBAABC10114.4词典编码四、LZ78算法

(1)字符流(Charstream)：要被编码的数据序列。

(2)字符(Character)：字符流中的基本数据单元。

(3)前缀(Prefix)：在一个字符之前的字符序列。(4)缀‑符串(String)：前缀＋字符。(5)码字(Codeword)：码字流中的基本数据单元，代表词典中的一串字符。(6)码字流(Codestream)：码字和字符组成的序列，是编码器的输出。4.4词典编码(7)词典(Dictionary)：缀-符串表。按照词典中的索引号对每条缀‑符串(String)指定一个码字(Codeword)。

(8)当前前缀(Currentprefix)：在编码算法中使用，指当前正在处理的前缀，用符号P表示。

(9)当前字符(Currentcharacter)：在编码算法中使用，指当前前缀之后的字符，用符号C表示。(10)当前码字(Currentcodeword)：在译码算法中使用，指当前处理的码字，用W表示当前码字，String.W表示当前码字的缀‑符串。4.4词典编码1、编码算法

LZ78的编码思想是不断地从字符流中提取新的缀‑符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Codeword)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Codeword)去替换字符流(Charstream)，生成码字流(Codestream)，从而达到压缩数据的目的。4.4词典编码步骤1：在开始时，词典和当前前缀P都是空的。步骤2：当前字符C：=字符流中的下一个字符。步骤3：判断P+C是否在词典中：

(1)如果“是”：用C扩展P，让P：=P+C；

(2)如果“否”：

①输出与当前前缀P相对应的码字和当前字符C；

②把字符串P+C添加到词典中。

③令P：=空值。

(3)判断字符流中是否还有字符需要编码

①如果“是”：返回到步骤2。

②如果“否”：若当前前缀P不是空的，输出相应于当前前缀P的码字，然后结束编码。

2、译码算法

具体算法如下：步骤1：在开始时词典是空的。步骤2：当前码字W：=码字流中的下一个码字。步骤3：当前字符C：=紧随码字之后的字符。步骤4：把当前码字的缀‑符串(string.W)输出到字符流(Charstream)，然后输出字符C。步骤5：把string.W+C添加到词典中。步骤6：判断码字流中是否还有码字要译

(1)如果“是”，就返回到步骤2。

(2)如果“否”，则结束。4.4词典编码4.4词典编码位置123456789字符ABBCBCABA步骤位置词典输出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)4.4词典编码五、LZW算法

在LZW算法中使用的术语与LZ78使用的相同，仅增加了一个术语—前缀根(Root)，它是由单个字符串组成的缀‑符串(String)。在编码原理上，LZW与LZ78相比有如下差别：①开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root)。②每个编码步骤开始时都使用一字符前缀(one-characterprefix)，因此在词典中搜索的第1个缀‑符串有两个字符。

4.4词典编码1、编码算法码字(Codeword)前缀(Prefix)1

……193A194B……255

……1305abcdefxyF01234……词典

4.4词典编码LZW编码算法步骤步骤1：开始时的词典包含所有可能的根(Root)，而当前前缀P为字符流中的第一个字符；

步骤2：当前字符(C)：=字符流中的下一个字符；

步骤3：判断缀‑符串P+C是否在词典中

(1)如果“是”：P：=P+C //(用C扩展P)；

(2)如果“否”

①把代表当前前缀P的码字输出到码字流;

②把缀‑符串P+C添加到词典;

③令P：=C//(现在的P仅包含一个字符C);

4.4词典编码步骤4：判断字符流中是否还有字符要编码

(1)如果“是”，就返回到步骤2；

(2)如果“否”

①把代表当前前缀P的码字输出到码字流;

②结束。

4.4词典编码2、译码算法

LZW译码算法中还用到另外两个术语：①当前码字(Currentcodeword)：指当前正在处理的码字，用cW表示，用string.cW表示当前缀‑符串；②先前码字(Previouscode