利用huffman树实现文件的压缩与解压

用huffman算法实现“文件的压缩与解压”怎么做啊~

我写过一个Huffman编码，但只是生成了编码表，没做成压缩，但可以利用查表做成文件压缩，另外用的是C++，改成C的话比较容易，只要把动下内存分配就行了，想要的话,msn:softnow@sina.com

楼主可以去看看最优二叉树的编码问题。
1、哈夫曼编码
在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符，则固定编码长度为5。然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。
为使不等长编码为前缀编码，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于求出了传送报文的最短长度。因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。
哈夫曼静态编码：它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，（用4Bytes的长度存储频率值，频率值的表示范围为0--2^32-1，这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。
哈夫曼动态编码：动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。[3]
2、哈夫曼译码
在通信中，若将字符用哈夫曼编码形式发送出去，对方接收到编码后，将编码还原成字符的过程，称为哈夫曼译码。[4]

这是本人写的动态哈夫曼压缩算法实现，压缩与解压缩时，
根据文件内容自动生成哈夫曼树，并动态调整节点的权重
和树的形状。900MHZ的PIII赛扬每秒钟可以压缩的好几MB
的数据，只是压缩率不高，文本文件的压缩后容量一般可
以减少25%，比RAR差远了。

源文件共三个，你在VC6.0中新建一个空的命令行项目，
将它们加进去，编译完就可以用了。

===========hfm.cpp===================

#include <stdio.h>
#include <string.h>
#include <io.h>
#include <sys/stat.h>
#include <fcntl.h>
#include "Huffman.h"

int wh;
int rh;

bool Write(unsigned char *s,int len){
_write(wh,s,len);
return true;
}

bool OpenFile(char* source,char* target){
int w_flag=_O_WRONLY | _O_CREAT | _O_EXCL | _O_BINARY;
int r_flag=_O_RDONLY | _O_BINARY;

rh=_open(source,r_flag,_S_IREAD | _S_IWRITE);
wh=_open(target,w_flag,_S_IREAD | _S_IWRITE);

if(rh==-1 || wh==-1){
if(rh!=-1){
_close(rh);
printf("\n打开文件：'%s'失败!",target);
}
if(wh!=-1){
_close(wh);
printf("\n打开文件：'%s'失败!",source);
}

return false;
}else{
return true;
}
}

void PrintUsage(){
printf("\n以动态哈夫曼算法压缩或解压缩文件。\n\n");
printf("\thfm -?\t\t\t\t显示帮助信息\n");
printf("\thfm -e -i source -o target\t压缩文件\n");
printf("\thfm -d -i source -o target\t解压缩文件\n\n");
}

void main(int argc,char *args[]){
int mode,i,j,K=0;
char src[4096];
char target[4096];
unsigned char buffer[BUFFER_SIZE];
Huffman *h;

mode=0;
for(i=1;i<argc;i++){
if(args[i][0]=='-' || args[i][0]=='/'){
switch(args[i][1]){
case '?':
mode=0;//帮助
break;
case 'e':
case 'E':
mode=1;//压缩
break;
case 'd':
case 'D':
mode=2;//解压缩
break;
case 'o':
case 'O':
if(i+1>=argc){
mode=0;
}else{//输出文件
j=0;
while(args[i+1][j]!='\0' && j<4096){
target[j++]=args[i+1][j];
}
if(j==4096){
mode=0;
}else{
target[j]='\0';
K |= 1;
}
}
break;
case 'i':
case 'I':
if(i+1>=argc){
mode=0;
}else{//输入文件
j=0;
while(args[i+1][j]!='\0' && j<4096){
src[j++]=args[i+1][j];
}
if(j==4096){
mode=0;
}else{
src[j]='\0';
K |=2;
}
}
break;
}
}
}

if(K!=3)mode=0;

switch(mode){
case 0:
PrintUsage();
return;
case 1://压缩
if(!OpenFile(src,target))return;
h=new Huffman(&Write,true);
i=BUFFER_SIZE;
while(i==BUFFER_SIZE){
i=_read(rh,buffer,BUFFER_SIZE);
h->Encode(buffer,i);
}
delete h;
_close(rh);
_close(wh);
printf("压缩完毕!");
break;
case 2://解压缩
if(!OpenFile(src,target))return;
h=new Huffman(&Write,false);
i=BUFFER_SIZE;
while(i==BUFFER_SIZE){
i=_read(rh,buffer,BUFFER_SIZE);
h->Decode(buffer,i);
}
delete h;
_close(rh);
_close(wh);
printf("解压缩完毕!");
break;
}

}

