实验2 Huffman编码对英文文本的压缩和解压缩文档格式.docx
《实验2 Huffman编码对英文文本的压缩和解压缩文档格式.docx》由会员分享,可在线阅读,更多相关《实验2 Huffman编码对英文文本的压缩和解压缩文档格式.docx(31页珍藏版)》请在冰点文库上搜索。
五、实验原理
1.压缩/解压缩流程
压缩流程:
读取扫描文本文件——〉统计字符频率——〉生成码字——〉保存压缩文件
解压缩流程:
读取扫描压缩文件——〉提取字符频率——〉生成码树——〉保存文本文件
2.Huffman编码算法(略)
3.文件操作和位运算(略)
六、Huffman算法的8种不同实现方式
1.huffman_a使用链表结构生成Huffman树的算法,这是最基本的实现方法,效率最低。
2.huffman_b使用《数据结构》(严蔚敏,吴伟民,1997,C语言版)中给出的算法,将二叉树存放在连续空间里(静态链表),空间的每个结点内仍有左子树、右子树、双亲等指针。
3.huffman_c使用CanonicalHuffman编码,同时对huffman_b的存储结构进行改造,将二叉树存放在连续空间tree里,空间的每个结点类型都和结点权值的数据类型相同,空间大小为2*num,tree[0]未用,tree[1..num]是每个元素的权值,生成Huffman后,tree[1..2*num-1]中是双亲结点索引。
4.huffman_d在huffman_c的基础上,增加预先排序的功能先用QuickSort算法对所有元素的权值从小到大排序,这样,排序后最前面的两个元素就是最小的一对元素了。
我们可以直接将它们挑出来,组合成一个子树。
然后再子树的权值用折半插入法插到已排序的元素表中,保证所有结点有序。
为了保证初始元素的顺序不变,我们另外使用了一个索引数组,所有排序中的交换操作都是在索引数组中进行的。
5.huffman_e在huffman_d的基础上,将索引数组放在tree的内部。
为编码方便,将元素权值放在tree[num..2*num-1]处。
将tree[0..num-1]作为索引数组。
排序改为从大到小。
对索引数组排序后,每次从最后选出2个最小值,相加后的结点权值放在索引数组最后,结点索引放在索引数组中倒数第2个位置,然后索引数组大小减1,并将最后一个索引值插入到前面的有序表中,保证索引数组仍然有序。
6.huffman_f在huffman_e的基础上,将排序改为利用堆排序原理选择最小的两个权值。
也即,将所有元素的权值组织成堆后,每次堆内的根结点就是最小值了。
每取出一个根结点后,就把堆尾元素调到根结点重建堆。
取出两个最小值合并成一个子树后,再把子树作为叶子结点放到堆中,并让其上升到合适的位置,保持堆性质不变。
因为每次不必完成整个排序过程,而只是组织成堆,因此,这种方法要比使用快速排序更快。
上述算法参考了mg-1.2.1中Huffman编码的实现,见http:
//www.cs.mu.oz.au/mg/
7.huffman_g当元素权值已经有序时,可以使用A.Moffat和J.Katajainen设计的在权值数组内部构建Huffman的方法。
A.Moffat和J.Katajainen对该算法的描述见http:
//www.cs.mu.oz.au/~alistair/abstracts/inplace.html
8.huffman_h在huffman_f的基础上,增加限制码长的功能。
限制码长的算法参考了zlib-1.1.4中构造限制码长的Huffman编码的源代码。
zlib的源代码见http:
//www.gzip.org/zlib/,其中限制长度的算法在tree.c的gen_bitlen()函数中。
七.Huffman的java实现:
界面类
publicclassComFileFrame{
publicstaticvoidmain(String[]args){
ComFileFramecff=newComFileFrame();
cff.showUI();
}
publicvoidshowUI(){
javax.swing.JFrameframe=newjavax.swing.JFrame();
frame.setSize(200,100);
frame.setLocationRelativeTo(null);
frame.setTitle("
own压缩软件"
);
frame.setLayout(newjava.awt.FlowLayout());
frame.setDefaultCloseOperation(3);
frame.setResizable(false);
javax.swing.JButtoncomf=newjavax.swing.JButton("
压缩"
javax.swing.JButtondecomf=newjavax.swing.JButton("
解压缩"
MouseListenerImplmli=newMouseListenerImpl();
comf.addMouseListener(mli);
decomf.addMouseListener(mli);
javax.swing.JLabellabel=newjavax.swing.JLabel("
Copyright@Chenjunqing"
label.addMouseListener(mli);
frame.add(comf);
frame.add(decomf);
frame.add(label);
frame.setVisible(true);
}
鼠标监听器类
packagejava.Huffman;
importjava.awt.event.MouseEvent;
importjava.awt.event.MouseListener;
importjavax.swing.JButton;
importjavax.swing.JLabel;
publicclassMouseListenerImplimplementsMouseListener{
publicvoidmouseClicked(MouseEvente){
Objectobj=e.getSource();
//得到鼠标单击的对象
if(objinstanceofJButton){//判断鼠标是否单击是按钮
JButtonb=(JButton)obj;
Stringtitle=b.getActionCommand();
//得到按钮的名称
javax.swing.JFileChooserchooser=newjavax.swing.JFileChooser();
//创建一个filechooser,用来获取路径
if(title=="
){//判断单击的是哪个按钮
chooser.setFileSelectionMode(javax.swing.JFileChooser.FILES_ONLY);
//压缩时只允许压缩文件
intt=chooser.showDialog(null,"
if(t==javax.swing.JFileChooser.APPROVE_OPTION){
Stringsource=chooser.getSelectedFile().getAbsolutePath();
//得到源文件的路径
//System.out.println("
sourceis:
"
+source);
//fortest
Stringdestination=source+"
.own"
;
//根据源文件路径产生新文件的路径
destinationis:
+destination);
CompresscomFile=newCompress();
try{
longstart=System.currentTimeMillis();
comFpressFile(source,destination);
longend=System.currentTimeMillis();
longtime=end-start;
javax.swing.JOptionPane.showMessageDialog(null,"
压缩完成!
\n"
+"
压缩用时:
+time+"
ms"
}catch(Exceptione1){
e1.printStackTrace();
}
}
}
elseif(title=="
){
if(source.endsWith("
own"
)){
Stringtemp=source.substring(0,source.length()-4);
ints=temp.lastIndexOf("
\\"
Stringdestination=temp.substring(0,s+1)+"
解压"
+temp.substring(s+1,temp.length());
//System.out.println("
CompressdecomFile=newCompress();
try{
longstart=System.currentTimeMillis();
decomFile.decompressFile(source,destination);
longend=System.currentTimeMillis();
longtime=end-start;
javax.swing.JOptionPane.showMessageDialog(null,"
解压完成!
解压用时:
}catch(Exceptione1){
e1.printStackTrace();
}
}else{
请选择由本软件压缩的文件"
}
elseif(objinstanceofJLabel){
javax.swing.JOptionPane.showMessageDialog(null,"
本软件压缩的文件拓展名为own!
@Override
publicvoidmousePressed(MouseEvente){
//TODOAuto-generatedmethodstub
publicvoidmouseReleased(MouseEvente){
publicvoidmouseEntered(MouseEvente){
publicvoidmouseExited(MouseEvente){
压缩与解压缩方法类
importjava.io.DataInputStream;
importjava.io.DataOutputStream;
importjava.io.FileInputStream;
importjava.io.FileOutputStream;
importjava.util.ArrayList;
importjava.util.HashMap;
/**
*利用Huffman编码进行压缩
*
*@authorChenjunqing
*/
publicclassCompress{
publicstaticvoidmain(String[]args)throwsException{
Compresscps=newCompress();
//HashMap<
Byte,Integer>
map=
//cps.countFile("
d:
\\我的文档\\桌面\\Test.java"
Byte,String>
code=cps.getFileCode(map);
//java.util.Set<
Byte>
set=code.keySet();
//java.util.Iterator<
iter=set.iterator();
//while(iter.hasNext()){
//Bytekey=iter.next();
//Stringvalue=code.get(key);
//System.out.println(key+"
\t"
+value);
//}
longstart=System.currentTimeMillis();
pressFile("
\\我的文档\\桌面\\005.png"
"
\\我的文档\\桌面\\005.own"
//压缩文件
cps.decompressFile("
\\我的文档\\桌面\\解压005.png"
//解压文件
longend=System.currentTimeMillis();
System.out.println("
TimeofRunningis:
+(end-start)+"
/**
*对一个文件进行字节的统计
*@parampath
*:
文件的路径
*@return:
返回一个Map<
字节,出现次数>
publicHashMap<
countFile(Stringpath)throwsException{
HashMap<
map=newHashMap<
();
FileInputStreamfis=newFileInputStream(path);
DataInputStreamdis=newDataInputStream(fis);
//创建文件输入流对象,按照数据类型读取。
intt=-1;
while((t=dis.read())!
=-1){
Bytekey=(byte)t;
if(map.containsKey(key)){
Integervalue=map.get(key);
value++;
map.put(key,value);
}else{
map.put(key,1);
dis.close();
////测试代码
//inttotal=0;
set1=map.keySet();
iter1=set1.iterator();
//while(iter1.hasNext()){
//Bytekey=iter1.next();
//intvalue=map.get(key);
//total++;
//System.out.println(total);
returnmap;
*得到一个HashMap<
的Huffman编码
*@parammap
要转化的HashMap<
返回一个HashMap<
,Byte是字节,String是其对应的Huffman编码。
getFileCode(HashMap<
map){
java.util.Set<
set=map.keySet();
//将MAP<
字符,次数>
的key放到一个Set集合
java.util.Iterator<
//Set向迭代器中放值
ArrayList<
TreeNode>
huff=newArrayList<
//将字符出现的次数作为权值(data),字符作为标志(Sign),把数据转化为节点,存入一个队列中
while(iter.hasNext()){
Bytekey=iter.next();
Integernum=map.get(key);
TreeNodetemp=newTreeNode(num);
temp.setSign(key);
huff.add(temp);
HuffmanTreehfmTree=newHuffmanTree();
//将队列转化为相应的Huffman树,返回树的根节点
TreeNoderoot=hfmTree.ArrayToHuffman(huff);
//hfmTree.printTree(root);
//打印huffman树
code=hfmTree.getHuffmanCode(root);
//得到huffman编码,结果保存在Map<
字符,huffman编码>
////测试代码
set1=code.keySet();
//total++;
returncode;
*得到源文件的压缩文件的方法
*@paramcode
由源文件得到的存储有其中每个字节及其对应Huffman编码的HashMap。
*@paramsource
源文件的路径
*@paramdestination
压缩文件存储的路径
publicvoidcompressFile(Stringsource,Stringdestination)
throwsException{
FileInputStreamfis=newFileInputStream(source);
FileOutputStreamfos=newFileOutputStream(destination);
DataOutputStreamdos=newDataOutputStream(fos);
Stringdata="
//用来暂存编码的过度变量
map=this.countFile(source);
code=this.getFileCode(map