java实现哈夫曼压缩的实例

2024-02-17 10:01:04 49

哈夫曼压缩的原理：

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

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

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

如何构造哈夫曼树?

一. 定义字节类

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

publicintdata;//节点数据
publicintweight;//该节点的权值
publicintpoint;//该节点所在的左右位置0-左1-右
privateNodeDataparent;//父节点引用
privateNodeDataleft;//左节点引用
privateNodeDataright;//右节点引用

二.建哈夫曼树

1.定义一个存储字节信息的数组:intarray_Bytes[256];

其中数组的下标[0,256)代表字节数值(一个字节8位,其值在[0,256)范围内);数组存储字节出现的次数.

2.遍历要压缩的文件,统计字节出现的次数.

InputStreamdata=newFileInputStream(path);
/********文件中字符个数********/
intnumber=data.available();
for(inti=0;i
3.将字节类对象存入优先队列


4.运用HashMap构造码表


哈夫曼压缩代码如下:


1.字节类


packagecompressFile;
/**
*节点数据
*功能：定义数据，及其哈夫曼编码
*@authorAndrew
*
*/
publicclassNodeData{
publicNodeData(){

}
publicintdata;//节点数据
publicintweight;//该节点的权值
publicintpoint;//该节点所在的左右位置0-左1-右
privateNodeDataparent;
privateNodeDataleft;
privateNodeDataright;

publicintgetData(){
returndata;
}
publicNodeDatagetParent(){
returnparent;
}
publicvoidsetParent(NodeDataparent){
this.parent=parent;
}
publicNodeDatagetLeft(){
returnleft;
}
publicvoidsetLeft(NodeDataleft){
this.left=left;
}
publicNodeDatagetRight(){
returnright;
}
publicvoidsetRight(NodeDataright){
this.right=right;
}
}


2.统计字节的类，并生成码表


packagecompressFile;

importjava.io.BufferedInputStream;
importjava.io.FileInputStream;
importjava.io.IOException;
importjava.io.InputStream;
importjava.util.ArrayList;
importjava.util.Comparator;
importjava.util.HashMap;
importjava.util.List;
importjava.util.Map;
importjava.util.PriorityQueue;



/**
*统计指定文件中每个字节数功能：定义数组，将文件中的字节类型及个数写入数组
*创建优先队列和哈夫曼树
*@authorAndrew
*
*/
publicclassStatisticBytes{


/**
*第一步：
*统计文件中字节的方法
*
*@parampath
*所统计的文件路径
*@return字节个数数组
*/
privateint[]statistic(Stringpath){
/******储存字节数据的数组--索引值代表字节类型-存储值代表权值******/
int[]array_Bytes=newint[256];
try{
InputStreamdata=newFileInputStream(path);
BufferedInputStreambuffered=newBufferedInputStream(data);
/********文件中字符个数********/
intnumber=data.available();
System.out.println("字节个数》》》"+number);
for(inti=0;icreateQueue(int[]array){
//定义优先队列，根据数据的权值排序从小到大
PriorityQueuequeue=
newPriorityQueue(array.length,newComparator(){
publicintcompare(NodeDatao1,NodeDatao2){
returno1.weight-o2.weight;
}
});

for(inti=0;iqueue){
while(queue.size()>1){

NodeDataleft=queue.poll();//取得左节点
NodeDataright=queue.poll();//取得右节点

NodeDataroot=newNodeData();//创建新节点
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);
}
NodeDatafirstNode=queue.poll();
returnfirstNode;
}
/**
*第四步：
*寻找叶节点并获得哈夫曼编码
*@paramroot根节点
*/
privatevoidachievehfmCode(NodeDataroot){

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());
}
}
/**
*根据某叶节点获得该叶节点的哈夫曼编码
*@paramleafNode叶节点对象
*/
privateStringachieveLeafCode(NodeDataleafNode){
Stringstr="";
/*****************存储节点01编码的队列****************/
Listlist_hfmCode=newArrayList();
list_hfmCode.add(leafNode.point);
NodeDataparent=leafNode.getParent();

while(null!=parent){
list_hfmCode.add(parent.point);
parent=parent.getParent();
}

intsize=list_hfmCode.size();
for(inti=size-2;i>=0;i--){
str+=list_hfmCode.get(i);
}
System.out.println(leafNode.weight+"的哈夫曼编码为>>>"+str);
returnstr;
}
/**
*第五步：
*根据获得的哈夫曼表创建码表
*Integer为字节byte[0~256)
*String为哈夫曼编码
*@return码表
*/
publicMapcreateMap(){
int[]hfm_Codes=this.statistic("F:\\JAVA\\压缩前.txt");//获得文件字节信息
PriorityQueuequeue=this.createQueue(hfm_Codes);//获得优先队列
/*
*获得哈夫曼树的根节点，
*this.createTree(queue)方法调用之后(含有poll())，queue.size()=0
*/
NodeDataroot=this.createTree(queue);
this.achievehfmCode(root);//获得哈夫曼编码并将其存入数组中

Mapmap=newHashMap();
for(inti=0;i<256;i++){
if(null!=array_Str[i]){
map.put(i,array_Str[i]);
}
}
returnmap;
}
/**
*存储字节哈夫曼编码的数组
*下标：字节数据
*元素：哈夫曼编码
*/
publicString[]array_Str=newString[256];
}

3.将码表写入压缩文件并压缩正文


packagecompressFile;

importjava.io.BufferedInputStream;
importjava.io.BufferedOutputStream;
importjava.io.DataOutputStream;
importjava.io.FileInputStream;
importjava.io.FileOutputStream;
importjava.io.IOException;
importjava.util.Iterator;
importjava.util.Map;
importjava.util.Set;

/**
*将码表和文件写入新的文件中
*@authorAndrew
*
*/
publicclassWriteFile{

//实例化创建码表类对象
privateStatisticBytesstatistic=newStatisticBytes();
privateMapmap=statistic.createMap();//获得码表
//字节接收变量，接收哈夫曼编码连接够8位时转换的字节
privateintexmpCode;
publicstaticintsize_File;

publicstaticvoidmain(String[]args){
WriteFilewriteFile=newWriteFile();
writeFile.init();
}

privatevoidinit(){

StringfilePath="F:\\JAVA\\压缩后.txt";
this.writeFile(filePath);
}

/**
*第一步：向文件中写入码表
*
*@paramdataOut
*基本数据流
*/
privatevoidwriteCodeTable(DataOutputStreamdataOut){
Setset=map.keySet();
Iteratorp=set.iterator();

try{
//向文件中写入码表的长度
dataOut.writeInt(map.size());
while(p.hasNext()){
Integerkey=p.next();
StringhfmCode=map.get(key);

dataOut.writeInt(key);//写入字节
//写入哈夫曼编码的长度
dataOut.writeByte(hfmCode.length());
for(inti=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){
intnum=8-transString.length()%8;
for(inti=0;i
二.哈夫曼解压 


  原理:将压缩的逆向，即你是如何压缩的就怎样去解压。相当于你根据自己定义的协议进行压缩与解压缩文件。


代码如下：


packagedecompressionFile;

importjava.io.DataInputStream;
importjava.io.FileInputStream;
importjava.io.FileOutputStream;
importjava.io.IOException;
importjava.io.InputStream;
importjava.io.OutputStream;
importjava.util.ArrayList;
importjava.util.HashMap;
importjava.util.Iterator;
importjava.util.List;
importjava.util.Map;
importjava.util.Set;

/**
*解压文件从压缩文件中读入数据解压
*
*@authorAndrew
*
*/
publicclassReadFile{
/**
*码表Integter:字节[0,255)String：哈夫曼编码
*/
privateMapcode_Map=newHashMap();

publicstaticvoidmain(String[]args){
ReadFilereadFile=newReadFile();
readFile.readFile();
}

/**
*第一步：从文件中读出码表
*
*@paramdataInput
*基本数据输入流
*
*/
privatevoidreadMap(DataInputStreamdataInput){

try{
//读出码表的长度
intsize_Map=dataInput.readInt();
/****************读出码表信息************************************/
for(inti=0;i>>>"+data+"!!!!!!!>>"+str);
code_Map.put(data,str);
}
/***************************************************************/
}catch(IOExceptione){
e.printStackTrace();
}
}

/**
*第二步：解压正式文件
*/
privatevoidreadFile(){
try{
//文件输入流
InputStreaminput=newFileInputStream("F:\\JAVA\\压缩后.txt");
//BufferedInputStreambIn=newBufferedInputStream(input);
DataInputStreamdInput=newDataInputStream(input);
//调用读出码表的方法
this.readMap(dInput);
bytezerofill=dInput.readByte();//读出文件补零个数
System.out.println("补零个数》》》>>>>"+zerofill);
//文件输出流
OutputStreamout=newFileOutputStream("F:\\JAVA\\解压后.txt");

StringtransString="";//接收用于匹配码表中哈夫曼编码的字符串
StringwaiteString="";//接收截取哈夫曼编码后剩余的字符串

/***********************************不耗内存的方法*****************************************/
intreadCode=input.read();//从压缩文件中读出一个数据
intsize=input.available();
for(intj=0;j<=size;j++){
System.out.println("readCodereadCodereadCode》》>>>>"+readCode);
waiteString+=this.changeIntToBinaryString(readCode);//将读到的整数转化为01字符串
for(inti=0;ilist=newArrayList();
//while(-1!=readCode){
//Stringstr=this.changeIntToBinaryString(readCode);
//for(inti=0;iset=code_Map.keySet();
Iteratorp=set.iterator();
while(p.hasNext()){
Integerkey=p.next();//获得码表中的字节数据
StringhfmCode=code_Map.get(key);//获得哈夫曼编码
if(hfmCode.equals(str)){
out.write(key);
returntrue;
}
}
returnfalse;
}
/**
*根据"除2取余，逆序排列"法
*将十进制数字转化为二进制字符串
*@parama要转化的数字
*@return01字符串
*/
privateStringchangeIntToBinaryString(inta){
intb=a;
intcount=0;//记录a可转化为01串的个数，在不够8为时便于补零
Stringstr="";//逆序二进制字符串
StringexmpStr="";//顺序二进制字符串

while(a!=0){
b=a/2;
if(a%2!=0){
str+=1;
}else{
str+=0;
}
a=b;
count++;
}
//不够8位的地方补零
for(inti=0;i<8-count;i++){
str+=0;
}
//将转化后的二进制字符串正序
for(intj=7;j>=0;j--){
System.out.print(str.charAt(j));
exmpStr+=str.charAt(j);
}
System.out.println("转化后的字符串>>>>>>>>>"+exmpStr);
returnexmpStr;
}
}

java实现哈夫曼压缩的实例

热门推荐

随机推荐