java实现哈夫曼压缩的实例
程序员文章站
2023-12-13 16:04:10
哈夫曼压缩的原理：
通过统计文件中每个字节出现的频率,将8位的01串转换为位数较短的哈夫曼编码.
其中哈夫曼编码是根据文件中字节出现的频率构建的,其中出现频...
哈夫曼压缩的原理：
通过统计文件中每个字节出现的频率,将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;
}
}