霍夫曼编码——现代压缩算法的灵魂我来我网·5come5 Forum

本页主题: 霍夫曼编码——现代压缩算法的灵魂	隐藏签名 \| 打印 \| 加为IE收藏 \| 收藏主题 \| 上一主题 \| 下一主题

一切随心

∷ 性别:

∷ 状态:

∷ 等级: 荣誉会员

∷ 发贴: 3407

∷ 威望: 3

∷ 浮云: 706

∷ 在线等级:

∷ 注册时间: 2003-10-27

∷ 最后登陆: 2008-02-29

【复制此帖地址只看此人回复】

5come5帮你背单词 [ neighbour /'neibə/ n. 邻居；v. 邻近，邻接 ]

霍夫曼编码——现代压缩算法的灵魂

来自：http://artpro.533.net/compress/default.htm

第一课：建立Huffman树

--------------------------------------------------------------------------------

Huffman码是属于不等长码，是文件压缩的一种重要方式，其中大家最熟悉的WinZip就用到了Huffman编码，常常在商用压缩程序中，Huffman编码结合其他压缩编码算法一起使用。
在图象压缩（例如JPEG、GIF格式）、声音压缩、一般的文件压缩（例WinZip）中，Huffman编码得到广泛的使用，另外一个方面，Huffman编码是电子、通讯、信息等相关专业的大学生/研究生的专业基础课的一个重要组成部分。
如果你希望看懂Linux内核，首先遇到的内核的解压缩就用到Huffman编码...
（在www.yahoo.com上用Huffman关键字查询得到90600个结果，很可惜，在新浪网上只能得到87条网页信息）

在RFC（Request For Comments：请求注解，属Internet国际标准(草案)）中，其RFC1950、RFC1951、RFC1952 是有关在Internet传输过程中进行文件压缩的标准，其中，首先提到Huffman编码，Huffman码是属于不等长码，是文件压缩的一种重要方式，其中大家最熟悉的Winzip就用到了Huffman编码，常常在商用压缩程序中，Huffman编码结合其他压缩编码算法一起使用，听说学完文件的压缩方法以后你的C语言和数据结构会有很大的进步，第一课我感到非常有趣，以下是我第一课的程序，我费了好大劲才搞懂，我的老师在给我讲解以后，又让我重作了一遍。

今天完成了建立Huffman树和Huffman码，虽然只有4个子函数，但涉及的内容却很广泛，其中涉及到C语言中最难理解的程序嵌套、双重循环和“树”的存储结构在《数据结构》课程中的实现方法，我的老师说，以下的这些算法算是经典程序中最优秀的一部分了，理解这些程序对理解Huffman编码有很多好处。

以下为我写的程序（具体细节以后有时间再慢慢讲解）：

头文件"huffman.h"

typedef struct tree_node
{
unsigned int count;
unsigned int saved_count;
int child0;
int child1;
}NODE;
typedef struct code
{
int code;
int bits;
}CODE;

void Gzip(FILE *fi,FILE *fo);
void BuildTree();
void FindMin(int i);
void tree_to_code(unsigned int code_so_far,int bits,int node);
void print_code(int bits,int code);

程序main.c

#include <stdio.h>
#include "huffman.h"
void main(int argc,char *argv[])
{
int i;
FILE *f,*f1;
printf("%d\n",argc);
for(i=0;i<argc;i++)
printf("%s\n",argv);
if(argc<=1)
return;
f=fopen(argv[1],"r");
if(f==NULL)
return;
/* f1=fopen(argv[2],"w");
if(f1==NULL)
return;*/
Gzip(f,f1);
fclose(f);
// fclose(f1);
}

程序 Huffman.c

#include <stdio.h>
#include "huffman.h"
NODE nodes[514];
CODE codes[257];
unsigned int min_1,min_2;
int root;
void Gzip(FILE *fi,FILE *fo)
{
int c;
while((c=fgetc(fi))!=EOF)
nodes[c].count++;
nodes[256].count=1;
nodes[513].count=0xffffffff;
BuildTree();
tree_to_code(0,0,root);
for(c=0;c<257;c++)
{
if(codes[c].bits!=0)
{
printf("%d ->",c);
print_code(codes[c].bits,codes[c].code);
printf("\n");
}
}
}

void print_code(int bits,int code)
{
int i;
int mask=1<<(bits-1);
for(i=0;i<bits;i++)
{
if((code&mask)==0)
putchar('0');
else
putchar('1');
mask>>=1;
}
}

void BuildTree()
{
int i;
for(i=256;i<514;i++)
{
FindMin(i);
if(min_2==513)
break;
}
root=min_1;
}
void FindMin(int k)
{
int i;
min_1=513;
min_2=513;
for(i=0;i<=k;i++)
{
if(nodes.count==0)
continue;
if(nodes.count<nodes[min_1].count)
{
min_2=min_1;
min_1=i;
}
else if(nodes.count<nodes[min_2].count)
min_2=i;
}
if(min_2==513)
return;
nodes[k+1].count=nodes[min_1].count+nodes[min_2].count;
nodes[min_1].saved_count=nodes[min_1].count;
nodes[min_2].saved_count=nodes[min_2].count;
nodes[k+1].child0=min_1;
nodes[k+1].child1=min_2;
nodes[min_1].count=0;
nodes[min_2].count=0;
}

void tree_to_code(unsigned int code_so_far,int bits,int node)
{
if(node <= 256)
{
codes[node].code=code_so_far;
codes[node].bits=bits;
return;
}
code_so_far<<=1;
bits++;
tree_to_code(code_so_far,bits,nodes[node].child0);
tree_to_code(code_so_far|1,bits,nodes[node].child1);
}

(按此下载执行文件huffman.exe，在运行时分别打印出0-255和256（End_of_file）的Huffman码)，使用方法：
在DOS下键入：

c:\> huffman file

其中file表示你需要对之编码的文件。本程序输出针对本文件得到的最优Huffman编码。

例如，针对某一ASCII文件trees.c我得到的输出是：
9 ->1101100010
10 ->00111
32 ->01
33 ->11011011110
34 ->111010111
35 ->1111111010
36 ->00000100010010
37 ->1110111011
38 ->1101100011
39 ->110110111110
40 ->1111011
41 ->1111100
42 ->101101
43 ->11101000
44 ->1111010
45 ->1011100
46 ->11101001
47 ->1110110
48 ->10110011
49 ->10100111
50 ->101001101
51 ->001101010
52 ->11111011000
53 ->1110111110
54 ->1011001001
55 ->1010011000
56 ->1101100000
57 ->00000100001
58 ->1101100001
59 ->1111110
60 ->111011100
61 ->1001
62 ->0000011
63 ->1110101100001
64 ->111010110000000
65 ->110110010
66 ->000001001
67 ->111010101
68 ->111010100
69 ->10111010
70 ->1111111011
71 ->11111011001
72 ->1101101110
73 ->101100101
74 ->00000100010011
75 ->00000100000
76 ->111110101
77 ->1110111010
78 ->1111101101
79 ->110110110
80 ->10110010001
82 ->1110111111
83 ->00000101
84 ->00110100
85 ->11101011001
87 ->000001000101
88 ->10110010000
89 ->11101011000001
90 ->00000100011
91 ->10110000
92 ->1110101101
93 ->10110001
95 ->110111
97 ->10000
98 ->001100
99 ->111100
100 ->00011
101 ->1100
102 ->101000
103 ->11111111
104 ->101111
105 ->10101
106 ->111010110001
107 ->110110011
108 ->00010
109 ->0011011
110 ->11010
111 ->10001
112 ->1010010
113 ->001101011
114 ->00001
115 ->11100
116 ->0010
117 ->000000
118 ->11011010
119 ->111110100
120 ->10111011
121 ->111111100
122 ->1010011001
123 ->111110111
124 ->110110111111
125 ->111011110
126 ->0000010001000
256 ->111010110000001

[ 此贴被一切随心在2006-01-02 20:45重新编辑 ]

Posted: 2006-01-02 20:24 | [楼主]

一切随心

∷ 性别:

∷ 状态:

∷ 等级: 荣誉会员

∷ 发贴: 3407

∷ 威望: 3

∷ 浮云: 706

∷ 在线等级:

∷ 注册时间: 2003-10-27

∷ 最后登陆: 2008-02-29

【复制此帖地址只看此人回复】

5come5帮你背单词 [ barrier /'bæriə/ n. 障碍(物)，栅栏 ]

第二课：Huffman编码

--------------------------------------------------------------------------------

补充了第一课的Huffman编码程序，变成以下的内容，这样，利用此程序就可以利用Huffman编码进行文件压缩了，但是，仅仅这样还不是一个完整的压缩程序，为了能够与商用压缩程序相媲美，就要好好研究一下文章“Info-ZIP note 981119”了，我正在对这篇文章进行研究，相信不久你就可以在我的网页上看到与商用压缩程序相媲美，与Winzip兼容的压缩程序了。

关于我作的Huffman编码其源代码如下：

文件Huffman.cpp

#include <stdio.h>
#include "huffman.h"
NODE nodes[514];
CODE codes[257];
unsigned int min_1,min_2;
int root;
int useable=0,x=0;

void Gzip(FILE *fi,FILE *fo)
{
int c;
while((c=fgetc(fi))!=EOF)
nodes[c].count++;
nodes[256].count=1;
nodes[513].count=0xffffffff;
BuildTree();
tree_to_code(0,0,root);
encode(fi,fo);
writeCode(fo,codes[256].code,codes[256].bits);
writeCode(fo,0,8-useable);
}

void writeCode(FILE* f,int code,int bits)
{
int y;
useable+=bits;
x<<=bits;
x+=code;
if(useable>=8)
{
y=x>>(useable-8);
y=y&0xff;
putc(y,f);
useable-=8;
}
}

void encode(FILE *fi,FILE* fo)
{
int c;
rewind(fi);
while((c=fgetc(fi))!=EOF)
writeCode(fo,codes[c].code,codes[c].bits);
}

void print_code(int bits,int code)
{
int i;
int mask=1<<(bits-1);
for(i=0;i<bits;i++)
{
if((code&mask)==0)
putchar('0');
else
putchar('1');
mask>>=1;
}
}

void BuildTree()
{
int i;
for(i=256;i<514;i++)
{
FindMin(i);
if(min_2==513)
break;
}
root=min_1;
}
void FindMin(int k)
{
int i;
min_1=513;
min_2=513;
for(i=0;i<=k;i++)
{
if(nodes.count==0)
continue;
if(nodes.count<nodes[min_1].count)
{
min_2=min_1;
min_1=i;
}
else if(nodes.count<nodes[min_2].count)
min_2=i;
}
if(min_2==513)
return;
nodes[k+1].count=nodes[min_1].count+nodes[min_2].count;
nodes[min_1].saved_count=nodes[min_1].count;
nodes[min_2].saved_count=nodes[min_2].count;
nodes[k+1].child0=min_1;
nodes[k+1].child1=min_2;
nodes[min_1].count=0;
nodes[min_2].count=0;
}

void tree_to_code(unsigned int code_so_far,int bits,int node)
{
if(node <= 256)
{
codes[node].code=code_so_far;
codes[node].bits=bits;
return;
}
code_so_far<<=1;
bits++;
tree_to_code(code_so_far,bits,nodes[node].child0);
tree_to_code(code_so_far|1,bits,nodes[node].child1);
}

--------------------------------------------------------------------------------

Posted: 2006-01-02 20:45 | [1 楼]

一切随心

∷ 性别:

∷ 状态:

∷ 等级: 荣誉会员

∷ 发贴: 3407

∷ 威望: 3

∷ 浮云: 706

∷ 在线等级:

∷ 注册时间: 2003-10-27

∷ 最后登陆: 2008-02-29

【复制此帖地址只看此人回复】

5come5帮你背单词 [ communism /'komjunizəm/ n. 共产主义 ]

第三章奇妙的二叉树：Huffman的贡献

(摘自http://artpro.533.net/compress/Chapter3.htm)

--------------------------------------------------------------------------------

提起 Huffman 这个名字，程序员们至少会联想到二叉树和二进制编码。的确，我们总以 Huffman 编码来概括 D.A.Huffman 个人对计算机领域特别是数据压缩领域的杰出贡献。我们知道，压缩 = 模型 + 编码，作为一种压缩方法，我们必须全面考虑其模型和编码两个模块的功效；但同时，模型和编码两个模块又相互具有[屏蔽]性。举例来说，一个使用 Huffman 编码方法的程序，完全可以采用不同的模型来统计字符在信息中出现的概率。因此，我们这一章将首先围绕 Huffman 先生最为重要的贡献 —— Huffman 编码展开讨论，随后，我们再具体介绍可以和 Huffman 联合使用的概率模型。

为什么是二叉树

为什么压缩领域中的编码方法总和二叉树联系在一起呢？原因非常简单，回忆一下我们介绍过的“前缀编码”：为了使用不固定的码长表示单个字符，编码必须符合“前缀编码”的要求，即较短的编码决不能是较长编码的前缀。要构造符合这一要求的二进制编码体系，二叉树是最理想的选择。考察下面这棵二叉树：

根(root)
0 | 1
+------+------+
0 | 1 0 | 1
+-----+-----+ +---+----+
| | | |
a | d e
0 | 1
+-----+-----+
| |
b c
要编码的字符总是出现在树叶上，假定从根向树叶行走的过程中，左转为0，右转为1，则一个字符的编码就是从根走到该字符所在树叶的路径。正因为字符只能出现在树叶上，任何一个字符的路径都不会是另一字符路径的前缀路径，符合要求的前缀编码也就构造成功了：

a - 00 b - 010 c - 011 d - 10 e - 11
Shannon-Fano 编码

进入 Huffman 先生构造的神奇二叉树之前，我们先来看一下它的前身，由 Claude Shannon 和 R.M.Fano 两人提出的 Shannon-Fano 编码。

讨论之前，我们假定要编码字符的出现概率已经由某一模型统计出来，例如，对下面这串出现了五种字符的信息( 40 个字符长 ):

cabcedeacacdeddaaabaababaaabbacdebaceada
五种字符的出现次数分别：a - 16，b - 7，c - 6，d - 6，e - 5。

Shannon-Fano 编码的核心仍然是构造二叉树，构造的方式非常简单：

1) 将给定符号按照其频率从大到小排序。对上面的例子，应该得到：

a - 16
b - 7
c - 6
d - 6
e - 5
2) 将序列分成上下两部分，使得上部频率总和尽可能接近下部频率总和。我们有：

a - 16
b - 7
-----------------
c - 6
d - 6
e - 5
3) 我们把第二步中划分出的上部作为二叉树的左子树，记 0，下部作为二叉树的右子树，记 1。

4) 分别对左右子树重复 2 3 两步，直到所有的符号都成为二叉树的树叶为止。现在我们有如下的二叉树：

