一、在讲具体代码实现之前，先给大家普及一下压缩软件的相关知识引用压缩软件是利用
算法将文件有损或无损地处理，以达到保留
最多文件信息，而令文件体积变小的
应用软件。压缩软件一般同时具有
解压缩的功能。压缩软件的的基本原理是查找文件内的重复字节,并建立一个相同字节的"词典"文件,并用一个代码表示,比如在文件里有几处有一个相同的词"中华人民共和国"用一个代码表示并写入"词典"文件,这样就可以达到缩小文件的目的。常见的压缩软件有WinRAR ,好压(Haozip),WinZip,7-Zip,WinMount,Peazip等等。
哈夫曼树作为数据结构
hashu.html" target="_blank">二叉树章节中最为华彩的一部分，有着其独特的魅力。给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，这样的二叉树便是哈夫曼树，也称为最优二叉树。
二、哈夫曼算法
引用 Huffman算法是一种基于统计的压缩方法。它的本质就是对文本文件中的字符进行重新
编码，对于使用频率越高的字符，其编码也越短。但是任何2个字符的编码， 是不能出现向前包含的。也就是说字符A(假设为00)的编码的前段，不可能为字符B（则B的编码不可能为001，因为这里B的编码中包含了A的前段00，这会给解码难带来不必要的困难，所以这是不允许的）的编码。经过编码后的文本文件，主要包含2个部分：Huffman码表部分和压缩内容部分。解压缩的时候，先把Huffman码表取出来，然后对压缩内容部分各个字符进行逐一解码,形成源文件。
哈夫曼编码生成步骤：
①扫描要压缩的文件，对字符出现的频率进行计算。
②把字符按出现的频率进行排序，组成一个
队列。
③把出现频率最低（权值）的两个字符作为叶子节点，它们的权值之和为根节点组成一棵树。
④把上面叶子节点的两个字符从队列中移除，并把它们组成的根节点加入到队列。
⑤把队列重新进行排序。重复步骤③④⑤直到队列中只有一个节点为止。
⑥把这棵树上的根节点定义为0（可自行定义0或1）左边为0，右边为1。这样就可以得到每个叶子节点的哈夫曼编码了。
三、编码流程（大体思路）
压缩：
1、将要压缩的文件一个一个字节的读出来即扫描要压缩的文件，并统计每个字节的权值即出现的频率。
2、以每个字节的权值来构造哈夫曼树，并给每个字节进行哈夫曼编码。
3、将每个字节和其对应得哈夫曼编码存放进一个Map中，即码表。
4、以这个码表为依照，将文件中的所有字节一一进行编码（生成10字符串），最后在把所有字节的编码依次末尾相加合成一个10字符串。
5、将这个10字符串重新组合，8个为一组，若最后一组不足8个则补0，并记录补0的个数，将每一组的10字符串转化为一个字节，
并将所有的10字符串合成一个字节数组，数组的最后一个元素存放补0的个数。
6、创建一个压缩文件，先将码表的大小写入文件，再将码表写入文件（码表里还有每个字节的哈夫曼编码长度的信息）。
7、最后将之前生成的字节数组写入文件（文件的主要信息）。
解压缩：
1、将压缩的文件同样一个一个字节的读出来。
2、先读出码表的大小，再通过码表的大小读出码表，并将码表的信息存放进一个Map。
3、再接着读出后面的所有字节，并转化成一个10字符串。
4、通过与码表的匹配，从10字符串的第一个字符开始读，若读到的子字符串与码表的某个字节的的编码相同，解压出相应的字节，把该字节保存起来。
并把上面的子字符串从编码中删除，重复上一步骤，直到该项编码
解析完成，最后将此10字符串还原成原来的文件的一个个字节。
5、再将这些字节写入一个新的文件，后缀名改成和原来文件一样，就能打开了。
四、核心代码
1、压缩文件
/**
* 压缩的文件操作
*
* @author king
*
*/
public class CompressFileOption {
/**
* 读取文件
*
* @param path
* :文件路径
* @return:将文件的内容以字节数组的样式返回
*/
public static byte[] readFile(String path) {
byte[] dataByte = null;
try {
java.io.FileInputStream fis = new java.io.FileInputStream(path);
int size = fis.available();// 可读的字节数
dataByte = new byte[size];
fis.read(dataByte);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
return dataByte;
}
/**
* 将码表的相关信息写入文件
*
* @param fileSize
* :原文件大小
* @param map
* :存放码表的map
* @param listCh
* :存放关键码的字符队列
* @param path
* :文件路径
* @throws Exception
*/
public static void writeMap(int fileSize,
java.util.HashMap<Byte, String> map, List<Byte> listBy, String path)
throws Exception {
java.io.FileOutputStream fos = new java.io.FileOutputStream(path);
java.io.DataOutputStream dos = new java.io.DataOutputStream(fos);
dos.writeInt(fileSize);// 将原文件大小写入文件
int mapSize = map.size();// 码表的大小
dos.writeInt(mapSize);// //将码表的大小写入文件
for (int i = 0; i < mapSize; i++) {
fos.write(listBy.get(i));// 将每个字节写入文件
String hfmcode_next = map.get(listBy.get(i));// 得到每个字节对应的哈夫曼编码
byte codeSize = (byte) hfmcode_next.length();// 每个字节对应的哈夫曼编码大小
fos.write(codeSize);// 将每个字节对应的哈夫曼编码大小写入文件
dos.writeChars(hfmcode_next);// 将每个字符对应的哈夫曼编码写入文件
}
dos.flush();
fos.close();
}
/**
* 将压缩好的字节数组写入文件
*
* @param b
* :压缩好的字节数组
* @param path
* :文件路径
*/
public static void writeFile(byte[] b, String path) {
try {
java.io.FileOutputStream fos = new java.io.FileOutputStream(path,
true);
java.io.DataOutputStream dos = new java.io.DataOutputStream(fos);
// 写入字节数组的大小
dos.writeInt(b.length);
fos.write(b);
fos.flush();
fos.close();
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
/**
* 将10字符串转化为一个字节
*
* @param str
* :传入的字符串
* @return:一个字节
*/
private byte CharArrayToByte(String str) {
char[] c = str.toCharArray();// 将字符串str转化为字符数组c
int len = c.length;
byte[] b = new byte[len];
byte value = 0;
byte value_next;
for (int i = 0; i < len; i++) {
b[i] = Byte.parseByte(c[i] + "");
// System.out.println(b[i]);
}
for (int i = 0; i < len; i++) {
value_next = (byte) (b[i] * Math.pow(2, len - i - 1));// 幂计算
value = (byte) (value + value_next);
}
return value;
}
/**
* 将10字符串以8个为一组转化为一个字节数组
*
* @param str
* @return
*/
private byte[] StringToByteArray(String str) {
char[] c = str.toCharArray();// 将字节串str转化为字符数组c
int len = c.length;// 字符串字符的个数
int lenByte;
String s = "";
char c_next;
byte[] b;
if (len % 8 == 0) {// 如果字符串的长度能被8整除
lenByte = len / 8 + 1;
b = new byte[lenByte];
for (int i = 0; i < lenByte - 1; i++) {
for (int j = i * 8; j < (i + 1) * 8; j++) {
c_next = c[j];
s = s + c_next;
}
System.out.println("第" + i + "个字符串：" + s);
b[i] = CharArrayToByte(s);
s = "";
System.out.println("第" + i + "个字符串转化为字节后的值：" + b[i]);
}
b[lenByte - 1] = 0;// 字节数组的最后一个存放补0的个数
} else {// 如果字符串的长度不能被8整除
lenByte = len / 8 + 2;
b = new byte[lenByte];
int remainder = len % 8;// 求出除8的余数
int zeroNum = 8 - remainder;// 补0的个数
System.out.println("补0数：" + zeroNum);
System.out.println("原字符串：" + str);
for (int i = 0; i < zeroNum; i++) {
str = str + '0';// 在字符串后面补0
}
System.out.println("补0后的字符串：" + str);
c = str.toCharArray();
System.out.println("补0后的字符串的字符个数：" + c.length);
for (int i = 0; i < lenByte - 1; i++) {
for (int j = i * 8; j < (i + 1) * 8; j++) {
c_next = c[j];
s = s + c_next;
}
System.out.println("第" + i + "个字符串：" + s);
b[i] = CharArrayToByte(s);
s = "";
System.out.println("第" + i + "个字符串转化为字节后的值：" + b[i]);
}
b[lenByte - 1] = (byte) zeroNum;// 字节数组的最后一个存放补0的个数
}
return b;
}
/**
* 压缩文件
*
* @param path1
* :原文件路径
* @param path2
* :压缩后的文件路径
* @throws Exception
*/
public void CompressFile(String path1, String path2) throws Exception {
// 从文件中得到字节数组
byte[] b = CompressFileOption.readFile(path1);
int b_size = b.length;// 原文件大小
byte[] b_compress;// 字节数组，存放压缩的字符串
String hfmcode = "";// 文件内所有字节的哈夫曼编码
String hfmcode_next;// 文件中每个字节的哈夫曼编码
// 计算字符串中每个字节的权值，并返回一个存放字节和它对应权值的节点队列
List<TreeNode> list = calWeight.calweight(b);
int size = list.size();
Huffman hfm = new Huffman();
// 构建哈夫曼树并返回根节点
TreeNode root = hfm.createHuffman(list);
// 创建哈夫曼编码使其与字符一一对应
hfm.createHfmCode(root, "");
java.util.HashMap<Byte, String> map = hfm.getMap();// 得到码表
List<Byte> listBy = hfm.getList();// 得到存放关键码队列
System.out.println("mapsize---->:" + map.size());
System.out.println("b---->:" + b.length);
for (int i = 0; i < b_size; i++) {
// 得到每个字节的哈夫曼编码
hfmcode_next = map.get(b[i]);
System.out.println("第"+i+"个： " + b[i] + "的编码：" + hfmcode_next);
hfmcode = hfmcode + hfmcode_next;// 将每个字节的哈夫曼编码依次相加为一个01字符串
}
System.out.println("01串大小：" + hfmcode.length());
System.out.println("01串：" + hfmcode);
char[] ch = hfmcode.toCharArray();
System.out.println("01串的大小：" + ch.length);
b_compress = StringToByteArray(hfmcode);// 得到字节数组
for (int i = 0; i < b_compress.length; i++) {
System.out.println("第" + i + "个字节" + b_compress[i]);
}
// 将文件大小和码表相关信息写入文件
writeMap(b_size, map, listBy, path2);
// 将字节数组写入文件
writeFile(b_compress, path2);
}
2、解压缩文件
/**
* 解压缩的文件操作
*
* @author king
*
*/
public class UncompressFileOption {
public static long fileSize;
/**
* 将8位10字符串前面缺0的补上0
*
* @param str
* @return
*/
private String addZero(String str) {
int strLen = str.length();
int zeroNum;
if (strLen < 8) {// 若字符串长度小于8则补0
zeroNum = 8 - strLen;
for (int i = 0; i < zeroNum; i++) {
str = "0" + str;
}
}
return str;
}
/**
* 将整型数组还原成之前的10串，即文件内容的哈夫曼编码
*
* @param n
* @return
*/
private String InttoBinaryString(int[] n) {
int len = n.length;
String[] s = new String[len];// 一个字符串数组存放二进制数据
String BinaryStr = "";
for (int i = 0; i < len - 1; i++) {
s[i] = Integer.toBinaryString(n[i]);
s[i] = addZero(s[i]);
BinaryStr = BinaryStr + s[i];
}
System.out.println("二进制形式表示:" + BinaryStr);
int BinaryStrLen = BinaryStr.length();// 得到为减0前的字符串大小
int zeroSub = n[len - 1];// 之前在末尾补0的个数，现在减去
System.out.println("减0前的字符串大小:" + BinaryStrLen);
System.out.println("需要在字符串末尾减0的个数表示:" + zeroSub);
BinaryStr = BinaryStr.substring(0, BinaryStrLen - zeroSub);
System.out.println("减0后的字符串大小:" + (BinaryStrLen - zeroSub));
System.out.println("减0后的二进制形式表示:" + BinaryStr);
return BinaryStr;
}
/**
* 字符串匹配，判断字符串child是否为parent的前子串
*
* @param parent
* @param child
* @return
*/
private boolean StringMatch(String parent, String child) {
char[] p = parent.toCharArray();
char[] c = child.toCharArray();
// System.out.println("数组p的长度：" + p.length);
// System.out.println("数组c的长度：" + c.length);
boolean b = false;
for (int i = 0; i < c.length; i++) {
if (c[i] == p[i]) {
b = true;
} else {
b = false;
break;// 有一个字符不匹配则跳出循环
}
}
return b;
}
/**
* 解压缩文件
*
* @param path2
* :压缩后的文件路径
* @param path3
* :解压缩后的文件路径
* @throws Exception
*/
public void UncompressFile(String path2, String path3) throws Exception {
HashMap<Byte, String> map = new HashMap<Byte, String>();
java.io.FileInputStream fis = new java.io.FileInputStream(path2);
java.io.DataInputStream dis = new java.io.DataInputStream(fis);
java.io.FileOutputStream fos = new java.io.FileOutputStream(path3);
fileSize = dis.readInt();// 得到原文件的大小
int mapSize = dis.readInt();// 得到码表的大小
byte[] mapKey = new byte[mapSize];// 创建一个字符数组,存放码表中的字节
byte codeSize;// 每个字节对应的哈夫曼编码大小
String hfmcode_next = "";
// 读取码表内容
for (int i = 0; i < mapSize; i++) {
mapKey[i] = (byte) fis.read();// 得到第i个字节
codeSize = (byte) fis.read();// 得到每个字节对应的哈夫曼编码大小
char[] codeChar = new char[codeSize];
for (int j = 0; j < codeSize; j++) {
codeChar[j] = dis.readChar();
hfmcode_next = hfmcode_next + codeChar[j];
}
map.put(mapKey[i], hfmcode_next);// 将键值对放入Map中
hfmcode_next = "";
}
int len = dis.readInt();// 得到压缩好的字节数组的大小
System.out.println("压缩好的字节数组的大小: " + len);
byte[] b = new byte[len];// 字节数组，存放压缩的字节串
int[] n = new int[len];// 整型数组
fis.read(b);// 得到压缩好的文件的字节数组
for (int i = 0; i < b.length; i++) {
System.out.println("第" + i + "个字节:" + b[i]);
// 将字节还原成原来的整型数据
if (b[i] < 0) {
n[i] = b[i] + 256;
} else {
n[i] = b[i];
}
System.out.println("第" + i + "个字节的整型表示:" + n[i]);
}
String formerStr = InttoBinaryString(n);// 得到原10串
System.out.println("formerStr:" + formerStr);
int size = map.size();
System.out.println("mapsize:" + size);
int endIndex = formerStr.length();
System.out.println("endIndex:" + endIndex);
int beginIndex;
// byte[] fileData = new byte[fileSize];
int count = 0;// 记录文件当前是第几个字节
while (!formerStr.isEmpty()) {// 如果字符串不为空
String child;
for (int i = 0; i < mapKey.length; i++) {
child = map.get(mapKey[i]);
if (formerStr.isEmpty()) {// 若字符串为空
break;
}
if (StringMatch(formerStr, child)) {// 若匹配
// 一个字节字节的写入文件
fos.write(mapKey[i]);
count++;
beginIndex = child.length();
formerStr = formerStr.substring(beginIndex, endIndex);
endIndex = endIndex - beginIndex;
}
}
}
fos.flush();
fos.close();
}
五、项目展示
1.压缩软件界面
2.浏览要压缩的文件并指定压缩后的文件路径
3.压缩文本文件的效果
4.解压缩文件及效果
5.压缩bmp格式图片文件效果明显，但是压缩和解压的时间都很长，需改进
- 大小: 24.6 KB
- 大小: 25.4 KB
- 大小: 27.2 KB
- 大小: 6.6 KB
- 大小: 7.2 KB
- CompressFile.rar (533.6 KB)
- 下载次数: 312
- 大小: 8.7 KB
相关文章
