「哈夫曼算法解压缩java」基于哈夫曼编码的文件压缩及解压缩
本篇文章给大家谈谈哈夫曼算法解压缩java，以及基于哈夫曼编码的文件压缩及解压缩对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
- 1、利用huffman树实现文件的压缩与解压
- 2、算法解析：哈夫曼（huffman）压缩算法
- 3、用huffman算法实现“文件的压缩与解压”怎么做啊
- 4、求助：用java实现哈夫曼编码压缩与解压缩算法。
利用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;iargc;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' j4096){
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' j4096){
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;iLIST_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;i8;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(top0){
this-OutputBit(stack[--top]);
}
return 0;
}
void Huffman::PrintNode(Hbtree *node,int level)
{
int i;
if(node){
for(i=0;ilevel*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;ilen;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;ilen;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==================
祝你好运！
算法解析：哈夫曼（huffman）压缩算法
本篇将介绍 哈夫曼压缩算法（Huffman compression）
众所周知，计算机存储数据时，实际上存储的是一堆0和1（二进制）。
如果我们存储一段字符：ABRACADABRA!
那么计算机会把它们逐一翻译成二进制，如A：01000001；B: 01000010; !: 00001010.
每个字符占8个bits, 这一整段字符则至少占12*8=96 bits。
但如果我们用一些特殊的值来代表这些字符，如：
图中，0代表A; 1111代表B；等等。此时，存储这段字符只需30bits，比96bits小多了，达到了压缩的目的。
我们需要这么一个表格来把原数据翻译成特别的、占空间较少的数据。同时，我们也可以用这个表格，把特别的数据还原成原数据。
首先，为了避免翻译歧义，这个表格需满足一个条件： 任何一个字符用的值都不能是其它字符的前缀 。
我们举个反例：A: 0; B: 01;这里，A的值是B的值的前缀。如果压缩后的数据为01xxxxxx,x为0或者1，那么这个数据应该翻译成A1xxxxxx, 还是Bxxxxxxx?这样就会造成歧义。
然后，不同的表格会有不同的压缩效果，如：
这个表格的压缩效果更好。
那么我们如何找到 最好的表格 呢？这个我们稍后再讲。
为了方便阅读，这个表格是可以写成一棵树的：
这棵树的节点左边是0，右边是1。任何含有字符的节点都没有非空子节点。（即上文提及的前缀问题。）
这棵树是在压缩的过程中建成的，这个表格是在树形成后建成的。用这个表格，我们可以很简单地把一段字符变成压缩后的数据，如：
原数据：ABRACADABRA!
表格如上图。
令压缩后的数据为S；
第一个字符是A，根据表格，A：11，故S=11;
第二个字符是B，根据表格，B：00，故S=1100;
第三个字符是R，根据表格，R：011，故S=1100011;
如此类推，读完所有字符为止。
压缩搞定了，那解压呢？很简单，跟着这棵树读就行了：
压缩后的数据S=11000111101011100110001111101
记住，读到1时，往右走，读到0时，往左走。
令解压后的字符串为D；
从根节点出发，第一个数是1，往右走：
第二个数是1，往右走：
读到有字符的节点，返回此字符，加到字符串D里。D:A;
返回根节点，继续读。
第三个数是0，往左走：
第四个数是0，往左走：
读到有字符的节点，返回此字符，加到字符串D里。D:AB;
返回根节点，继续读。
第五个数是0，往左走：
第六个数是1，往右走：
第七个数是1，往右走：
读到有字符的节点，返回此字符，加到字符串D里。D:ABR;
返回根节点，继续读。
如此类推，直到读完所有压缩后的数据S为止。
压缩与解压都搞定了之后 我们需要先把原数据读一遍，并把每个字符出现的次数记录下来。如：
ABRACADABRA!中，A出现了5次;B出现了2次;C出现了1次;D出现了1次;R出现了2次;!出现了1次。
理论上，出现频率越高的字符，我们给它一个占用空间越小的值，这样，我们就可以有最佳的压缩率
由于哈夫曼压缩算法这块涉及内容较多 ，文章篇幅很长；全文全方面讲解了Compose布局的各方面知识。更多Android前言技术进阶，我自荐一套《 完整的Android的资料，以及一些视频课讲解 》 现在私信发送“进阶”或者“笔记”即可免费获取
最后我想说：
对于程序员来说，要学习的知识内容、技术有太多太多，要想不被环境淘汰就只有不断提升自己，从来都是我们去适应环境，而不是环境来适应我们
技术是无止境的，你需要对自己提交的每一行代码、使用的每一个工具负责，不断挖掘其底层原理，才能使自己的技术升华到更高的层面
Android 架构师之路还很漫长，与君共勉
用huffman算法实现“文件的压缩与解压”怎么做啊
我写过一个Huffman编码，但只是生成了编码表，没做成压缩，但可以利用查表做成文件压缩，另外用的是C++，改成C的话比较容易，只要把动下内存分配就行了，想要的话,msn:softnow@sina.com
求助：用java实现哈夫曼编码压缩与解压缩算法。
你好，由于内容比较多，先概述一下先。如图所示，为我写的一个压缩软件，原理是利用哈弗曼算法实现的。我将资料整理好稍后就发到你邮箱，但在这里简要说明一下代码。
请看我的空间
中的文章共5篇（太长了）
1.HuffmanTextEncoder类完成压缩功能，可直接运行，压缩测试用文本文件。
2.HuffmanTextDecoder类完成解压缩功能，可直接运行，解压缩 压缩后的文本文件。
3.BitReader,工具类，实现对BufferedInputStream的按位读取。
4.BitWriter,工具类，实现按位写入的功能。该类来自网络。
5.MinHeapT ,模板工具类，实现了一个最小堆。生成Huffman树时使用。
哈夫曼算法解压缩java的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于基于哈夫曼编码的文件压缩及解压缩、哈夫曼算法解压缩java的信息别忘了在本站进行查找喔。