哈夫曼壓縮是個無損的壓縮算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長度算法一族。意思是個體符號（例如，文本文件中的字符）用一個特定長度的位序列替代。因此，在文件中出現頻率高的符號，使用短的位序列，而那些很少出現的符號，則用較長的位序列。我們先來看基本概念。 

1.什么是哈夫曼樹?

哈夫曼樹是一種***二叉樹，它的***點體現在它的的帶權路徑長度最小。(結點的帶權路徑長度為：結點的路徑長度乘以結點的權值，樹的帶權路徑長度為所有葉子結點帶權路徑長度之和)

2.什么是哈弗曼編碼?

從哈弗曼樹的根結點開始，按照左子樹分配代碼“0”，右子樹分配代碼“1”的規則，直到葉子結點為止，每個葉子結點的哈弗曼編碼就是從根結點開始，一直到該葉子結點為止，把途中經過的代碼按順序串起來就OK了。

3.什么是哈弗曼壓縮?

Huffman( 哈夫曼 ) 算法在上世紀五十年代初提出來了，它是一種無損壓縮方法，在壓縮過程中不會丟失信息熵，而且可以證明 Huffman 算法在無損壓縮算法中是***的。 Huffman 原理簡單，實現起來也不困難，在現在的主流壓縮軟件得到了廣泛的應用。對應用程序、重要資料等絕對不允許信息丟失的壓縮場合， Huffman 算法是非常好的選擇。

哈夫曼壓縮，一般用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長度算法一族。意思是個體符號(例如，文本文件中的字符)用一個特定長度的位序列替代。因此，在文件中出現頻率高的符號，使用短的位序列，而那些很少出現的符號，則用較長的位序列。

有了以上的基本概念，我們就可以動手實現哈弗曼壓縮軟件了!

4.哈弗曼壓縮軟件的實現：

在文件中，所有的數據都是以字節的形式存在的，一個字節是8位，所以所有可能出現的字節在0——256之間(不包括256)，所以，***步要做的事情就是，把文件所有的字節的出現頻率統計出來，并用頻率做為權值生成一棵哈弗曼樹：

Java代碼：

int[] ByteCount = new int[256];//字節頻率統計  
InputStream fis = new FileInputStream(pathName_former);  
InputStream bis = new BufferedInputStream(fis);//創建文件輸入流  
while(bis.available()>0){  
int tmp = bis.read();  
ByteCount[tmp]++;  
}//統計頻率  
//構造哈弗曼樹  
hfmTree hfm = new hfmTree(ByteCount);  
Java代碼  
public hfmTree(int[] rank){//根據頻率構造哈弗曼樹  
//把頻率不為零的字節加入節點優先級隊列  
PriorityQueue nodes = new java.util.PriorityQueue();  
for(int i=0;i  
if(rank[i]!=0){  
nodes.add(new hfmNode(rank[i],i));  
}  
}  
//構造哈弗曼樹  
while(nodes.size()!=1){  
hfmNode node_1 = nodes.poll();//1  
hfmNode node_2 = nodes.poll();//2  
hfmNode addNode = new hfmNode(node_1.getRank()+node_2.getRank(),0);  
addNode.setLeft(node_1);  
addNode.setRight(node_2);  
nodes.add(addNode);  
}  
root = nodes.poll();  
}//構造函數(correct) 

接下來，要做的就是獲得0——256之間每個字節所對應的哈弗曼編碼，用一個String[] Code = new Code[256]保存下來：

Java代碼//獲得編碼  
private void getStrByte(hfmNode node,String s){  
if(node.getLeft()==null&&node.getRight()==null){  
Code[node.getData()] = s;//獲得編碼字符串  
}  
if(node.getLeft()!=null){  
getStrByte(node.getLeft(),s+"0");  
}//左零 if(node.getRight()!=null){  
getStrByte(node.getRight(),s+"1");  
}//右1  
}  
然后就是把每個字節的編碼長度打入文件：Java代碼//先將0-255的編碼長度打到文件里  
for(int i=0;i  
if(Code[i]==null||Code[i]==""){  
Code[i] = "";  
bos.write(0);  
}else{  
bos.write(Code[i].length());  
}  
} 

接下來就是，將每個字節的編碼打入文件(這里需要吧8個長度的01串轉換成一個byte打入文件)：

Java代碼//把每個字節的編碼表打到文件里  
int i = 0;//第i個字節  
int count = 0;//滿8打一，計數器  
String writeCode = "";//寫入的8位編碼  
String allCode = "";//所有待寫入的編碼  
String inCode = "";  
while(i<256||count>=8){  
if(count>=8){//滿8  
writeCode = allCode.substring(0,8);//前8位  
count-=8;  
allCode = allCode.substring(8);  
bos.write(changeString(writeCode));//寫入一個字節  
}else{  
count+=Code[i].length();  
allCode+=Code[i];  
inCode+=Code[i];  
i++;//嚴重錯誤發生地  
}  
}  
//如果不滿8位的  
if(allCode.length()>0){  
int len = 8-allCode.length();//補零  
for(int j=0;j  
allCode+="0";  
}  
inCode+=allCode;  
bos.write(changeString(allCode));  
} 

***就是把文件中的所有字節按照這種哈弗曼的編碼方式保存到文件中，過程類似于上一步(在***打入末尾補入的0的個數，主要是為了方便解壓縮)：Java代碼//編碼表輸出完畢，將文件中的字節按照這種編碼方式壓縮。

InputStream ins = new FileInputStream(pathName_former);  
InputStream buf = new BufferedInputStream(ins);//創建輸入流  
count = 0;  
writeCode = "";  
allCode = "";  
while(buf.available()>0||count>=8){  
if(count>=8){//滿8  
writeCode = allCode.substring(0,8);//前8位  
count-=8;  
allCode = allCode.substring(8);  
bos.write(changeString(writeCode));//寫入一個字節  
}else{  
int data = buf.read();  
count+=Code[data].length();  
allCode+=Code[data];  
}  
}  
//如果不滿8位的  
if(allCode.length()>0){  
int len = 8-allCode.length();//補零  
for(int j=0;j  
allCode+="0";  
}  
bos.write(changeString(allCode));  
bos.write(len);//補入了幾個0  
}else{  
bos.write(0);//補入了0個0  
} 

到這里，整個壓縮過程基本完成了。希望對大家有幫助。

【編輯推薦】

1. 詳細解析Java中抽象類和接口的區別
2. 如何在Java應用程序中動態分配CPU資源
3. 常見的十四種Java開發工具的特點
4. JavaScript開發規范要求
5. JavaBean中使用JDBC方式進行事務處理