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

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

一切随心

∷ 性别:

∷ 状态:

∷ 等级: 荣誉会员

∷ 发贴: 3407

∷ 威望: 3

∷ 浮云: 706

∷ 在线等级:

∷ 注册时间: 2003-10-27

∷ 最后登陆: 2008-02-29

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

5come5帮你背单词 [ adhere /əd'hiə/ vi. 粘着；坚持，遵守，依附，追随 ]

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

来自：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重新编辑 ]