=======end of hfm.cpp=======================

=======Huffman.cpp=============================
// Huffman.cpp: implementation of the Huffman class.
//
//////////////////////////////////////////////////////////////////////

#include "Huffman.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Huffman::Huffman(Output *output,bool mode)
{
Hbtree *tmp;
int i;

this->mode=mode;

//设置输出函数，当缓冲区满时，将调用该函数输出
this->output=output;

//初始化列表
for(i=0;i<LIST_LENGTH;i++)this->list[i]=NULL;

//初始化哈夫曼树
this->root=this->NewNode(NOT_CHAR,LEFT,NULL);
this->current=this->root;
tmp=this->NewNode(CODE_ESCAPE,RIGHT,root);
tmp->count=1;
tmp=this->NewNode(CODE_FINISH,LEFT,root);
tmp->count=0;
root->count=root->child[LEFT]->count+root->child[RIGHT]->count;

//设置缓冲区指针
this->char_top=BOTTOM_BIT;
this->bit_top=TOP_BIT;
this->buffer[0]=0;

//重构哈夫曼树的最大计数值
this->max_count=MAX_COUNT;
this->shrink_factor=SHRINK_FACTOR;
this->finished=false;
}

Huffman::~Huffman()
{
if(this->mode==true){//如果是编码
//输出结束码
this->OutputEncode(CODE_FINISH);
this->char_top++;
}

//强制清空缓冲区
this->Flush();

//释放空间
this->ReleaseNode(this->root);
}

Hbtree * Huffman::NewNode(int value, int index, Hbtree *parent)
{
Hbtree *tmp=new Hbtree;
tmp->parent=parent;
tmp->child[0]=NULL;
tmp->child[1]=NULL;
tmp->count=(1 << SHRINK_FACTOR);
tmp->index=(index==0) ? 0 : 1;
tmp->value=value;

if(value!=NOT_CHAR)this->list[tmp->value]=tmp;
if(parent!=NULL)parent->child[tmp->index]=tmp;
return tmp;
}

void Huffman::ReleaseNode(Hbtree *node)
{
if(node!=NULL){
this->ReleaseNode(node->child[LEFT]);
this->ReleaseNode(node->child[RIGHT]);
delete node;
}
}

//输出一位编码
int Huffman::OutputBit(int bit)
{
unsigned char candidates[]={1,2,4,8,16,32,64,128};

if(bit!=0)
this->buffer[this->char_top] |= candidates[this->bit_top];
this->bit_top--;
if(this->bit_top < BOTTOM_BIT){
this->bit_top=TOP_BIT;
this->char_top++;

if(this->char_top >= BUFFER_SIZE){//输出缓冲区
this->output(this->buffer,BUFFER_SIZE);
this->char_top=0;
}

this->buffer[this->char_top]=0;
}
return 0;
}

//输出缓冲区
int Huffman::Flush()
{
this->output(this->buffer,this->char_top);
this->char_top=0;
return 0;
}

int Huffman::Encode(unsigned char c)
{
int value=c,
candidates[]={128,64,32,16,8,4,2,1},
i;

if(this->list[value]==NULL){//字符不存在于哈夫曼树中
//输出转义码
this->OutputEncode(CODE_ESCAPE);
//输出字符
for(i=0;i<8;i++)this->OutputBit(value & candidates[i]);

this->InsertNewNode(value);

}else{
//输出字符编码
this->OutputEncode(value);

//重新调整哈夫曼树
this->BalanceNode(this->list[value]->parent);
}

//重组哈夫曼树
if(this->root->count>=this->max_count)
this->RearrangeTree();

return 0;
}

void Huffman::BalanceNode(Hbtree *node)
{
Hbtree *parent,*child,*brother;
int i,j;

parent=node->parent;
if(parent==NULL)return;//根节点无需调整

if(node->value==NOT_CHAR){//非叶子节点
child=node->child[LEFT]->count > node->child[RIGHT]->count ?
node->child[LEFT] : node->child[RIGHT];

if(child->count > parent->count - node->count){
//失衡

i=!(node->index);
j=child->index;
node->count=parent->count - child->count;
brother=parent->child[i];

node->child[j]=brother;
brother->index=j;
brother->parent=node;

parent->child[i]=child;
child->index=i;
child->parent=parent;
}
}
this->BalanceNode(parent);
}