根(root)
0 | 1
+------+------+
0 | 1 0 | 1
+-----+-----+ +---+----+
| | | |
a b c |
0 | 1
+-----+-----+
| |
d e
于是我们得到了此信息的编码表：

a - 00 b - 01 c - 10 d - 110 e - 111
可以将例子中的信息编码为：

cabcedeacacdeddaaabaababaaabbacdebaceada
10 00 01 10 111 110 111 00 10 00 10 ......
码长共 91 位。考虑用 ASCII 码表示上述信息需要 8 * 40 = 240 位，我们确实实现了数据压缩。

Huffman 编码

Huffman 编码构造二叉树的方法和 Shannon-Fano 正好相反，不是自上而下，而是从树叶到树根生成二叉树。现在，我们仍然使用上面的例子来学习 Huffman 编码方法。

1) 将各个符号及其出现频率分别作为不同的小二叉树（目前每棵树只有根节点）。

a(16) b(7) c(6) d(6) e(5)
2) 在 1 中得到的树林里找出频率值最小的两棵树，将他们分别作为左、右子树连成一棵大一些的二叉树，该二叉树的频率值为两棵子树频率值之和。对上面的例子，我们得到一个新的树林：

| (11)
a(16) b(7) c(6) +---+---+
| |
d e
3) 对上面得到的树林重复 2 的做法，直到所有符号都连入树中为止。这一步完成后，我们有这样的二叉树：

