這是我們的課程中布置的作業。找一些資料將作業完畢，順便將其寫到博客，以后看起來也方便。

原理介紹

什么是Huffman壓縮

Huffman( 哈夫曼 ) 算法在上世紀五十年代初提出來了，它是一種無損壓縮方法，在壓縮過程中不會丟失信息熵。并且能夠證明 Huffman 算法在無損壓縮算法中是最優的。

Huffman 原理簡單，實現起來也不困難，在如今的主流壓縮軟件得到了廣泛的應用。

相應用程序、重要資料等絕對不同意信息丟失的壓縮場合， Huffman 算法是非常好的選擇。

怎么實現Huffman壓縮

哈夫曼壓縮是個無損的壓縮算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長度算法一族。意思是個體符號(比如，文本文件里的字符)用一個特定長度的位序列替代。

因此。在文件里出現頻率高的符號，使用短的位序列。而那些非常少出現的符號。則用較長的位序列。

二叉樹

在計算機科學中。二叉樹是每個結點最多有兩個子樹的有序樹。

通常子樹的根被稱作 “ 左子樹 ” ( left subtree )和 “ 右子樹 ” ( right subtree )。

哈夫曼編碼 (Huffman Coding)

哈夫曼編碼是一種編碼方式，哈夫曼編碼是可變字長編碼 (VLC) 的一種。 uffman 于 1952 年提出一種編碼方法。該方法全然依據字符出現概率來構造異字頭的平均長 度最短的碼字，有時稱之為最佳編碼，一般就叫作 Huffman 編碼。

Huffman編碼生成步驟

掃描要壓縮的文件，對字符出現的頻率進行計算。

把字符按出現的頻率進行排序，組成一個隊列。

把出現頻率最低(權值)的兩個字符作為葉子節點。它們的權值之和為根節點組成一棵樹。

把上面葉子節點的兩個字符從隊列中移除，并把它們組成的根節點增加到隊列。

把隊列又一次進行排序。反復步驟 3、4、5 直到隊列中僅僅有一個節點為止。

把這棵樹上的根節點定義為 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 三個二進制位。

效果顯而易見。

編碼實現

流程圖

編碼流程

Created with Rapha?l 2.1.0開始讀入待壓縮文件，計算文件里各字符的權重依據權重構建Huffman樹依據Huffman樹獲得各個字符的HUffman編碼，并建立Huffman編碼的HashTable將字符總數、字符種數，以及Huffman樹寫入壓縮文件文件頭再次讀入待壓縮文件。依據其內容和coding hash table 將壓縮后的數據寫入文件結束

數據結構

CharacterWeight：記錄字符值。以及其在待壓縮文件里的權重。

public class CharacterCode {

private int weight;//字符值

private char character;//字符值

private String code;//其相應huffman編碼

}

HuffmanNode：huffman樹中的節點信息。

public class HuffmanNode {

private int parent;//父節點

private int lChild;//左子

private int rChild;//右子

private int weight;//權重

}

程序關鍵步驟

Huffman樹的構建

Huffman樹的變量：ArrayList list；

流程圖

Created with Rapha?l 2.1.0開始i=0n=字符的種數循環遍歷查找列表中權重最小的兩個node創建一個新的節點作為找到的兩個權重最小的節點的父節點，并將該父節點的權重置為權重最小的兩節點的權重和。將該節點增加數組中。

i++i

代碼

for(int i=0;i

//w1 : the first min weight w2: the second min weight

//i1 : the first min weight index, i2:　the second min weight index

int w1 = MAX_VALUE, w2=MAX_VALUE;

int i1 = 0, i2 = 0;

// find the two node with the minimum weight

for(int j=0;j

HuffmanNode node = tree.get(j);

if(node.getWeight()< w1 && node.getParent()==-1){

w2 = w1;

w1 = node.getWeight();

i2 = i1;

i1 = j;

}

else if(node.getWeight()

w2 = node.getWeight();

i2 = j;

}

}

//set the two node to be the children of a new node, and add the new node to the tree

HuffmanNode pNode = new HuffmanNode(w1+w2);

pNode.setlChild(i1);

pNode.setrChild(i2);

tree.add(pNode);

tree.get(i1).setParent(tree.indexOf(pNode));

tree.get(i2).setParent(tree.indexOf(pNode));}

依據Huffman 樹獲得Huffman編碼

從葉子節點開始網上遍歷Huffman樹，直到到達根節點，依據當前節點為其父節點的左兒子還是右兒子確定這一位值是0還是1。最后將依次獲得的0,1字符串反轉獲得Huffman編碼。

for(int i=0;i

HuffmanNode node = tree.get(i);

HuffmanNode pNode = tree.get(node.getParent());

String code ="";

while(true){

if(pNode.getlChild()==tree.indexOf(node)){

code = "0"+code;

}

else if(pNode.getrChild() == tree.indexOf(node)){

code = "1"+code;

}

else {

System.out.println("Tree Node Error!!!");

return null;

}

node=pNode;

if(node.getParent()!=-1)

pNode=tree.get(node.getParent());

else

break;

}

list.get(i).setCode(new String(code));

}

