java實(shí)現(xiàn)哈夫曼壓縮的實(shí)例
更新時(shí)間：2017年07月05日 10:37:19 投稿：lqh
這篇文章主要介紹了java實(shí)現(xiàn)哈夫曼壓縮的實(shí)例的相關(guān)資料,需要的朋友可以參考下
哈夫曼壓縮的原理：
通過統(tǒng)計(jì)文件中每個(gè)字節(jié)出現(xiàn)的頻率,將8位的01串轉(zhuǎn)換為位數(shù)較短的哈夫曼編碼.
其中哈夫曼編碼是根據(jù)文件中字節(jié)出現(xiàn)的頻率構(gòu)建的,其中出現(xiàn)頻率越高的字節(jié),其路徑長度越短;
出現(xiàn)頻率越低的字節(jié)其路徑長度越長.從而達(dá)到壓縮的目的.
如何構(gòu)造哈夫曼樹?
一. 定義字節(jié)類
我的字節(jié)類定義了一下屬性
public int data;//節(jié)點(diǎn)數(shù)據(jù) public int weight;//該節(jié)點(diǎn)的權(quán)值 public int point;//該節(jié)點(diǎn)所在的左右位置 0-左 1-右 private NodeData parent;//父節(jié)點(diǎn)引用 private NodeData left;//左節(jié)點(diǎn)引用 private NodeData right;//右節(jié)點(diǎn)引用
二.建哈夫曼樹
1.定義一個(gè)存儲字節(jié)信息的數(shù)組: int array_Bytes[256];
其中數(shù)組的下標(biāo)[0,256)代表字節(jié)數(shù)值(一個(gè)字節(jié)8位,其值在[0,256)范圍內(nèi));數(shù)組存儲字節(jié)出現(xiàn)的次數(shù).
2.遍歷要壓縮的文件,統(tǒng)計(jì)字節(jié)出現(xiàn)的次數(shù).
InputStream data = new FileInputStream(path);
/******** 文件中字符個(gè)數(shù) ********/
int number = data.available();
for (int i = 0; i < number; i++) {
int b = data.read();
array_Bytes[b] ++;
}
data.close();
3.將字節(jié)類對象存入優(yōu)先隊(duì)列
4.運(yùn)用HashMap 構(gòu)造碼表
哈夫曼壓縮代碼如下:
1.字節(jié)類
package compressFile;
/**
* 節(jié)點(diǎn)數(shù)據(jù)
* 功能：定義數(shù)據(jù)，及其哈夫曼編碼
* @author Andrew
*
*/
public class NodeData {
public NodeData(){
}
public int data;//節(jié)點(diǎn)數(shù)據(jù)
public int weight;//該節(jié)點(diǎn)的權(quán)值
public int point;//該節(jié)點(diǎn)所在的左右位置 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.統(tǒng)計(jì)字節(jié)的類，并生成碼表
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;
/**
* 統(tǒng)計(jì)指定文件中每個(gè)字節(jié)數(shù) 功能：定義數(shù)組，將文件中的字節(jié)類型及個(gè)數(shù)寫入數(shù)組
* 創(chuàng)建優(yōu)先隊(duì)列和哈夫曼樹
* @author Andrew
*
*/
public class StatisticBytes {
/**
* 第一步：
* 統(tǒng)計(jì)文件中字節(jié)的方法
*
* @param path
* 所統(tǒng)計(jì)的文件路徑
* @return 字節(jié)個(gè)數(shù)數(shù)組
*/
private int[] statistic(String path) {
/******儲存字節(jié)數(shù)據(jù)的數(shù)組--索引值代表字節(jié)類型-存儲值代表權(quán)值******/
int[] array_Bytes = new int[256];
try {
InputStream data = new FileInputStream(path);
BufferedInputStream buffered = new BufferedInputStream(data);
/******** 文件中字符個(gè)數(shù) ********/
int number = data.available();
System.out.println("字節(jié)個(gè)數(shù)》》》"+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;
}
/**
* 第二步：
* 根據(jù)統(tǒng)計(jì)的字節(jié)數(shù)組創(chuàng)建優(yōu)先隊(duì)列
* @param array 統(tǒng)計(jì)文件字節(jié)的數(shù)組
* @return 優(yōu)先隊(duì)列
*/
private PriorityQueue<NodeData> createQueue(int[] array){
//定義優(yōu)先隊(duì)列，根據(jù)數(shù)據(jù)的權(quán)值排序從小到大
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;//設(shè)置該節(jié)點(diǎn)的數(shù)據(jù)
node.weight = array[i];//設(shè)置該節(jié)點(diǎn)的權(quán)值
queue.add(node);
}
}
return queue;
}
/**
* 第三步：
* 根據(jù)優(yōu)先隊(duì)列創(chuàng)建哈夫曼樹
* @param queue 優(yōu)先隊(duì)列
* @return 哈夫曼樹根節(jié)點(diǎn)
*/
private NodeData createTree(PriorityQueue<NodeData> queue){
while(queue.size() > 1){
NodeData left = queue.poll();//取得左節(jié)點(diǎn)
NodeData right = queue.poll();//取得右節(jié)點(diǎn)
NodeData root = new NodeData();//創(chuàng)建新節(jié)點(diǎn)
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;
}
/**
* 第四步：
* 尋找葉節(jié)點(diǎn)并獲得哈夫曼編碼
* @param root 根節(jié)點(diǎn)
*/
private void achievehfmCode(NodeData root){
if(null == root.getLeft() && null == root.getRight()){
array_Str[root.data] = this.achieveLeafCode(root);
/**
*
* 得到將文件轉(zhuǎn)換為哈夫曼編碼后的文集長度
* 文件長度 = 一種編碼的長度 * 該編碼出現(xiàn)的次數(shù)
*/
WriteFile.size_File += (array_Str[root.data].length())*(root.weight);
}
if(null != root.getLeft()){
achievehfmCode(root.getLeft());
}
if(null != root.getRight()){
achievehfmCode(root.getRight());
}
}
/**
* 根據(jù)某葉節(jié)點(diǎn)獲得該葉節(jié)點(diǎn)的哈夫曼編碼
* @param leafNode 葉節(jié)點(diǎn)對象
*/
private String achieveLeafCode(NodeData leafNode){
String str = "";
/*****************存儲節(jié)點(diǎn) 01 編碼的隊(duì)列****************/
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;
}
/**
* 第五步：
* 根據(jù)獲得的哈夫曼表創(chuàng)建 碼表
* Integer 為字節(jié)byte [0~256)
* String 為哈夫曼編碼
* @return 碼表
*/
public Map<Integer,String> createMap(){
int[] hfm_Codes = this.statistic("F:\\JAVA\\壓縮前.txt");//獲得文件字節(jié)信息
PriorityQueue<NodeData> queue = this.createQueue(hfm_Codes);//獲得優(yōu)先隊(duì)列
/*
* 獲得哈夫曼樹的根節(jié)點(diǎn)，
* this.createTree(queue)方法調(diào)用之后(含有poll())，queue.size()=0
*/
NodeData root = this.createTree(queue);
this.achievehfmCode(root);//獲得哈夫曼編碼并將其存入數(shù)組中
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;
}
/**
* 存儲字節(jié)哈夫曼編碼的數(shù)組
* 下標(biāo)：字節(jié)數(shù)據(jù)
* 元素：哈夫曼編碼
*/
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 {
// 實(shí)例化創(chuàng)建碼表類對象
private StatisticBytes statistic = new StatisticBytes();
private Map<Integer, String> map = statistic.createMap();// 獲得碼表
// 字節(jié)接收變量，接收哈夫曼編碼連接夠8位時(shí)轉(zhuǎn)換的字節(jié)
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
* 基本數(shù)據(jù)流
*/
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);//寫入字節(jié)
//寫入哈夫曼編碼的長度
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);
/********************寫入補(bǔ)零個(gè)數(shù)*********************/
if(0 != size_File % 8){
dataOut.writeByte(8 - (size_File % 8));
}
String transString = "";//中轉(zhuǎn)字符串,存儲字符串直到size大于8
String waiteString = "";//轉(zhuǎn)化字符串,
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();
}
}
/**
* 附屬第二步：
* 將字符串轉(zhuǎn)化為byte
*
* @param str
* 要轉(zhuǎn)化的字符串
* @return 如果str的長度大于8返回一個(gè)截取前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 "";
}
}
二.哈夫曼解壓
原理:將壓縮的逆向，即你是如何壓縮的就怎樣去解壓。相當(dāng)于你根據(jù)自己定義的協(xié)議進(jìn)行壓縮與解壓縮文件。
代碼如下：
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;
/**
* 解壓文件 從壓縮文件中讀入數(shù)據(jù)解壓
*
* @author Andrew
*
*/
public class ReadFile {
/**
* 碼表 Integter: 字節(jié) [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
* 基本數(shù)據(jù)輸入流
*
*/
private void readMap(DataInputStream dataInput) {
try {
// 讀出碼表的長度
int size_Map = dataInput.readInt();
/**************** 讀出碼表信息 ************************************/
for (int i = 0; i < size_Map; i++) {
int data = dataInput.readInt();// 讀入字節(jié)信息
String str = "";// 哈夫曼編碼
// 哈夫曼編碼長度,存儲時(shí)以字符寫入
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);
// 調(diào)用讀出碼表的方法
this.readMap(dInput);
byte zerofill = dInput.readByte();// 讀出文件補(bǔ)零個(gè)數(shù)
System.out.println("補(bǔ)零個(gè)數(shù)》》》>>>>"+zerofill);
// 文件輸出流
OutputStream out = new FileOutputStream("F:\\JAVA\\解壓后.txt");
String transString = "";//接收用于匹配碼表中哈夫曼編碼的字符串
String waiteString = "";//接收截取哈夫曼編碼后剩余的字符串
/***********************************不耗內(nèi)存的方法*****************************************/
int readCode = input.read();//從壓縮文件中讀出一個(gè)數(shù)據(jù)
int size = input.available();
for(int j=0; j<=size; j++){
System.out.println("readCodereadCodereadCode》》>>>>"+readCode);
waiteString += this.changeIntToBinaryString(readCode);//將讀到的整數(shù)轉(zhuǎn)化為01字符串
for(int i=0; i<waiteString.length(); i++){
//將從文件中讀出的01串一個(gè)一個(gè)字節(jié)的截取添加與碼表中的哈夫曼編碼比較
transString += waiteString.charAt(i);
if(this.searchHC(transString, out)){
// waiteString = waiteString.substring( i+1 );
transString = "";
}
}
waiteString = "";
readCode = input.read();
if(j == size-1){
break;
}
}
/************************************處理最后一個(gè)字***************************************/
// 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串一個(gè)一個(gè)字節(jié)的截取添加與碼表中的哈夫曼編碼比較
transString += waiteString.charAt(i);
if(this.searchHC(transString, out)){
// waiteString = waiteString.substring( i+1 );
transString = "";
}
}
// this.searchHC(transString, out);
/***********************************隊(duì)列法，耗內(nèi)存****************************************/
// int readCode = input.read();//從壓縮文件中讀出一個(gè)數(shù)據(jù)
// 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 串與碼表中的哈夫曼編碼比較
* 若在碼表中含有與之對應(yīng)的哈夫曼編碼則將碼表中對應(yīng)的
* 數(shù)據(jù)寫入解壓文件，否則不寫入
* @param str 從文件中讀到的01 字符串
* @param out 文件輸出流
* @return 若寫入文件返回true，否則返回false
* @throws IOException 寫入發(fā)生錯(cuò)誤時(shí)拋出異常
*/
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();//獲得碼表中的字節(jié)數(shù)據(jù)
String hfmCode = code_Map.get(key);//獲得哈夫曼編碼
if(hfmCode.equals(str)){
out.write(key);
return true;
}
}
return false;
}
/**
* 根據(jù) "除2取余，逆序排列"法
* 將十進(jìn)制數(shù)字轉(zhuǎn)化為二進(jìn)制字符串
* @param a 要轉(zhuǎn)化的數(shù)字
* @return 01 字符串
*/
private String changeIntToBinaryString(int a) {
int b = a;
int count = 0; //記錄 a 可轉(zhuǎn)化為01串的個(gè)數(shù)，在不夠8為時(shí)便于補(bǔ)零
String str = "";// 逆序二進(jìn)制字符串
String exmpStr = "";// 順序二進(jìn)制字符串
while (a != 0) {
b = a/2;
if (a % 2 != 0) {
str += 1;
} else {
str += 0;
}
a = b;
count++;
}
//不夠8位的地方補(bǔ)零
for (int i = 0; i < 8 - count; i++) {
str += 0;
}
//將轉(zhuǎn)化后的二進(jìn)制字符串正序
for (int j = 7; j >= 0; j--) {
System.out.print(str.charAt(j));
exmpStr += str.charAt(j);
}
System.out.println("轉(zhuǎn)化后的字符串>>>>>>>>>"+exmpStr);
return exmpStr;
}
}
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了java中File類應(yīng)用遍歷文件夾下所有文件，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-08-08
Java Web使用Html5 FormData實(shí)現(xiàn)多文件上傳功能
這篇文章主要介紹了Java Web使用Html5 FormData實(shí)現(xiàn)多文件上傳功能,需要的朋友可以參考下2017-07-07
這篇文章主要給大家介紹了關(guān)于Java在運(yùn)行時(shí)識別類型信息的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友可以參考借鑒，下面來一起看看吧2019-01-01
IntelliJ?IDEA?2020.2?全家桶及以下版本激活工具大全【喜訊】
這篇文章主要介紹了IntelliJ?IDEA?2020.2?全家桶及以下版本激活工具大全【喜訊】,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-09-09
Spring Boot 整合mybatis 與 swagger2
之前使用springMVC+spring+mybatis，總是被一些繁瑣的xml配置,還經(jīng)常出錯(cuò)，下面把以前的一些ssm項(xiàng)目改成了spring boot + mybatis，相對于來說優(yōu)點(diǎn)太明顯了，具體內(nèi)容詳情大家通過本文學(xué)習(xí)吧2017-08-08
解決Eclipse的Servers視圖中無法添加Tomcat6/Tomcat7的方法
這篇文章主要介紹了解決Eclipse的Servers視圖中無法添加Tomcat6/Tomcat7的方法的相關(guān)資料,需要的朋友可以參考下2017-02-02
這篇文章主要介紹了Spinrg WebFlux中Cookie的讀寫的示例，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2019-01-01
漢諾塔問題的描述如下：有3根柱子A、B和C，在A上從上往下按照從小到大的順序放著一些圓盤，以B為中介，把盤子全部移動到C上。移動過程中，要求任意盤子的下面要么沒有盤子，要么只能有比它大的盤子。編程實(shí)現(xiàn)3階漢諾塔的求解步驟2014-02-02
Spring中的ContextLoaderListener詳細(xì)解析
這篇文章主要介紹了Spring中的ContextLoaderListener詳細(xì)解析,在web容器即Tomact容器啟動web應(yīng)用即servlet應(yīng)用時(shí),會觸發(fā)ServletContextEvent時(shí)間,這個(gè)事件會被ServletContextListener監(jiān)聽,需要的朋友可以參考下2023-12-12
這篇文章主要為大家詳細(xì)介紹了Java經(jīng)典排序算法之歸并排序，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望可以對你有所幫助2021-07-07