根(root)
0 | 1
+------+----------------+
| 0 | 1
| +---------+-----------+
| 0 | 1 0 | 1
a +-------+------+ +-------+-------+
| | | |
b c d e
由此，我们可以建立和 Shannon-Fano 编码略微不同的编码表：

a - 0 b - 100 c - 101 d - 110 e - 111
对例子中信息的编码为：

cabcedeacacdeddaaabaababaaabbacdebaceada
101 0 100 101 111 110 111 0 101 0 101 ......
码长共 88 位。这比使用 Shannon-Fano 编码要更短一点。

让我们回顾一下熵的知识，使用我们在第二章学到的计算方法，上面的例子中，每个字符的熵为：

Ea = - log2(16 / 40) = 1.322
Eb = - log2( 7 / 40) = 2.515
Ec = - log2( 6 / 40) = 2.737
Ed = - log2( 6 / 40) = 2.737
Ee = - log2( 5 / 40) = 3.000
信息的熵为：

E = Ea * 16 + Eb * 7 + Ec * 6 + Ed * 6 + Ee * 5 = 86.601
也就是说，表示该条信息最少需要 86.601 位。我们看到，Shannon-Fano 编码和 Huffman 编码都已经比较接近该信息的熵值了。同时，我们也看出，无论是 Shannon-Fano 还是 Huffman，都只能用近似的整数位来表示单个符号，而不是理想的小数位。我们可以将它们做一个对比：

