java实现哈夫曼压缩的实例

java实现哈夫曼压缩的实例

哈夫曼压缩的原理：

通过统计文件中每个字节出现的频率,将8位的01串转换为位数较短的哈夫曼编码.

其中哈夫曼编码是根据文件中字节出现的频率构建的,其中出现频率越高的字节,其路径长度越短;

出现频率越低的字节其路径长度越长.从而达到压缩的目的.

如何构造哈夫曼树?

一.  定义字节类

我的字节类定义了一下属性

pubDqOBXlic 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 createQueue(int[] array){

//定义优先队列，根据数据的权值排序从小到大

PriorityQueue queue =

new PriorityQueue(array.length,new Comparator(){

public int compare(NodeData o1, NodeData o2) {

return o1.weight - o2.weight;

}

});

for(int i=0; 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 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 list_hfmCode = new ArrayList();

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 createMap(){

int[] hfm_Codes = this.statistic("F:\\JAVA\\压缩前.txt");//获得文件字节信息

PriorityQueue queue = this.createQueue(hfm_Codes);//获得优先队列

/*

* 获得哈夫曼树的根节点，

* this.createTree(queue)方法调用之后(含有poll())，queue.size()=0

*/

NodeData root = this.createTree(queue);

this.achievehfmCode(root);//获得哈夫曼编码并将其存入数组中

Map map = new HashMap();

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 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 set = map.keySet();

Iterator 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

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

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

transString += 0;

}

}

transString = this.changeStringToByte(transString);

bOut.write(exmpCode);

bIn.close();

bOut.flush();

bOut.close();

out.close();

} catch (IOException eDqOBX) {

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 code_Map = new HashMap();

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

//将从文件中读出的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);

transShttp://tring = "";

for(int i=0; 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 list = new ArrayList();

// while(-1 != readCode){

// String str = this.changeIntToBinaryString(readCode);

// for(int i=0; i

// list.add(str.charAt(i));

// }

// readCode = input.read();

// }

// for(int j=0; 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 set = code_Map.keySet();

Iterator 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;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。