java实现哈夫曼压缩的实例

哈夫曼压缩的原理：

通过统计文件中每个字节出现的频率,将8位的01串转换为位数较短的哈夫曼编码.

其中哈夫曼编码是根据文件中字节出现的频率构建的,其中出现频率越高的字节,其路径长度越短;

出现频率越低的字节其路径长度越长.从而达到压缩的目的.

如何构造哈夫曼树?

一.  定义字节类 

        我的字节类定义了一下属性   

   public int data;//节点数据 
public int weight;//该节点的权值 
public int point;//该节点所在的左右位置 0-左 1-右 
private nodedata parent;//父节点引用 
private nodedata left;//左节点引用 
private nodedata right;//右节点引用 

二.建哈夫曼树

1.定义一个存储字节信息的数组: int array_bytes[256]; 

  其中数组的下标[0,256)代表字节数值(一个字节8位,其值在[0,256)范围内);数组存储字节出现的次数.

2.遍历要压缩的文件,统计字节出现的次数. 

 inputstream data = new fileinputstream(path); 
 /******** 文件中字符个数 ********/ 
 int number = data.available(); 
 for (int i = 0; i < number; i++) { 
int b = data.read(); 
array_bytes[b] ++; 
 } 
data.close(); 

3.将字节类对象存入优先队列

4.运用hashmap 构造码表

哈夫曼压缩代码如下:

1.字节类

package compressfile; 
/** 
 * 节点数据 
 * 功能：定义数据，及其哈夫曼编码 
 * @author andrew 
 * 
 */ 
public class nodedata { 
  public nodedata(){ 
     
  } 
  public int data;//节点数据 
  public int weight;//该节点的权值 
  public int point;//该节点所在的左右位置 0-左 1-右 
  private nodedata parent; 
  private nodedata left; 
  private nodedata right; 
   
  public int getdata(){ 
    return data; 
  } 
  public nodedata getparent() { 
    return parent; 
  } 
  public void setparent(nodedata parent) { 
    this.parent = parent; 
  } 
  public nodedata getleft() { 
    return left; 
  } 
  public void setleft(nodedata left) { 
    this.left = left; 
  } 
  public nodedata getright() { 
    return right; 
  } 
  public void setright(nodedata right) { 
    this.right = right; 
  } 
} 

2.统计字节的类，并生成码表

package compressfile; 
 
import java.io.bufferedinputstream; 
import java.io.fileinputstream; 
import java.io.ioexception; 
import java.io.inputstream; 
import java.util.arraylist; 
import java.util.comparator; 
import java.util.hashmap; 
import java.util.list; 
import java.util.map; 
import java.util.priorityqueue; 
 
 
 
/** 
 * 统计指定文件中每个字节数 功能：定义数组，将文件中的字节类型及个数写入数组 
 * 创建优先队列和哈夫曼树 
 * @author andrew 
 * 
 */ 
