长篇连载 无损数据压缩 <转贴>

这篇文章很好，请大家在全文未连载完之前不要回贴。以免影响阅读的完整性。

谢谢！！！

[编辑 -  1/22/03 by  bradley]

数据压缩可分成两种类型，一种叫做无损压缩，另一种叫做有损压缩。

无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/2到1/4。一些常用的无损压缩算法有哈夫曼(Huffman)算法和LZW(Lenpel-Ziv & Welch)压缩算法。

有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如，图象和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图象所表达的意思产生误解，但可大大提高压缩比。

本章重要介绍目前用得最多和技术最成熟的无损压缩编码技术，包括包含霍夫曼编码、算术编码、RLE编码和词典编码。对于不打算开发压缩技术和编写压缩程序的读者可不必深究编译码的详细过程

4.1 香农-范诺与霍夫曼编码

4.1.1 香农-范诺编码

香农-范诺编码算法需要用到下面两个基本概念：

(1) Entropy(熵)的概念


 熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。
 某个事件的信息量用Ii＝-log2 pi表示 ， 其中pi为第i个事件的概率，0< pi? 1

(2) 信源S的熵的定义

按照香农(Shannon)的理论，信源S的熵定义为

 

其中pi是符号Si在S中出现的概率；log2(1/pi)表示包含在Si中的信息量，也就是编码Si所需要的位数。例如，一幅用256级灰度表示的图象，如果每一个象素点灰度的概率均为 pi=1/256，编码每一个象素点就需要8比特。

举例：有一幅40个象素组成的灰度图象，灰度共有5级，分别用符号A、B、C、D和E表示，40个象素中出现灰度A的象素数有15个，出现灰度B的象素数有7个，出现灰度C的象素数有7个等等，如表4-01所示。如果用3个比特表示5个等级的灰度值，也就是每个象素用3比特表示，编码这幅图象总共需要120比特。

表4-01 符号在图象中出现的数目

符 号
 A
 B
 C
 D
 E
 
出现的次数
 15
 7
 7
 6
 5
 

按照香农理论，这幅图象的熵为

这就是说每个符号用2.196比特表示可以，40个象素需用87.84比特。

最早阐述和实现这种编码的是Shannon(1948年)和Fano(1949年)，因此被称为Shannon- Fano(香农-范诺)算法。这种方法采用从上到下的方法进行编码。首先按照符号出现的频度或概率排序，例如A、B、C、D、E，如表4-02所示，然后使用递归方法分成两个部分，每一部分具有近似相同的次数，如图4-01所示。按照这种方法进行编码得到的总比特数为91。压缩比约为1.3 : 1。

表4-02 Shannon-Fano算法举例表

符号
 出现的次数(pi)
 log2(1/pi)
 分配的代码
 需要的比特数
 
A
 15 (0.375)
 1.4150
 00
 30
 
B
 7 (0.175)
 2.5145
 01
 14
 
C
 7 (0.175)
 2.5145
 10
 14
 
D
 6 (0.150)
 2.7369
 110
 18
 
E
 5 (0.125)
 3.0000
 111
 15
 

　

4.1.2 霍夫曼编码

霍夫曼(Huffman)在1952年提出了另一种编码方法，即从下到上的编码方法。现仍以一个具体的例子说明它的编码步骤：


压缩比1.37:1。
  
  初始化，根据符号概率的大小按由大到小顺序对符号进行排序，如表4-03和图4-02所示。
 
 把概率最小的两个符号组成一个节点，如图4-02中的D和E组成节点P1。
 
 重复步骤2，得到节点P2、P3和P4，形成一棵“树”，其中的P4称为根节点。
 
 从根节点P4开始到相应于每个符号的“树叶”，从上到下标上“0”(上枝)或者“1”(下枝)，至于哪个为“1”哪个为“0”则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。
 
 从根节点P4开始顺着树枝到每个叶子分别写出每个符号的代码，如表4-03所示。
 
 按照Shannon理论，这幅图象的熵为
 

图像美好好学！！

请问bradley大侠，文章是哪里来的？很想细读，请告之

表4-03 霍夫曼编码举例

符号
 出现的次数
 log2(1/pi)
 分配的代码
 需要的位数
 
A
 15(0.3846)
 1.38
 0
 15
 
B
 7(0.1795)
 2.48
 100
 21
 
C
 6(0.1538)
 2.70
 101
 18
 
D
 6(0.1538)
 2.70
 110
 18
 
E
 5(0.1282)
 2.96
 111
 15
 

霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。例如，码串中的第1位为0，那末肯定是符号A，因为表示其它符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行译码。

