哈夫曼解压缩算法

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

这是本人写的动态哈夫曼压缩算法实现，压缩与解压缩时，
根据文件内容自动生成哈夫曼树，并动态调整节点的权重
和树的形状。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==================

祝你好运！

Ⅱ 跪求哈夫曼编码压缩与其它压缩算法的比较（复杂性和压缩效果）

（1）所形成的Huffman编码的码字是不是唯一的，但是可以被指定为唯一的编码效率为“1”大，小的是“0”时，两个最小概率符号赋值。反之也可以。如果两个符号的发生的概率是相等的，排列无论前面是可能的，所以霍夫曼码字的结构不是唯一的，对于相同的信息源，不管如何在上述的顺序安排的，它的平均码字长度是不改变，因此，编码效率是独一无二的。
（2）只有当不均匀时，每个符号的信息源的发生的概率，霍夫曼编码的效果是唯一明显的。
（3）霍夫曼编码必须是精确的原始文件中的各符号的发生频率的统计数据，并且如果没有准确的统计数据，压缩将低于预期。 Huffman编码通常必须经过两道，第一遍统计的第二次产生编码，编码速度是比较慢的。电路的复杂性的另一种实现的各种长度的编码，解码处理是相对复杂的，因此，解压缩处理是相对缓慢。
（4）Huffman编码只能使用整数来表示一个符号，而不是使用小数，这在很大程度上限制了压缩效果。
（5）霍夫曼是所有的位，如果改变其中一个可以使数据看起来完全不同

Ⅲ 如何用哈夫曼编码实现英文文本的压缩和解压缩

哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。有人用C函数写了这个编码，见下面链接

http://ke..com/view/189694.htm

Ⅳ 如何写压缩软件，运用哈夫曼算法实现

到文件压缩大家很容易想到的就是rar,zip等我们常见的压缩格式。然而，还有一种就是大家在学习数据结构最常见到的哈夫曼树的数据结构，以前还不知道他又什么用，其实他最大的用途就是用来做压缩，也是一些rar,zip压缩的祖先，称为哈弗曼压缩（什么你不知道谁是哈弗曼，也不知道哈弗曼压缩，不急等下介绍）。

随着网络与多媒体技术的兴起，人们需要存储和传输的数据越来越多，数据量越来越大，以前带宽有限的传输网络和容量有限的存储介质难以满足用户的需求。

特别是声音、图像和视频等媒体在人们的日常生活和工作中的地位日益突出，这个问题越发显得严重和迫切。如今，数据压缩技术早已是多媒体领域中的关键技术之一。

一、什么是哈弗曼压缩

Huffman(哈夫曼)算法在上世纪五十年代初提出来了，它是一种无损压缩方法，在压缩过程中不会丢失信息熵，而且可以证明Huffman算法在无损压缩算法中是最优的。Huffman原理简单，实现起来也不困难，在现在的主流压缩软件得到了广泛的应用。对应用程序、重要资料等绝对不允许信息丢失的压缩场合，Huffman算法是非常好的选择。

二、怎么实现哈弗曼压缩

哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。

故我们得了解几个概念：

1、二叉树：在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。2、哈夫曼编码(Huffman Coding)：是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。三、哈夫曼编码生成步骤：

①扫描要压缩的文件，对字符出现的频率进行计算。

②把字符按出现的频率进行排序，组成一个队列。

③把出现频率最低（权值）的两个字符作为叶子节点，它们的权值之和为根节点组成一棵树。

④把上面叶子节点的两个字符从队列中移除，并把它们组成的根节点加入到队列。

⑤把队列重新进行排序。重复步骤③④⑤直到队列中只有一个节点为止。

⑥把这棵树上的根节点定义为0（可自行定义0或1）左边为0，右边为1。这样就可以得到每个叶子节点的哈夫曼编码了。

既如 (a)、(b)、(c)、(d)几个图，就可以将离散型的数据转化为树型的了。

如果假设树的左边用0表示右边用1表示，则每一个数可以用一个01串表示出来。

则可以得到对应的编码如下：
1-->110
2-->111
3-->10
4-->0
每一个01串，既为每一个数字的哈弗曼编码。
为什么能压缩：
压缩的时候当我们遇到了文本中的1、2、3、4几个字符的时候，我们不用原来的存储，而是转化为用它们的01串来存储不久是能减小了空间占用了吗。（什么01串不是比原来的字符还多了吗？怎么减少？）大家应该知道的，计算机中我们存储一个int型数据的时候一般式占用了2^32-1个01位，因为计算机中所有的数据都是最后转化为二进制位去存储的。所以，想想我们的编码不就是只含有0和1嘛，因此我们就直接将编码按照计算机的存储规则用位的方法写入进去就能实现压缩了。
比如：
1这个数字，用整数写进计算机硬盘去存储，占用了2^32-1个二进制位
而如果用它的哈弗曼编码去存储，只有110三个二进制位。
效果显而易见。

Ⅳ 求助：用java实现哈夫曼编码压缩与解压缩算法。