public class statisticbytes { 
 
   
  /** 
   * 第一步： 
   * 统计文件中字节的方法 
   * 
   * @param path 
   *      所统计的文件路径 
   * @return 字节个数数组 
   */ 
  private int[] statistic(string path) { 
    /******储存字节数据的数组--索引值代表字节类型-存储值代表权值******/ 
    int[] array_bytes = new int[256]; 
    try { 
      inputstream data = new fileinputstream(path); 
      bufferedinputstream buffered = new bufferedinputstream(data); 
      /******** 文件中字符个数 ********/ 
      int number = data.available(); 
      system.out.println("字节个数》》》"+number); 
      for (int i = 0; i < number; i++) { 
        int b = data.read(); 
        array_bytes[b] ++; 
      } 
       
      data.close(); 
    } catch (ioexception e) { 
      e.printstacktrace(); 
    } 
    return array_bytes; 
  } 
  /** 
   * 第二步： 
   * 根据统计的字节数组创建优先队列 
   * @param array 统计文件字节的数组 
   * @return    优先队列 
   */ 
  private priorityqueue<nodedata> createqueue(int[] array){ 
    //定义优先队列，根据数据的权值排序从小到大 
    priorityqueue<nodedata> queue =  
        new priorityqueue<nodedata>(array.length,new comparator<nodedata>(){ 
      public int compare(nodedata o1, nodedata o2) { 
        return o1.weight - o2.weight; 
      } 
    }); 
     
    for(int i=0; i<array.length; i++){ 
      if(0 != array[i]){ 
        nodedata node = new nodedata(); 
        node.data = i;//设置该节点的数据 
        node.weight = array[i];//设置该节点的权值 
        queue.add(node); 
      } 
    } 
    return queue; 
  } 
  /** 
   * 第三步： 
   * 根据优先队列创建哈夫曼树 
   * @param queue  优先队列  
   * @return     哈夫曼树根节点 
   */ 
  private nodedata createtree(priorityqueue<nodedata> queue){ 
    while(queue.size() > 1){ 
       
      nodedata left = queue.poll();//取得左节点 
      nodedata right = queue.poll();//取得右节点 
       
      nodedata root = new nodedata();//创建新节点 
      root.weight = left.weight + right.weight; 
       
      root.setleft(left); 
      root.setright(right); 
      left.setparent(root); 
      right.setparent(root); 
       
      left.point = 0; 
      right.point = 1; 
       
      queue.add(root); 
    } 
    nodedata firstnode = queue.poll(); 
    return firstnode; 
  } 
  /** 
   * 第四步： 
   * 寻找叶节点并获得哈夫曼编码 
   * @param root  根节点 
   */ 
  private void achievehfmcode(nodedata root){ 
     
    if(null == root.getleft() && null == root.getright()){ 
      array_str[root.data] = this.achieveleafcode(root); 
      /** 
       * 
       * 得到将文件转换为哈夫曼编码后的文集长度 
       * 文件长度 = 一种编码的长度 * 该编码出现的次数 
       */ 
      writefile.size_file += (array_str[root.data].length())*(root.weight); 
    } 
    if(null != root.getleft()){ 
      achievehfmcode(root.getleft()); 
    } 
    if(null != root.getright()){ 
      achievehfmcode(root.getright()); 
    } 
  } 
  /** 
   * 根据某叶节点获得该叶节点的哈夫曼编码 
   * @param leafnode  叶节点对象 
   */ 
  private string achieveleafcode(nodedata leafnode){ 
    string str = ""; 
    /*****************存储节点 01 编码的队列****************/ 
    list<integer> list_hfmcode = new arraylist<integer>(); 
    list_hfmcode.add(leafnode.point); 
    nodedata parent = leafnode.getparent(); 
     
    while(null != parent){ 
      list_hfmcode.add(parent.point); 
      parent = parent.getparent(); 
    } 
     
    int size = list_hfmcode.size(); 
    for(int i=size-2; i>=0; i--){ 
      str += list_hfmcode.get(i); 
    } 
    system.out.println(leafnode.weight+"的哈夫曼编码为>>>"+str); 
    return str; 
  } 
  /** 
   * 第五步： 
   * 根据获得的哈夫曼表创建 码表 
   * integer 为字节byte [0~256) 
   * string 为哈夫曼编码 
   * @return 码表 
   */ 
  public map<integer,string> createmap(){ 
    int[] hfm_codes = this.statistic("f:\\java\\压缩前.txt");//获得文件字节信息 
    priorityqueue<nodedata> queue = this.createqueue(hfm_codes);//获得优先队列 
    /* 
     * 获得哈夫曼树的根节点， 
     * this.createtree(queue)方法调用之后(含有poll())，queue.size()=0 
     */ 
    nodedata root = this.createtree(queue); 
    this.achievehfmcode(root);//获得哈夫曼编码并将其存入数组中 
     
    map<integer,string> map = new hashmap<integer,string>(); 
    for(int i=0; i<256; i++){ 
      if(null != array_str[i]){ 
        map.put(i, array_str[i]); 
      } 
    } 
    return map; 
  } 
  /** 
   * 存储字节哈夫曼编码的数组 
   * 下标：字节数据 
   * 元素：哈夫曼编码 
   */ 
  public string[] array_str = new string[256]; 
} 