采用霍夫曼编码时有两个问题值得注意：①霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪怕仅仅是1位出现错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套，这种现象称为错误传播(error propagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。②霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。尽管如此，霍夫曼码还是得到广泛应用。

与香农-范诺编码相比，这两种方法都自含同步码，在编码之后的码串中都不须要另外添加标记符号，即在译码时分割符号的特殊代码。此外，霍夫曼编码方法的编码效率比香农-范诺编码效率高一些。请读者自行验证。

4.2 算术编码

算术编码在图象数据压缩标准(如JPEG，JBIG)中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。算术编码器的编码过程可用下面的例子加以解释。

例1：假设信源符号为{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)，其中[x, y)表示半开放间隔，即包含x不包含y。上面的信息可综合在表4-04中。

表4-04 信源符号，概率和初始编码间隔

符号
 00
 01
 10
 11  
 
概率
 0.1
 0.4
 0.2
 0.3  
 
初始编码间隔
 [0, 0.1)
 [0.1, 0.5)
 [0.5, 0.7)
 [0.7, 1)  
 

如果二进制消息序列的输入为：10 00 11 00 10 11 01。编码时首先输入的符号是10，找到它的编码范围是[0.5, 0.7)。由于消息中第二个符号00的编码范围是[0, 1)，因此它的间隔就取[0.5, 0.7)的第一个十分之一作为新间隔[0.5, 0.52)。依此类推，编码第3个符号11时取新间隔为[0.514, 0.52)，编码第4个符号00时，取新间隔为[0.514, 0.5146)，… 。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图4-03所示。

这个例子的编码和译码的全过程分别表示在表4-05和表4-06中。根据上面所举的例子，可把计算过程总结如下。


 考虑一个有M个符号ai(i=1, …，M)的字符表集，假设概率p(ai)=pi，而= p1 + p2 + … + pM =1。输入符号用xn表示，第n个子间隔的范围用In=[ln , rn)=[ln-1 + , ln-1+ )表示，其中，和，ln表示间隔左边界的值, rn表示间隔右边界的值，表示间隔长度。编码过程如下：
 
 步骤1：首先在1和0之间给每个符号分配一个初始子间隔，子间隔的长度等于它的概率，初始子间隔的范围用I1＝[l1，r1)= [，)表示。令，和。
 
 步骤2：L和R的二进制表达式分别表示为：
 

和
其中和等于“1”或者“0”。

 比较u1和v1：①如果u1 ?v1，不发送任何数据，转到步骤3；②如果u1＝v1，就发送二进制符号u1。
 
 比较u2和v2：①如果u2 ?v2，不发送任何数据，转到步骤3；②如果u2＝v2，就发送二进制符号u1。
 

…

这种比较一直进行到两个符号不相同为止，然后进入步骤3，

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

 
令L＝ln，R＝rn和dn= rn-ln，然后转到步骤2。

表4-05 编码过程

步骤  
 输入
符号
 编码间隔  
 编码判决
 
1
 10
 [0.5, 0.7) 符号的间隔范围[0.5, 0.7)  
2
 00
 [0.5, 0.52) [0.5, 0.7)间隔的第一个1/10
3
 11
 [0.514, 0.52) [0.5, 0.52)间隔的最后一个1/10
4
 00
 [0.514, 0.5146) [0.514, 0.52)间隔的第一个1/10
5
 10
 [0.5143, 0.51442) [0.514, 0.5146)间隔的第五个1/10开始，二个1/10
6
 11
 [0.514384, 0.51442) [0.5143, 0.51442)间隔的最后3个1/10
7
 01
 [0.5143836, 0.514402) [0.514384, 0.51442)间隔的4个1/10，从第1个1/10开始
8
 从[0.5143876, 0.514402中选择一个数作为输出：0.5143876
 

表4-06 译码过程

步骤  
 间隔
 译码符号  
 译码判决  
 
1
 [0.5, 0.7) 10
 0.51439在间隔 [0.5, 0.7)
2
 [0.5, 0.52) 00
 0.51439在间隔 [0.5, 0.7)的第1个1/10
3
 [0.514, 0.52) 11
 0.51439在间隔[0.5, 0.52)的第7个1/10
4
 [0.514, 0.5146) 00
 0.51439在间隔[0.514, 0.52)的第1个1/10
5
 [0.5143, 0.51442) 10
 0.51439在间隔[0.514, 0.5146)的第5个1/10
6
 [0.514384, 0.51442) 11
 0.51439在间隔[0.5143, 0.51442)的第7个1/10
7
 [0.51439, 0.5143948) 01
 0.51439在间隔[0.51439, 0.5143948)的第1个1/10
7
 译码的消息：10 00 11 00 10 11 01
 

例2：假设有4个符号的信源，它门的概率如表4-07所示：

表4-07 符号概率

信源符号ai
 a1
 a2
 a3
 a4
 
概率pi
 p1=0.5 p2=0.25 p3=0.125 p4=0.125
初始编码间隔
 [0, 0.5) [0.5, 0.75) [0.75, 0.875) [0.875, 1)

输入序列为xn：a2，a1，a3，…。它的编码过程如图4-04所示，现说明如下。

输入第1个符号是x1=a2，可知i=2，定义初始间隔I1＝[l1，r1)= [，)＝[0.5, 0.75)，由此可知d1=0.25，左右边界的二进制数分别表示为：L＝0.5=0.1(B)，R＝0.7＝0.11… (B) 。按照步骤2，u1=v1，发送1。因u2?v2，因此转到步骤3。