文件的压缩与解压缩
上篇博客学习了哈夫曼树，也自己动手建立了一棵哈树。接下來，我们将在原本的基础上更进一步。通过哈弗曼编码来实现对文件的压缩与解压缩。----------- 下面进入正题。
要实现的目标 ：利用哈夫曼编码思想，设计对一个文本文件（.txt）中的字符进行哈夫曼编码，生成编码压缩文件，并且还可将一个压缩后的文件进行解码还原为原始文本文件（.txt）。
对问题的分析：本程序我们只针对纯文本文件（.txt）的压缩。为了使文件尽可能的缩短，可以对文件中每个字符出现的次数进行统计。设法让出现次数多的字符的二进制码短些，而让那些很少出现的字符的二进制码长一些。若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。为了确保哈夫曼编码的唯一性，我们可以对它的左右子树的大小给予比较限定，如：左子树的权值小于右子树的权值。哈夫曼树中的左右分支各代表‘0’和‘1’,则从根节点到叶子节点所经历的路径分支的‘0’和‘1’组成的字符串，为该节点对应字符的哈夫曼编码。
那么，我们解决问题（压缩）的步骤大致分为如下几步：
1.读取源文件内容，统计各个字符所出现的次数。PS：这里可以采用HashMap来进行存储，当然，你也可以采用其他的数据结构进行存储。
2.统计完成后，接下来就是我们熟悉的构建哈夫曼树啦（上篇博客有写）。我们根据字符所出现的次数的多少进行构建。 构建完成后，我们会发现，出行频率多的处于比较靠上的层次，频率低的则集中在下层。 这是为什么呢？ 呵呵，继续往下看你或许就会明白了。
3.哈树生成后，我们就该为他编码了。在整个哈树中，每个叶子节点的key值都是源文件中出现的，而他的value值则为频次。那么，我们定哈夫曼树中的左右分支各代表‘0’和‘1’,则从根节点到叶子节点所经历的路径分支的‘0’和‘1’组成的字符串，为该节点对应字符的哈夫曼编码。
什么意思？我们还是看个图吧》》》》》
假设对这段文字进行编码：abbcccdddd a：1次 b：2次 c：3次 d：4次
编码后我们会发现，这些字符都能用其哈弗曼编码来进行替代了，如：
a：000
b: 001
c: 01
d: 1
你是不是发现，出现频次越多的字符，其编码的长度越短呀！！！！ 每次，我们在还原的时候，就能尽可能的将出现频率多的字符用相对短的编码来表示，出现频次少的用较长的编码表示，这样的话，我们的编码的总长度就能控制的相对较少。
通过这一步的操作，我们将获取一份可贵的码表呀（解压时也将用到它）！
4.对照码表，将文件的内容，用哈弗曼编码替换,形成一个编码串。
如：abbcccdddd —> 0000010010101011111
5.将编码串按每8位一组，转换成一个byte值，写入byte数组。
在分组的过程中要注意：我们在截取字串的时候，如果遇到不足八位的情况，就在其前面补零，并用byte的最后一个元素表示其补零的个数。
6.将码表和byte数组写入文件，压缩就此完成！~！~
例外： 解压缩正好是压缩的逆过程...
下面附上我的代码：
ps：楼主代码仅供参考，我想表达的主要是自己解决这个问题的思路，代码也未经过多优化。且解决问题的方法多种多样，有好有坏，有效率高的也有效率低的。你有更好的方法，欢迎提出来，欢迎吐槽，大家一起学习，一起进步！
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Random;
/**
* 哈弗曼压缩
*
* @author 吴泽鑫 2013.5.14
*
*/
public class HuffmanCompress {
// 保存从文件中读取的内容
private static StringBuffer str = new StringBuffer();
// 编码的字串
private static StringBuffer code_string;
// 对编码字串进行八位一组解析后，所生成byte数组
private static byte[] code_bytes;
/**
*
* @param path
* 目标文件的路径
* @return 将文件中的内容读入到StringBuffer中，并返回
*/
public StringBuffer readfile(String path) {
File file = new File(path);
int temp;
char c;
// 创建文件输入流
try {
// 创建文件如数流
FileInputStream fin = new FileInputStream(file);
// 封装InputStreamReader
InputStreamReader iread = new InputStreamReader(fin);
// 创建文件输出流
FileOutputStream fou = new FileOutputStream(new File(
"src\\新建 Microsoft Word 文档2.doc"));
// 利用循环读取文件里面的内容 将内容保存至str中
while ((temp = iread.read()) != -1) {
str.append((char) temp);
}
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
return null;
}
public StringBuffer getStr() {
return str;
}
public static void main(String[] args) {
HuffmanCompress huffmancompress = new HuffmanCompress();
// 讀取文件內容，存入StringBuffered中
huffmancompress.readfile("src\\新建 文本文档.txt");
System.out.print(str + "长度：" + str.length());
// 新建一个HashMap String：统计的字符 Integer：出现的频次
Map<String, Integer> map = new HashMap<String, Integer>();
// 统计字符个数
map = huffmancompress.countchar(str, map);
// 根据map,生成一课哈树
HuffmanNode root = huffmancompress.CreatHTree(map);
// System.out.println("【map的大小】-> " + map.size());
// 创建一个码表
List<HuffmanNode> coad_list = new ArrayList<HuffmanNode>();
// 给哈树进行编码
coad_list = huffmancompress.SetCode(root, coad_list);
// System.out.println("【coad_list的长度】-> " + coad_list.size());
// System.out.println("【叶子节点" + "个数】-> " + coad_list.size()
// + "【数据内容如下：（key，count，coad）】");
for (int i = 0; i < coad_list.size(); i++) {
// 小处理： 消除第一个根节点的0，这个0无用。
coad_list.get(i).setCode(
coad_list.get(i).getCode()
.substring(1, coad_list.get(i).getCode().length()));
System.out.println(coad_list.get(i).getKey() + " "
+ coad_list.get(i).getValue() + " "
+ coad_list.get(i).getCode());
}
// 将文件内容转换成编码字串
code_string = huffmancompress.ToCode(str, coad_list);
// System.out.println("\n编码字串为：" + code_string);
// 将编码字串按八位一组转换成byte,存入byte数组中区
code_bytes = HuffmanCompress.SaveToBytes(code_string, coad_list);
// 压缩
HuffmanCompress.CompressFile("新建 文本文档2.txt", coad_list);
// 解压缩
HuffmanCompress.UnZip("新建 文本文档2.txt", "src\\新建 文本文档3.txt");
// 打印所生成的哈树
// huffmancompress.printhuffman(root);
}
/**
* 解压缩过程
*
* @param path_source
* 需要进行解压缩的文件的路径
* @param path_object
* 转换后所形成的新的文件的路径
*/
private static void UnZip(String path_source, String path_object) {
try {
// 创建文件输入流
ObjectInputStream ofin = new ObjectInputStream(new FileInputStream(
path_source));
// 创建文件输出流
FileOutputStream ofout = new FileOutputStream(path_object);
try {
// 读取文件的码表——>需修改 本例测试
List<HuffmanNode> coad_list = new ArrayList<HuffmanNode>();
coad_list = (List<HuffmanNode>) ofin.readObject();
System.out.println("测试---获取码表的长度" + coad_list.size());
System.out.println("测试---获取码表的數字" + coad_list.get(0).getKey()
+ coad_list.get(0).getValue() + " "
+ coad_list.get(0).getCode());
// 读取压缩文件的内容
byte[] bytes = new byte[code_bytes.length];
ofin.read(bytes);
System.out.println("测试---获取压缩文件内容的长度" + bytes.length);
System.out.println("测试---获取压缩文件内容为:" + bytes[0]);
System.out.println("测试---获取压缩文件内容为:" + bytes[1]);
// System.out.println("测试---获取压缩文件内容为(补零个数):" + bytes[2]);
// 将获取的压缩文件的内容转换成Sring编码二进制字串 賦予str
StringBuffer str = new StringBuffer();
for (int i = 0; i < bytes.length; i++) {
str.append(changetoString(bytes[i]));
}
System.out.println("还原字串编码为：" + str);
// 根据码表，将二进制编码字串转换成对应的数据
changtoChar(str.toString(), ofout, coad_list);
} catch (ClassNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
/**
*
* @param str
* @param ofout
* @param coad_list
*/
private static void changtoChar(String str, FileOutputStream ofout,
List<HuffmanNode> coad_list) {
System.out.println("还原字串编码为：" + str);
StringBuffer sb = new StringBuffer();
// 保存最后一个8位字串前面补零的个数 默认为0个
int count = 0;
// 截取最后8为数据 最后八位数据表示补零的个数
String t = str.substring(str.length() - 8);
count = changetobyte(t);
System.out.println("源码：" + str + "最后8位：" + t + "\n补零个数为："
+ changetobyte(t));
str = str.substring(0, str.length() - 8);
System.out.println("取出最后8位后：" + str + "\n补零个数为：" + changetobyte(t));
// 根據count记录的补零个数，除去多余的0
String s1 = str.substring(0, str.length() - 8);
String s2 = str.substring(str.length() - 8);
s2 = s2.substring(count);
System.out.print("最后一位" + s2);
str = s1 + s2;
System.out.print("最后" + str);
for (int i = 0; i < str.length(); i++) {
// 取出以为字串编码
char c = str.charAt(i);
sb.append(c);
String s = sb.toString();
int j;
// 判断是否能在码表中找到对应的
for (j = 0; j < coad_list.size(); j++) {
if (s.equals(coad_list.get(j).getCode())) {
System.out.print(coad_list.get(j).getKey());
try {
ofout.write(coad_list.get(j).getKey().getBytes());
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
sb.setLength(0);
break;
}
}
}
}
private static String changetoString(byte b) {
int m = b;
if (m < 0) {
m *= -1;
}
// 用于保存转换后形成的二进制
String s = "";
// 用于不足8位是补0
StringBuffer s2 = new StringBuffer();
// 用于补符号位 0 （正数）或 1（负数）
StringBuffer s3 = new StringBuffer();
// 补零位数
byte lack = 0;
while (m > 0) {
s = m % 2 + s;
m = m / 2;
}
if (s.length() < 8) {
lack = (byte) (8 - s.length());
for (int i = lack; i > 0; i--) {
s2.append('0');
}
}
if (b < 0) {
s2.setCharAt(0, '1');
}
s = s2.append(s).toString();
// s += s2;
System.out.println(b + " 二进制 " + s + "长度" + s.length());
return s;
}
/**
* 文件压缩方法
* @param path 所产生的压缩文件的路径
* @param coad_list 码表
*/
private static void CompressFile(String path, List<HuffmanNode> coad_list) {
try {
// 創建一個ObjectOutputStream對象輸出流
ObjectOutputStream ofout = new ObjectOutputStream(
new FileOutputStream(path));
// 将码表写入文件
ofout.writeObject(coad_list);
// 将压缩后的内容写入文件
ofout.write(code_bytes);
// 强制写入
ofout.flush();
// 关闭流
ofout.close();
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
/**
* 将编码字串按八位一组转换成byte,存入byte数组中区
*
* @param code_string
* 字符编码串
* @param coad_list
* 码表
* @return
*/
private static byte[] SaveToBytes(StringBuffer code_string,
List<HuffmanNode> coad_list) {
// 获取编码字串的长度
int length = code_string.length();
// 用于保存下表
int index = 0;
// 统计补零的个数 默認為0個
byte lack = 0;
String code = code_string.toString();
// 判断其长度是否为8（位）的倍数,确定byte数组的长度
if (length % 8 == 0) {
code_bytes = new byte[length / 8 + 1];
} else {
code_bytes = new byte[(length / 8) + 2];
}
// System.out.println("code的长度" + code.length());
while (code.length() > 1) {
if (code.length() >= 8) {// 当长度大于等于8时
// 直接截取 8位 装换成byte 存入code_byte数组中去
code_bytes[index] = changetobyte(code.substring(0, 8));
index++;
// 将所取出来的8为字串，从字串中出去掉
code = code.substring(8);
} else { // 当长度不足8位時 我们需要进行补零，补齐8位
// 算出需要补零的个数
lack = (byte) (8 - code.length());
StringBuffer tempstring = new StringBuffer();
// 开始补零
for (int i = lack; i > 0; i--) {
tempstring.append('0');
}
// 将补足8位的串补足（前面补零）
code = tempstring.append(code).toString();
}
}
// 将补零的个数也加入到code_bytes数组中 ， 为将来解压缩时提供依据
code_bytes[index] = lack;
// 返回所生成的byte数组
return code_bytes;
}
/**
* 将二进制字串转换成对应的byte（8位）
*
* @param s
* 带转换成byte的字串
*/
private static byte changetobyte(String s) {
System.out.println("组装Byte：" + s);
// //
// ///////////////
byte a = (byte) (((byte) s.charAt(1) - 48) * 64
+ ((byte) s.charAt(2) - 48) * 32 + ((byte) s.charAt(3) - 48)
* 16 + ((byte) s.charAt(4) - 48) * 8
+ ((byte) s.charAt(5) - 48) * 4 + ((byte) s.charAt(6) - 48) * 2 + ((byte) s
.charAt(7) - 48));
if ((s.charAt(0) - 48) == 1) {
a *= -1;
}
return a;
}
/**
* 将文件内容根据码表转换成编码（0,1）字串
* @param str 文件内容
* @param coad_list 码表
* @return 编码字串
*/
private StringBuffer ToCode(StringBuffer str, List<HuffmanNode> coad_list) {
// 创建一个缓冲字符串
StringBuffer str2 = new StringBuffer();
// 创建一个字符串
String t = new String();
// 利用循环 每读取一个字符，就对照码表，将其转换成编码，并加入到缓冲字符串str2中
for (int i = 0; i < str.length(); i++) {
// 取出字符
char c = str.charAt(i);
// 查码表
t = FindCodeTable(c, coad_list);
// 存入编码串
str2.append(t);
}
return str2;
}
/**
* 对照码表
*
* @param c
* 需要进行对照的字符
* @param coad_list
* 码表
* @return
*/
private String FindCodeTable(char c, List<HuffmanNode> coad_list) {
// 从码表中逐个去匹配 找到了就返回他所对应的编码
for (int i = 0; i < coad_list.size(); i++) {
if (String.valueOf(c).equals(coad_list.get(i).getKey())) {
return coad_list.get(i).getCode();
}
}
return null;
}
/**
* 给哈树设置编码
*
* @param root
* 根节点
* @param coad_list
* 保存叶子节点的队列（哈希编码有值）
* @return coad_list 叶子节点的队列
*/
private List<HuffmanNode> SetCode(HuffmanNode root,
List<HuffmanNode> coad_list) {
if ((root.getLeft_child() == null) && (root.getRight_child() == null)) {
// 为叶子节点
coad_list.add(root);
} else {
// 获取当前节点的哈夫曼编码值
String str = root.getCode();
// 左节点的编码值加上当前节点的编码值
str += root.getLeft_child().getCode();
// 把加后的编码值赋值给左节点
root.getLeft_child().setCode(str);
// 递归左节点
SetCode(root.getLeft_child(), coad_list);
// 获取当前节点的编码值
String str1 = root.getCode();
// 右节点的编码值加上当前节点的编码值
str1 += root.getRight_child().getCode();
// 把加后的编码值赋值给右节点
root.getRight_child().setCode(str1);
// 递归右节点
SetCode(root.getRight_child(), coad_list);
}
return coad_list;
}
/**
* 打印哈夫曼树 ——> 使用先序遍历（根-左-右）
*
* @param rootnode
* 哈树的根节点
*/
private void printhuffman(HuffmanNode rootnode) {
// 指定根节点，从根几点开始找
HuffmanNode temp = rootnode;
// 打印根节点的值
System.out.println("【" + temp.getKey() + "】" + " " + temp.getValue()
+ " " + temp.getCode());
if (rootnode.getLeft_child() != null) {
temp = rootnode.getLeft_child();
// 递归调用自己，表示只要左节点不为空，就把左节点作为新的根节点继续上边步奏
printhuffman(temp);
}
if (rootnode.getRight_child() != null) {
temp = rootnode.getRight_child();
printhuffman(temp);// 同上
}
}
/**
* 根据Map表中的权值，生成一颗哈树
*
* @param map
* Map表
* @return 返回哈树的根节点
*/
private HuffmanNode CreatHTree(Map<String, Integer> map) {
Comparator<HuffmanNode> comparator = new Comparator<HuffmanNode>() {
@Override
public int compare(HuffmanNode o1, HuffmanNode o2) {
int numbera = o1.getValue();
int numberb = o2.getValue();
if (numberb < numbera) {
return 1;
} else if (numberb > numbera) {
return -1;
} else {
return 0;
}
}
};
PriorityQueue<HuffmanNode> queue = new PriorityQueue<HuffmanNode>(
map.size(), comparator);
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
HuffmanNode node = new HuffmanNode((String) entry.getKey(),
(int) entry.getValue());
queue.add(node);
}
while (queue.size() != 1) {
// 取得两个最小的节点
HuffmanNode node1 = queue.poll();
HuffmanNode node2 = queue.poll();
// 生成一个新的节点
HuffmanNode node3 = new HuffmanNode(node1.getValue()
+ node2.getValue(), "0");
node3.setLeft_child(node1);
node1.setCode("0");
node3.setRight_child(node2);
node2.setCode("1");
queue.add(node3);
}
// 获取哈树根节点
HuffmanNode root = queue.poll();
return root;
}
/**
* 统计文件类容中，各个字符出现的频率，且用Map保存，并返回一个统计结果（Map值）
*
* @param str
* 文件内容
* @param map
* 統計結果
* @return map 即各个字符出现的频率情况
*/
private Map<String, Integer> countchar(StringBuffer str,
Map<String, Integer> map) {
System.out.println();
char c;
for (int i = 0; i < str.length(); i++) {
c = str.charAt(i);
String key = String.valueOf(c);
if (map.containsKey(key)) {
map.put(key, map.get(key) + 1);
} else
map.put(key, 1);
}
// map遍历输出
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
String s = (String) entry.getKey();
int n = (int) entry.getValue();
System.out.println(s + " " + n);
}
return map;
}
}
节点类：
import java.io.Serializable;
/**
* 哈夫曼树节点的定义
*
* @author Administrator
*
*/
public class HuffmanNode implements Serializable {
// 成员属性
private HuffmanNode left_child = null;
private HuffmanNode right_child = null;
private HuffmanNode parend = null;
// 权值
private int value;
// key值
private String key;
// 哈弗曼编码
private String code;
public String getCode() {
return code;
}
public void setCode(String code) {
this.code = code;
}
// 构造函数
public HuffmanNode(String key, int value) {
this.value = value;
this.key = key;
}
public HuffmanNode(int value, String code) {
this.value = value;
this.code = code;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public HuffmanNode getLeft_child() {
return left_child;
}
public void setLeft_child(HuffmanNode left_child) {
this.left_child = left_child;
}
public HuffmanNode getRight_child() {
return right_child;
}
public void setRight_child(HuffmanNode right_child) {
this.right_child = right_child;
}
public HuffmanNode getParend() {
return parend;
}
public void setParend(HuffmanNode parend) {
this.parend = parend;
}
}
哈弗曼压缩程序写完之后你会发现，当文件内容不是很多的时候，或是重复的频次过于多的时候，压缩后的大小反倒比没压缩的时候大，尤其是重复的频次过多时，解压时反到可能会出错。当然哈弗曼编码的效率也很值得商榷。 以及我的这个程序只能针对TXT类型的文本，对于doc、xls、ppt又或是其他图片文件的压缩也是不支持的，还有多文件、文件夹的整合压缩都还没有实现的诸多问题，在日后的过程中需要慢慢的完善。
作为我们这种还在学校里面混的菜鸟，自信一定是要有的，要敢去想敢去写。大神牛人们花一天能弄好的程序，我们多花点时间，也能做好，不去尝试就永远都不会。也许我们的代码执行的效率没有他们高，程序也没有他们优化的好，程序结构也不明显，可维护性差，bug也很多...但这也是一个过程，哪个牛人不是从小菜鸟走过来的呢~！~