3.将码表写入压缩文件并压缩正文

package compressfile; 
 
import java.io.bufferedinputstream; 
import java.io.bufferedoutputstream; 
import java.io.dataoutputstream; 
import java.io.fileinputstream; 
import java.io.fileoutputstream; 
import java.io.ioexception; 
import java.util.iterator; 
import java.util.map; 
import java.util.set; 
 
/** 
 * 将码表和文件写入新的文件中 
 * @author andrew 
 * 
 */ 
public class writefile { 
 
  // 实例化创建码表类对象 
  private statisticbytes statistic = new statisticbytes(); 
  private map<integer, string> map = statistic.createmap();// 获得码表 
  // 字节接收变量，接收哈夫曼编码连接够8位时转换的字节 
  private int exmpcode; 
  public static int size_file; 
 
  public static void main(string[] args) { 
    writefile writefile = new writefile(); 
    writefile.init(); 
  } 
 
  private void init() { 
 
    string filepath = "f:\\java\\压缩后.txt"; 
    this.writefile(filepath); 
  } 
 
  /** 
   * 第一步： 向文件中写入码表 
   * 
   * @param dataout 
   *      基本数据流 
   */ 
  private void writecodetable(dataoutputstream dataout) { 
    set<integer> set = map.keyset(); 
    iterator<integer> p = set.iterator(); 
 
    try { 
      //向文件中写入码表的长度 
      dataout.writeint(map.size()); 
      while (p.hasnext()) { 
        integer key = p.next(); 
        string hfmcode = map.get(key); 
 
        dataout.writeint(key);//写入字节 
        //写入哈夫曼编码的长度 
        dataout.writebyte(hfmcode.length()); 
        for(int i=0; i<hfmcode.length(); i++){ 
          dataout.writechar(hfmcode.charat(i));//写入哈夫曼编码 
        } 
      } 
    } catch (ioexception e) { 
      e.printstacktrace(); 
    } 
  } 
 
  /** 
   * 第二步： 向压缩文件中写入编码 
   * 
   * @param path 
   */ 
  private void writefile(string path) { 
 
    try { 
      // 输入流 
      fileinputstream in = new fileinputstream("f:\\java\\压缩前.txt"); 
      bufferedinputstream bin = new bufferedinputstream(in); 
      // 输出流 
      fileoutputstream out = new fileoutputstream(path); 
      dataoutputstream dataout = new dataoutputstream(out); 
      bufferedoutputstream bout = new bufferedoutputstream(out); 
      // 向文件中写入码表 
      this.writecodetable(dataout); 
      /********************写入补零个数*********************/ 
      if(0 != size_file % 8){ 
        dataout.writebyte(8 - (size_file % 8)); 
      } 
       
      string transstring = "";//中转字符串,存储字符串直到size大于8 
      string waitestring = "";//转化字符串, 
       
      int size_file = in.available(); 
      for(int i=0; i<size_file; i++){ 
        int j = bin.read(); 
        system.out.println("]]]]]]]]]]]>>"); 
        waitestring = this.changestringtobyte(transstring + statistic.array_str[j]); 
        if(waitestring != ""){  
          bout.write(exmpcode); 
          transstring = waitestring; 
        }else{ 
          transstring += statistic.array_str[j]; 
        } 
      } 
      if("" != transstring){ 
        int num = 8-transstring.length()%8; 
        for(int i=0; i<num; i++){ 
          transstring += 0; 
        } 
      } 
      transstring = this.changestringtobyte(transstring); 
      bout.write(exmpcode); 
       
      bin.close(); 
      bout.flush(); 
      bout.close(); 
      out.close(); 
    } catch (ioexception e) { 
      e.printstacktrace(); 
    } 
  } 
 
