java哈夫曼压缩

Ⅰ 怎样使用哈夫曼树编写一段程序实现对信息编码的压缩我要代码，谢谢了！

/**********************************************************************
*Name:哈夫曼编码源代码
*实现过程：着先通过HuffmanTree()函数构造哈夫曼树，然后在主函数main()中
*自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在
*父结点左侧，则置码为0,若在右侧,则置码为1。最后输出生成的编码。
************************************************************************/
#include<stdio.h>
#include<stdlib.h>

#defineMAXBIT100
#defineMAXVALUE10000
#defineMAXLEAF30
#defineMAXNODEMAXLEAF*2-1

typedef侍迹struct
{
intbit[MAXBIT];
intstart;
}HCodeType;/*编码结构体*/
typedefstruct
{
intweight;
intparent;
int敬谈或lchild;
intrchild;
intvalue;
}HNodeType;/*结点结构体*/

/*构造一颗哈夫曼树*/
voidHuffmanTree(HNodeTypeHuffNode[MAXNODE],intn)
{
/*i、j：循环变量，m1、m2：构造哈夫曼树不同过亮伍程中两个最小权值结点的权值，
x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
inti,j,m1,m2,x1,x2;
/*初始化存放哈夫曼树数组HuffNode[]中的结点*/
for(i=0;i<2*n-1;i++)
{
HuffNode[i].weight=0;//权值
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
HuffNode[i].value=i;//实际值，可根据情况替换为字母
}/*endfor*/

/*输入n个叶子结点的权值*/
for(i=0;i<n;i++)
{
printf("Pleaseinputweightofleafnode%d:
",i);
scanf("%d",&HuffNode[i].weight);
}/*endfor*/

/*循环构造Huffman树*/
for(i=0;i<n-1;i++)
{
m1=m2=MAXVALUE;/*m1、m2中存放两个无父结点且结点权值最小的两个结点*/
x1=x2=0;
/*找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树*/
for(j=0;j<n+i;j++)
{
if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
elseif(HuffNode[j].weight<m2&&HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
}/*endfor*/
/*设置找到的两个子结点x1、x2的父结点信息*/
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;

printf("x1.weightandx2.weightinround%d:%d,%d
",i+1,HuffNode[x1].weight,HuffNode[x2].weight);/*用于测试*/
printf("
");
}/*endfor*/
/*for(i=0;i<n+2;i++)
{
printf("Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d
",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
}*///测试
}/*endHuffmanTree*/

//解码
voiddecodeing(charstring[],HNodeTypeBuf[],intNum)
{
inti,tmp=0,code[1024];
intm=2*Num-1;
char*nump;
charnum[1024];
for(i=0;i<strlen(string);i++)
{
if(string[i]=='0')
num[i]=0;
else
num[i]=1;
}
i=0;
nump=&num[0];

while(nump<(&num[strlen(string)]))
{tmp=m-1;
while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
{

if(*nump==0)
{
tmp=Buf[tmp].lchild;
}
elsetmp=Buf[tmp].rchild;
nump++;

}

printf("%d",Buf[tmp].value);
}


}


intmain(void)
{

HNodeTypeHuffNode[MAXNODE];/*定义一个结点结构体数组*/
HCodeTypeHuffCode[MAXLEAF],cd;/*定义一个编码结构体数组，同时定义一个临时变量来存放求解编码时的信息*/
inti,j,c,p,n;
charpp[100];
printf("Pleaseinputn:
");
scanf("%d",&n);
HuffmanTree(HuffNode,n);


for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=HuffNode[c].parent;
while(p!=-1)/*父结点存在*/
{
if(HuffNode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;/*求编码的低一位*/
c=p;
p=HuffNode[c].parent;/*设置下一循环条件*/
}/*endwhile*/

/*保存求出的每个叶结点的哈夫曼编码和编码的起始位*/
for(j=cd.start+1;j<n;j++)
{HuffCode[i].bit[j]=cd.bit[j];}
HuffCode[i].start=cd.start;
}/*endfor*/

/*输出已保存好的所有存在编码的哈夫曼编码*/
for(i=0;i<n;i++)
{
printf("%d'sHuffmancodeis:",i);
for(j=HuffCode[i].start+1;j<n;j++)
{
printf("%d",HuffCode[i].bit[j]);
}
printf("start:%d",HuffCode[i].start);

printf("
");

}
printf("Decoding?PleaseEntercode:
");
scanf("%s",&pp);
decodeing(pp,HuffNode,n);
getch();
return0;
}

Ⅱ 哈夫曼树

转自： http://blog.csdn.net/hikvision_java_gyh/article/details/8952596
哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1 L1+W2 L2+W3 L3+...+ Wn Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。【例】给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为: (a)WPL=7 2+5 2+2 2+4 2=36 (b)WPL=7 3+5 3+2 1+4 2=46 (c)WPL=7 1+5 2+2 3+4 3=35其中(c)树的WPL最小，可以验证，它就是哈夫曼树。

构造哈夫曼树的算法如下： 1）对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,..., Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。 2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 4）重复2）和3），直到集合F中只有一棵二叉树为止。 例如，对于4个权值为1、3、5、7的节点构造一棵哈夫曼树，其构造过程如下图所示：

可以计算得到该哈夫曼树的路径长度WPL＝(1+3) 3+2 5+1*7=26。
哈夫曼编码应用 大数据 量的图像信息会给存储器的存储容量，通信干线信道的带宽，以及计算机的处理速度增加极大的压力。单纯靠增加存储器容量，提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的，这时就要考虑压缩。压缩的关键在于编码，如果在对数据进行编码时，对于常见的数据，编码器输出较短的码字；而对于少见的数据则用较长的码字表示，就能够实现压缩。【例】：假设一个文件中出现了8种符号S0，SQ，S2，S3，S4，S5，S6，S7，那么每种符号要编码，至少需要3bit。假设编码成 000，001， 010，011，100，101，110，111。那么符号序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1编码后变成 ，共用了42bit。我们发现S0，S1，S2这3个符号出现的频率比较大，其它符号出现的频率比较小，我们采用这样的编码方案：S0到S7的码辽分别01，11，101，0000，0001，0010，0011， 100，那么上述符号序列变成，共用了39bit。尽管有些码字如 S3，S4，S5，S6变长了(由3位变成4位)，但使用频繁的几个码字如S0，S1变短了，所以实现了压缩。对于上述的编码可能导致解码出现非单值性：比如说，如果S0的码字为01，S2的码字为011，那么当序列中出现011时，你不知道是S0的码字后面跟了个1，还是完整的一个S2的码字。因此，编码必须保证较短的编码决不能是较长编码的前缀。符合这种要求的编码称之为前缀编码。要构造符合这样的二进制编码体系，可以通过二叉树来实现。以下是哈夫曼树的 Java 实现：
[java] view plain

// 二叉树节点
public class Node implements Comparable { private int value; private Node leftChild; private Node rightChild; public Node(int value) { this.value = value; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public Node getLeftChild() { return leftChild; } public void setLeftChild(Node leftChild) { this.leftChild = leftChild; } public Node getRightChild() { return rightChild; } public void setRightChild(Node rightChild) { this.rightChild = rightChild; } public int compareTo(Object o) { Node that = (Node) o; double result = this.value - that.value; return result > 0 ? 1 : result == 0 ? 0 : -1; } }

private static Node build(List<Node> nodes) {
nodes = new ArrayList<Node>(nodes);
sortList(nodes);
while (nodes.size() > 1) {
createAndReplace(nodes);
}
return nodes.get(0);
}

/**

/**

private static void sortList(List<Node> nodes) {
Collections.sort(nodes);
}

`
/**

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

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

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

Ⅳ 哈夫曼实现压缩

我的作业，哈弗曼树的建立，不过那个字符的频率要自己编的。
//main.cpp
#include"HuffmanTree.h"
#include<string.h>
#include<stdlib.h>
//#include<iostream>

//using namespace std;

int main(){

HuffmanTree huftree;
char Choose;
while(1){
cout<<"\n\n**********************欢迎使用哈夫曼编码/译码系统**********************\n"<<endl<<endl;
cout<<" 您可以进行以下操作:\n";
cout<<" 1 建立哈夫曼树\n";
cout<<" 2 编码(源文已在文件ToBeTran中，或键盘输入)\n";
cout<<" 3 译码(码文已在文件CodeFile中)\n";
cout<<" 4 显示码文\n";
cout<<" 5 显示哈夫曼树\n";
cout<<" 6 退出\n\n";

cout<<" 请选择一个操作:";
cin>>Choose;
switch(Choose)
{
case '1':
huftree.CreateHuffmanTree();
break;
case '2':
huftree.Encoder();
break;
case '3':
huftree.Decoder();
break;
case '4':
huftree.PrintCodeFile();
break;
case '5':
huftree.PrintHuffmanTree();
break;
case '6':
cout<<"\n**********************感谢使用本系统!*******************\n\n";
system("pause");
return 0;
}//switch
}//while
}//main

//Huffmannode.h
#ifndef _HuffmanNode_
#define _HuffmanNode_
struct HuffmanNode
{
int weight; //存放结点的权值，假设只考虑处理权值为整数的情况
int parent; //-1表示为根结点，否则表示为非根结点
int lchild,rchild; //分别存放该结点的左右孩子的所在单元的编号
};
#endif

//huffmantree.h
#ifndef _HuffmanTree_
#define _HuffmanTree_
#include"HuffmanNode.h"
#include<iostream>
#include<fstream>
#include<string>
using namespace std;

class HuffmanTree //哈夫曼树
{
public:
struct HuffmanNode *Node; //Node[]存放哈夫曼树
char *Info; //Info[]存放源文用到的字符——源码，如'a','b','c','d','e'，此内容可以放入结点中，不单独设数组存放
int LeafNum; //哈夫曼树的叶子个数，也是源码个数
public:
HuffmanTree();
~HuffmanTree();
void CreateHuffmanTree(); /*在内存中建立哈夫曼树，存放在Node[]中。 让用户从两种建立哈夫曼树的方法中选择：
1.从键盘读入源码字符集个数，每个字符，和每个字符的权重，建立哈夫曼树，
并将哈夫曼树写入文件hfmTree中。2.从文件hfmTree中读入哈夫曼树信息，建立哈夫曼树*/
void CreateHuffmanTreeFromKeyboard();
void CreateHuffmanTreeFromFile();
void Encoder(); /*使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树），
对文件ToBeTran中的正文进行编码，并将码文写入文件CodeFile中。
ToBeTran的内容可以用记事本等程序编辑产生。*/
void Decoder(); /*待译码的码文存放在文件CodeFile中，使用建立好的哈夫曼树（如果不在内存，
则从文件hfmTree中读入并建立内存里的哈夫曼树）将码文译码，
得到的源文写入文件TextFile中，并同时输出到屏幕上。*/
void PrintCodeFile(); /*将码文文件CodeFile显示在屏幕上*/
void PrintHuffmanTree(); /*将哈夫曼树以直观的形式（凹入表示法，或广义表，或其他树形表示法）显示在屏幕上，
同时写入文件TreePrintFile中*/
void PrintHuffmanTree_aoru(int T,int layer=1); /*凹入表示法显示哈夫曼树，由PrintHuffmanTree()调用*/
};
#endif

//huffmantree.cpp
#include"HuffmanTree.h"
#include<string>
#include<limits> //为使用整型最大值

//#include<iostream>
using namespace std;

//******************************************************
HuffmanTree::HuffmanTree()
{
LeafNum=0;
Node=NULL;
Info+NULL;

}
//******************************************************
HuffmanTree::~HuffmanTree()
{
delete []Node;
Node=NULL;
delete []Info;
Info=NULL;

}
//******************************************************
void HuffmanTree::CreateHuffmanTree()
{
char Choose;
cout<<"你要从文件中读入哈夫曼树(按1)，还是从键盘输入哈夫曼树(按2)？";
cin>>Choose;
if(Choose=='2') {//键盘输入建立哈夫曼树
CreateHuffmanTreeFromKeyboard();
}//choose=='2'
else { //从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
CreateHuffmanTreeFromFile();
}
}
//******************************************************
void HuffmanTree::CreateHuffmanTreeFromKeyboard()
{
int Num;
int i,j,pos1,pos2,max1,max2;
cout<<"\n请输入源码字符集个数：";
cin>>Num;
if (Num<=1)
{
cout<<"无法建立少于2个叶子结点的哈夫曼树。\n\n";
return;
}
LeafNum=Num;
Node=new HuffmanNode[2*Num-1];
Info=new char[2*Num-1];
for( i=0;i<Num;i++) {//读入哈夫曼树的叶子结点信息
cout<<"请输入第"<<i+1<<"个字符值";
getchar();
Info[i]=getchar(); //源文的字符存入字符数组Info[]
getchar();
cout<<"请输入该字符的权值或频度";
cin>>Node[i].weight; //源文的字符权重存入Node[].weight
Node[i].parent=-1; //为根结点
Node[i].lchild=-1; //无左孩子
Node[i].rchild=-1; //无右孩子
}

for( i=Num;i<2*Num-1;i++) //循环建立哈夫曼树内部结点 表示需做Num-1次合并
{
pos1=-1;pos2=-1; //分别用来存放当前最小值和次小值的所在单元编号
max1=32767; max2=32767; //32767为整形数的最大值 分别用来存放当前找到的最小值和次小值
for(j=0;j<i;j++) //在根结点中选出权值最小的两个
{
if(Node[j].parent==-1) //是否为根结点
if(Node[j].weight<max1) //是否比最小值要小
{
max2=max1; //原最小值变为次小值
max1=Node[j].weight; //存放最小值
pos2=pos1; //修改次小值所在的单元编号
pos1=j; //修改最小值所在的单元编号
}
else
if(Node[j].weight<max2) //比原最小值大但比原此小值小
{
max2=Node[j].weight;
pos2=j;
}
}
Node[pos1].parent=i;
Node[pos2].parent=i;
Node[i].lchild=pos1;
Node[i].rchild=pos2;
Node[i].parent=-1;
Node[i].weight=Node[pos1].weight+Node[pos2].weight;

} //for

LeafNum=Num;
cout<<"哈夫曼树已成功构造完成。\n";

//把建立好的哈夫曼树写入文件hfmTree.dat
char ch;
cout<<"是否要替换原来的哈夫曼树文件(Y/N):";
cin>>ch;
if (ch!='y'&&ch!='Y') return;
ofstream fop;
fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); //打开文件
if(fop.fail()) {
cout<<"\n哈夫曼树文件打开失败，无法将哈夫曼树写入hfmTree.dat文件。\n";
return;
}
fop.write((char*)&Num,sizeof(Num)); //先写入哈夫曼树的叶子结点个数
for( i=0;i<Num;i++) { //再写入源文字符集的所有字符（存储在Info[]中）
fop.write((char*)&Info[i],sizeof(Info[i]));
flush(cout);
}
for( i=0;i<2*Num-1;i++) { //最后写入哈夫曼树的各个结点（存储在Node[]中）
fop.write((char*)&Node[i],sizeof(Node[i]));
flush(cout);
}
fop.close(); //关闭文件
cout<<"\n哈夫曼树已成功写入hfmTree.dat文件。\n";
}

//******************************************************
void HuffmanTree::CreateHuffmanTreeFromFile()
{
ifstream fip;
fip.open("hfmTree.dat",ios::binary|ios::in);
if(fip.fail()) {
cout<<"哈夫曼树文件hfmTree.dat打开失败，无法建立哈夫曼树。\n";
return;
}
fip.read((char*)&LeafNum,sizeof(LeafNum));
if (LeafNum<=1) {
cout<<"哈夫曼树文件中的数据有误，叶子结点个数少于2个，无法建立哈夫曼树。\n";
fip.close();
return;
}
Info=new char[LeafNum];
Node=new HuffmanNode[2*LeafNum-1];
for( int i=0;i<LeafNum;i++)
fip.read((char*)&Info[i],sizeof(Info[i]));
for(int i=0;i<2*LeafNum-1;i++)
fip.read((char*)&Node[i],sizeof(Node[i]));
fip.close();
cout<<"哈夫曼树已成功构造完成。\n";
}

//******************************************************
void HuffmanTree::Encoder()
{
if(Node==NULL) //内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1)
{
cout<<"内存无哈夫曼树。操作撤销。\n\n";
return;
}
}//if

char *SourceText; //字符串数组，用于存放源文
//让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入
char Choose;
cout<<"你要从文件中读入源文(按1)，还是从键盘输入源文(按2)？";
cin>>Choose;
if(Choose=='1')
{
ifstream fip1("ToBeTran.txt");
if(fip1.fail())
{
cout<<"源文文件打开失败!无法继续执行。\n";
return;
}
char ch;
int k=0;
while(fip1.get(ch)) k++; //第一次读文件只统计文件中有多少个字符，将字符数存入k
fip1.close();

SourceText=new char[k+1]; //申请存放源文的字符数组空间
ifstream fip2("ToBeTran.txt");//第二次读源文文件，把内容写入SourceText[]
k=0;
while(fip2.get(ch)) SourceText[k++]=ch;
fip2.close();
SourceText[k]='\0';
cout<<"需编码的源文为：";
cout<<SourceText<<endl;
}
else { //从键盘输入源文
string SourceBuff;
cin.ignore();
cout<<"请输入需要编码的源文(可输入任意长，按回车键结束):\n";
getline(cin,SourceBuff,'\n');
int k=0;
while(SourceBuff[k]!='\0')
k++;
SourceText=new char[k+1];
k=0;
while(SourceBuff[k]!='\0') {
SourceText[k]=SourceBuff[k];
k++;
}
SourceText[k]='\0';
}

ofstream fop("CodeFile.dat",ios::trunc); //打开码文存放文件
char *code;
code=new char[LeafNum]; //存放一个源文字符的编码
int k=0;
int i,j,start;
while(SourceText[k]!='\0') //源文串中从第一个字符开始逐个编码
{
start=0;
for(i=0;i<LeafNum;i++)
if(Info[i]==SourceText[k]) //求出该文字所在单元的编号
break;
j=i;
while(Node[j].parent!=-1) //结点j非根
{
j=Node[j].parent; //求结点j的双亲结点
if(Node[j].lchild==i) //是左子树，则生成代码0
code[start++]='0';
else
code[start++]='1'; //是右子树，则生成代码1
i=j;
}
code[start]='\0'; //置串结束符
for(i=0;i<start/2;i++)
{
j=code[i];
code[i]=code[start-1-i];
code[start-1-i]=j;
}
i=0; //将源文的当前字符的对应编码写入码文文件
while(code[i]!='\0')
{
fop<<code[i];
i++;
}
k++; //源文串中的字符后移一个

}
fop.close();
cout<<"已完成编码，码文已写入文件CodeFile.dat中。\n\n";
}

//******************************************************
void HuffmanTree::Decoder()
{

//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1)
{
cout<<"内存无哈夫曼树。操作撤销。\n\n";
return;
}
}

//将码文从文件CodeFile.dat中读入 CodeStr[]
ifstream fip1("CodeFile.dat");
if(fip1.fail())
{
cout<<"没有码文，无法译码。\n";
return;
}

char* CodeStr;
int k=0;
char ch;
while(fip1.get(ch))
{
k++;
}
fip1.close();
CodeStr=new char[k+1];
ifstream fip2("CodeFile.dat");
k=0;
while(fip2.get(ch))
CodeStr[k++]=ch;
fip2.close();
CodeStr[k]='\0';

cout<<"经译码得到的源文为：";
ofstream fop("TextFile.dat");

int j=(LeafNum-1)*2; //j指向哈夫曼树的根

int i=0; //码文从第一个符号开始，顺着哈夫曼树由根下行，按码文的当前符号决定下行到左孩子还是右孩子
while(CodeStr[i]!='\0') //下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符
{
if(CodeStr[i]=='0')
j=Node[j].lchild; //往左走
else
j=Node[j].rchild; //往右走
if(Node[j].rchild==-1) //到达叶子结点
{
cout<<Info[j]; //输出叶子结点对应的字符
j=LeafNum*2-1-1; //表示重新从根结点开始往下搜索
}
i++;
}
fop.close();
cout<<"\n译码成功且已存到文件TextFile.dat中。\n\n";
}
//******************************************************
void HuffmanTree::PrintCodeFile()
{
char ch;
int i=1;
ifstream fip("CodeFile.dat");
ofstream fop("CodePrin.dat");
if(fip.fail())
{
cout<<"没有码文文件，无法显示码文文件内容。\n";
return;
}
while(fip.get(ch))
{
cout<<ch;
fop<<ch;
if(i==50)
{
cout<<endl;
fop<<endl;
i=0;
}
i++;
}
cout<<endl;
fop<<endl;
fip.close();
fop.close();
}
//******************************************************
void HuffmanTree::PrintHuffmanTree()
{
//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"内存无哈夫曼树。操作撤销。\n\n";
return;
}
}

ofstream fop("TreePrint.dat",ios_base::trunc);
fop.close();
PrintHuffmanTree_aoru(2*LeafNum-1-1);
return;
}
//******************************************************
void HuffmanTree::PrintHuffmanTree_aoru(int T,int layer)//凹入表示法
{
if(Node[T].lchild!=-1)
PrintHuffmanTree_aoru(Node[T].lchild,layer+1);//左子树
for(int i=1;i<=layer;i++)// 根
cout<<'\0'<<'\0'<<'\0';
cout<<Node[T].weight<<endl;
if(Node[T].rchild!=-1)
PrintHuffmanTree_aoru(Node[T].rchild,layer+1); // 右子树

}

Ⅳ 求助：用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树时使用。

Ⅵ （哈夫曼压缩）将01字符串转换为二进制文件的方法

//你没说什么语言！如果需要其它的话，我再翻译一下滑老！
//没什么效率，但是满足需求了
importjava.io.*;

publicclassZ{
	
	publicstaticvoidmain(String[]args)throwsException{
		//System.out.println(decode(encode("00001000")));
		//System.out.println(decode(encode("11111000")));
		writeHuffman("011");
		System.out.println(read()Huffman());
	}
	
	//每次传进去的字符串都是8个字符长度，刚好能够表示一个byte
	publicstaticbyteencode(Strings){
		inta=0;
		for(inti=0;i<8;i++){
			charch=s.charAt(i);
			a=a<<信塌升1;
			if(ch=='1'){
				a=a|0x1;
			}
		}
		return(byte)a;
	}
	
	//上一步的逆操作
	publicstaticStringdecode(byteb){
		StringBuildersb=newStringBuilder();
		for(inti=0;i<8;i++){
			sb.append((b&(0x1<<(7-i)))>0?'1':'0');
		}
		returnsb.toString();
	}
	
	//再写一下文件操作
	//假设你已经得到了通过huffman树编码的字符串，那么就这样写写入文件
	publicstaticvoidwriteHuffman(Strings)throwsException{
		//因为huffman编码字符串不总是8个字符的倍数，那么我们不足8时补0，并记录我们到底补了几个。
		//我们把补位数放在文件的第一个字节
		int衫卖z=8-s.length()%8;
		if(z==8){
			z=0;
		}
		byte[]buffer=newbyte[1024];
		buffer[0]=(byte)z;
		intpos=1,nBytes=(int)(Math.ceil(s.length()/((double)8)));
		Filef=newFile("test.huffman");
		FileOutputStreamos=newFileOutputStream(f);
		for(inti=0;i<nBytes;i++){
			Stringss;
			if(s.length()>=(i+1)*8){
				ss=s.substring(i*8,(i+1)*8);
			}else{
				ss=s.substring(i*8);
				while(ss.length()<8){
					ss=newStringBuilder(ss).append('0').toString();
				}
			}
			buffer[pos]=encode(ss);
			pos++;
			if(pos==1024){
				os.write(buffer);
				pos=0;
			}
		}
		if(pos>0){
			os.write(buffer,0,pos);
		}
		os.close();
	}
	
	
	//我们把压缩过的文本放在test.huffman里面
	publicstaticStringreadHuffman()throwsException{
		Filef=newFile("test.huffman");
		FileInputStreamfs=newFileInputStream(f);
		byte[]buffer=newbyte[1024];
		intlen=0;
		StringBuildersb=newStringBuilder();
		bytez=(byte)fs.read();
		while((len=fs.read(buffer))!=-1){
			for(inti=0;i<len;i++){
				sb.append(decode(buffer[i]));
			}
		}
		fs.close();
		returnsb.substring(0,sb.length()-z);
	}
	
}

c++ 版本

#include"stdafx.h"
#include<stdio.h>
#include<iostream>
#include<string>
#include<cmath>

usingnamespacestd;

unsignedcharencode(constchar*s){
	inta=0;
	for(inti=0;i<8;i++){
		if(s[i]=='1'){
			a=a|(0x1<<(7-i));
		}
	}
	return(unsignedchar)a;
}

voiddecode(unsignedchara,char*buf){
	for(inti=0;i<8;i++){
		buf[i]=(((a>>(7-i))&0x1)!=0)?'1':'0';
	}
}

voidwriteHuffman(conststring&s){
	unsignedcharz=8-s.length()%8;
	if(z==8){
		z=0;
	}
	unsignedcharbuffer[1024];
	buffer[0]=z;

	intpos=1,nBytes=(int)(ceil(s.length()/((double)8)));
	constchar*ps=s.c_str();
	FILE*fp=fopen("test.huffman","wb");
	charextended[8];
	for(inti=0;i<nBytes;i++){
		constchar*p;
		if(s.length()>=(i+1)*8){
			p=ps+i*8;
		}
		else{
			char*pp=extended;
			for(intj=i*8;j<s.length();j++){
				*pp=s[j];
				pp++;
			}
			for(intj=0;j<z;j++){
				*pp='0';
				pp++;
			}
			p=extended;
		}
		buffer[pos]=encode(p);
		pos++;
		if(pos==1024){
			fwrite(buffer,sizeof(unsignedchar),1024,fp);
			pos=0;
		}
	}

	if(pos>0){
		fwrite(buffer,sizeof(unsignedchar),pos,fp);
	}

	fclose(fp);

}

string&readHuffman(){
	FILE*fp=fopen("test.huffman","rb");
	fseek(fp,0L,SEEK_END);
	size_tfileSize=ftell(fp);
	rewind(fp);

	unsignedcharbuffer[1024];
	fread(buffer,sizeof(unsignedchar),1,fp);
	unsignedcharz=buffer[0];

	size_tstringSize=(fileSize-1)*8;
	char*ptr=newchar[stringSize+1];
	char*optr=ptr;
	size_tlen;
	while((len=fread(buffer,sizeof(unsignedchar),1024,fp))!=0){
		for(inti=0;i<len;i++){
			decode(buffer[i],ptr);
			ptr=ptr+8;
		}
	}
	fclose(fp);
	ptr=ptr-z;
	*ptr='';
	string*str=newstring(optr);
	delete[]optr;
	return*str;
}

intmain(void)
{
	writeHuffman("00010");
	cout<<readHuffman()<<endl;
	getchar();
	return0;
}

Ⅶ 哈夫曼编码与译码 java

class HaffmanNode //哈夫曼树的结点类
{
int weight; //租誉权值
int parent,left,right; //父母结点和散岁左右孩子下标

public HaffmanNode(int weight)
{
this.weight = weight;
this.parent=-1;
this.left=-1;
this.right=-1;
}
public HaffmanNode()
{
this(0);
}
public String toString()
{
return this.weight+", "+this.parent+", "+this.left+", "+this.right;
}
return code;
}

public static void main(String[] args)
{
int[] weight={5,29,7,8,14,23,3,11}; //指定权值集合
HaffmanTree htree = new HaffmanTree(weight);
System.out.println("哈夫曼树的结点数组:\n"冲型睁+htree.toString());
String[] code = htree.haffmanCode();
System.out.println("哈夫曼编码:");
for (int i=0; i<code.length; i++)
System.out.println(code[i]);
}
}

Ⅷ 哈夫曼编码的压缩实现

压缩代码非常简单，首先用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;
}

