文章收藏的好句子：變好的過程都不太舒服，試試再努力點。

目錄

1、赫夫曼編碼字節

? ? ?1、1?赫夫曼編碼字節數組

? ? ?1、2?赫夫曼編碼壓縮后的字節數組轉換成二進制編碼

? ? ?1、3?赫夫曼解碼

1、赫夫曼編碼字節

1、1?赫夫曼編碼字節數組

本篇文章是在Java版赫夫曼編碼這篇文章的基礎上寫的，在Java版赫夫曼編碼這篇文章中，我們用?“the virus mutated and became weaker and weaker”?這句話生成了對應它的赫夫曼編碼，再通過它的赫夫曼編碼生成了對應的二進制編碼：10010100011110101010010011100001001011101110110010100101110011111000101011110101000101001101110011101111011111101000111101100001111100101011110101000101000111101100001111100 （Java版赫夫曼編碼這篇文章通過赫夫曼編碼取出的二進制編碼算法有些錯誤，所以Java版赫夫曼編碼這篇文章取出的二進制編碼不對）?！皌he virus mutated and became weaker and weaker”?這句話如果直接轉換為字節數組的話，那么字節數組的長度是46 ；如果生成它對應的赫夫曼編碼，再通過它的赫夫曼編碼生成對應的二進制編碼，通過它的二進制編碼轉換成字節數組的話，字節數組的長度又是多少呢？好，我們先把? ??

10010100011110101010010011100001001011101110110010100101110011111000101011110101000101001101110011101111011111101000111101100001111100101011110101000101000111101100001111100

? ?這一串二進制編碼當作一串字符放進記事本統計它們的字符數，如圖1所示；

?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?圖1

看圖1，字符串的長度是173個，我們知道一個字節占8位，所以我們按8位二進制碼壓縮成一個整數，看能壓縮多少個整數；173 / 8 = 21.625 ，就算它們是22個整數，當到第168個二進制碼的時候，剛好能壓縮到21個整數，當到第169個二進制碼的時候，不足8位，只有5位，所以單獨用5位二進制碼壓縮成一位整數；所以?“the virus mutated and became weaker and weaker”?這句話的赫夫曼編碼字節數組的長度是22?。

好，我們用代碼驗證?“the?virus?mutated and became weaker and weaker”?這句話的赫夫曼編碼字節數組的長度是不是22?？

（1）寫一個節點類 Node ：

