java實現哈夫曼壓縮的例項

NO IMAGE

哈夫曼壓縮的原理:

通過統計檔案中每個位元組出現的頻率,將8位的01串轉換為位數較短的哈夫曼編碼.

其中哈夫曼編碼是根據檔案中位元組出現的頻率構建的,其中出現頻率越高的位元組,其路徑長度越短;

出現頻率越低的位元組其路徑長度越長.從而達到壓縮的目的.

如何構造哈夫曼樹?

一.  定義位元組類 

        我的位元組類定義了一下屬性   


public int data;//節點資料 
public int weight;//該節點的權值 
public int point;//該節點所在的左右位置 0-左 1-右 
private NodeData parent;//父節點引用 
private NodeData left;//左節點引用 
private NodeData right;//右節點引用 

二.建哈夫曼樹

1.定義一個儲存位元組資訊的陣列: int array_Bytes[256]; 

  其中陣列的下標[0,256)代表位元組數值(一個位元組8位,其值在[0,256)範圍內);陣列儲存位元組出現的次數.

2.遍歷要壓縮的檔案,統計位元組出現的次數. 


InputStream data = new FileInputStream(path); 
/******** 檔案中字元個數 ********/ 
int number = data.available(); 
for (int i = 0; i < number; i  ) { 
int b = data.read(); 
array_Bytes[b]   ; 
} 
data.close(); 

3.將位元組類物件存入優先佇列

4.運用HashMap 構造碼錶

哈夫曼壓縮程式碼如下:

1.位元組類


package compressFile; 
/** 
* 節點資料 
* 功能:定義資料,及其哈夫曼編碼 
* @author Andrew 
* 
*/ 
public class NodeData { 
public NodeData(){ 
} 
public int data;//節點資料 
public int weight;//該節點的權值 
public int point;//該節點所在的左右位置 0-左 1-右 
private NodeData parent; 
private NodeData left; 
private NodeData right; 
public int getData(){ 
return data; 
} 
public NodeData getParent() { 
return parent; 
} 
public void setParent(NodeData parent) { 
this.parent = parent; 
} 
public NodeData getLeft() { 
return left; 
} 
public void setLeft(NodeData left) { 
this.left = left; 
} 
public NodeData getRight() { 
return right; 
} 
public void setRight(NodeData right) { 
this.right = right; 
} 
} 

2.統計位元組的類,並生成碼錶


