文件压缩总结
历时10多天,文件压缩终于能用了。从最开始的构造huffman树到最后的解压缩,遇到了不少纠结的难题。下面就和大家分享一下做文件压缩的心得。
1.构建huffman树。由于数据结构基础有限,也想不到高明的压缩方法,便只能用书上的一种简单而实用的方法---huffman编码。Huffman树是一种特殊的二叉树,我把构建它分成了4部,建立了4个方法:
a.统计传入数据中每个字符出现的次数,这个数据可以是一个文件,也可以是一个字符串。字符作为key,次数作为value存入一个map中。
b.将上面得到的map作为参数,建立一个由TreeNode组成的ArrayList其中map的key值作为TreeNode的flag,map中的value作为TreeNode的weight。
c.上面一步便得到了由huffman树叶子节点组成的ArrayList,然后就是建树了,由于huffman树的叶结点的个数为n,那么它的中间结点的个数肯定是n-1,由次每次对ArrayList由小到大排序,取出前面的最小值和次小值,新建一个结点,对这3个结点进行连接,然后新节点入队,前面两个出队,循环n-1次最终可得到连接好的huffman树。
d.将得到的huffman树进行编码,得到编好码的huffman树。
这4步c和d是最难的,d步的代码想了很久也没有想出来,最后还是问了别人才搞到递归算法,后来自己还设计了一种非递归的算法,递归和非递归的代码如下:
/**
* 先序遍历huffman树,并得到其编码(递归算法)
* @param root: 要遍历的huffman树
* @param hfmCode: 所遍历结点的huffman编码
*/
public void preVisitTree(TreeNode root , String hfmCode){
//如果根不为0
if(root != null){
root.setHuffmanCode(hfmCode);
String lCode = hfmCode + "0";
preVisitTree(root.getLchild() , lCode);
String rCode = hfmCode+"1";
preVisitTree(root.getRchild() , rCode);
}
}
/**
* 非递归获取哈夫曼编码
* @param root: 哈夫曼树根节点
*/
public void setHfmCode(TreeNode root){
java.util.ArrayList<TreeNode> treeList = new java.util.ArrayList<TreeNode>();
treeList.add(root);
TreeNode tempNode;//临时引用
String hfmCode = "";
//对huffman树层次遍历
while(!treeList.isEmpty()){
tempNode = treeList.remove(0);//头元素出队进行运算
hfmCode = tempNode.getHuffmanCode();
if(tempNode.getLchild() != null){
treeList.add(tempNode.getLchild());
hfmCode = tempNode.getHuffmanCode();
tempNode.getLchild().setHuffmanCode(hfmCode + "0");
}
if(tempNode.getRchild() != null){
treeList.add(tempNode.getRchild());
hfmCode = tempNode.getHuffmanCode();
tempNode.getRchild().setHuffmanCode(hfmCode + "1");
}
}
}
2.压缩文件到指定目录。至此,压缩的第一部就已经完成,我们得到了一个由file中所有字节作为flag,其个数作为weight的带huffman编码的树。
我们压缩后的文件应该分为两部分:码表和压缩体。
码表是一个由字节作为key,字节对应的huffman编码作为value的map对象。个人认为如果将码表压缩在文件前端,对解压缩应该要方便一些。因为解压缩一开始就可以把码表读出来保存在map对象中。码表压缩时第一位应该保存一个int值,是map的size()。而且压缩码表的时候可以用一个小技巧,压缩时的码表是map<Byte , String>由于解压缩是是用字符串找字节,而map中的方法containsKey()和get()都只能是由key值找value值,为了方便可以先存value(String)再存key(Byte),当然也可以先存key(Byte)再存value(String)上一部就留给解压缩码表时完成。值得注意的是无论先存什么,为了后来操作方便都应该在存入String前存入一个int值是这个String(huffman)编码的长度。
压缩压缩体的时候也有许多小技巧,为了方便操作,第一个存入的数据可以是这个压缩体的大小。而第二个则是字符串末尾补零的个数,因为将文件的所有字节转换为一个字符串,这个串不一定就是8的倍数,最后很有可能要补0,为此我专门写了一个方法来计算压缩体的大小和补零的个数,利用的则是层次遍历第一部的到的huffman树,代码如下:
/**
* 得到补零的个数和压缩后文件的字节数
* @param src:源文件地址
* @param root:压缩用huffman树根节点
*/
public void getCompressInfo(String src, TreeNode root) {
// 辅助计数器
int tempCount = 0;
// 建立一个结点队列
java.util.ArrayList<TreeNode> treeList = new java.util.ArrayList<TreeNode>();
treeList.add(root);
TreeNode tempNode;// 临时变量
while (!treeList.isEmpty()) {
tempNode = treeList.remove(0);
// 如果是叶子结点,则累加其1,0个数
if (tempNode.getLchild() == null && tempNode.getRchild() == null) {
// 统计补零个数
numOfZero += tempNode.getWeight() * tempNode.getHuffmanCode().length();
numOfZero = numOfZero % 8;
// 统计字节数
tempCount += tempNode.getWeight() * tempNode.getHuffmanCode().length();
count += tempCount / 8;
tempCount = tempCount % 8;
}
// 如果有左右孩子则入队
if (tempNode.getLchild() != null) {
treeList.add(tempNode.getLchild());
}
if (tempNode.getRchild() != null) {
treeList.add(tempNode.getRchild());
}
}
if (tempCount != 0) {
count++;
}
numOfZero = 8 - numOfZero;
}
存好这两个数据以后则将源文件中的字节一个个的读出来,读出一个,从map中找到其对应的huffmanCode,一步步累加,当这个huffmanCode大于等于8的时候则将前八位转换成一个int(这里可以自己写方法也可以用效率更高的Java API方法Integer.parseInt),写入后八位。然后截取掉前八位,这两个步骤都可以用String类中的substring方法。
3.将文件解压缩。解压缩是压缩的逆过程,但比压缩更加纠结。解压缩第一步就是读出码表将其保存如一个map<String , Byte>中。
读完码表后便可以对压缩体解压。解压时需要注意的是要和压缩时压缩进去的数据一一对应。错一点点就会产生蝴蝶效应,全部解错。另外和压缩一样,解压缩也可以读一个换成String然后在码表中找到对应的字节,剩下的找不到的前加到下一个String,其中最要注意的就是在用Integer.toBinaryString时,前面位的0可能丢失,如果得到的字符串不足八位,则前面一定要补零。实现这一步的关键代码如下:
// 处理前面所有未补零的字节
while (count > 1) {
b = dis.read();//从压缩文件中读取第一个压缩体的字节 String tempStr = Integer.toBinaryString(b);// 得到压缩后的字节,并将其转化为字符串
int strLen = tempStr.length();//如果tempStr不足八位.前面补零
if(strLen < 8){
for(int i = 0 ; i < 8-strLen ; i++){
tempStr = "0" + tempStr;
}
}
str = str + tempStr;
count--;
// 一位一位的查找map中是否由对应的字节,有则写入
while (str.length() != 0) {
if (str.length() == 1) {
firstCode += str;
str = "";
}
if (str.length() > 1) {
firstCode += str.substring(0, 1);
str = str.substring(1);
}
if (map.containsKey(firstCode)) {
dos.write(map.get(firstCode));// 得到串对应的value值,并写入
firstCode = "";// 将firstCode重新初始化
}
}
}
if(numOfZero != 0){//处理最后的补零位
b = dis.read();
String tempStr = Integer.toBinaryString(b);
if(tempStr.length() < 8){
int k = 8 - tempStr.length();
for(int i = 0 ; i < k ; i++){
tempStr = "0" + tempStr;
}
}
tempStr = tempStr.substring(0,8 - numOfZero);
str = str+tempStr;
for(int i = 0 ; i < tempStr.length() ; i++){
// 一位一位的查找map中是否由对应的字节,有则写入
if(str.length() == 1){
firstCode += str;
str = "";
}
if (str.length() > 1) {
firstCode += str.substring(0,1);
str = str.substring(1);
}
if (map.containsKey(firstCode)) {
dos.write(map.get(firstCode));// 得到串对应的value值,并写入
firstCode = "";// 将firstCode重新初始化
}
}
}
由这三步,压缩基本就可以实现了,在这次做压缩的过程中,遇到了许多的bug,我们应当直面惨淡的bug,不断的System.out.println()测试每一步数据,找到他再仔细思考,找到一个修改一个。让写出的程序可以针对每一种特殊情况的发生。
分享到:
相关推荐
android源码开发实战19.01.zip,
AlphaControls v7.59 Stable Released(19.01.2012) - Full Source.7z
中国流行性感冒发病数为122.68万例,占传染病发病总人数的19.01.docx
DEV5.11+EGE19.11。支持win10,win7.可以避免EGE15.01的程序白屏卡死现象。相关安装文档可以看我的文档。
CSharpAdvanced-19.01.2021 包含课程CSharpAdvanced的资料的存储库-19.01.2021
Dupzilla 从用户所选文件夹中删除重复的文件
非常好的皮肤控件。for d5-xe2 c++6--2010
EGE图形库ege19.01_all.7z
该文件用于高级格式化安国芯片的U盘,解决windows系统格式化被写保护的U盘问题。2019最新软件。内含帮助文档,帮助各个格式化U盘困难的各位。
Node.js 是一个基于 Chrome V8 引擎的 JavaScript 运行时
ege19.01_all (支持vc2019,vc2017,vc2015,devcpp5.11,codeblocks,etc)
版本 v19.01.11 新增资源库可选择联网更新功能 新增清空列表前提示确认 新增加载收藏夹前提示确认 新增可选是否启用广告过滤 新增清晰度选择保存记录 更新资源库勾选功能改为下拉单选 更新磁力链获取方式为双向获取 ...
vt_pro-e_5.3.19.01
三个版本的安国主控工具。 1. ALCOR_U2_MP_v18.05.29.02→6989SN-GTC/GTD/GTE,MLC:V6.0,D3_ED3:V6/7.0 带AU698X量产工具手册 2.ALCOR_U2_MP_v19.04.01.00→6989SN-GTC/GTD/GTE,MLC:V6.0,D3_ED3:VA.0 ...
12341231231231231231231
这是一个图形库 作者张唐 使用方法和ege图形库一样 该资源仅供学习参考 谢谢
19.01.2013 0.98.99 Mathlib (sc151) based on Naoki Shibata's SLEEF-lib. SMP Mandelbrot, randall (flatassembler forums) Updates for network and audio drivers/applications Improved Fourier Transform ...
文件文献权ArquitecturaTangoRestôSoportadas版本超级探戈餐厅必不可少的功能19.01.000.2576或更高。安装维修服务说明: •在API档案库中执行以下操作,请在API档案库中执行以下操作: preinstall.resto.api....
因此您可以使用 plex 搜索剪辑有海报和拇指以及其他一些元数据它使用 JSON api,因此不会因站点更改而中断更新: 15.04.2015 小修正速度提升19.01.2015 修复新的 api 格式03.09.2014 添加了新的 512px 图标02.09....