符号理想位数 S-F 编码 Huffman 编码
( 熵 ) 需要位数需要位数
----------------------------------------------------
a 1.322 2 1
b 2.515 2 3
c 2.737 2 3
d 2.737 3 3
e 3.000 3 3
----------------------------------------------------
总计 86。601 91 88
这就是象 Huffman 这样的整数位编码方式无法达到最理想的压缩效果的原因。

为 Huffman 编码选择模型（附范式 Huffman 编码）

最简单，最容易被 Huffman 编码利用的模型是“静态统计模型”，也就是说在编码前统计要编码的信息中所有字符的出现频率，让后根据统计出的信息建立编码树，进行编码。这种模型的缺点是显而易见的：首先，对数据量较大的信息，静态统计要消耗大量的时间；其次，必须保存统计出的结果以便解码时构造相同的编码树，或者直接保存编码树本身，而且，对于每次静态统计，都有不同的结果，必须分别予以保存，这要消耗大量的空间（这意味着压缩效率的下降）；再次，事实上，即使不将编码树计算在内，对通常含有 0 - 255 字符集的计算机文件来说，静态统计模型统计出的频率是字符在整个文件中的出现频率，往往反映不出字符在文件中不同局部出现频率的变化情况，使用这一频率进行压缩，大多数情况下得不到太好压缩效果，文件有时甚至在压缩后反而增大了。所以，“静态统计模型”一般仅作为复杂算法的某一部分出现，在信息的某一局部完成压缩功能。我们很难将其用于[屏蔽]的压缩系统。

有一种有效的“静态统计模型”的替代方案，如果我们要压缩的所有信息具有某些共同的特性，也即在分布上存在着共同的特征，比如我们要压缩的是普通的英文文本，那么，字母 a 或者字母 e 的出现频率应当是大致稳定的。使用语言学家事先已经建立好的字母频率表来进行压缩和解压缩，不但不用保存多份统计信息，而且一般说来对该类文件有着较好的压缩效果。这种方案除了适应性不太强以外，偶尔还会有一些尴尬的时候。读一遍下面这段话：

If Youth，throughout all history， had had a champion to stand up for it； to show a doubting world that a child can think；and， possibly， do it practically； you wouldn't constantly run across folks today who claim that "a child don't know anything." - Gadsby by E.V.Wright, 1939.

发现什么问题了吗？哦，整段话中竟没有出现一次英文中出现频率最高的字母 e ！真让人惊讶，但没有办法，事先拟定的频率分布总有意外的时候。