package compressFile; 
import java.io.BufferedInputStream; 
import java.io.FileInputStream; 
import java.io.IOException; 
import java.io.InputStream; 
import java.util.ArrayList; 
import java.util.Comparator; 
import java.util.HashMap; 
import java.util.List; 
import java.util.Map; 
import java.util.PriorityQueue; 
/** 
* 統計指定檔案中每個位元組數 功能:定義陣列,將檔案中的位元組型別及個數寫入陣列 
* 建立優先佇列和哈夫曼樹 
* @author Andrew 
* 
*/ 
public class StatisticBytes { 
/** 
* 第一步: 
* 統計檔案中位元組的方法 
* 
* @param path 
*      所統計的檔案路徑 
* @return 位元組個數陣列 
*/ 
private int[] statistic(String path) { 
/******儲存位元組資料的陣列--索引值代表位元組型別-儲存值代表權值******/ 
int[] array_Bytes = new int[256]; 
try { 
InputStream data = new FileInputStream(path); 
BufferedInputStream buffered = new BufferedInputStream(data); 
/******** 檔案中字元個數 ********/ 
int number = data.available(); 
System.out.println("位元組個數》》》" number); 
for (int i = 0; i < number; i  ) { 
int b = data.read(); 
array_Bytes[b]   ; 
} 
data.close(); 
} catch (IOException e) { 
e.printStackTrace(); 
} 
return array_Bytes; 
} 
/** 
* 第二步: 
* 根據統計的位元組陣列建立優先佇列 
* @param array 統計檔案位元組的陣列 
* @return    優先佇列 
*/ 
private PriorityQueue<NodeData> createQueue(int[] array){ 
//定義優先佇列,根據資料的權值排序從小到大 
PriorityQueue<NodeData> queue =  
new PriorityQueue<NodeData>(array.length,new Comparator<NodeData>(){ 
public int compare(NodeData o1, NodeData o2) { 
return o1.weight - o2.weight; 
} 
}); 
for(int i=0; i<array.length; i  ){ 
if(0 != array[i]){ 
NodeData node = new NodeData(); 
node.data = i;//設定該節點的資料 
node.weight = array[i];//設定該節點的權值 
queue.add(node); 
} 
} 
return queue; 
} 
/** 
* 第三步: 
* 根據優先佇列建立哈夫曼樹 
* @param queue  優先佇列  
* @return     哈夫曼樹根節點 
*/ 
private NodeData createTree(PriorityQueue<NodeData> queue){ 
while(queue.size() > 1){ 
NodeData left = queue.poll();//取得左節點 
NodeData right = queue.poll();//取得右節點 
NodeData root = new NodeData();//建立新節點 
root.weight = left.weight   right.weight; 
root.setLeft(left); 
root.setRight(right); 
left.setParent(root); 
right.setParent(root); 
left.point = 0; 
right.point = 1; 
queue.add(root); 
} 
NodeData firstNode = queue.poll(); 
return firstNode; 
} 
/** 
* 第四步: 
* 尋找葉節點並獲得哈夫曼編碼 
* @param root  根節點 
*/ 
private void achievehfmCode(NodeData root){ 
if(null == root.getLeft() && null == root.getRight()){ 
array_Str[root.data] = this.achieveLeafCode(root); 
/** 
* 
* 得到將檔案轉換為哈夫曼編碼後的文集長度 
* 檔案長度 = 一種編碼的長度 * 該編碼出現的次數 
*/ 
WriteFile.size_File  = (array_Str[root.data].length())*(root.weight); 
} 
if(null != root.getLeft()){ 
achievehfmCode(root.getLeft()); 
} 
if(null != root.getRight()){ 
achievehfmCode(root.getRight()); 
} 
} 
/** 
* 根據某葉節點獲得該葉節點的哈夫曼編碼 
* @param leafNode  葉節點物件 
*/ 
private String achieveLeafCode(NodeData leafNode){ 
String str = ""; 
/*****************儲存節點 01 編碼的佇列****************/ 
List<Integer> list_hfmCode = new ArrayList<Integer>(); 
list_hfmCode.add(leafNode.point); 
NodeData parent = leafNode.getParent(); 
while(null != parent){ 
list_hfmCode.add(parent.point); 
parent = parent.getParent(); 
} 
int size = list_hfmCode.size(); 
for(int i=size-2; i>=0; i--){ 
str  = list_hfmCode.get(i); 
} 
System.out.println(leafNode.weight "的哈夫曼編碼為>>>" str); 
return str; 
} 
/** 
* 第五步: 
* 根據獲得的哈夫曼表建立 碼錶 
* Integer 為位元組byte [0~256) 
* String 為哈夫曼編碼 
* @return 碼錶 
*/ 
public Map<Integer,String> createMap(){ 
int[] hfm_Codes = this.statistic("F:\\JAVA\\壓縮前.txt");//獲得檔案位元組資訊 
PriorityQueue<NodeData> queue = this.createQueue(hfm_Codes);//獲得優先佇列 
/* 
* 獲得哈夫曼樹的根節點, 
* this.createTree(queue)方法呼叫之後(含有poll()),queue.size()=0 
*/ 
NodeData root = this.createTree(queue); 
this.achievehfmCode(root);//獲得哈夫曼編碼並將其存入陣列中 
Map<Integer,String> map = new HashMap<Integer,String>(); 
for(int i=0; i<256; i  ){ 
if(null != array_Str[i]){ 
map.put(i, array_Str[i]); 
} 
} 
return map; 
} 
/** 
* 儲存位元組哈夫曼編碼的陣列 
* 下標:位元組資料 
* 元素:哈夫曼編碼 
*/ 
public String[] array_Str = new String[256]; 
} 

