java实现哈夫曼文件解压缩

本文实例为大家分享了java实现哈夫曼文件解压缩的具体代码，供大家参考，具体内容如下

1、哈夫曼压缩对已经经过压缩处理的文件压缩率比较低，比如ppt和视频。

2、这个程序主要涉及到集合、树、io相关知识。

字符的统计可以用map集合进行统计。
哈夫曼树的构建过程也并不复杂：
①先对树的集合按照根节点大小进行排序
②拿出根节点数值最小的两棵树，用它两构建成一颗新的树；
③从集合中删除之前那两颗根节点最小的数；
④把新生成的树加入到集合中
一直循环重复上面的过程，直到集合的大小变成1为止；
写出、读取文件时注意使用对象流object流。

3、个程序可以对字符进行压缩，也可以对文件进行压缩。代码中的主函数中只是调用了对文件解压缩的方法，若想对字符进行解压缩，可以调用对应的方法。

4、代码如下：

package huffmancode;

import java.io.fileinputstream;
import java.io.fileoutputstream;
import java.io.inputstream;
import java.io.objectinputstream;
import java.io.objectoutputstream;
import java.io.outputstream;
import java.util.arraylist;
import java.util.collections;
import java.util.hashmap;
import java.util.list;
import java.util.map;
import java.util.set;

public class huffmancode 
{

 public static void main(string[] args) 
 {
  string srcfile="d://mydata.txt";//要压缩的文件
  string dstfile="d://mydata.zip";//压缩后的文件
  zipfile(srcfile, dstfile);//压缩文件
  system.out.println("压缩成功！");
  
  unzipfile(dstfile,"d://unzip.txt");//对刚才的文件进行解压，解压后的文件名称叫做unzip.txt
  system.out.println("解压文件成功！");  
 }
 
 public static void unzipfile(string zipfile,string dstfile)
 {
  inputstream inputstream=null;
  objectinputstream objectinputstream=null;
  outputstream outputstream=null;
  try 
  {
   inputstream=new fileinputstream(zipfile);
   objectinputstream=new objectinputstream(inputstream);
   byte [] array= (byte [])objectinputstream.readobject();
   map<byte,string> map=(map<byte,string>)objectinputstream.readobject();
   byte[] decode = decode(map, array);
   outputstream=new fileoutputstream(dstfile);
   outputstream.write(decode);
  } catch (exception e) 
  {
   system.out.println(e);
  }finally
  {
   try {
    outputstream.close();
    objectinputstream.close();
    inputstream.close();
    
   } catch (exception e2) {
    system.out.println(e2);
   }
   
  }
  
  
 }
 
 public static void zipfile(string srcfile,string dstfile)
 {
  fileinputstream inputstream=null;
  outputstream outputstream=null;
  objectoutputstream objectoutputstream=null;
  
  try 
  {
   inputstream=new fileinputstream(srcfile);
   byte [] b=new byte[inputstream.available()];
   inputstream.read(b);
   byte[] huffmanzip = huffmanzip(b);
   outputstream=new fileoutputstream(dstfile);
   objectoutputstream=new objectoutputstream(outputstream);
   objectoutputstream.writeobject(huffmanzip);
   objectoutputstream.writeobject(map);
  } catch (exception e)
  {
   system.out.println(e);
  }
  finally 
  {
   if(inputstream!=null)
   {
    try 
    {
     objectoutputstream.close();
     outputstream.close();
     inputstream.close();//释放资源
    
    } catch (exception e2) 
    {
     system.out.println(e2);
    }
    
   }  
  }
 }
 
 private static byte[] decode(map<byte, string> map,byte [] array)
 {
  stringbuilder stringbuilder = new stringbuilder();
  for(int i=0;i<array.length;i++)
  {
   boolean flag=(i==array.length-1);
   stringbuilder.append(bytetobitstring(!flag, array[i]));
  }
  
  map<string, byte> map2=new hashmap<string, byte>();//反向编码表
  set<byte> keyset = map.keyset();
  for(byte b:keyset)
  {
   string value=map.get(b);
   map2.put(value, b);
  }
  list<byte> list=new arraylist<byte>();
  for (int i = 0; i < stringbuilder.length();) 
  {
   int count=1;
   boolean flag=true;
   byte byte1=null;
   while (flag) 
   {
    string substring = stringbuilder.substring(i, i+count);
    byte1 = map2.get(substring);
    if(byte1==null)
    {
     count++;
    }
    else 
    {
     flag=false;
    }
    
   }
   list.add(byte1);
   i+=count;  
  }
  
  byte [] by=new byte[list.size()];
  for(int i=0;i<by.length;i++)
  {
   by[i]=list.get(i);
  }
  return by;
 }
 