你好，由于内容比较多，先概述一下先。如图所示，为我写的一个压缩软件，原理是利用哈弗曼算法实现的。我将资料整理好稍后就发到你邮箱，但在这里简要说明一下代码。

请看我的空间

http://hi..com/%D2%B6%BF%C6%C1%BC/blog

中的文章共5篇（太长了）

http://hi..com/%D2%B6%BF%C6%C1%BC/blog/item/93c35517bb528146f2de32fd.html

1.HuffmanTextEncoder类完成压缩功能，可直接运行，压缩测试用文本文件。

2.HuffmanTextDecoder类完成解压缩功能，可直接运行，解压缩压缩后的文本文件。

3.BitReader,工具类，实现对BufferedInputStream的按位读取。

4.BitWriter,工具类，实现按位写入的功能。该类来自网络。

5.MinHeap<T>,模板工具类，实现了一个最小堆。生成Huffman树时使用。

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

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

Ⅶ 哈夫曼压缩算法的内容是什么

注:哈夫曼和lzss算法不是同一种算法,先用哈夫曼再用lzss算法压缩后会发现经哈夫曼压缩后再用lzss压缩文件会变大,具体原因不明
lzss原理:
把编码位置置于输入数据流的开始位置。
在前向缓冲器中查找窗口中最长的匹配串
①
pointer
：=匹配串指针。
②
length
：=匹配串长度。
判断匹配串长度length是否大于等于最小匹配串长度(min_length)
，
如果“是”：输出指针，然后把编码位置向前移动length个字符。
如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。
如果前向缓冲器不是空的，就返回到步骤2。
例：编码字符串如表03-05-3所示，编码过程如表03-05-4所示。现说明如下：
“步骤”栏表示编码步骤。
“位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。
“匹配”栏表示窗口中找到的最长的匹配串。
“字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。
“输出”栏的输出为：
①
如果匹配串本身的长度length
>=
min_length，输出指向匹配串的指针，格式为(back_chars，
chars_length)。该指针告诉译码器“在这个窗口中向后退back_chars个字符然后拷贝chars_length个字符到输出”。
②
如果匹配串本身的长度length
>=
min_length，则输出真实的匹配串。
表:输入数据流
位置
1234567891011
字符
aabbcbbaabc
表:编码过程(min_length
=
2)
步骤位置匹配串输出
11--a
22aa
33--
b
44bb
55--c
66b
b(3,2)
78
a
a
b(7,3)
811cc

Ⅷ 如何用哈夫曼算法实现简单的文件压缩

我使用两种方法从zip文件中读取数据，第一种的代码是从“UTF开始”到“UTF结束”，看到有人（http://www.csdn.net/develop/article/6839.shtm）介绍过这种用法，但是我用的时候，出现java.io.UTFDateFormatException异常，我跟踪调试的时候，发现问题出现在读取的时候，写是可以的。
第二种的代码是从“int开始”到“int结束”，可以正确解压缩各种文件（二进制读取，应该也没问题的），但是速度很慢，请问各位大虾，有没有什么办法解决？
代码如下：
……
String doc="";
zin = new ZipInputStream(new FileInputStream(待解压缩文件));
while(((entry = zin.getNextEntry()) != null)&&!entry.isDirectory())
{
FileOutputStream fout =
new FileOutputStream(解压缩后的文件名);
DataOutputStream dout = new DataOutputStream(fout);
DataInputStream in = new DataInputStream(zin);
/*
//UTF开始
doc=in.readUTF();
in.close();
dout.writeUTF(doc);
dout.close();
//UTF结束
*/
//int开始
int c;
while((c = in.read()) != -1)
dout.write(c);
dout.close();
//int结束
fout.close();
zin.closeEntry();
System.out.println("Close entry successful!");
}
zin.close();
……

Ⅸ 哈夫曼编码的压缩实现

