자바 하프 만 압축 실현 실례

19815 단어 자바하프 만
하프 만 압축 의 원리:
통계 파일 에서 바이트 마다 나타 나 는 빈 도 를 통 해 8 비트 의 01 열 을 자릿수 가 짧 은 하프 만 인 코딩 으로 변환 합 니 다.
그 중에서 하 프 만 인 코딩 은 파일 에 있 는 바이트 가 나타 나 는 주파수 에 따라 구 축 된 것 으로 그 중에서 빈도 가 높 은 바이트 가 나타 날 수록 경로 의 길이 가 짧다.
주파수 가 낮은 바이트 가 나타 날 수록 경로 의 길이 가 길 어 지고 압축 의 목적 을 달성 합 니 다.
어떻게 하프 만 나 무 를 만 듭 니까?
하나  정의 바이트 클래스 
        제 바이트 클래스 가 속성 을 정 의 했 습 니 다.   

   public int data;//     
public int weight;//       
public int point;//           0-  1-  
private NodeData parent;//      
private NodeData left;//      
private NodeData right;//      
2.건 하프 만 나무
1.바이트 정 보 를 저장 하 는 배열 을 정의 합 니 다:int arrayBytes[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 ""; 
  } 
} 
2.하프 만 스트레스 해소 
   원리:압축 의 역방향,즉 당신 이 압축 하 는 대로 압축 을 푼다.자신 이 정의 한 프로 토 콜 에 따라 파일 을 압축 하고 압축 을 푸 는 것 과 같다.
코드 는 다음 과 같 습 니 다:

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

좋은 웹페이지 즐겨찾기