//输出一个字符的编码
int Huffman::OutputEncode(int value)
{
int stack[CODE_FINISH+2],top=0;
Hbtree *tmp=this->list[value];

//输出编码
if(value<=MAX_VALUE){//字符
while(tmp!=NULL){
stack[top++]=tmp->index;
tmp->count++;
tmp=tmp->parent;
}
}else{//控制码
while(tmp!=NULL){
stack[top++]=tmp->index;
tmp=tmp->parent;
}
}
top--;
while(top>0){
this->OutputBit(stack[--top]);
}

return 0;
}

void Huffman::PrintNode(Hbtree *node,int level)
{
int i;
if(node){
for(i=0;i<level*3;i++)printf(" ");
printf("%p P:%p L:%p R:%p C:%d",node,node->parent,node->child[0],node->child[1],node->count);
if(node->value!=NOT_CHAR)printf(" V:%d",node->value);
printf("\n");

this->PrintNode(node->child[LEFT],level+1);
this->PrintNode(node->child[RIGHT],level+1);
}
}

int Huffman::Encode(unsigned char *s, int len)
{
int i;
for(i=0;i<len;i++)this->Encode(s[i]);
return 0;
}

void Huffman::PrintTree()
{
this->PrintNode(this->root,0);
}

int Huffman::RecountNode(Hbtree *node)
{
if(node->value!=NOT_CHAR)return node->count;
node->count=
this->RecountNode(node->child[LEFT]) +
this->RecountNode(node->child[RIGHT]);
return node->count;
}

void Huffman::RearrangeTree()
{
int i,j,k;
Hbtree *tmp,*tmp2;

//所有非控制码的计数值右移shrink_factor位，并删除计数值为零的节点
for(k=0;k<=MAX_VALUE;k++){
if(this->list[k]!=NULL){
tmp=this->list[k];
tmp->count >>= this->shrink_factor;
if(tmp->count ==0){
this->list[k]=NULL;
tmp2=tmp->parent;
i=tmp2->index;
j=!(tmp->index);
if(tmp2->parent!=NULL){
tmp2->parent->child[i]=tmp2->child[j];
tmp2->child[j]->parent=tmp2->parent;
tmp2->child[j]->index=i;
}else{
this->root=tmp2->child[j];
this->current=this->root;
this->root->parent=NULL;
}
delete tmp;
delete tmp2;
}
}
}

//重新计数
this->RecountNode(this->root);

//重新调整平衡
for(i=0;i<=MAX_VALUE;i++){
if(this->list[i]!=NULL)
this->BalanceNode(this->list[i]->parent);
}
}

void Huffman::InsertNewNode(int value)
{
int i;
Hbtree *tmp,*tmp2;

//将字符加入哈夫曼树
tmp2=this->list[CODE_FINISH];
tmp=this->NewNode(NOT_CHAR, tmp2->index, tmp2->parent);
tmp->child[LEFT]=tmp2;
tmp2->index=LEFT;
tmp2->parent=tmp;

tmp2=this->NewNode(value,RIGHT,tmp);
tmp->count=tmp->child[LEFT]->count+tmp->child[RIGHT]->count;
i=tmp2->count;
while((tmp=tmp->parent)!=NULL)tmp->count+=i;
//从底向上调整哈夫曼树
this->BalanceNode(tmp2->parent);
}

int Huffman::Decode(unsigned char c)
{
this->Decode(c,7);
return 0;
}

int Huffman::Decode(unsigned char *s,int len)
{
int i;
for(i=0;i<len;i++)this->Decode(s[i]);
return 0;
}

int Huffman::Decode(unsigned char c, int start)
{
int value=c,
candidates[]={1,2,4,8,16,32,64,128},
i,j;
Hbtree *tmp;

if(this->finished)return 0;

i=start;
if(this->current==NULL){//转义状态下
while(this->remain >= 0 && i>=0){
if((candidates[i] & value) !=0){
this->literal |= candidates[this->remain];
}
this->remain--;
i--;
}

if(this->remain < 0){//字符输出完毕

//输出字符
this->OutputChar(this->literal);
//将字符插入哈夫曼树
this->InsertNewNode(literal);
//重组哈夫曼树
if(this->root->count>=this->max_count)
this->RearrangeTree();

//设置环境
this->current=this->root;
}
}else{
j=((value & candidates[i])!=0)?1:0;
tmp=this->current->child[j];
i--;
while(tmp->value==NOT_CHAR && i>=0){
j=((value & candidates[i])!=0)?1:0;
tmp=tmp->child[j];
i--;
}

if(tmp->value==NOT_CHAR){//中间节点
this->current=tmp;
}else{
if(tmp->value<=MAX_VALUE){//编码内容
j=tmp->value;
this->OutputChar((unsigned char)j);

//修改计数器
tmp=this->list[j];
while(tmp!=NULL){
tmp->count++;
tmp=tmp->parent;
}
//调整平衡度
this->BalanceNode(this->list[j]->parent);

//重组哈夫曼树
if(this->root->count>=this->max_count)
this->RearrangeTree();

//设置环境
this->current=this->root;
}else{
if(tmp->value==CODE_ESCAPE){//转义码
this->current=NULL;
this->remain=7;
this->literal=0;
}else{//结束码
this->finished=true;
return 0;
}
}
}

}

if(i>=0)this->Decode(c,i);
return 0;
}

