多媒体大作业

2020-03-03 12:01:06 来源：范文大全收藏下载本文

多媒体大作业文件压缩与解压缩的实现

学号：姓名：班级：

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);//创建位输出流

//将按编码转换后的位写入