对英文或中文文本，有一种比较实用的静态模型：不是把字符而是把英文单词或中文词语作为统计频率和编码的单位进行压缩。也就是说，每次编码的不再是 a b c 这样的单个符号，而是 the look flower 这样的单词。这种压缩方式可以达到相当不错的压缩效果，并被广泛地用于全文检索系统。

对基于词的编码方式，需要解决几个技术难点。首先是分词的问题，英文单词可以由词间空格分隔，但中文怎么办呢？其实，有很多中文分词算法可以解决这个问题，本书就不再详细介绍了。王笨笨就曾开发过一个不错的分词模块，但希望通过收取一定报酬的方式提供该模块，如有需要，请和王笨笨 E-Mail 联系。一旦我们将词语分离出来，我们就可以对每个词进行频率统计，然后建立 Huffman 编码树，输出编码时，一个编码将代替一个词语。但要注意，英文和汉语的单词数量都在几万到十几万左右，也就是说，我们的 Huffman 编码树将拥有十几万个叶子节点，这对于一棵树来说太大太大了，系统将无力承担所需要的资源，这怎么办呢？我们可以暂时抛开树结构，采用另一种构造 Huffman 编码的方式——范式 Huffman 编码。

范式 Huffman 编码(Canonical Huffman Code)的基本思路是：并非只有使用二叉树建立的前缀编码才是 Huffman 编码，只要符合(1)是前缀编码(2)某一字符编码长度和使用二叉树建立的该字符的编码长度相同这两个条件的编码都可以叫做 Huffman 编码。考虑对下面六个单词的编码：

符号出现次数传统 Huffman 编码范式 Huffman 编码
------------------------------------------------------------
单词1 10 000 000
单词2 11 001 001
单词3 12 100 010
单词4 13 101 011
单词5 22 01 10
单词6 23 11 11
注意到范式 Huffman 编码的独特之处了吗？你无法使用二叉树来建立这组编码，但这组编码确实能起到和 Huffman 编码相同的作用。而且，范式 Huffman 编码具有一个明显的特点：当我们把要编码的符号按照其频率从小到大排列时，如果把范式 Huffman 编码本身作为单词的话，也呈现出从小到大的字典顺序。

构造范式 Huffman 编码的方法大致是：

1) 统计每个要编码符号的频率。

2) 根据这些频率信息求出该符号在传统 Huffman 编码树中的深度（也就是表示该符号所需要的位数 - 编码长度）。因为我们关心的仅仅是该符号在树中的深度，我们完全没有必要构造二叉树，仅用一个数组就可以模拟二叉树的创建过程并得到符号的深度，具体方法这里就不详述了。

3) 分别统计从最大编码长度 maxlength 到 1 的每个长度对应了多少个符号。根据这一信息从 maxlength 个 0 开始以递增顺序为每个符号分配编码。例如，编码长度为 5 的符号有 4 个，长度为 3 的有 1 个，长度为 2 的有 3 个，则分配的编码依次为： 00000 00001 00010 00011 001 01 10 11

4) 编码输出压缩信息，并保存按照频率顺序排列的符号表，然后保存每组同样长度编码中的最前一个编码以及该组中的编码个数。

现在完全可以不依赖任何树结构进行高速解压缩了。而且在整个压缩、解压缩过程中需要的空间比传统 Huffman 编码少得多。

最后要提到的是，Huffman 编码可以采用自适应模型，根据已经编码的符号频率决定下一个符号的编码。这时，我们无需为解压缩预先保存任何信息，整个编码是在压缩和解压缩过程中动态创建的，而且自适应编码由于其符号频率是根据信息内容的变化动态得到的，更符合符号的局部分布规律，因此在压缩效果上比静态模型好许多。但是，采用自适应模型必须考虑编码表的动态特性，即编码表必须可以随时更新以适应符号频率的变化。对于 Huffman 编码来说，我们很难建立能够随时更新的二叉树，使用范式 Huffman 编码是个不错的选择，但依然存在不少技术上的难题。幸好，如果愿意的话，我们可以暂时不考虑自适应模型的 Huffman 编码，因为对于自适应模型我们还有许多更好的选择，下面几章将要谈到的算术编码、字典编码等更为适合采用自适应模型，我们将在其中深入探讨自适应模型的各种实现方法。

--------------------------------------------------------------------------------

Posted: 2006-01-02 20:45 | [2 楼]

一切随心

∷ 性别:

∷ 状态:

∷ 等级: 荣誉会员

∷ 发贴: 3407

∷ 威望: 3

∷ 浮云: 706

∷ 在线等级:

∷ 注册时间: 2003-10-27

∷ 最后登陆: 2008-02-29

【复制此帖地址只看此人回复】