/*** Node 實現 Comparable 是為了讓Node 對象持續排序 Collections 集合排序*/ public class Node implements Comparable<Node>{private Byte data;//存放十進制的 Ascill 碼，比 'a' 字符，那么 Ascill 碼就是97private int weight;//權值private Node left;//左孩子private Node right;//右孩子@Overridepublic int compareTo(Node arg0) {// 從小到大排序return this.weight - arg0.weight;}public Node(Byte data, int weight) {super();this.data = data;this.weight = weight;}public Byte getData() {return data;}public Node getLeft() {return left;}public void setLeft(Node left) {this.left = left;}public Node getRight() {return right;}public void setRight(Node right) {this.right = right;}public int getWeight() {return weight;}}

（2）創建一個實現將一大串二進制編碼壓縮成字節數組的類?Test?:

public class Test {Node root;//保存 ”通過赫夫曼樹編碼表取出的二進制編碼“String s;//拼接赫夫曼樹的節點的路徑，節點的左路徑用“0” 表示，右路徑用“1”表示StringBuilder sb = new StringBuilder();Map<Byte,String> huffumanCodes = new HashMap<Byte,String>();public static void main(String[] args) {String s = "the virus mutated and became weaker and weaker";byte[] bs = s.getBytes();Test test = new Test();byte[] bytes = test.huffumanZip(bs);System.out.println("壓縮后的字節數組：" + Arrays.toString(bytes));System.out.println("壓縮后的字節數組長度：" + bytes.length);}private byte[] huffumanZip(byte[] bs) {List<Node> list = getNode(bs);//創建赫夫曼樹root = createHuffmanTree(list);//生成赫夫曼編碼表，將 赫夫曼編碼表 存放到 huffumanCodes 中getCodes(root, "", sb);/*** 該方法通過赫夫曼編碼得到對應的二進制編碼，* 最后通過壓縮二進制編碼得到 對應的赫夫曼編碼字節數組*/byte[] bytes = zip(bs,huffumanCodes);//對應的赫夫曼編碼字節數組return bytes;}/*** 該方法通過赫夫曼編碼得到對應的二進制編碼，* 最后通過壓縮二進制編碼得到 對應的赫夫曼編碼字節數組* */private byte[] zip(byte[] bytes,Map<Byte, String> heffumanCodes) {StringBuilder sb = new StringBuilder();for (int i = 0; i < bytes.length; i++) {byte b = bytes[i];sb.append(heffumanCodes.get(b));}s = sb.toString();System.out.println("s = " + s);int length = 0;if (sb.length() % 8 == 0) {length = sb.length() / 8;} else {length = sb.length() / 8 + 1;}/*** 創建壓縮后的 byte數組*/byte[] bytes2 = new byte[length];/*** 記錄 bytes2 的索引*/int num = 0;for (int i = 0; i < sb.length(); i += 8) {String stringByte ;if (i + 8 >= sb.length()) {stringByte = sb.substring(i,sb.length());} else {stringByte = sb.substring(i,i + 8);}bytes2[num] = (byte) Integer.parseInt(stringByte, 2); num++;}return bytes2;}//生成赫夫曼編碼表/*** * @param node 傳入的節點* @param code 節點的左路徑用“0” 表示，右路徑用“1”表示* @param sb 拼接code* @return*/private void getCodes(Node node,String code,StringBuilder sb) {StringBuilder sb2 = new StringBuilder(sb);//將code 加入到 sb2 中sb2.append(code);if (node != null) {//非葉子節點if (node.getData() == null) {//向左遞歸處理getCodes(node.getLeft(), "0", sb2);//向右遞歸處理getCodes(node.getRight(), "1", sb2);//是葉子節點} else {huffumanCodes.put(node.getData(), sb2.toString());}}}private List<Node> getNode(byte[] bs) {ArrayList<Node> list = new ArrayList<Node>();//統計byte出現的次數Map<Byte,Integer> map = new HashMap<Byte,Integer>();for (int i = 0; i<bs.length; i++) {Integer count = map.get(bs[i]);//第一次存放該字節if (count == null) {map.put(bs[i],1);} else {map.put(bs[i], count + 1);}}for (Map.Entry<Byte, Integer> entry : map.entrySet()) {Byte data = entry.getKey();int weight = entry.getValue();Node node = new Node(data,weight);list.add(node);}return list;}//創建赫夫曼樹private Node createHuffmanTree(List<Node> list) {while (list.size() > 1) {// 排序，從小到大排序Collections.sort(list);// System.out.println("list = " + list);/*** 這個一定是權值最小的節點*/Node minNode = list.get(0);/*** 除了 minNode 節點，該節點就是權值最小的節點，只是該節點比 minNode 節點大， 比其他節點都小*/Node secondMinNode = list.get(1);/*** 構建一棵新的二叉樹*/Node parentNode = new Node(null,minNode.getWeight()+ secondMinNode.getWeight());parentNode.setLeft(minNode);parentNode.setRight(secondMinNode);/*** 從 list 集合中刪除2棵已經構建成一棵二叉樹的2個節點*/list.remove(minNode);list.remove(secondMinNode);/*** 將新的二叉樹的父節點加入到 list 集合中*/list.add(parentNode);}/*** 構建完哈夫曼樹后，list 集合中的第一個節點肯定是根節點*/return list.get(0);}}

日志打印如下所示：

果然，“the?virus?mutated and became weaker and weaker”?這句話的赫夫曼編碼字節數組的長度是22?；這里我們說一下程序的大概思路：先將?"the virus mutated and became weaker and weaker"?這句話直接轉換成字節數組（我給它取名叫B1），B1 中元素的 int 值就是 Ascill 碼的十進制數，通過 HashMap 來統計 B1 中元素出現的次數，也就是每個字節元素的Ascill 碼出現的次數；統計完后，就將每個字節元素的Ascill 碼出現的次數作為節點的權值創建節點，并將節點保存到 ArrayList 中；再通過 ArrayList 中的數據創建一棵赫夫曼樹，用赫夫曼樹生成對應的赫夫曼編碼表（就是一個 Map?集合，key?是字符十進制的 Ascill?碼，value?是葉子節點的二進制形式的權值），又再通過赫夫曼編碼表取出葉子節點二進制形式的權值并拼接成一串字符串，用8位為一個單位（將字符按8串取余?，余數如果大于0小于8，那么將余數單獨作為一個字節）的形式將字符串壓縮成一個字節數組；最后赫夫曼編碼字節數組的壓縮就大功告成了，這樣就節省了字節數組的空間。

1、2?赫夫曼編碼壓縮后的字節數組轉換成二進制編碼

在上面的案例中，我們將?“the?virus?mutated and became weaker and weaker” 這句話最終轉變成了赫夫曼編碼壓縮后的字節數組 {-108, 122, -92, -31, 46, -20, -91, -49, -118, -11, 20, -36, -17, 126, -113, 97, -14, -67, 69, 30, -61, 28}；我們這里將赫夫曼編碼壓縮后的字節數組轉換成二進制編碼，也就是將赫夫曼編碼壓縮后的字節數組?{-108, 122, -92, -31, 46, -20, -91, -49, -118, -11, 20, -36, -17, 126, -113, 97, -14, -67, 69, 30, -61, 28}?轉換成原先通過赫夫曼編碼得到的一大串的二進制編碼?

10010100011110101010010011100001001011101110110010100101110011111000101011110101000101001101110011101111011111101000111101100001111100101011110101000101000111101100001111100

赫夫曼編碼壓縮后的字節數組轉換成二進制編碼的思路是這樣的；

（1）用 for?循環遍歷壓縮后的字節數組，將每個字節轉換成對應的長度為8的字符串，字符串里面的內容一定是0和1；當然字符串的長度不一定是8，當最后一個字節轉換成字符串的時候長度有可能比8還小。

（2）字節轉換成字符串的過程中，如果不是最后一個字節，每個字節的10進制 Ascill?碼必須或上256，至于為什么要或上256，可以看代碼實現的注釋。

（3）字節轉換成字符串的過程中，如果不是最后一個字節，將切割字符串的后8位出來并返回；如果是最后一個字節且最后一個字節的10進制 Ascill?碼大于0，不用切割字符串，直接把字符串返回。

（4）每個字節轉成字符串后，將每個字符串拼接起來，這樣就將壓縮后的字節數組轉換成一大串的二進制編碼。

好，我們在上面案例的基礎上實現一把代碼；

（1）在 Test?類中添加decodeBinaryStr(byte[] encodeBytes)?方法和?decodeDecimal(boolean isNeedSub, int encodeByte)?方法：

/*** 將壓縮后的字節數組反編譯為二進制數字串* @param encodeBytes * @return 二進制數字串*/private String decodeBinaryStr(byte[] encodeBytes) {StringBuilder sb = new StringBuilder();boolean isNeedSub = true;for (int i = 0; i < encodeBytes.length; i++) {if (i == encodeBytes.length - 1 && encodeBytes[i] > 0) {isNeedSub = false;}sb.append(decodeDecimal(isNeedSub, encodeBytes[i]));}return sb.toString();}/*** 轉換* @param isNeedSub 是否需要截取* @param encodeByte 當前需要轉換的數據* @return*/private String decodeDecimal(boolean isNeedSub, int encodeByte) {String str = "";/*1、為什么要 encodeByte |= 256 ？當encodeByte是負數的時候，Integer.toBinaryString(encodeByte) 得到的是32位的字符串可以執行 str.substring(str.length() - 8) 不報錯；當encodeByte是正數的時候，Integer.toBinaryString(encodeByte) 得到不一定是大于等于8位的字符串，執行 str.substring(str.length() - 8) 就有可能報錯，就比如正數7，執行Integer.toBinaryString(7)就得到"111"，"111".substring("111".length() - 8)就會報錯；如果 7 |= 256 就等于 363，再執行 Integer.toBinaryString(363) 就得到"100000111"，再執行 "100000111".substring("100000111".length() - 8) 就得到 "00000111"，目的是7轉換成二進制的時候，如果不夠8位，就用0在前面補夠8位嘛2、256的二進制為: 1 0000 0000, 無論任務數字與256進行或運算后, 絕對能保證第九位的1, 則后八位有效轉換完成后, 截取后八位作為有效數據3、注意: 最后一位需要處理的數據不一定滿8位, 所以不滿八位的情況下一定為正數, 需要原樣處理,所以 isNeedSub 為 false*/if (isNeedSub) {encodeByte |= 256;} //返回 encodeByte 對應的二進制補碼str = Integer.toBinaryString(encodeByte);if (isNeedSub) {str = str.substring(str.length() - 8);}?return str;}

（2）在 Test 類中程序入口添加相應的代碼：

public static void main(String[] args) {String s = "the virus mutated and became weaker and weaker";byte[] bs = s.getBytes();Test test = new Test();byte[] bytes = test.huffumanZip(bs);System.out.println("壓縮后的字節數組：" + Arrays.toString(bytes));System.out.println("壓縮后的字節數組長度：" + bytes.length);String decodeBinaryStr = test.decodeBinaryStr(bytes);String result = test.s.equals(decodeBinaryStr) ? "相同" : "不相同";System.out.println("通過赫夫曼編碼表取出的二進制編碼與解壓后的二進制編碼是否相同？" + result);}

日志打印如下所示：

我們看到，通過赫夫曼編碼表取出的二進制編碼與字節數組轉換成二進制編碼是相同的，證明壓縮后的字節數組轉換成二進制編碼成功。

1、3?赫夫曼解碼

我們在本篇文章的 “ 赫夫曼編碼壓縮后的字節數組轉換成二進制編碼?”?案例中，將赫夫曼編碼壓縮后的字節數組 {-108, 122, -92, -31, 46, -20, -91, -49, -118, -11, 20, -36, -17, 126, -113, 97, -14, -67, 69, 30, -61, 28}，轉換成原先通過赫夫曼編碼得到的一大串的二進制編碼?

10010100011110101010010011100001001011101110110010100101110011111000101011110101000101001101110011101111011111101000111101100001111100101011110101000101000111101100001111100

我們要用原先通過赫夫曼編碼得到的一大串的二進制編碼?10010100011110101010010011100001001011101110110010100101110011111000101011110101000101001101110011101111011111101000111101100001111100101011110101000101000111101100001111100 解碼成相應的文本內容，也就是赫夫曼解碼。

它的實現思路是這樣的：

（1）將赫夫曼編碼表（映射關系是<Byte,String>）的映射關系反過來并保存在另外一個集合中（我叫它gather吧，gather的映射關系是<String,Byte>）。

（2）用?for?循環遍歷字節數組解壓出來的二進制編碼字符串，遍歷出來的二進制編碼字符串昨為 gather?的 key，gather?通過 key?取出得到一個 Byte，如果這個 Byte?不為空，證明拿到這個解碼的字符的字節成功，就將其保存到一個 List?集合中。

（3）將 List?集合中的 Byte?元素保存到一個 byte?數組中。

（4）將 byte?數組轉換成一個字符串，最終解碼相應的文本內容。

如果它的實現思路看不懂，那么就看下面的代碼實現，再回看它的實現思路就懂了。

好，我們現在代碼實現一把：

（1）在 Test 類中添加?decodeContent(String binaryStr, Map<Byte, String> pathMap) 方法和?doDecodeContent(String binaryStr, Map<String, Byte> pathByteMap) 方法；

/*** 根據解壓后的二進制編碼串和赫夫曼編碼表得到原始的字符串內容** @param binaryStr 壓縮后的字節數組轉換成的二進制編碼串* @param pathMap 赫夫曼編碼表* @return*/private byte[] decodeContent(String binaryStr, Map<Byte, String> pathMap) {//將映射關系倒換過來，即保存的<key,value>變成保存<value,key>Map<String, Byte> pathByteMap = reverseMap(pathMap);// 根據路徑一段段截取二進制數字串, 并拼湊為有效的byte碼byte[] resultBytes = doDecodeContent(binaryStr, pathByteMap);return resultBytes;}/*** 反編譯為最終需要的字節碼* @param binaryStr 壓縮后的字節數組轉換成的二進制編碼串* @param pathByteMap 赫夫曼編碼表(<Byte,String>)的倒映射表(<String, Byte>)* @return*/private byte[] doDecodeContent(String binaryStr, Map<String, Byte> pathByteMap) {// 截取的每一個數字, 添加到集合中List<Byte> lstBytes = new ArrayList<>();for (int i = 0; i < binaryStr.length();) {int count = 1;while(true) {// 1、以count作為一個標識位, 一直向后移動；舉例：假設 binaryStr = "1001010001111010101001001110000..."// 那么就用 count 一個個往后移動一位，直到匹配到 pathByteMap 的 key，currStr 就有可能是 "1"、"10"、"100"...String currStr = binaryStr.substring(i, i + count);// 如果路徑到字符映射中, 包含該路徑, 則匹配成功;舉例：假設 binaryStr = "1001010001111010101001001110000...",//假設pathByteMap的內容是<{"1001",116},{"01000",104}...>//當key = "1"、"10"、"100"時拿出來的 Byte 那就是為空，key = "1001"時，Byte 就不為空，則證明匹配成功，查找到這個字節if (null != pathByteMap.get(currStr)) {// 將 字節添加到 lstBytes 集合中，也就是將字符的10進制 Ascill 碼添加到 lstBytes 集合中lstBytes.add(pathByteMap.get(currStr));break;}count++;}// 匹配成功后, i直接進count位, 進行下一位字節查找；舉例假設 binaryStr = "1001010001111010101001001110000...",//假設pathByteMap的內容是<{"1001",116},{"01000",104}...>，//當執行binaryStr.substring(0, 5)這條語句的時候就找到了第一個字節(從"1001"從pathByteMap拿到一個字節)//那么查找下一個字節的count就從5開始i += count;}// 將List集合的Byte轉換為byte數組保存byte[] bytes = new byte[lstBytes.size()];int index = 0;for (Byte currByte : lstBytes) {bytes[index++] = currByte;}return bytes;}

（2）在 Test 類中的程序入口處調用稍微做一下修改：

public static void main(String[] args) {String s = "the virus mutated and became weaker and weaker";byte[] bs = s.getBytes();Test test = new Test();byte[] bytes = test.huffumanZip(bs);System.out.println("壓縮后的字節數組：" + Arrays.toString(bytes));System.out.println("壓縮后的字節數組長度：" + bytes.length);String decodeBinaryStr = test.decodeBinaryStr(bytes);System.out.println("decodeBinaryStr = " + decodeBinaryStr);String result = test.s.equals(decodeBinaryStr) ? "相同" : "不相同";System.out.println("通過赫夫曼編碼表取出的二進制編碼與解壓后的二進制編碼是否相同？" + result);byte[] decodeByte = test.decodeContent(decodeBinaryStr, test.huffumanCodes);System.out.println("解壓后的數據：" + new String(decodeByte));}

日志打印如下所示：

看見了沒，解壓后的數據和壓縮前的一模一樣，哈哈。

總結

以上是生活随笔為你收集整理的Java版赫夫曼编码字节和赫夫曼解码的全部內容，希望文章能夠幫你解決所遇到的問題。

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