怎么利用java语言实现一个哈夫曼压缩功能
本篇文章给大家分享的是有关怎么利用java语言实现一个哈夫曼压缩功能，小编觉得挺实用的，因此分享给大家学习，希望大家阅读完这篇文章后可以有所收获，话不多说，跟着小编一起来看看吧。
公司主营业务：做网站、成都做网站、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。创新互联建站是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联建站推出鼓楼免费做网站回馈大家。
哈夫曼压缩的原理：
通过统计文件中每个字节出现的频率,将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 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 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>");
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 二.哈夫曼解压
原理:将压缩的逆向，即你是如何压缩的就怎样去解压。相当于你根据自己定义的协议进行压缩与解压缩文件。
代码如下：
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 list = new ArrayList();
// while(-1 != readCode){
// String str = this.changeIntToBinaryString(readCode);
// for(int i=0; i 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;
}
}
以上就是怎么利用java语言实现一个哈夫曼压缩功能，小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注创新互联行业资讯频道。
标题名称：怎么利用java语言实现一个哈夫曼压缩功能
网站网址：http://6mz.cn/article/pccjdh.html