文件压缩总结(哈夫曼压缩)
在学习哈弗曼压缩之前,还是首先来了解什么是哈夫曼树,哈夫曼编码。
1.哈夫曼树是一种最优二叉树,它的带权路径长度达到最小。树的带权路径长度为所有叶子结点带权路径长度之和。
而结点的带权路径长度是结点的路径长度乘以结点的权值。
2.哈夫曼编码是依据字符出现概率来构造异字头的平均长度最短的码字。从哈弗曼树的根结点开始,按照左子树代码为“0”,右子树代码为“1”的规则,直到树的叶子结点,每个叶子结点的哈弗曼编码就是从根结点开始,将途中经过的枝结点和叶子结点的代码按顺序串起来。
哈夫曼压缩是字节符号用一个特定长度的01序列替代,在文件中出现频率高的符号,使用短的01序列,而出现频率少的字节符号,则用较长的01序列表示。
这里的文件压缩,我还只能做简单的 文件A-->压缩为文件B--->解压为文件C,看文件A和文件C是不是相同。
那么就要分两个大步骤,小步骤:
不过,根据哈弗曼树的特点,我们首先还是要定义结点类型
public class TreeNode {
public TreeNode parent; //双亲结点
public TreeNode left; //左孩子结点
public TreeNode right; //右孩子结点
public byte con;// 结点的数据
public int rate;
public String bian="";
public int count=0;
public TreeNode(byte con, int rate) {
super();
this.con= con;
this.rate = rate;
}
}
然后分两大步骤
一. 首先压缩文件
1. 将源文件A中数据按字节读取,然后用MAP统计每个字节出现的次数(Key--不同的字节,value--次数)。
while (t != -1) {// 如果未到达结尾
byte b = (byte) t;
if (map.containsKey(b)) {// 如果map里面包含number键
int value = map.get(b);// 就可以通过get函数得到number对应的value的值
value++;// 使次数加1
map.put(b, value);
} else {// 如果map里面不包含number键
map.put(b, 1);// number的次数只有一次
}
// 继续读取下一个
t = bis.read();
}
2. 将Map中的value值作为权值,建哈夫曼树,并得到每个字节的哈弗曼编码。
/**
* 创建哈树
* @param nodeQueue 已经得到的优先队列
* @return 创建哈树后,返回树的根结点
*/
public static TreeNode creatTree(PriorityQueue<TreeNode> nodeQueue){
byte a=0; //定义一个byte,用来表示 枝节点的 字节
TreeNode root=null; //用来表示树的根结点
while(nodeQueue.size()>=2){ //当优先队列中 的元素大于2 时,还可以使它们组成新的跟结点
TreeNode left=nodeQueue.poll(); //获取当前队列中的最小元素,并将队列中的该元素删除 。是该节点作为左孩子
TreeNode right=nodeQueue.poll(); //获取当前队列中的最小元素,作为右孩子
root=new TreeNode(a,left.rate+right.rate); //左右孩子的频率之和作为 根结点的 频率
root.left=left; //连接孩子结点和根结点的关系
root.right=right;
if(nodeQueue.size()==0){
return root;
}
nodeQueue.add(root);
}
return root;
}
/**
* 得到哈树 叶子结点的哈弗曼编码
* @param node 哈树的根结点
* @return 将叶子结点的 《字节,编码》存放入 map 中返回
*/
public static HashMap<Byte,String> getCode(TreeNode node){
if(node.con!=(byte)0){
System.out.println((char)node.con+"--zuo--"+node.bian);
codemap.put(node.con, node.bian);
}
TreeNode left=node.left; // 获得左孩子结点
if(left!=null){ //若为非空 则获得它的 哈弗曼编码
left.bian=node.bian+"0";
left.count++;
getCode(left);
}
TreeNode right=node.right; // 获得右孩子结点
if(right!=null){ //若为非空 则获得它的 哈弗曼编码
right.bian=node.bian+"1";
right.count++;
getCode(right);
}
return codemap;
}
3. 压缩关键(压缩文件的格式:码表+文件信息)
再构造Map(Key--每个不同的字节,value--哈弗曼编码)。将文件中的字符串转换成对应的哈弗曼编码(即 0 1串)。将得到的0 1 串转换成字节(当最后不够构成一个字节时,在后面添加0),并最后用一个字节记录添加的0的个数。将整个Map的信息写进文件B,就是码表。同时将得到的字节写进文件B中。
length=writes.length(); //得到当前01串文件的大小
if(length%8==0){
length=length/8+1;
}
else{
length=length/8+2;
}
byte[] ws=new byte[length];
System.out.println("数组的长度是:"+length);
while(writes.length()>0){ //将01串文件写到文件中
length=writes.length(); //得到当前01串文件的大小
if(length>=8){ //若长度大于等于8
write=writes.substring(0,8); //取其前八位
ws[i]=changInt(write); //将这八位的01串转换成 byte
writes=writes.substring(8); //同时得到原文件第8位后面的01串
System.out.println(write+"--ws-->"+(int)ws[i]);
i++;
}else{ //当01文件的长度不够8位时
int bu0=8-length;
for(int j=0;j<bu0;j++){ //再后面补0
writes=writes+"0";
}
ws[ws.length-1]=(byte)bu0;
}
}
bos.write(ws, 0,ws.length);
bos.flush();
bos.close();
其实将码表写进文件中有两种方法,不过,龙哥为了让我们对文件的格式有更深刻的了解,叫我们使用最原始的方法,就是将码表里的信息一个一个的写进文件。具体将字节,哈弗曼编码及每个编码的长度同时记录在文件中。其实在写码表的时候还可以用ObjectInputStream和ObjectOutputStream流,直接将整个码表作为一个对象一次就可以写进文件中,这样就简单多了。不过,初学时,还是使用前者好些,这样有利于自己对整个项目的深层掌握。等对这个项目完全非常了解掌握后,就可以做精简版的文件压缩了。
二.解压过程
4.根据码表得到Map(Key--每个不同的字节,value--哈弗曼编码),将得到的Map转换成Map2(Key--哈弗曼编码,value--每个不同的字节)。并将文件B中的文件信息部分转换成01串
int MapL=dis.readInt(); //得到 map 的长度
codess=new String[MapL];
for(int t=0;t<MapL;t++){
byte zij=dis.readByte(); //得到每个字节
byte coL=dis.readByte();//得到 每个编码的长度
byte[] codes=new byte[coL]; //定义一个 byte 数组 ,用来存储 每个 哈夫曼编码
dis.read(codes, 0, coL);
//将一个字节的哈弗曼编码 转换成 字符串形式
String cos=new String(codes); //得到一个整的 哈夫曼编码
codess[t]=cos; //
System.out.println(zij+"--对应点->"+cos);
map.put(cos,zij); //每次获得的 一个字节于它对应的 编码, 就将它们放入 map 中
}
读取文件中的字节,并将其转换成0 1串
int length=dis.readInt();
System.out.println("-文件的长度->"+length);
for(int j=0;j<length-1;j++){
b=dis.readByte(); //读取文件中的 字节
System.out.println("---重新输出-->"+b);
String s=Integer.toBinaryString(b);
System.out.println("-b的二进制-->"+s+"--->"+s.length());
if(s.length()>8){
s0="";
s0=s.substring(24,s.length());
}else if(s.length()<8){
int len=8-s.length();
for(int k=0;k<len;k++){
s1=s1+"0";
}
s0=s1+s;
}
code=code+s0; //调用toBinaryString 方法,将十进制转换成 01二进制
System.out.println(code+"-总长度为:"+code.length());
}
b=dis.readByte();
n=b;
System.out.println("-n的值是:-->"+n);
dis.close();
fis.close();
code=code.substring(0, (code.length()-n));
System.out.println("-新的code ->"+code);
5.根据Map2将得到的01串拆分,也就是将01串中头部分 与Map中的Key值匹配,依次将整个01串 还原成字节,同时将得到的所有字节写进文件C中
rWrite(code,fHou);
public void rWrite(String code,String fHou){
System.out.println("--->看不懂错误啊!!");
String path="D:\\1000\\A"+fHou;
FileOutputStream fos;
try {
fos = new FileOutputStream(path);// 申明一个文件输出流
// 转成缓冲流
DataOutputStream dos = new DataOutputStream(fos);
int m=1; //标志获取01 串的最后位置
String code2=""; //存储每次获得的原文件01 串的一个子集
while(code.length()>=m){
code2=code.substring(0,m);//获取当前01 字符串的 前m 位
System.out.println("???进来没?"+"-->"+code2);
for(int j=0;j<codess.length;j++){
if(code2.equals(codess[j])){
byte b2=map.get(codess[j]); //由编码,获取他的 字节
System.out.println("--->"+(char)b2);
dos.writeByte(b2);
code=code.substring(m);
m=0;
System.out.println("code的长度为:"+code.length());
break;
}
}
m++;
}
dos.close();
fos.close();
} catch (IOException e) {
e.printStackTrace();
}
}
这里就基本上完成了文件的压缩和解压了。
遇到的困难:
1. 之前建树是个大问题,因为建哈弗曼树涉及到了排序的问题,而每个结点又不是一个简单的数据类型,开始有尝试过队列和数组来实现排序的问题,但在实现过程中,遇到很大困难,原因还是前面那个,结点的类型比较复杂,在树形中当前结点交换位置影响到其孩子结点。开始还没意识到这个大问题,总是不能把树正确的搞出来,后来经龙哥指导才知道问题出在哪里。所有他建议使用优先队列,这个好啊,太方便了。不过,说实在话,这个优先队列在针对复杂的对象时,也还是要纠结一番啊,难懂。以后还要多多学习使用。
2. 开始对码表的写入也很是纠结,觉得这是个大问题,很复杂,不知道怎么下手。后来经多次指点之前做过的画图板的保存的文件格式,类似完成码表的写入操作。
3. 还只是单文件的压缩和解压,还不能实现大文件夹的压缩
遇到的问题还是很多,感觉还是基础太不扎实了,很多东西都不会用,而且总是不能有效利用前面学过的知识点,不能将所学系统联系起来。最要命的是特粗心,总是不注意细节,导致很多问题纠结很久,最后发现是出在小问题上。以后一定要特别注意这点。
分享到:
相关推荐
利用哈夫曼编码思想,设计对一个文本文件(.txt)中的字符进行哈夫曼编码,生成编码压缩文件(.txt),并且还可将压缩后的文件进行解码还原为原始文本文件(.txt)。 实现的功能: (1)压缩:实现对文件的压缩,生成...
文件包含可执行程序和源代码,可以直接下载运行。C++ QT 实现文件压缩,有两种压缩算法,一是哈夫曼编码,还要一个是游程编码
实验目的:理解哈弗曼信源编码算法,并能应用于文件压缩中。 实验内容:写出程序,利用哈弗曼编码实现对文件的压缩,并能解压文件。 实验步骤: 1、压缩 (1) 统计原始文件中各字节出现的概率(次数); (2) 采用...
数据结构课程设计用哈夫曼编码实现文件压缩: 一、实验题目: 用哈夫曼编码实现文件压缩 二、实验目的: 1、了解文件的概念。 2、掌握线性链表的插入、删除等算法。 3、掌握Huffman树的概念及构造方法。 4、掌握...
哈夫曼编码进行文本压缩
编码:利用建立好的哈夫曼树对源文件进行编码,实现文件压缩,然后将结果以文件形式保存,如编码文件codefile。 d.译码:利用建立好的哈夫曼树对codefile中的代码进行译码。结果存入译码文件decofile中。 e.输出:...
将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint 中。 3. 测试数据 用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:...
使用哈夫曼编码实现对文本文件的压缩和解压缩
114243 用哈夫曼编码实现文件压缩 doc
哈夫曼编码-文件压缩,数据结构作业,C语言 用哈夫曼树对ASCII文件进行压缩,编码后得到实际压缩的文件,同时还有解码功能,界面的效果 文件夹中含程序的多个版本,分别是代表程序编写是的不同阶段 程序使用C编写,...
用Java实现,哈夫曼编码实现文件压缩,有详细注释
使用小顶堆,哈夫曼树,实现一个简单的文件压缩程序
大二课设作业。使用哈夫曼树进行文件编码,从而实现文件的压缩。整个程序基于QT5.12进行操作,并且实现了可视化界面。包括编码,解码。如果有什么问题,可私戳了解。
利用哈夫曼编码对数据进行无损压缩,实现Huffman压缩的编码器和译码器。 1.首先读入待压缩源文件。 2.然后建立并分析字母表,对每种字符的出现频度进行统计,以频度作为建立Huffman树的权值。 3. 频度表建好后,就...
利用无失真信源编码方法中的哈夫曼编码进行程序设计实践,实现对文件的压缩与解压操作。
上回传的那个可能忘了上传源码,非常抱歉,这里就将源码上传,源码里有错误的话,请指正。
利用哈夫曼编码原理对磁盘文件进行压缩与解压
该技术一般可将数据文件压缩掉20%至90%,其压缩效率取决于被压缩文件的特征。 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时,降低传输成本。但是,这要求在发送端通过一个编码系统对待传送电文...
mfc可视化界面实现的哈夫曼数据压缩编码程序,可以打开文件进行哈夫曼编码压缩,压缩后文件可以存储。