Ⅸ java如何直接解压zip格式二进制流

Java代码
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.util.zip.ZipEntry;
import java.util.zip.ZipInputStream;
import java.util.zip.ZipOutputStream;

class ZipTest {
// 压缩
public static void zip(String zipFileName, String inputFile)
throws Exception {
File f = new File(inputFile);
ZipOutputStream out = new ZipOutputStream(new FileOutputStream(
zipFileName));
zip(out, f, f.getName());
System.out.println("zip done");
out.close();

Ⅹ 如何用哈夫曼编码对图像进行压缩

% 演示图象的哈夫曼编解码过程
% chenyong 2009.04.20

clear all;
close all;
clc;
Dimens = 256; % 矩阵维数，假设矩阵为方阵即256*256
src_size = Dimens^2; % 矩阵元素的个数
gray_level = 9; % 灰度级

src = randn(Dimens); %产生模拟图像矩阵，满足正态分布，零均值，方差为1
%src = randint(Dimens,Dimens,gray_level); % 产生随机图像矩阵，灰度值为0~63，满足均匀分布
src_one = reshape(src,1,src_size);
src_max = max(src_one);
src_min = min(src_one);
quan = linspace(src_min,src_max,gray_level); % 产生均匀量化区间
src_d = []; % 数字矩阵
for row = 1:Dimens % 逐点量化
for vol = 1:Dimens
diff = abs(src(row,vol)-quan);
[min_diff,min_index] = min(diff);
quan_gray = min_index -1;
src_d(row,vol) = quan_gray;
end
end

%将数字图像矩阵还原成模拟矩阵
src_a = [];
quan_space = quan(2)-quan(1);
for row = 1:Dimens
for vol = 1:Dimens
src_a(row,vol) = src_d(row,vol) * quan_space + src_min;
end
end

% prob数组保存图像中各灰度出现的概率
prob = [];
for src_value=0:(gray_level-1)
index = find(src_d==src_value);
i = src_value + 1;
prob(i) = length(index)/src_size;
end

% 画出直方图
% stem(0:gray_level-1,prob);
% xlabel('灰度值');
% ylabel('概率');
% title('灰度直方图');

% huffman编码
p = prob;
n=length(p);
q=p;
m=zeros(n-1,n);
for i=1:n-1
[q,l]=sort(q);
m(i,:)=[l(1:n-i+1),zeros(1,i-1)];
q=[q(1)+q(2),q(3:n),1];
end
bre=zeros(n-1,n);
bre(n-1,1)=0+j; %虚部表示当前的二进制数的位数，以下类似
bre(n-1,2)=1+j;
for time=1:n-2
loc_1 = find(real(m(n-time,:))==1);
prebit = bre(n-time,loc_1);
bre(n-time-1,1) = (real(prebit)*2 + 0) + j*(imag(prebit)+1);
bre(n-time-1,2) = (real(prebit)*2 + 1) + j*(imag(prebit)+1);

loc_not1 = find(real(m(n-time,:))>1);
bre(n-time-1,3:3+time-1) = bre(n-time,loc_not1);
end
[m1,index] = sort(m(1,:));
code = bre(1,index);
code_data = real(code);
code_bits = imag(code);
disp(['gray level',' ', 'huffman code']);
for i = 1:length(code)
disp([num2str(i-1),' ' ,num2str(dec2bin(code_data(i)))]);
disp([num2str(i-1),' ' ,num2str(dec2bin(code_data(i),code_bits(i)))]);
end
code_binary = dec2bin(code_data);

%逐点编码
out = [];
for row = 1:Dimens
for vol = 1:Dimens
now_gray = src_d(row,vol);
now_code = code_binary(now_gray+1,:);
now_bits = code_bits(now_gray+1);
now_code = now_code(end-now_bits+1:end);
out = [out, now_code];
end
end

%计算压缩比
real_bitnum = length(out);
bitnum_no_huffman = src_size*nextpow2(gray_level);
comp_ratio =bitnum_no_huffman/real_bitnum;
Lavg = real_bitnum/src_size;
Hshannon = (-1)*prob*(log2(prob))';
disp(['Lavg = ',num2str(Lavg)]);
disp(['normal bit num = ',num2str(nextpow2(gray_level))]);
disp(['comp_ratio = ',num2str(comp_ratio)]);
disp(['Hshannon = ',num2str(Hshannon)]);