基本概念

代碼實現

package com.atguigu.huffmancode;import com.sun.org.glassfish.external.statistics.CountStatistic; import com.sun.org.glassfish.external.statistics.StringStatistic;import java.security.AlgorithmConstraints; import java.util.*;/*** @創建人 wdl* @創建時間 2021/3/27* @描述*/ 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);//40byte[] huffmanCodesBytes = huffmanZip(contentBytes);System.out.println("壓縮后的結果"+Arrays.toString(huffmanCodesBytes)+huffmanCodesBytes.length);//測試一把byteToBitString方法byte[] sourceBytes = decode(huffmanCodes, huffmanCodesBytes);System.out.println(new String(sourceBytes));// // List<Node> nodes = getNodes(contentBytes); // System.out.println(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(Arrays.toString(huffmanCodeBytes));//17//發送huffmanCodeBytes數組}//完成數據的解壓//思路//1.將huffmanCodeBytes//重現先轉成赫夫曼編碼對應的二進制的字符串“0100000//2.、將“111"對照赫夫曼編碼=》i like/**** @param huffmanCodes 哈夫曼編碼表map* @param huffmanBytes 赫夫曼編碼的到的字節數組* @return 原來的字符串對應的數組*///編寫一個方法，完成對壓縮數據的解碼private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){//1.先得到huffmanBytes 對應的二進制字符串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));}//吧字符串按照指定的赫夫曼編碼進行解碼//把赫夫曼編碼表進行調換，因為要反向查詢Map<String, Byte> map = new HashMap<>();for(Map.Entry<Byte, String> entry:huffmanCodes.entrySet()){map.put(entry.getValue(),entry.getKey());} // System.out.println(map);//創建一個集合，存放byteArrayList<Byte> list = new ArrayList<>();for (int i = 0; i < stringBuilder.length();) {//i可以理解成就是一個索引，掃描stringBuilderint count=1;//小的計數器boolean flag=true;Byte b=null;while (flag){//遞增的取出key 1//取出一個字符'1' '0'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"//吧list中的數據放入到byte數組并返回byte[] b = new byte[list.size()];for (int i = 0; i < b.length; i++) {b[i]=list.get(i);}return b;}/*** 將一個byte轉成一個二進制的字符串* @param b* @param flag 表示是否需要補高位，如果是true，表示需要補高位，如果是false表示不補,如果是最后一個字節，無需補高位* @return 是該b 對應的二進制的字符串，(注意是按補碼返回)*/private static String byteToBitString(boolean flag,byte b){//使用變量保存bint temp=b;//b轉成int//如果是正數我們還存在補高位的問題if(flag){temp|=256;}String str = Integer.toBinaryString(temp);//返回的是temp對應的二進制補碼if(flag){return str.substring(str.length()-8);}else {return str;}}//使用一個方法，將前面的方法封裝起來，便于我們的調用/**** @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;}/**** @param bytes 這時原始的字符串對應的byte[]* @param huffmanCodes 生成的赫夫曼編碼map* @return 返回赫夫曼編碼表處理后的byte[]*///編寫一個方法，將字符串對應的byte[]數組，通過生成的赫夫曼編碼表，返回一個赫夫曼編碼壓縮有的byte[]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));}System.out.println("測試stringBuilder="+stringBuilder.toString());//將1010111011 轉成byte數組//統計返回byte[] huffmanCodeBytes 長度//一句話 int len=(stringBuilder.length()+7)/8int 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;//記錄是第幾個bytefor (int i = 0; i < stringBuilder.length(); i+=8) {//因為每8位對應一個byte，所以步長+8String strByte;if(i+8>stringBuilder.length()){//不夠8位strByte = stringBuilder.substring(i);}else {strByte = stringBuilder.substring(i, i + 8);}//將strByte轉成一個byte，放入到huffmanCodeByteshuffmanCodeBytes[index]= (byte) Integer.parseInt(strByte,2);index++;}return huffmanCodeBytes;}//生成赫夫曼樹對應的赫夫曼編碼//思路：//1.將赫夫曼編碼表存放在Map<Byte,String>形式static Map<Byte,String> huffmanCodes= new HashMap<Byte,String>();// 32->01 97->100...//2.在生成赫夫曼編碼表示，需要去拼接璐姐，定義一個StringBuilder存儲某個葉子結點的路徑static StringBuilder stringBuilder=new StringBuilder();//這里為了調用方便,我們重載getCodesprivate 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加入到stringBuild2stringBuilder2.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());}}}//前序遍歷的方法private static void preOrder(Node root){if(root!=null){root.preOrder();}else {System.out.println("赫夫曼樹為空");}}/**** @param bytes 接收字節數組* @return 返回的就是List形式*/private static List<Node> getNodes(byte[] bytes){//1.創建一個ArrayListArrayList<Node> nodes = new ArrayList<>();//遍歷bytes 統計每一個byte出現的次數->map[key,value]HashMap<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集合//遍歷mapfor(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);//將新的二叉樹，加入到nodesnodes.add(parent);}//nodes最后的節點，就是哈夫曼樹的根節點return nodes.get(0);}}//創建Node，待數據和權值 class Node implements Comparable<Node>{Byte data;//存放數據(字符)本身，比如'a'=>97 ' '=>32int weight;//權值，表示字符出現的次數Node left;Node right;public Node(Byte data, int weight) {this.data = data;this.weight = weight;}@Overridepublic int compareTo(Node o) {//從小到大排序return this.weight-o.weight;}@Overridepublic 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();}}}

總結

以上是生活随笔為你收集整理的利用赫夫曼编码进行数据解压的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。