資料壓縮、解壓

應用執行個體
代碼實作，轉為赫夫曼樹

public class HuffmanCode {

  public static void main(String[] args) {
    String content = "i like like like java do you like a java";
    byte[] contentBytes = content.getBytes();
    System.out.println(contentBytes.length); //40

    List<Node> nodes = getNodes(contentBytes);
    System.out.println("nodes=" + nodes);
    
    //測試一把，建立的赫夫曼樹
    System.out.println("赫夫曼樹");
    Node huffmanTreeRoot = createHuffmanTree(nodes);
    System.out.println("前序周遊");
    huffmanTreeRoot.preOrder();
  }
  
  //前序周遊的方法
  private static void preOrder(Node root) {
    if(root != null) {
      root.preOrder();
    }else {
      System.out.println("赫夫曼樹為空");
    }
  }
  
  /**
   * @param bytes 接收位元組數組
   * @return 傳回的就是 List 形式   [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],
   */
  private static List<Node> getNodes(byte[] bytes) {
    //1建立一個ArrayList
    ArrayList<Node> nodes = new ArrayList<Node>();
    //周遊 bytes , 統計 每一個byte出現的次數->map[key,value]
    Map<Byte, Integer> counts = new HashMap<>();
    for (byte b : bytes) {
      Integer count = counts.get(b);
      if (count == null) { // Map還沒有這個字元資料,第一次
        counts.put(b, 1);
      } else {
        counts.put(b, count + 1);
      }
    }
    //把每一個鍵值對轉成一個Node 對象，并加入到nodes集合
    //周遊map
    for(Map.Entry<Byte, Integer> entry: counts.entrySet()) {
      nodes.add(new Node(entry.getKey(), entry.getValue()));
    }
    return nodes;
  }
  
  //可以通過List 建立對應的赫夫曼樹
  private static Node createHuffmanTree(List<Node> nodes) {
    while(nodes.size() > 1) {
      //排序, 從小到大
      Collections.sort(nodes);
      //取出第一顆最小的二叉樹
      Node leftNode = nodes.get(0);
      //取出第二顆最小的二叉樹
      Node rightNode = nodes.get(1);
      //建立一顆新的二叉樹,它的根節點 沒有data, 隻有權值
      Node parent = new Node(null, leftNode.weight + rightNode.weight);
      parent.left = leftNode;
      parent.right = rightNode;
      //将已經處理的兩顆二叉樹從nodes删除
      nodes.remove(leftNode);
      nodes.remove(rightNode);
      //将新的二叉樹，加入到nodes
      nodes.add(parent);
    }
    //nodes 最後的結點，就是赫夫曼樹的根結點
    return nodes.get(0);
  }

}

//建立Node ,待資料和權值
class Node implements Comparable<Node>  {
  Byte data; // 存放資料(字元)本身，比如'a' => 97 ' ' => 32
  int weight; //權值, 表示字元出現的次數
  Node left;//
  Node right;

  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.left != null) {
      this.left.preOrder();
    }
    if(this.right != null) {
      this.right.preOrder();
    }
  }

}

轉為赫夫曼編碼

//生成赫夫曼樹對應的赫夫曼編碼
  //思路:
  //1. 将赫夫曼編碼表存放在 Map<Byte,String> 形式
  //   生成的赫夫曼編碼表{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
  static Map<Byte, String> huffmanCodes = new HashMap<Byte,String>();
  //2. 在生成赫夫曼編碼表示，需要去拼接路徑, 定義一個StringBuilder 存儲某個葉子結點的路徑
  static StringBuilder stringBuilder = new StringBuilder();

  //為了調用友善，我們重載 getCodes
  private static Map<Byte, String> getCodes(Node root) {
    if(root == null) {
      return null;
    }
    //處理root的左子樹
    getCodes(root.left, "0", stringBuilder);
    //處理root的右子樹
    getCodes(root.right, "1", stringBuilder);
    return huffmanCodes;
  }
  
  /**
   * 功能：将傳入的node結點的所有葉子結點的赫夫曼編碼得到，并放入到huffmanCodes集合
   * @param node  傳入結點
   * @param code  路徑： 左子結點是 0, 右子結點 1
   * @param stringBuilder 用于拼接路徑
   */
  private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
    StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
    //将code 加入到 stringBuilder2
    stringBuilder2.append(code);
    if(node != null) { //如果node == null不處理
      //判斷目前node 是葉子結點還是非葉子結點
      if(node.data == null) { //非葉子結點
        //遞歸處理
        //向左遞歸
        getCodes(node.left, "0", stringBuilder2);
        //向右遞歸
        getCodes(node.right, "1", stringBuilder2);
      } else { //說明是一個葉子結點
        //就表示找到某個葉子結點的最後
        huffmanCodes.put(node.data, stringBuilder2.toString());
      }
    }
  }

