多媒体大作业由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“多媒体大作业要求”。
多媒体大作业 文件压缩与解压缩的实现
学号： 姓名： 班级：
2015/12/17
日期：
目录
一 文件
二 压缩解压缩实现细节
三 代码
四 测试结果
五 存在问题
一文件
文件格式 ：.txt.jpg 文件都可以
本次测试 为一篇文章的txt文件，以及一张图片。
二压缩解压缩实现细节
算法：哈夫曼算法 原理及步骤：
1．读取文件，统计每一种字节出现的次数，将出现的字节种类与对应的次数保存起来（可采用数组或者是HashMap，或者是其他的数据结构）
保存完了之后干什么呢？？当然是构建哈弗曼树呀。第二步：
2.利用得到的字节与对应的频次构建哈弗曼树，需要注意的是，构建树的时候是以字节出现的频次作为我们的评判标准，出现次数越多的放在越上层。
比如我们上面所说的这个文件，它所构成的树应该是这样的：
我们现在得到的树还处于未编码的状态，那么第三步毫无疑问就是我们所说的编码了：
3.将得到的哈弗曼树进行编码
编码之后的树就变成这个样子了（采取向左编1的方式）：
编码之后，A所对应的的编码就是111，B就是110，C是10，D是0，那么我们的文件就变成了11111011,01010100，000，下面要把这些10串每8个作为一组编码成一个新的字节（2进制转10进制），所以这里每8位我也特别用逗号表示出来了。
(1)如果最后几位不满8个怎么办？
定义这样一个规则，在最后的位置补0，在文件的末尾再加一位表示最后一个数补0的个数，这样的话这个问题就变得很简单了。
(2)压缩之后怎么知道压缩前每种字节对应的编码是什么样子的？
那么要完成压缩，最关键的一步，还要将压缩时所得到的每个字节对应的码表写入文件，这样才能保证，所做的工作是可逆的。4．根据每种字节对应的哈弗曼编码，将文件转换成01字符串 5．将得到的01串重新编码成新的byte数组写入文件
6.对象化的实现方法中，提供了按位输入与输出的类，这些类都是自定义的，因为在编程中所能操作的计算机的最小单元是byte，那么在这个类中是怎么做的呢？将一个字节进行8次移位按位与运算，就得到了这个字节的8个bit的表示方式。
三代码
哈夫曼树类
package 哈弗曼压缩;
import java.io.DataInputStream;import java.io.DataOutputStream;import java.io.IOException;import java.util.PriorityQueue;
public cla HuffmanTree {
private CharCounter theCounts;//字符统计类对象
private HuffNode root;//根结点
private HuffNode[] theNodes=new HuffNode[BitUtils.DIFF_BYTES+1];//public static final int ERROR=-3;//错误
public static final int INCOMPLETE_CODE=-2;//不完全的结点编码 public static final int END=BitUtils.DIFF_BYTES;//字节的溢出位 /** * 实例化一个字符统计类对象 */ public HuffmanTree(){
} /** * 可以通过CharCounter对象来创建一个huffmanTree对象 * @param cc CharCounter对象 */ public HuffmanTree(CharCounter cc){ theCounts=cc;root=null;theCounts=new CharCounter();root=null;存储HuffNode的数组
createTree();//创建HuffmanTree } /** * 得到要寻找的字符编码所在的树结点,如果该字符不在树上，则返回null表示出错,否 * @param ch 当前结点的下标 * @return 结点相对的字符编码数组 */ public int[] getCode(int ch){
HuffNode current=theNodes[ch];
if(current==null)return null;String v=“”;//结点的编码
HuffNode parent=current.parent;
while(parent!=null){
if(parent.left==current)v=“0”+v;//左结点编码 else 则,通过父亲链逆向查找,直到到达根结点
}
} v=“1”+v;//右结点编码
//向下遍历
current=current.parent;parent=current.parent;int len=v.length();int [] result=new int[len];//创建一个与编码相同大小数组 for(int i=0;i
* @return 存储在结点中的值(如果结点不是叶子结点,则返回符号INCOMPLETE)*/ public int getChar(String code){
} /** * 写入编码表的方法
* @param out 写入的数据流 * @throws IOException */ public
void
writeEncodingTable(DataOutputStream
out)
throws HuffNode leaf=root;//获取根结点 int len=code.length();//按照编码向左或向右遍历到叶子结点
for(int i=0;leaf!=null&&i
if(code.charAt(i)=='0')leaf=leaf.left;leaf=leaf.right;else //根结点为空
if(leaf==null)return ERROR;return leaf.value;IOException{ for(int i=0;i
if(theCounts.getCount(i)>0){ out.writeByte(i);//将字节写入（通常是文件）
out.writeInt(theCounts.getCount(i));//将字节出现的次数写入（通常是文件）
} }
} //最后写入0表示编码的结束 out.writeByte(0);out.writeInt(0);/** * 读取编码表的方法
* @param in 数据输入流对象 * @throws IOException */ public
void
readEncodingTable(DataInputStream
in)
throws IOException{ for(int i=0;i
} ch=in.readByte();//读到的字节 num=in.readInt();//字符出现的次数 if(num==0)//如果读到0表示编码表的结束
break;theCounts.setCount(ch, num);createTree();//创建HuffmanTree } /** * 构造哈弗曼编码树的方法 */ public void createTree(){
//创建一个优先队列来保存HuffNode PriorityQueue pq=new PriorityQueue();
for(int i=0;i
}
theNodes[END] =new HuffNode(END,1,null,null,null);pq.add(theNodes[END]);//当剩余的结点多于一个时 while(pq.size()>1){ if(theCounts.getCount(i)>0){//如果某一个字节出现过
HuffNode newNode=new theNodes[i]=newNode;HuffNode(i,theCounts.getCount(i),null,null,null);pq.add(newNode);//将新结点添加到队列中 } //每次取出当前最小的两个结点
HuffNode n1=pq.remove();//remove方法与poll方法的唯一不同之处在于:此队列为空时将抛出一个异常
HuffNode n2=pq.remove();
} 解压缩类
package 哈弗曼压缩;/** * 包含解压缩的包装类 */ import java.io.DataInputStream;import java.io.IOException;import java.io.InputStream;
public cla HZIPInputStream extends InputStream{
private BitInputStream bin;//位输入流
private HuffmanTree codeTree;//编码的HuffmanTree对象 /** * 封装InputStream对象,实例化HuffmanTree对象与BitInputStream对象,并读
} //将最小的两个结点链接形成新结点 HuffNode n1.parent=n2.parent=result;//将新结点添加到队列当中 pq.add(result);
result=new HuffNode(INCOMPLETE_CODE,n1.weight+n2.weight,n1,n2,null);root=pq.element();//根结点就是队列中的最后一个结点 } 入哈弗曼编码
* @param in
* @throws IOException */ public HZIPInputStream(InputStream in)throws IOException{
} /** * 读取文件的方法 */ //数据输入流
DataInputStream din=new DataInputStream(in);
codeTree=new HuffmanTree();codeTree.readEncodingTable(din);
bin=new BitInputStream(in);
} public int read()throws IOException{
} /** * 关闭输入流 */ public void close()throws IOException{ } bin.close();String bits=“”;//哈弗曼编码的字符串 int bit;//位
int decode;//解码后的字符 while(true){
} bit=bin.readBit();if(bit ==-1)throw new IOException(“Unexpected EOF”);//意外的资源结束
bits+=bit;decode=codeTree.getChar(bits);//获取编码对应的字符
if(decode==HuffmanTree.INCOMPLETE_CODE)//向下搜索到叶子结点
continue;else if(decode==HuffmanTree.ERROR)//编码出错
throw new IOException(“Unexpected error”);else if(decode==HuffmanTree.END)//编码溢出
return-1;else return decode;压缩类
package 哈弗曼压缩;/** * 包含压缩的包装类 */ import java.io.ByteArrayInputStream;import java.io.ByteArrayOutputStream;import java.io.DataOutputStream;import java.io.IOException;import java.io.OutputStream;
public cla HZIPOutputStream extends OutputStream{
private
ByteArrayOutputStream
byteOut=new ByteArrayOutputStream();//实例化的一个字节数组输出流对象
private DataOutputStream dout;//数据输出流对象 /**
* 实例化一个DataOutputStream对象的构造方法 * @param out 输出流对象 * @throws IOException */ public HZIPOutputStream(OutputStream out)throws IOException{ } /** * 写入编码频率的方法 */ public void write(int ch)throws IOException{ } /** * 关闭流的方法 */ public void close()throws IOException{ byte[] theInput=byteOut.toByteArray();//将字节数组输出流转换数据转
byteIn=new byteOut.write(ch);dout=new DataOutputStream(out);换成字节数组进行输入
ByteArrayInputStream ByteArrayInputStream(theInput);//将字节数组封装到字节输入流中
CharCounter countObj=new CharCounter(byteIn);//实例化字符统计对象byteIn.close();//关闭字节输入流
HuffmanTree
codeTree=new
HuffmanTree(countObj);//
通
过并统计字节数组的字符出现的次数
CharCounter对象实例化一个HuffmanTree对象
codeTree.writeEncodingTable(dout);//将编码写入数据输出流中
BitOutputStream bout=new BitOutputStream(dout);//创建位输出流
//将按编码转换后的位写入
int len=theInput.length;for(int i=0;i
//关闭流
bout.close();byteOut.close();符
}
}
四测试结果
文件压缩前
Txt文件
界面
开始压缩txt
Txt压缩完
txt解压缩
Txt解压缩完
经过压缩及解压缩后的文件重新打开
Jpg压缩及解压缩完后。
五存在问题
当文件较小或过大时，压缩之后的文件比源文件还大。文件较小时，由于要写入编码表，所以造成了较大的空间占用。
而文件较大时，由于各种字节出现的频率已经趋于了相近的地步，那么我们再来回顾一下哈弗曼的压缩过程时会发现，极端情况下，当所有字节都出现过，且出现的次数相同时，每一种字节的编码长度都达到了8位（哈弗曼树的第9层刚好有256个叶子结点），达不到压缩的效果。