压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点：
CHuffmanNode nodes[511];
for(int nCount = 0; nCount < 256; nCount++)
nodes[nCount].byAscii = nCount;
其次，计算在输入缓冲区数据中，每个ASCII码出现的频率：
for(nCount = 0; nCount < nSrcLen; nCount++)
nodes[pSrc[nCount]].nFrequency++;
然后，根据频率进行排序：
qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);
哈夫曼树，获取每个ASCII码对应的位序列：
int nNodeCount = GetHuffmanTree(nodes); 构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点（树根）。
// parent node
pNode = &nodes[nParentNode++];
// pop first child
pNode->pLeft = PopNode(pNodes, nBackNode--, false);
// pop second child
pNode->pRight = PopNode(pNodes, nBackNode--, true);
// adjust parent of the two poped nodes
pNode->pLeft->pParent = pNode->pRight->pParent = pNode;
// adjust parent frequency
pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency; 有一个好的诀窍来避免使用任何队列组件。ASCII码只有256个，但实际分配了511个(CHuffmanNode nodes[511])，前255个记录ASCII码，而用后255个记录哈夫曼树中的父节点。并且在构造树的时候只使用一个指针数组(ChuffmanNode *pNodes[256])来指向这些节点。同样使用两个变量来操作队列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。
接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中：
int nDesIndex = 0;
// loop to write codes
for(nCount = 0; nCount < nSrcLen; nCount++)
{
*(DWORD*)(pDesPtr+(nDesIndex>>3)) |=
nodes[pSrc[nCount]].dwCode << (nDesIndex&7);
nDesIndex += nodes[pSrc[nCount]].nCodeLength;
}
(nDesIndex>>3): >>3 以8位为界限右移后到达右边字节的前面
(nDesIndex&7): &7 得到最高位.
此外，在压缩缓冲区中，必须保存哈夫曼树的节点以及位序列，这样才能在解压缩时重新构造哈夫曼树（只需保存ASCII值和对应的位序列）。 解压缩比构造哈夫曼树要简单的多，将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住，这里的输入缓冲区是一个包含每个ASCII值的编码的位流。因此，为了用ASCII值替换编码，我们必须用位流搜索哈夫曼树，直到发现一个叶节点，然后将它的ASCII值添加到输出缓冲区中：
int nDesIndex = 0;
DWORD nCode;
while(nDesIndex < nDesLen)
{
nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
pNode = pRoot;
while(pNode->pLeft)
{
pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
nCode >>= 1;
nSrcIndex++;
}
pDes[nDesIndex++] = pNode->byAscii;
}

Ⅹ 霍夫曼 解压缩

哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。 例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

本文描述在网上能够找到的最简单，最快速的哈夫曼编码。本方法不使用任何扩展动态库，比如STL或者组件。只使用简单的C函数，比如：memset，memmove，qsort，malloc，realloc和memcpy。
因此，大家都会发现，理解甚至修改这个编码都是很容易的。

背景
哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。
编码使用
我用简单的C函数写这个编码是为了让它在任何地方使用都会比较方便。你可以将他们放到类中，或者直接使用这个函数。并且我使用了简单的格式，仅仅输入输出缓冲区，而不象其它文章中那样，输入输出文件。
bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);
bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);
要点说明
速度
为了让它(huffman.cpp)快速运行，我花了很长时间。同时，我没有使用任何动态库，比如STL或者MFC。它压缩1M数据少于100ms（P3处理器，主频1G）。
压缩
压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点：
CHuffmanNode nodes[511];
for(int nCount = 0; nCount < 256; nCount++)
nodes[nCount].byAscii = nCount;
然后，计算在输入缓冲区数据中，每个ASCII码出现的频率：
for(nCount = 0; nCount < nSrcLen; nCount++)
nodes[pSrc[nCount]].nFrequency++;
然后，根据频率进行排序：
qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);
现在，构造哈夫曼树，获取每个ASCII码对应的位序列：
int nNodeCount = GetHuffmanTree(nodes);
构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点（树根）。
// parent node
pNode = &nodes[nParentNode++];
// pop first child
pNode->pLeft = PopNode(pNodes, nBackNode--, false);
// pop second child
pNode->pRight = PopNode(pNodes, nBackNode--, true);
// adjust parent of the two poped nodes
pNode->pLeft->pParent = pNode->pRight->pParent = pNode;
// adjust parent frequency
pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency;
这里我用了一个好的诀窍来避免使用任何队列组件。我先前就直到ASCII码只有256个，但我分配了511个(CHuffmanNode nodes[511])，前255个记录ASCII码，而用后255个记录哈夫曼树中的父节点。并且在构造树的时候只使用一个指针数组(ChuffmanNode *pNodes[256])来指向这些节点。同样使用两个变量来操作队列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。
接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中：
int nDesIndex = 0;
// loop to write codes
for(nCount = 0; nCount < nSrcLen; nCount++)
{
*(DWORD*)(pDesPtr+(nDesIndex>>3)) |=
nodes[pSrc[nCount]].dwCode << (nDesIndex&7);
nDesIndex += nodes[pSrc[nCount]].nCodeLength;
}
(nDesIndex>>3): >>3 以8位为界限右移后到达右边字节的前面
(nDesIndex&7): &7 得到最高位.
注意：在压缩缓冲区中，我们必须保存哈夫曼树的节点以及位序列，这样我们才能在解压缩时重新构造哈夫曼树（只需保存ASCII值和对应的位序列）。
解压缩
解压缩比构造哈夫曼树要简单的多，将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住，这里的输入缓冲区是一个包含每个ASCII值的编码的位流。因此，为了用ASCII值替换编码，我们必须用位流搜索哈夫曼树，直到发现一个叶节点，然后将它的ASCII值添加到输出缓冲区中：
int nDesIndex = 0;
DWORD nCode;
while(nDesIndex < nDesLen)
{
nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
pNode = pRoot;
while(pNode->pLeft)
{
pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
nCode >>= 1;
nSrcIndex++;
}
pDes[nDesIndex++] = pNode->byAscii;
}