壓縮

//編寫一個方法，将字元串對應的byte[] 數組，通過生成的赫夫曼編碼表，傳回一個赫夫曼編碼 壓縮後的byte[]
  /**
   * @param bytes 這時原始的字元串對應的 byte[]
   * @param huffmanCodes 生成的赫夫曼編碼map
   * @return 傳回赫夫曼編碼處理後的 byte[] 
   * 舉例： String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
   * 傳回的是 字元串 "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100"
   * => 對應的 byte[] huffmanCodeBytes  ，即 8位對應一個 byte,放入到 huffmanCodeBytes
   * huffmanCodeBytes[0] =  10101000(補碼) => byte  [推導  10101000=> 10101000 - 1 => 10100111(反碼)=> 11011000= -88 ]
   * huffmanCodeBytes[1] = -88
   */
  private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
    //1.利用 huffmanCodes 将  bytes 轉成  赫夫曼編碼對應的字元串
    StringBuilder stringBuilder = new StringBuilder();
    //周遊bytes 數組 
    for(byte b: bytes) {
      stringBuilder.append(huffmanCodes.get(b));
    }
    //将 "1010100010111111110..." 轉成 byte[]
    //統計傳回  byte[] huffmanCodeBytes 長度
    //一句話 int len = (stringBuilder.length() + 7) / 8;
    int len;
    if(stringBuilder.length() % 8 == 0) {
      len = stringBuilder.length() / 8;
    } else {
      len = stringBuilder.length() / 8 + 1;
    }
    //建立 存儲壓縮後的 byte數組
    byte[] huffmanCodeBytes = new byte[len];
    int index = 0;//記錄是第幾個byte
    for (int i = 0; i < stringBuilder.length(); i += 8) { //因為是每8位對應一個byte,是以步長 +8
        String strByte;
        if(i+8 > stringBuilder.length()) {//不夠8位
          strByte = stringBuilder.substring(i);
        }else{
          strByte = stringBuilder.substring(i, i + 8);
        } 
        //将strByte 轉成一個byte,放入到 huffmanCodeBytes
        huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);
        index++;
    }
    return huffmanCodeBytes;
  }

測試

public class HuffmanCode {
  public static void main(String[] args) {
    String content = "i like like like java do you like a java";
    byte[] contentBytes = content.getBytes();
    System.out.println(contentBytes.length); //40

    List<Node> nodes = getNodes(contentBytes);
    System.out.println("nodes=" + nodes);
    
    //測試一把，建立的赫夫曼樹
    System.out.println("赫夫曼樹");
    Node huffmanTreeRoot = createHuffmanTree(nodes);
    System.out.println("前序周遊");
    huffmanTreeRoot.preOrder();

    //測試一把是否生成了對應的赫夫曼編碼
    Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
    System.out.println("~生成的赫夫曼編碼表= " + huffmanCodes);
    
    //測試壓縮
    byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
    System.out.println("huffmanCodeBytes=" + Arrays.toString(huffmanCodeBytes));//17
  }
}

封裝優化

public class HuffmanCode {
  public static void main(String[] args) {
    String content = "i like like like java do you like a java";
    byte[] contentBytes = content.getBytes();
    System.out.println(contentBytes.length); //40
    
    byte[] huffmanCodesBytes= huffmanZip(contentBytes);
    System.out.println("壓縮後的結果是:" + Arrays.toString(huffmanCodesBytes) + " 長度= " + huffmanCodesBytes.length);
  }
}

  //使用一個方法，将前面的方法封裝起來，便于我們的調用.
  /**
   * @param bytes 原始的字元串對應的位元組數組
   * @return 是經過 赫夫曼編碼處理後的位元組數組(壓縮後的數組)
   */
  private static byte[] huffmanZip(byte[] bytes) {
    List<Node> nodes = getNodes(bytes);
    //根據 nodes 建立的赫夫曼樹
    Node huffmanTreeRoot = createHuffmanTree(nodes);
    //對應的赫夫曼編碼(根據 赫夫曼樹)
    Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
    //根據生成的赫夫曼編碼，壓縮得到壓縮後的赫夫曼編碼位元組數組
    byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
    return huffmanCodeBytes;
  }