  /** 
   * 附属第二步： 
   * 将字符串转化为byte 
   * 
   * @param str 
   *      要转化的字符串 
   * @return 如果str的长度大于8返回一个截取前8位后的str 
   *     否则返回"" 
   */ 
  private string changestringtobyte(string str) { 
    if (8 <= str.length()) { 
      exmpcode = ((str.charat(0) - 48) * 128 
          + (str.charat(1) - 48) * 64 + (str.charat(2) - 48) * 32 
          + (str.charat(3) - 48) * 16 + (str.charat(4) - 48) * 8 
          + (str.charat(5) - 48) * 4 + (str.charat(6) - 48) * 2  
          + (str.charat(7) - 48)); 
      str = str.substring(8); 
      return str; 
    } 
    return ""; 
  } 
} 

二.哈夫曼解压 

   原理:将压缩的逆向，即你是如何压缩的就怎样去解压。相当于你根据自己定义的协议进行压缩与解压缩文件。

代码如下：

package decompressionfile; 
 
import java.io.datainputstream; 
import java.io.fileinputstream; 
import java.io.fileoutputstream; 
import java.io.ioexception; 
import java.io.inputstream; 
import java.io.outputstream; 
import java.util.arraylist; 
import java.util.hashmap; 
import java.util.iterator; 
import java.util.list; 
import java.util.map; 
import java.util.set; 
 
/** 
 * 解压文件 从压缩文件中读入数据解压 
 * 
 * @author andrew 
 * 
 */ 
public class readfile { 
  /** 
   * 码表 integter: 字节 [0,255) string： 哈夫曼编码 
   */ 
  private map<integer, string> code_map = new hashmap<integer, string>(); 
 
  public static void main(string[] args) { 
    readfile readfile = new readfile(); 
    readfile.readfile(); 
  } 
 
  /** 
   * 第一步： 从文件中读出码表 
   * 
   * @param datainput 
   *      基本数据输入流 
   * 
   */ 
  private void readmap(datainputstream datainput) { 
 
    try { 
      // 读出码表的长度 
      int size_map = datainput.readint(); 
      /**************** 读出码表信息 ************************************/ 
      for (int i = 0; i < size_map; i++) { 
        int data = datainput.readint();// 读入字节信息 
        string str = "";// 哈夫曼编码 
        // 哈夫曼编码长度,存储时以字符写入 
        byte codesize = datainput.readbyte(); 
        for (byte j = 0; j < codesize; j++) { 
          str += datainput.readchar(); 
        } 
        system.out.println("&&&&&&&&&&>>>>"+data+"!!!!!!!>>"+str); 
        code_map.put(data, str); 
      } 
      /***************************************************************/ 
    } catch (ioexception e) { 
      e.printstacktrace(); 
    } 
  } 
 