int Huffman::OutputChar(unsigned char c)
{
this->buffer[this->char_top++]=c;
if(this->char_top>=BUFFER_SIZE){//输出缓冲区
this->output(this->buffer,BUFFER_SIZE);
this->char_top=0;
}
return 0;
}

========end of Huffman.cpp==================

========Huffman.h============================
// Huffman.h: interface for the Huffman class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(NULL)
#include <stdio.h>
#endif

#if !defined(AFX_HUFFMAN_H__B1F1A5A6_FB57_49B2_BB67_6D1764CC04AB__INCLUDED_)
#define AFX_HUFFMAN_H__B1F1A5A6_FB57_49B2_BB67_6D1764CC04AB__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#define MAX_COUNT 65536 //最大计数值，大于此值时
#define MAX_VALUE 255 //编码的最大值
#define CODE_ESCAPE MAX_VALUE+1 //转义码
#define CODE_FINISH MAX_VALUE+2 //结束码
#define LIST_LENGTH MAX_VALUE+3 //编码列表长度
#define SHRINK_FACTOR 2 //减小的比例，通过右移位实现
#define LEFT 0 //左孩子索引
#define RIGHT 1 //右孩子索引
#define NOT_CHAR -1 //非字符

#define TOP_BIT 7 //字符最高位
#define BOTTOM_BIT 0 //字符最低位
#define BUFFER_SIZE 81920 //缓冲区大小

//输出函数
typedef bool (Output)(unsigned char *s,int len);

//哈夫曼树的节点定义
typedef struct Hnode{
int count;//计数器
int index;//父节点的孩子索引（0--左孩子，1--右孩子）
Hnode* child[2];
Hnode* parent;
int value;
}Hbtree;

class Huffman
{
private:
//输出一个解码的字符
int OutputChar(unsigned char c);
//从指定位置开始解码
int Decode(unsigned char c,int start);
//插入一个新节点
void InsertNewNode(int value);
//重新调整哈夫曼树构型
void RearrangeTree();
//对各节点重新计数
int RecountNode(Hbtree *node);
//打印哈夫曼树节点
void PrintNode(Hbtree *node,int level);
//输出一个值的编码
int OutputEncode(int value);
//调节哈夫曼树节点使之平衡
void BalanceNode(Hbtree *node);
//输出一位编码
int OutputBit(int bit);
//释放哈夫曼树节点
void ReleaseNode(Hbtree *node);
//新建一个节点
Hbtree *NewNode(int value,int index, Hbtree *parent);
//输出函数地址
Output *output;
//哈夫曼树根地址
Hbtree *root;
//哈夫曼编码单元列表
Hbtree *list[LIST_LENGTH];
//输出缓冲区
unsigned char buffer[BUFFER_SIZE];
//缓冲区顶
int char_top,bit_top;
//收缩哈夫曼树参数
int max_count,shrink_factor;
//工作模式，true--编码，false--解码
bool mode;
//解码的当前节点
Hbtree *current;
int remain;//当前字符剩余的位数
unsigned char literal;//按位输出的字符
bool finished;

public:

//解码指定长度的字符串
int Decode(unsigned char *s,int len);
//解码一个字符
int Decode(unsigned char c);
//打印哈夫曼树
void PrintTree();
//编码指定长度的字符串
int Encode(unsigned char *s,int len);
//编码一个字符
int Encode(unsigned char c);
//清空缓冲区
int Flush();

//output指输出函数，mode指工作模式，true--编码，false--解码
Huffman(Output *output,bool mode);

//析构函数
virtual ~Huffman();
};

#endif // !defined(AFX_HUFFMAN_H__B1F1A5A6_FB57_49B2_BB67_6D1764CC04AB__INCLUDED_)

================end of Huffman.h==================

祝你好运！

---