解壓

public class HuffmanCode {
  public static void main(String[] args) {
    String content = "i like like like java do you like a java";
    byte[] contentBytes = content.getBytes();
    System.out.println(contentBytes.length); //40
    
    byte[] huffmanCodesBytes= huffmanZip(contentBytes);
    System.out.println("壓縮後的結果是:" + Arrays.toString(huffmanCodesBytes) + " 長度= " + huffmanCodesBytes.length);

    //測試一把byteToBitString方法
    //System.out.println(byteToBitString((byte)1));
    byte[] sourceBytes = decode(huffmanCodes, huffmanCodesBytes);
    System.out.println("原來的字元串=" + new String(sourceBytes)); // "i like like like java do you like a java"
  }
}

  //完成資料的解壓
  //思路
  //1. 将huffmanCodeBytes [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
  //   重寫先轉成 赫夫曼編碼對應的二進制的字元串 "1010100010111..."
  //2.  赫夫曼編碼對應的二進制的字元串 "1010100010111..." =》 對照 赫夫曼編碼  =》 "i like like like java do you like a java"
  
  //編寫一個方法，完成對壓縮資料的解碼
  /**
   * @param huffmanCodes 赫夫曼編碼表 map
   * @param huffmanBytes 赫夫曼編碼得到的位元組數組
   * @return 就是原來的字元串對應的數組
   */
  private static byte[] decode(Map<Byte,String> huffmanCodes, byte[] huffmanBytes) {
    //1. 先得到 huffmanBytes 對應的 二進制的字元串 ， 形式 1010100010111...
    StringBuilder stringBuilder = new StringBuilder();
    //将byte數組轉成二進制的字元串
    for(int i = 0; i < huffmanBytes.length; i++) {
      byte b = huffmanBytes[i];
      //判斷是不是最後一個位元組
      boolean flag = (i == huffmanBytes.length - 1);
      stringBuilder.append(byteToBitString(!flag, b));
    }
    //把字元串安裝指定的赫夫曼編碼進行解碼
    //把赫夫曼編碼表進行調換，因為反向查詢 a->100 100->a
    Map<String, Byte>  map = new HashMap<String,Byte>();
    for(Map.Entry<Byte, String> entry: huffmanCodes.entrySet()) {
      map.put(entry.getValue(), entry.getKey());
    }
    //建立要給集合，存放byte
    List<Byte> list = new ArrayList<>();
    //i 可以了解成就是索引,掃描 stringBuilder 
    for(int  i = 0; i < stringBuilder.length(); ) {
      int count = 1; // 小的計數器
      boolean flag = true;
      Byte b = null;
      while(flag) {
        //1010100010111...
        //遞增的取出 key 1 
        String key = stringBuilder.substring(i, i+count);//i 不動，讓count移動，指定比對到一個字元
        b = map.get(key);
        if(b == null) {//說明沒有比對到
          count++;
        }else {
          //比對到
          flag = false;
        }
      }
      list.add(b);
      i += count;//i 直接移動到 count  
    }
    //當for循環結束後，我們list中就存放了所有的字元  "i like like like java do you like a java"
    //把list 中的資料放入到byte[] 并傳回
    byte b[] = new byte[list.size()];
    for(int i = 0;i < b.length; i++) {
      b[i] = list.get(i);
    }
    return b;
    
  }
  
  /**
   * 将一個byte 轉成一個二進制的字元串, 如果看不懂，可以參考我講的Java基礎 二進制的原碼，反碼，補碼
   * @param b 傳入的 byte
   * @param flag 标志是否需要補高位如果是true ，表示需要補高位，如果是false表示不補, 如果是最後一個位元組，無需補高位
   * @return 是該b 對應的二進制的字元串，（注意是按補碼傳回）
   */
  private static String byteToBitString(boolean flag, byte b) {
    //使用變量儲存 b
    int temp = b; //将 b 轉成 int
    //如果是正數我們還存在補高位
    if(flag) {
      temp |= 256; //按位與 256  1 0000 0000  | 0000 0001 => 1 0000 0001
    }
    String str = Integer.toBinaryString(temp); //傳回的是temp對應的二進制的補碼
    if(flag) {
      return str.substring(str.length() - 8);
    } else {
      return str;
    }
  }