  /** 
   * 第二步： 解压正式文件 
   */ 
  private void readfile() { 
    try { 
      // 文件输入流 
      inputstream input = new fileinputstream("f:\\java\\压缩后.txt"); 
      // bufferedinputstream bin = new bufferedinputstream(input); 
      datainputstream dinput = new datainputstream(input); 
      // 调用读出码表的方法 
      this.readmap(dinput); 
      byte zerofill = dinput.readbyte();// 读出文件补零个数 
      system.out.println("补零个数》》》>>>>"+zerofill); 
      // 文件输出流 
      outputstream out = new fileoutputstream("f:\\java\\解压后.txt"); 
       
      string transstring = "";//接收用于匹配码表中哈夫曼编码的字符串 
      string waitestring = "";//接收截取哈夫曼编码后剩余的字符串 
       
      /***********************************不耗内存的方法*****************************************/ 
      int readcode = input.read();//从压缩文件中读出一个数据 
      int size = input.available(); 
      for(int j=0; j<=size; j++){ 
        system.out.println("readcodereadcodereadcode》》>>>>"+readcode); 
        waitestring += this.changeinttobinarystring(readcode);//将读到的整数转化为01字符串 
        for(int i=0; i<waitestring.length(); i++){ 
          //将从文件中读出的01串一个一个字节的截取添加与码表中的哈夫曼编码比较 
          transstring += waitestring.charat(i); 
          if(this.searchhc(transstring, out)){ 
//           waitestring = waitestring.substring( i+1 ); 
            transstring = ""; 
          } 
        } 
        waitestring = ""; 
        readcode = input.read(); 
        if(j == size-1){ 
          break; 
        } 
      } 
      /************************************处理最后一个字***************************************/ 
//     int lastbyte = input.read(); 
      string lastword = this.changeinttobinarystring(readcode); 
      waitestring = transstring + lastword.substring(0, 8-zerofill); 
      transstring = ""; 
      for(int i=0; i<waitestring.length(); i++){ 
        //将从文件中读出的01串一个一个字节的截取添加与码表中的哈夫曼编码比较 
        transstring += waitestring.charat(i); 
        if(this.searchhc(transstring, out)){ 
//         waitestring = waitestring.substring( i+1 ); 
          transstring = ""; 
        } 
      } 
//     this.searchhc(transstring, out); 
      /***********************************队列法，耗内存****************************************/ 
//     int readcode = input.read();//从压缩文件中读出一个数据 
//     list<character> list = new arraylist<character>(); 
//     while(-1 != readcode){ 
//       string str = this.changeinttobinarystring(readcode); 
//       for(int i=0; i<str.length(); i++){ 
//         list.add(str.charat(i)); 
//       } 
//       readcode = input.read(); 
//     } 
//     for(int j=0; j<list.size()-zerofill; j++){ 
//       transstring += list.get(j); 
//       if(this.searchhc(transstring, out)){ 
//         transstring = ""; 
//       } 
//     } 
      /*****************************************************************************************/ 
      input.close(); 
      out.close(); 
    } catch (ioexception e) { 
      e.printstacktrace(); 
    } 
  } 
  /** 
   * 将从文件中读到的01 串与码表中的哈夫曼编码比较 
   * 若在码表中含有与之对应的哈夫曼编码则将码表中对应的 
   * 数据写入解压文件，否则不写入 
   * @param str 从文件中读到的01 字符串 
   * @param out 文件输出流 
   * @return   若写入文件返回true，否则返回false 
   * @throws ioexception 写入发生错误时抛出异常 
   */ 
  private boolean searchhc(string str, outputstream out) throws ioexception{ 
    set<integer> set = code_map.keyset(); 
    iterator<integer> p = set.iterator(); 
    while (p.hasnext()) { 
      integer key = p.next();//获得码表中的字节数据 
      string hfmcode = code_map.get(key);//获得哈夫曼编码 
      if(hfmcode.equals(str)){ 
        out.write(key); 
        return true; 
      } 
    } 
    return false; 
  } 
  /** 
   * 根据 "除2取余，逆序排列"法 
   * 将十进制数字转化为二进制字符串 
   * @param a  要转化的数字 
   * @return  01 字符串 
   */ 
  private string changeinttobinarystring(int a) { 
    int b = a; 
    int count = 0; //记录 a 可转化为01串的个数，在不够8为时便于补零 
    string str = "";// 逆序二进制字符串 
    string exmpstr = "";// 顺序二进制字符串 
 
    while (a != 0) { 
      b = a/2; 
      if (a % 2 != 0) { 
        str += 1; 
      } else { 
        str += 0; 
      } 
      a = b; 
      count++; 
    } 
    //不够8位的地方补零 
    for (int i = 0; i < 8 - count; i++) { 
      str += 0; 
    } 
    //将转化后的二进制字符串正序 
    for (int j = 7; j >= 0; j--) { 
      system.out.print(str.charat(j)); 
      exmpstr += str.charat(j); 
    } 
    system.out.println("转化后的字符串>>>>>>>>>"+exmpstr); 
    return exmpstr; 
  } 
}