 private static string bytetobitstring(boolean flag, byte b)
 {
  int temp=b;
  if(flag)
  {
   temp|=256;
  }
  
  string binarystring = integer.tobinarystring(temp);
  if(flag)
  {
   return binarystring.substring(binarystring.length()-8);
  }
  else
  {
   return binarystring;
  }
  
 }
 
 private static byte[] huffmanzip(byte [] array)
 {
  list<node> nodes = getnodes(array);
  node createhuffmantree = createhuffmantree(nodes);
  map<byte, string> m=getcodes(createhuffmantree);
  byte[] zip = zip(array, m);
  return zip; 
 }
 
 //
 private static byte[] zip(byte [] array,map<byte,string> map)
 {
  stringbuilder sbuilder=new stringbuilder();
  for(byte item:array)
  {
   string value=map.get(item);
   sbuilder.append(value);
  }
  //system.out.println(sbuilder);
  int len;
  if(sbuilder.tostring().length()%8==0)//如果可以整除
  {
   len=sbuilder.tostring().length()/8;
  }
  else //如果不能整除
  {
   len=sbuilder.tostring().length()/8+1;
  }
  
  byte [] by=new byte[len];
  int index=0;
  for(int i=0;i<sbuilder.length();i+=8)
  {
   string string;
   if((i+8)>sbuilder.length())
   {
    string=sbuilder.substring(i);
   }
   else 
   {
    string=sbuilder.substring(i, i+8);
   }
      
   by[index]=(byte)integer.parseint(string,2);
   index++;
  }
  
  return by;
   
 }
 
 
 //重载
 private static map<byte, string> getcodes(node root)
 {
  if(root==null)
  {
   return null;
  }
  getcodes(root.leftnode,"0",sbuilder);
  getcodes(root.rightnode,"1",sbuilder);
  return map;
 }
 
 
 
 //获取哈夫曼编码
  static map<byte, string> map=new hashmap<>();
  static stringbuilder sbuilder=new stringbuilder();
  public static void getcodes(node node,string code,stringbuilder stringbuilder)
  {
   stringbuilder stringbuilder2=new stringbuilder(stringbuilder);
   stringbuilder2.append(code);
   if(node!=null)
   {
    if(node.data==null)//非叶子结点
    {
     //向左递归
     getcodes(node.leftnode,"0",stringbuilder2);
     //向右递归
     getcodes(node.rightnode,"1",stringbuilder2);
    }
    else //如果是叶子结点
    {
     map.put(node.data,stringbuilder2.tostring());
    }
   }
  }
 
 
 
 public static list<node> getnodes(byte [] array)
 {
  list<node> list=new arraylist<node>();
  map<byte, integer> map=new hashmap<byte, integer>();
  for(byte data:array)
  {
   integer count=map.get(data);//通过键获取值
   if(count==null)//说明此时map集合中还没有改字符
   {
    map.put(data, 1);
   }
   else 
   {
    map.put(data,count+1);
   }
  }
  //遍历map集合
  set<byte> set=map.keyset();
  for(byte key:set)
  {
   int value=map.get(key);
   node node=new node(key, value);
   list.add(node);
  }
  return list;
 }
 
 private static node createhuffmantree(list<node> list)
 {
  while(list.size()>1)
  {
   collections.sort(list);//先对集合进行排序
   node leftnode=list.get(0);
   node rightnode=list.get(1);
   
   node parentnode=new node(null, leftnode.weight+rightnode.weight);
   parentnode.leftnode=leftnode;
   parentnode.rightnode=rightnode;
   
   list.remove(leftnode);
   list.remove(rightnode);
   
   list.add(parentnode);
  }
  return list.get(0);
  
 }

}

class node implements comparable<node>
{
 byte data;//字符
 int weight;//字符出现的次数
 node leftnode;
 node rightnode;
 
 public node(byte data,int weight)//构造器
 {
  this.data=data;
  this.weight=weight;
 }

 @override
 public int compareto(node o) 
 {
  return this.weight-o.weight;
 }

 @override
 public string tostring() 
 {
  return "node [data=" + data + ", weight=" + weight + "]";
 }
 
 //前序遍历
 public void preorder()
 {
  system.out.println(this);
  if(this.leftnode!=null)
  {
   this.leftnode.preorder();
  }
  if(this.rightnode!=null)
  {
   this.rightnode.preorder();
  }
 }
 
 
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。