哈夫曼压缩的原理：
通过统计文件中每个字节出现的频率,将8位的01串转换为位数较短的哈夫曼编码.
其中哈夫曼编码是根据文件中字节出现的频率构建的,其中出现频率越高的字节,其路径长度越短;
出现频率越低的字节其路径长度越长.从而达到压缩的目的.
如何构造哈夫曼树?
一. 定义字节类
我的字节类定义了一下属性
java" id="highlighter_783288">
|
1
2
3
4
5
6
|
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.遍历要压缩的文件,统计字节出现的次数.
|
1
2
3
4
5
6
7
8
|
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.字节类
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
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.统计字节的类，并生成码表
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
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.将码表写入压缩文件并压缩正文
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
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 "";
}
}
|
二.哈夫曼解压
原理:将压缩的逆向，即你是如何压缩的就怎样去解压。相当于你根据自己定义的协议进行压缩与解压缩文件。
代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
|
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;
}
}
|
原文链接：http://1641606815.iteye.com/blog/1602277