壓縮、解壓檔案

public class HuffmanCode {

  public static void main(String[] args) {
    //測試壓縮檔案
    String srcFile = "d://Uninstall.xml";
    String dstFile = "d://Uninstall.zip";
    zipFile(srcFile, dstFile);
    System.out.println("壓縮檔案ok~~");

    //測試解壓檔案
    String zipFile = "d://Uninstall.zip";
    String dstFile = "d://Uninstall2.xml";
    unZipFile(zipFile, dstFile);
    System.out.println("解壓成功!");
  }
  
  //編寫一個方法，完成對壓縮檔案的解壓
  /**
   * @param zipFile 準備解壓的檔案
   * @param dstFile 将檔案解壓到哪個路徑
   */
  public static void unZipFile(String zipFile, String dstFile) {
    //定義檔案輸入流
    InputStream is = null;
    //定義一個對象輸入流
    ObjectInputStream ois = null;
    //定義檔案的輸出流
    OutputStream os = null;
    try {
      //建立檔案輸入流
      is = new FileInputStream(zipFile);
      //建立一個和  is關聯的對象輸入流
      ois = new ObjectInputStream(is);
      //讀取byte數組  huffmanBytes
      byte[] huffmanBytes = (byte[])ois.readObject();
      //讀取赫夫曼編碼表
      Map<Byte,String> huffmanCodes = (Map<Byte,String>)ois.readObject();
      //解碼
      byte[] bytes = decode(huffmanCodes, huffmanBytes);
      //将bytes 數組寫入到目标檔案
      os = new FileOutputStream(dstFile);
      //寫資料到 dstFile 檔案
      os.write(bytes);
    } catch (Exception e) {
      // TODO: handle exception
      System.out.println(e.getMessage());
    } finally {
      try {
        os.close();
        ois.close();
        is.close();
      } catch (Exception e2) {
        // TODO: handle exception
        System.out.println(e2.getMessage());
      }
    }
  }
  
  //編寫方法，将一個檔案進行壓縮
  /**
   * @param srcFile 你傳入的希望壓縮的檔案的全路徑
   * @param dstFile 我們壓縮後将壓縮檔案放到哪個目錄
   */
  public static void zipFile(String srcFile, String dstFile) {
    //建立輸出流
    OutputStream os = null;
    ObjectOutputStream oos = null;
    //建立檔案的輸入流
    FileInputStream is = null;
    try {
      //建立檔案的輸入流
      is = new FileInputStream(srcFile);
      //建立一個和源檔案大小一樣的byte[]
      byte[] b = new byte[is.available()];
      //讀取檔案
      is.read(b);
      //直接對源檔案壓縮
      byte[] huffmanBytes = huffmanZip(b);
      //建立檔案的輸出流, 存放壓縮檔案
      os = new FileOutputStream(dstFile);
      //建立一個和檔案輸出流關聯的ObjectOutputStream
      oos = new ObjectOutputStream(os);
      //把 赫夫曼編碼後的位元組數組寫入壓縮檔案
      oos.writeObject(huffmanBytes); //我們是把
      //這裡我們以對象流的方式寫入 赫夫曼編碼，是為了以後我們恢複源檔案時使用
      //注意一定要把赫夫曼編碼 寫入壓縮檔案
      oos.writeObject(huffmanCodes);
    }catch (Exception e) {
      // TODO: handle exception
      System.out.println(e.getMessage());
    }finally {
      try {
        is.close();
        oos.close();
        os.close();
      }catch (Exception e) {
        // TODO: handle exception
        System.out.println(e.getMessage());
      }
    }
  }

}

資料壓縮、解壓

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method