java实现哈夫曼压缩的实例

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

 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(); 

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;   } } 

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]; } 

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;   } }