3.將碼錶寫入壓縮檔案並壓縮正文


package compressFile; 
import java.io.BufferedInputStream; 
import java.io.BufferedOutputStream; 
import java.io.DataOutputStream; 
import java.io.FileInputStream; 
import java.io.FileOutputStream; 
import java.io.IOException; 
import java.util.Iterator; 
import java.util.Map; 
import java.util.Set; 
/** 
* 將碼錶和檔案寫入新的檔案中 
* @author Andrew 
* 
*/ 
public class WriteFile { 
// 例項化建立碼錶類物件 
private StatisticBytes statistic = new StatisticBytes(); 
private Map<Integer, String> map = statistic.createMap();// 獲得碼錶 
// 位元組接收變數,接收哈夫曼編碼連線夠8位時轉換的位元組 
private int exmpCode; 
public static int size_File; 
public static void main(String[] args) { 
WriteFile writeFile = new WriteFile(); 
writeFile.init(); 
} 
private void init() { 
String filePath = "F:\\JAVA\\壓縮後.txt"; 
this.writeFile(filePath); 
} 
/** 
* 第一步: 向檔案中寫入碼錶 
* 
* @param dataOut 
*      基本資料流 
*/ 
private void writeCodeTable(DataOutputStream dataOut) { 
Set<Integer> set = map.keySet(); 
Iterator<Integer> p = set.iterator(); 
try { 
//向檔案中寫入碼錶的長度 
dataOut.writeInt(map.size()); 
while (p.hasNext()) { 
Integer key = p.next(); 
String hfmCode = map.get(key); 
dataOut.writeInt(key);//寫入位元組 
//寫入哈夫曼編碼的長度 
dataOut.writeByte(hfmCode.length()); 
for(int i=0; i<hfmCode.length(); i  ){ 
dataOut.writeChar(hfmCode.charAt(i));//寫入哈夫曼編碼 
} 
} 
} catch (IOException e) { 
e.printStackTrace(); 
} 
} 
/** 
* 第二步: 向壓縮檔案中寫入編碼 
* 
* @param path 
*/ 
private void writeFile(String path) { 
try { 
// 輸入流 
FileInputStream in = new FileInputStream("F:\\JAVA\\壓縮前.txt"); 
BufferedInputStream bIn = new BufferedInputStream(in); 
// 輸出流 
FileOutputStream out = new FileOutputStream(path); 
DataOutputStream dataOut = new DataOutputStream(out); 
BufferedOutputStream bOut = new BufferedOutputStream(out); 
// 向檔案中寫入碼錶 
this.writeCodeTable(dataOut); 
/********************寫入補零個數*********************/ 
if(0 != size_File % 8){ 
dataOut.writeByte(8 - (size_File % 8)); 
} 
String transString = "";//中轉字串,儲存字串直到size大於8 
String waiteString = "";//轉化字串, 
int size_File = in.available(); 
for(int i=0; i<size_File; i  ){ 
int j = bIn.read(); 
System.out.println("]]]]]]]]]]]>>"); 
waiteString = this.changeStringToByte(transString   statistic.array_Str[j]); 
if(waiteString != ""){  
bOut.write(exmpCode); 
transString = waiteString; 
}else{ 
transString  = statistic.array_Str[j]; 
} 
} 
if("" != transString){ 
int num = 8-transString.length()%8; 
for(int i=0; i<num; i  ){ 
transString  = 0; 
} 
} 
transString = this.changeStringToByte(transString); 
bOut.write(exmpCode); 
bIn.close(); 
bOut.flush(); 
bOut.close(); 
out.close(); 
} catch (IOException e) { 
e.printStackTrace(); 
} 
} 
/** 
* 附屬第二步: 
* 將字串轉化為byte 
* 
* @param str 
*      要轉化的字串 
* @return 如果str的長度大於8返回一個擷取前8位後的str 
*     否則返回"" 
*/ 
private String changeStringToByte(String str) { 
if (8 <= str.length()) { 
exmpCode = ((str.charAt(0) - 48) * 128 
(str.charAt(1) - 48) * 64   (str.charAt(2) - 48) * 32 
(str.charAt(3) - 48) * 16   (str.charAt(4) - 48) * 8 
(str.charAt(5) - 48) * 4   (str.charAt(6) - 48) * 2  
(str.charAt(7) - 48)); 
str = str.substring(8); 
return str; 
} 
return ""; 
} 
} 