頭文件設計

編碼

類型

字節數

字符總數

Int

4

字符種類數

Short

2

葉子節點

char字符 short 父節點

3

非葉子節點

Short 左兒子 short 右兒子 short父節點

6

文件頭長度(單位： byte)

l= 9n

當中n 為字符種類數。

文件內容的編碼和寫入

Created with Rapha?l 2.1.0開始將待壓縮文件讀入字符數組依據coding hash table 獲得huffman編碼字符串,并將該字符串增加到buff中查看buff，假設字符數大于8則將字符串轉換為Short類型變量并寫入文件將寫入的字符從buff中刪除是否到達文件尾？結束yesno

代碼

while((temp=reader.read())!=-1){//!= EOF

// get the code from the code table

String code = codeTable.get((char)temp);

c++;

if(c>=count/96){

System.out.print("=");

c=0;

}

try{

StringBuilder codeString = new StringBuilder(code);

outputStringBuffer.append(codeString);

while(outputStringBuffer.length()>8){

out.write(Short.parseShort(outputStringBuffer.substring(0, 8),2));

outputStringBuffer.delete(0, 8);

}

} catch(Exception e){

e.printStackTrace();

}

}

解碼實現

流程圖

Created with Rapha?l 2.1.0開始讀壓縮文件。讀入文件頭，獲得字符總數。字符種數以及huffman表信息。重建huffman樹讀入正文，依據重建得到的huffman樹獲得原本的字符。將字符寫入解壓縮后的文件是否到達文件尾部？結束yesno

數據結構

HuffmanNode：huffman樹中的節點信息。

public class HuffmanNode {

private int parent;//父節點

private int lChild;//左子

private int rChild;//右子

private int weight;//權重

}

程序關鍵步驟

重建Huffman樹。

在文件頭中存放的原本就是Huffman樹的節點信息。

in = new DataInputStream(new FileInputStream(file));

count = in.readInt();

charNum = in.readShort();

nodeNum = 2*charNum -1;

//rebuild the huffman tree

for(int i=0;i

HuffmanNode node = new HuffmanNode((char)in.readByte());

int parent = in.readShort();

node.setParent(parent);

tree.add(node);

}

for(int i=charNum;i

HuffmanNode node = new HuffmanNode(' ');

int l = in.readShort();

int r = in.readShort();

int p = in.readShort();

node.setlChild(l);

node.setrChild(r);

node.setParent(p);

tree.add(node);

}

解碼

流程圖

Created with Rapha?l 2.1.0開始Buff.length<32從文件里讀入整數將讀入的整數轉為二進制字符串，并將其加到buff中依據buff中的01字符從頂向下遍歷huffman樹。得到葉子節點、其相應的解碼值，將其寫入文件，從buff中遍歷刪去已經遍歷過的字符字符數是否達到總數處理buff中剩余內容結束yesnoyesno

代碼

while(true){

while(buff.length()<32){

temp = in.readInt();

String codeString = Integer.toBinaryString(temp);

while(codeString.length()<32){

codeString='0'+codeString;

}

buff.append(codeString);

}

node = tree.get(tree.size()-1);

dep = 0;

while(!(node.getlChild()==-1&&node.getrChild()==-1)){

if(dep>=buff.length()){

System.out.println( "Buff overflow");

}

if(buff.charAt(dep)=='0'){

node = tree.get(node.getlChild());

}

else if(buff.charAt(dep)=='1'){

node = tree.get(node.getrChild());

}

else{

System.out.println("Coding error");

}

dep++;

}

char c = node.getCH();

num++;

if(num>=n/99){

System.out.print("=");

num=0;

}

count++;

if(count>=n){

break;

}

charBuff+=c;

if(charBuff.length()>256){

writer.write(charBuff);

charBuff="";

}

buff.delete(0, dep);

}

} catch(EOFException e){

//just do nothing

}

catch(Exception e){

e.printStackTrace();

} finally{

//there may be data released in the buff and charbuff, so we need to process them

while(buff.length()>0){

node = tree.get(tree.size()-1);

dep = 0;

while(!(node.getlChild()==-1&&node.getrChild()==-1)){

if(dep>=buff.length()){

break;

}

if(buff.charAt(dep)=='0'){

node = tree.get(node.getlChild());

}

else if(buff.charAt(dep)=='1'){

node = tree.get(node.getrChild());

}

else{

System.out.println("Coding error");

//return;

}

dep++;

}

char c = node.getCH();

num++;

if(num>=n/99){

System.out.print("=");

num=0;

}

count++;

if(count>=n){

break;

}

charBuff+=c;

if(charBuff.length()>256){

try {

writer.write(charBuff);

} catch (IOException e1) {

// TODO Auto-generated catch block

e1.printStackTrace();

}

charBuff="";

}

buff.delete(0, dep);

}

try {

writer.write(charBuff);

writer.close();

} catch (IOException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

}

try{

writer.close();

} catch(IOException e){

throw e;

}

項目源代碼

留坑回頭放上

總結

以上是生活随笔為你收集整理的huffman编码的程序流程图_Huffman编码实现压缩解压缩的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。