嵊州市18362379132： 用Huffman编码压缩文件的思路,以及应该怎么做? - ？
禹侮滋阴： 我讲一下我的思路: 用java的字节流读取一个文件,假设这个文件是100字节的. int b; FileInputStream in = new FileInputStream(＂文件路径＂); while((b = in.read()) != -1){...}这样便得到100个整形(0~255)的数.然后按照huffman的思想是统计每个数在这100个出现的概率,然后将最小的两个概率合起来作为两个叶子结点......一直做下去,直至生成一棵数.

嵊州市18362379132： 如何用哈夫曼算法实现简单的文件压缩? - ？
禹侮滋阴： 我使用两种方法从zip文件中读取数据,第一种的代码是从“UTF开始”到“UTF结束”,看到有人(http://www.csdn.net/develop/article/6839.shtm)介绍过这种用法,但是我用的时候,出现java.io.UTFDateFormatException异常,我跟踪调试的...

嵊州市18362379132： 哈夫曼编码法的压缩和解压缩怎么实现? - ？
禹侮滋阴： 建立一棵赫夫曼树,设每个父节点的左子节点为1,右子节点为0,然后由根节点到所要编码的字符的叶节点的路径确定字符的编码.比如要编码a,假设a在第三层,则由根节点到a的路径为:根节点——右子节点(0)——左子节点(1).那么a的编码就为01.就这样把所有字符进行编码,建立一个赫夫曼编码表.利用这个编码表把字符串编码就是压缩了,解压缩就是把参照赫夫曼编码表把编码转为字符串.

嵊州市18362379132： 如何用哈夫曼编码实现英文文本的压缩和解压缩? - ？
禹侮滋阴： 哈夫曼压缩是个无损的压缩算法,一般用来压缩文本和程序文件.哈夫曼压缩属于可变代码长度算法一族.意思是个体符号(例如,文本文件中的字符)用一个特定长度的位序列替代.因此,在文件中出现频率高的符号,使用短的位序列,而那些很少出现的符号,则用较长的位序列.有人用C函数写了这个编码,见下面链接http://baike.baidu.com/view/189694.htm

嵊州市18362379132： 如何写压缩软件,运用哈夫曼算法实现 - ？
禹侮滋阴： 到文件压缩大家很容易想到的就是rar,zip等我们常见的压缩格式.然而,还有一种就是大家在学习数据结构最常见到的哈夫曼树的数据结构,以前还不知道他又什么用,其实他最大的用途就是用来做压缩,也是一些rar,zip压缩的祖先,称为哈弗...

嵊州市18362379132： 哈夫曼编码的压缩实现 - ？
禹侮滋阴： 压缩代码非常简单,首先用ASCII值初始化511个哈夫曼节点: CHuffmanNode nodes[511]; for(int nCount = 0; nCount < 256; nCount++) nodes[nCount].byAscii = nCount; 其次,计算在输入缓冲区数据中,每个ASCII码出现的频率: for(nCount = ...

嵊州市18362379132： 用哈夫曼树算法设计对文件文件的压缩和解压缩的实验程序解析 - ？
禹侮滋阴： 楼主可以去看看最优二叉树的编码问题. 1、哈夫曼编码 在数据通信中,需要将传送的文字转换成二进制的字符串,用0,1码的不同排列来表示字符.例如,需传送的报文为“AFTER DATA EAR ARE ART AREA”,这里用到的字符集为“A,E,R...

嵊州市18362379132： 请教 设计一算法 利用哈弗曼编码简易压缩一文档？
禹侮滋阴： 压缩:扫描一遍,得到频率统计,构造出编码树扫描第二遍,对每个字符按对应的编码输出,记住输出的是二进制的编码而不是ASCII码解压:由huffman树的性质,可以根据编码树构造有限状态机,然后扫描一遍就出来了.

嵊州市18362379132： 利用哈夫曼编码进行压缩压缩率一般达到多少? - ？
禹侮滋阴： 哈夫曼编码进行压缩的压缩率是根据平均码长来计算的,压缩率比较低. 例如:用三位二进行数进行的等长编码平均长度为3,而根据哈夫曼树编码的平均码长为: 4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87...

嵊州市18362379132： 用哈夫曼树算法设计对文件文件的压缩和解压缩的程序怎么写? - ？
禹侮滋阴： #include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>struct head{ unsigned char b; /*the charactor*/ long count; /*the frequency*/ long parent,lch,rch; /*make a tree*/ char bits[256]; /*the haffuman code*/}header[512],tmp;void ...