二.哈夫曼解壓 

   原理:將壓縮的逆向,即你是如何壓縮的就怎樣去解壓。相當於你根據自己定義的協議進行壓縮與解壓縮檔案。

程式碼如下:


package decompressionFile; 
import java.io.DataInputStream; 
import java.io.FileInputStream; 
import java.io.FileOutputStream; 
import java.io.IOException; 
import java.io.InputStream; 
import java.io.OutputStream; 
import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.Iterator; 
import java.util.List; 
import java.util.Map; 
import java.util.Set; 
/** 
* 解壓檔案 從壓縮檔案中讀入資料解壓 
* 
* @author Andrew 
* 
*/ 
public class ReadFile { 
/** 
* 碼錶 Integter: 位元組 [0,255) String: 哈夫曼編碼 
*/ 
private Map<Integer, String> code_Map = new HashMap<Integer, String>(); 
public static void main(String[] args) { 
ReadFile readFile = new ReadFile(); 
readFile.readFile(); 
} 
/** 
* 第一步: 從檔案中讀出碼錶 
* 
* @param dataInput 
*      基本資料輸入流 
* 
*/ 
private void readMap(DataInputStream dataInput) { 
try { 
// 讀出碼錶的長度 
int size_Map = dataInput.readInt(); 
/**************** 讀出碼錶資訊 ************************************/ 
for (int i = 0; i < size_Map; i  ) { 
int data = dataInput.readInt();// 讀入位元組資訊 
String str = "";// 哈夫曼編碼 
// 哈夫曼編碼長度,儲存時以字元寫入 
byte codeSize = dataInput.readByte(); 
for (byte j = 0; j < codeSize; j  ) { 
str  = dataInput.readChar(); 
} 
System.out.println("&&&&&&&&&&>>>>" data "!!!!!!!>>" str); 
code_Map.put(data, str); 
} 
/***************************************************************/ 
} catch (IOException e) { 
e.printStackTrace(); 
} 
} 
/** 
* 第二步: 解壓正式檔案 
*/ 
private void readFile() { 
try { 
// 檔案輸入流 
InputStream input = new FileInputStream("F:\\JAVA\\壓縮後.txt"); 
// BufferedInputStream bIn = new BufferedInputStream(input); 
DataInputStream dInput = new DataInputStream(input); 
// 呼叫讀出碼錶的方法 
this.readMap(dInput); 
byte zerofill = dInput.readByte();// 讀出檔案補零個數 
System.out.println("補零個數》》》>>>>" zerofill); 
// 檔案輸出流 
OutputStream out = new FileOutputStream("F:\\JAVA\\解壓後.txt"); 
String transString = "";//接收用於匹配碼錶中哈夫曼編碼的字串 
String waiteString = "";//接收擷取哈夫曼編碼後剩餘的字串 
/***********************************不耗記憶體的方法*****************************************/ 
int readCode = input.read();//從壓縮檔案中讀出一個資料 
int size = input.available(); 
for(int j=0; j<=size; j  ){ 
System.out.println("readCodereadCodereadCode》》>>>>" readCode); 
waiteString  = this.changeIntToBinaryString(readCode);//將讀到的整數轉化為01字串 
for(int i=0; i<waiteString.length(); i  ){ 
//將從檔案中讀出的01串一個一個位元組的擷取新增與碼錶中的哈夫曼編碼比較 
transString  = waiteString.charAt(i); 
if(this.searchHC(transString, out)){ 
//           waiteString = waiteString.substring( i 1 ); 
transString = ""; 
} 
} 
waiteString = ""; 
readCode = input.read(); 
if(j == size-1){ 
break; 
} 
} 
/************************************處理最後一個字***************************************/ 
//     int lastByte = input.read(); 
String lastWord = this.changeIntToBinaryString(readCode); 
waiteString = transString   lastWord.substring(0, 8-zerofill); 
transString = ""; 
for(int i=0; i<waiteString.length(); i  ){ 
//將從檔案中讀出的01串一個一個位元組的擷取新增與碼錶中的哈夫曼編碼比較 
transString  = waiteString.charAt(i); 
if(this.searchHC(transString, out)){ 
//         waiteString = waiteString.substring( i 1 ); 
transString = ""; 
} 
} 
//     this.searchHC(transString, out); 
/***********************************佇列法,耗記憶體****************************************/ 
//     int readCode = input.read();//從壓縮檔案中讀出一個資料 
//     List<Character> list = new ArrayList<Character>(); 
//     while(-1 != readCode){ 
//       String str = this.changeIntToBinaryString(readCode); 
//       for(int i=0; i<str.length(); i  ){ 
//         list.add(str.charAt(i)); 
//       } 
//       readCode = input.read(); 
//     } 
//     for(int j=0; j<list.size()-zerofill; j  ){ 
//       transString  = list.get(j); 
//       if(this.searchHC(transString, out)){ 
//         transString = ""; 
//       } 
//     } 
/*****************************************************************************************/ 
input.close(); 
out.close(); 
} catch (IOException e) { 
e.printStackTrace(); 
} 
} 
/** 
* 將從檔案中讀到的01 串與碼錶中的哈夫曼編碼比較 
* 若在碼錶中含有與之對應的哈夫曼編碼則將碼錶中對應的 
* 資料寫入解壓檔案,否則不寫入 
* @param str 從檔案中讀到的01 字串 
* @param out 檔案輸出流 
* @return   若寫入檔案返回true,否則返回false 
* @throws IOException 寫入發生錯誤時丟擲異常 
*/ 
private boolean searchHC(String str, OutputStream out) throws IOException{ 
Set<Integer> set = code_Map.keySet(); 
Iterator<Integer> p = set.iterator(); 
while (p.hasNext()) { 
Integer key = p.next();//獲得碼錶中的位元組資料 
String hfmCode = code_Map.get(key);//獲得哈夫曼編碼 
if(hfmCode.equals(str)){ 
out.write(key); 
return true; 
} 
} 
return false; 
} 
/** 
* 根據 "除2取餘,逆序排列"法 
* 將十進位制數字轉化為二進位制字串 
* @param a  要轉化的數字 
* @return  01 字串 
*/ 
private String changeIntToBinaryString(int a) { 
int b = a; 
int count = 0; //記錄 a 可轉化為01串的個數,在不夠8為時便於補零 
String str = "";// 逆序二進位制字串 
String exmpStr = "";// 順序二進位制字串 
while (a != 0) { 
b = a/2; 
if (a % 2 != 0) { 
str  = 1; 
} else { 
str  = 0; 
} 
a = b; 
count  ; 
} 
//不夠8位的地方補零 
for (int i = 0; i < 8 - count; i  ) { 
str  = 0; 
} 
//將轉化後的二進位制字串正序 
for (int j = 7; j >= 0; j--) { 
System.out.print(str.charAt(j)); 
exmpStr  = str.charAt(j); 
} 
System.out.println("轉化後的字串>>>>>>>>>" exmpStr); 
return exmpStr; 
} 
} 

您可能感興趣的文章:

圖文詳解JAVA實現哈夫曼樹java哈夫曼樹例項程式碼