5come5帮你背单词 [ feeling /'fi:liŋ/ n. 感情，感觉，知觉 ]

第五章聪明的以色列人(上)：LZ77

(摘自http://artpro.533.net/compress/Chapter3.htm)

--------------------------------------------------------------------------------

全新的思路

我们在第三和第四章中讨论的压缩模型都是基于对信息中单个字符出现频率的统计而设计的，直到 70 年代末期，这种思路在数据压缩领域一直占据着统治地位。在我们今天看来，这种情形在某种程度上显得有些可笑，但事情就是这样，一旦某项技术在某一领域形成了惯例，人们就很难创造出在思路上与其大相径庭的哪怕是更简单更实用的技术来。

我们敬佩那两个在数据压缩领域做出了杰出贡献的以色列人，因为正是他们打破了 Huffman 编码一统天下的格局，带给了我们既高效又简便的“字典模型”。至今，几乎我们日常使用的所有通用压缩工具，象 ARJ，PKZip，WinZip，LHArc，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR……甚至许多硬件如网络设备中内置的压缩算法，无一例外，都可以最终归结为这两个以色列人的杰出贡献。

说起来，字典模型的思路相当简单，我们日常生活中就经常在使用这种压缩思想。我们常常跟人说“奥运会”、“IBM”、“TCP”之类的词汇，说者和听者都明白它们指的是“奥林匹克运动会”、“国际商业机器公司”和“传输控制协议”，这实际就是信息的压缩。我们之所以可以顺利使用这种压缩方式而不产生语义上的误解，是因为在说者和听者的心中都有一个事先定义好的缩略语字典，我们在对信息进行压缩（说）和解压缩（听）的过程中都对字典进行了查询操作。字典压缩模型正是基于这一思路设计实现的。

最简单的情况是，我们拥有一本预先定义好的字典。例如，我们要对一篇中文文章进行压缩，我们手中已经有一本《现代汉语词典》。那么，我们扫描要压缩的文章，并对其中的句子进行分词操作，对每一个[屏蔽]的词语，我们在《现代汉语词典》查找它的出现位置，如果找到，我们就输出页码和该词在该页中的序号，如果没有找到，我们就输出一个新词。这就是静态字典模型的基本算法了。

你一定可以发现，静态字典模型并不是好的选择。首先，静态模型的适应性不强，我们必须为每类不同的信息建立不同的字典；其次，对静态模型，我们必须维护信息量并不算小的字典，这一额外的信息量影响了最终的压缩效果。所以，几乎所有通用的字典模型都使用了自适应的方式，也就是说，将已经编码过的信息作为字典，如果要编码的字符串曾经出现过，就输出该字符串的出现位置及长度，否则输出新的字符串。根据这一思路，你能从下面这幅图中读出其中包含的原始信息吗？

啊，对了，是“吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮”。现在你该大致明白自适应字典模型的梗概了吧。好了，下面就让我们来深入学习字典模型的第一类实现——LZ77 算法。

滑动的窗口

LZ77 算法在某种意义上又可以称为“滑动窗口压缩”，这是由于该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为术语字典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行术语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制字典的大小才能保证算法的效率；随着压缩的进程滑动字典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。

参照下图，让我们熟悉一下 LZ77 算法的基本流程。

1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。

2、输出三元符号组 ( off, len, c )。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为可匹配的长度，c 为下一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。

3、输出三元符号组 ( 0, 0, c )。其中 c 为下一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。

我们结合实例来说明。假设窗口的大小为 10 个字符，我们刚编码过的 10 个字符是：abcdbbccaa，即将编码的字符为：abaeaaabaee

我们首先发现，可以和要编码字符匹配的最长串为 ab ( off = 0, len = 2 ), ab 的下一个字符为 a，我们输出三元组：( 0, 2, a )

现在窗口向后滑动 3 个字符，窗口中的内容为：dbbccaaaba

下一个字符 e 在窗口中没有匹配，我们输出三元组：( 0, 0, e )

窗口向后滑动 1 个字符，其中内容变为：bbccaaabae

我们马上发现，要编码的 aaabae 在窗口中存在( off = 4, len = 6 )，其后的字符为 e，我们可以输出：( 4, 6, e )

这样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上述数据的压缩。

解压缩的过程十分简单，只要我们向压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符 c 输出（如果 off 和 len 都为 0 则只输出后继字符 c )即可还原出原始数据。

当然，真正实现 LZ77 算法时还有许多复杂的问题需要解决，下面我们就来对可能碰到的问题逐一加以探讨。

编码方法

我们必须精心设计三元组中每个分量的表示方法，才能达到较好的压缩效果。一般来讲，编码的设计要根据待编码的数值的分布情况而定。对于三元组的第一个分量——窗口内的偏移，通常的经验是，偏移接近窗口尾部的情况要多于接近窗口头部的情况，这是因为字符串在与其接近的位置较容易找到匹配串，但对于普通的窗口大小（例如 4096 字节）来说，偏移值基本还是均匀分布的，我们完全可以用固定的位数来表示它。

编码 off 需要的位数 bitnum = upper_bound( log2( MAX_WND_SIZE ))

由此，如果窗口大小为 4096，用 12 位就可以对偏移编码。如果窗口大小为 2048，用 11 位就可以了。复杂一点的程序考虑到在压缩开始时，窗口大小并没有达到 MAX_WND_SIZE，而是随着压缩的进行增长，因此可以根据窗口的当前大小动态计算所需要的位数，这样可以略微节省一点空间。

对于第二个分量——字符串长度，我们必须考虑到，它在大多数时候不会太大，少数情况下才会发生大字符串的匹配。显然可以使用一种变长的编码方式来表示该长度值。在前面我们已经知道，要输出变长的编码，该编码必须满足前缀编码的条件。其实 Huffman 编码也可以在此处使用，但却不是最好的选择。适用于此处的好的编码方案很多，我在这里介绍其中两种应用非常广泛的编码。

第一种叫 Golomb 编码。假设对正整数 x 进行 Golomb 编码，选择参数 m，令

b = 2m

q = INT((x - 1)/b)

r = x - qb - 1

则 x 可以被编码为两部分，第一部分是由 q 个 1 加 1 个 0 组成，第二部分为 m 位二进制数，其值为 r。我们将 m = 0, 1, 2, 3 时的 Golomb 编码表列出：

值 x m = 0 m = 1 m = 2 m = 3
-------------------------------------------------------------
1 0 0 0 0 00 0 000
2 10 0 1 0 01 0 001
3 110 10 0 0 10 0 010
4 1110 10 1 0 11 0 011
5 11110 110 0 10 00 0 100
6 111110 110 1 10 01 0 101
7 1111110 1110 0 10 10 0 110
8 11111110 1110 1 10 11 0 111
9 111111110 11110 0 110 00 10 000
从表中我们可以看出，Golomb 编码不但符合前缀编码的规律，而且可以用较少的位表示较小的 x 值，而用较长的位表示较大的 x 值。这样，如果 x 的取值倾向于比较小的数值时，Golomb 编码就可以有效地节省空间。当然，根据 x 的分布规律不同，我们可以选取不同的 m 值以达到最好的压缩效果。

对我们上面讨论的三元组 len 值，我们可以采用 Golomb 方式编码。上面的讨论中 len 可能取 0，我们只需用 len + 1 的 Golomb 编码即可。至于参数 m 的选择，一般经验是取 3 或 4 即可。

可以考虑的另一种变长前缀编码叫做 γ 编码。它也分作前后两个部分，假设对 x 编码，令 q = int( log2x )，则编码的前一部分是 q 个 1 加一个 0，后一部分是 q 位长的二进制数，其值等于 x - 2q 。γ编码表如下：

值 x γ编码
---------------------
1 0
2 10 0
3 10 1
4 110 00
5 110 01
6 110 10
7 110 11
8 1110 000
9 1110 001
其实，如果对 off 值考虑其倾向于窗口后部的规律，我们也可以采用变长的编码方法。但这种方式对窗口较小的情况改善并不明显，有时压缩效果还不如固定长编码。

对三元组的最后一个分量——字符 c，因为其分布并无规律可循，我们只能老老实实地用 8 个二进制位对其编码。

根据上面的叙述，相信你一定也能写出高效的编码和解码程序了。

另一种输出方式

LZ77 的原始算法采用三元组输出每一个匹配串及其后续字符，即使没有匹配，我们仍然需要输出一个 len = 0 的三元组来表示单个字符。试验表明，这种方式对于某些特殊情况（例如同一字符不断重复的情形）有着较好的适应能力。但对于一般数据，我们还可以设计出另外一种更为有效的输出方式：将匹配串和不能匹配的单个字符分别编码、分别输出，输出匹配串时不同时输出后续字符。

我们将每一个输出分成匹配串和单个字符两种类型，并首先输出一个二进制位对其加以区分。例如，输出 0 表示下面是一个匹配串，输出 1 表示下面是一个单个字符。

之后，如果要输出的是单个字符，我们直接输出该字符的字节值，这要用 8 个二进制位。也就是说，我们输出一个单个的字符共需要 9 个二进制位。

如果要输出的是匹配串，我们按照前面的方法依次输出 off 和 len。对 off，我们可以输出定长编码，也可以输出变长前缀码，对 len 我们输出变长前缀码。有时候我们可以对匹配长度加以限制，例如，我们可以限制最少匹配 3 个字符。因为，对于 2 个字符的匹配串，我们使用匹配串的方式输出并不一定比我们直接输出 2 个单个字符（需要 18 位）节省空间（是否节省取决于我们采用何种编码输出 off 和 len）。

这种输出方式的优点是输出单个字符的时候比较节省空间。另外，因为不强求每次都外带一个后续字符，可以适应一些较长匹配的情况。

如何查找匹配串

在滑动窗口中查找最长的匹配串，大概是 LZ77 算法中的核心问题。容易知道，LZ77 算法中空间和时间的消耗集中于对匹配串的查找算法。每次滑动窗口之后，都要进行下一个匹配串的查找，如果查找算法的时间效率在 O(n2) 或者更高，总的算法时间效率就将达到 O(n3)，这是我们无法容忍的。正常的顺序匹配算法显然无法满足我们的要求。事实上，我们有以下几种可选的方案。

1、限制可匹配字符串的最大长度（例如 20 个字节），将窗口中每一个 20 字节长的串抽取出来，按照大小顺序组织成二叉有序树。在这样的二叉有序树中进行字符串的查找，其效率是很高的。树中每一个节点大小是 20(key) + 4(off) + 4(left child) + 4(right child) = 32。树中共有 MAX_WND_SIZE - 19 个节点，假如窗口大小为 4096 字节，树的大小大约是 130k 字节。空间消耗也不算多。这种方法对匹配串长度的限制虽然影响了压缩程序对一些特殊数据（又很长的匹配串）的压缩效果，但就平均性能而言，压缩效果还是不错的。

2、将窗口中每个长度为 3 （视情况也可取 2 或 4）的字符串建立索引，先在此索引中匹配，之后对得出的每个可匹配位置进行顺序查找，直到找到最长匹配字符串。因为长度为 3 的字符串可以有 2563 种情况，我们不可能用静态数组存储该索引结构。使用 Hash 表是一个明智的选择。我们可以仅用 MAX_WND_SIZE - 1 的数组存储每个索引点，Hash 函数的参数当然是字符串本身的 3 个字符值了，Hash 函数算法及 Hash 之后的散列函数很容易设计。每个索引点之后是该字符串出现的所有位置，我们可以使用单链表来存储每一个位置。值得注意的是，对一些特殊情况比如 aaaaaa...之类的连续字串，字符串 aaa 有很多连续出现位置，但我们无需对其中的每一个位置都进行匹配，只要对最左边和最右边的位置操作就可以了。解决的办法是在链表节点中纪录相同字符连续出现的长度，对连续的出现位置不再建立新的节点。这种方法可以匹配任意长度的字符串，压缩效果要好一些，但缺点是查找耗时多于第一种方法。

3、使用字符树( trie )来对窗口内的字符串建立索引，因为字符的取值范围是 0 - 255，字符树本身的层次不可能太多，3 - 4 层之下就应该换用其他的数据结构例如 Hash 表等。这种方法可以作为第二种方法的改进算法出现，可以提高查找速度，但空间的消耗较多。

如果对窗口中的数据进行索引，就必然带来一个索引位置表示的问题，即我们在索引结构中该往偏移项中存储什么数据：首先，窗口是不断向后滑动的，我们每次将窗口向后滑动一个位置，索引结构就要作相应的更新，我们必须删除那些已经移动出窗口的数据，并增加新的索引信息。其次，窗口不断向后滑动的事实使我们无法用相对窗口左边界的偏移来表示索引位置，因为随着窗口的滑动，每个被索引的字符串相对窗口左边界的位置都在改变，我们无法承担更新所有索引位置的时间消耗。

解决这一问题的办法是，使用一种可以环形滚动的偏移系统来建立索引，而输出匹配字符串时再将环形偏移还原为相对窗口左边界的真正偏移。让我们用图形来说明，窗口刚刚达到最大时，环形偏移和原始偏移系统相同：

偏移： 0 1 2 3 4 ...... Max
|--------------------------------------------------------------|
环形偏移： 0 1 2 3 4 ...... Max
窗口向后滑动一个字节后，滑出窗口左端的环形偏移 0 被补到了窗口右端：

偏移： 0 1 2 3 4 ...... Max
|--------------------------------------------------------------|
环形偏移： 1 2 3 4 5 ...... Max 0
窗口再滑动 3 个子节后，偏移系统的情况是：

偏移： 0 1 2 3 4 ...... Max
|--------------------------------------------------------------|
环形偏移： 4 5 6 7 8...... Max 0 1 2 3
依此类推。

我们在索引结构中保存环形偏移，但在查找到匹配字符串后，输出的匹配位置 off 必须是原始偏移（相对窗口左边），这样才可以保证解码程序的顺利执行。我们用下面的代码将环形偏移还原为原始偏移：

// 由环形 off 得到真正的off(相对于窗口左边)
// 其中 nLeftOff 为当前与窗口左边对应的环形偏移值
int GetRealOff(int off)
{
if (off >= nLeftOff)
return off - nLeftOff;
else
return (_MAX_WINDOW_SIZE - (nLeftOff - off));
}
这样，解码程序无需考虑环形偏移系统就可以顺利高速解码了。

资源

结合上面的讨论，典型的 LZ77 算法应当不难实现，我们本章给出的源码是一个较为特殊的实现。

示例程序 lz77.exe 使用对匹配串和单个字符分类输出的模型，输出匹配串时，off 采用定长编码，len 采用γ编码。索引结构采用 2 字节长字符串的索引，使用 256 * 256 大小的静态数组存储索引点，每个索引点指向一个位置链表。链表节点考虑了对 aaaaa... 之类的重复串的优化。

示例程序的独特之处在于使用了 64k 大小的固定长度窗口，窗口不做滑动（因此不需要环形偏移系统，也节省了删除索引点的时间）。压缩函数每次只对最多 64k 长的数据进行压缩，主函数将原始文件分成 64k 大小的块逐个压缩存储。使用这种方法首先可以增大匹配的概率，字符串可以在 64k 空间内任意寻找最大匹配串，以此提高压缩效率。其次，这种方法有利于实现解压缩的同步。也就是说，利用这种方法分块压缩的数据，很容易从原始文件中间的任何一个位置开始解压缩，这尤其适用于全文检索系统中全文信息的保存和随机读取。

--------------------------------------------------------------------------------

Posted: 2006-01-02 20:46 | [3 楼]