導航:首頁 > 文件處理 > java哈夫曼壓縮

java哈夫曼壓縮

發布時間:2023-05-27 04:14:50

Ⅰ 怎樣使用哈夫曼樹編寫一段程序實現對信息編碼的壓縮我要代碼,謝謝了!

/**********************************************************************
*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)]);

閱讀全文

與java哈夫曼壓縮相關的資料

熱點內容
鏤空加密隔斷牆效果圖 瀏覽:539
windows7怎麼安裝證書伺服器 瀏覽:952
證券業務的程序員 瀏覽:202
u點伺服器wifi密碼如何設置 瀏覽:864
寶馬x5大燈編程 瀏覽:673
python安裝和使用 瀏覽:381
加密的門禁卡復制了用不了 瀏覽:714
javacsv讀寫 瀏覽:806
ug編程教程pdf 瀏覽:763
latex編譯軟體安卓版 瀏覽:248
如何在信合app上交居民醫保 瀏覽:109
丑惡pdf 瀏覽:365
陝西定頻壓縮機銷售公司 瀏覽:795
安卓系統如何幫人打王者 瀏覽:427
sbtlinux安裝 瀏覽:141
阿里雲sip伺服器 瀏覽:73
身為程序員的你怎麼拚命 瀏覽:453
android圖片手勢放大 瀏覽:586
錢的所有演算法 瀏覽:13
光模塊伺服器怎麼直接連電腦 瀏覽:376