什么是赫夫曼編碼
本篇內(nèi)容介紹了“什么是赫夫曼編碼”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！
站在用戶的角度思考問(wèn)題，與客戶深入溝通，找到城關(guān)網(wǎng)站設(shè)計(jì)與城關(guān)網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：網(wǎng)站制作、成都做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、域名注冊(cè)、雅安服務(wù)器托管、企業(yè)郵箱。業(yè)務(wù)覆蓋城關(guān)地區(qū)。
基本介紹
赫夫曼編碼也翻譯為(哈夫曼編碼)Huffman Coding，又稱為霍夫曼編碼，是一種編碼方式，屬于一種程序算法。
赫夫曼編碼是赫夫曼樹(shù)在電訊通訊中的經(jīng)典的應(yīng)用場(chǎng)景之一。
赫夫曼編碼廣泛的用于數(shù)據(jù)文件壓縮。其壓縮率通常在20%~90%之間。
赫夫曼碼是可變字長(zhǎng)編碼(VLC)的一種.Hufuuman于1952年提出一種編碼方法，稱之為最佳編碼。
原理剖析
在通信領(lǐng)域中信息的處理方式1：定長(zhǎng)編碼
如: i like like like java do you like a java 共40個(gè)字符，包括空格，其對(duì)應(yīng)的ASCII碼,與二進(jìn)制編碼如下圖
按照二進(jìn)制來(lái)傳遞信息，總的長(zhǎng)度是359(包含空格)
在通信領(lǐng)域中信息的處理方式2：變長(zhǎng)編碼
i like like like java do you like a java 共40個(gè)字符，包括空格。變長(zhǎng)編碼處理如下圖
字符的編碼都不能是其他字符編碼的前綴，符合此要求的編碼叫做前綴編碼，即不能匹配到重復(fù)的編碼。
在通信領(lǐng)域中信息的處理方式3：赫夫曼編碼
i like like like java do you like a java 共40個(gè)字符，包括空格。變長(zhǎng)編碼處理如下圖
按照上面字符出現(xiàn)的次數(shù)構(gòu)建一顆赫夫曼樹(shù)，次數(shù)作為權(quán)值。
根據(jù)赫夫曼樹(shù)，給各個(gè)字符，規(guī)定編碼(前綴編碼),向左的路徑為0 向右的路徑為1：編碼如下：
按照上面的赫夫曼編碼，我們的"i like like like java do you like a java" 字符串對(duì)應(yīng)的編碼(注意這里我們使用的無(wú)損壓縮)如下圖。
說(shuō)明：
原來(lái)的長(zhǎng)度是359，壓縮了(359-133)/359=62.9%
此編碼滿足前綴編碼，即字符的編碼都不能是其他字符編碼的前綴。不會(huì)造成匹配的多義性。
赫夫曼編碼是無(wú)損壓縮!!
注意：
這個(gè)赫夫曼樹(shù)根據(jù)排序方法不同，也可能不一樣，這樣對(duì)應(yīng)的赫夫曼編碼也不完全一樣，但是wpl是一樣的，都是最小的，比如我們讓每次生成的新的二叉樹(shù)總是排在權(quán)值相同的二叉樹(shù)的最后一個(gè)，則生成的二叉樹(shù)為：
創(chuàng)建對(duì)應(yīng)的赫夫曼樹(shù)
根據(jù)赫夫曼編碼壓縮數(shù)據(jù)的原理，需要?jiǎng)?chuàng)建"i like like like java do you like a java" 對(duì)應(yīng)的赫夫曼樹(shù)
思路：
先創(chuàng)建Node節(jié)點(diǎn)，Node {data{存放數(shù)據(jù)}，weight(權(quán)值),left,right};
得到"i like like like java do you like a java" 對(duì)應(yīng)的byte[] 數(shù)組;
編寫(xiě)一個(gè)方法，將準(zhǔn)備構(gòu)建赫夫曼樹(shù)的node節(jié)點(diǎn)放到List
可以通過(guò)集合List
赫夫曼樹(shù)應(yīng)用案例
將一串字符串進(jìn)行壓縮與解壓縮
package com.xie.huffmancode; import java.util.*; public class HuffmanCode { public static void main(String[] args) { String str = "i like like like java do you like a java"; byte[] contentBytes = str.getBytes(); System.out.println("contentBytes=" + Arrays.toString(contentBytes)); List<Node> nodes = getNodes(contentBytes); //生成赫夫曼樹(shù) Node hufffmanTreeRoot = createHufffmanTree(nodes); //生成的赫夫曼編碼表 getCodes(hufffmanTreeRoot, "", stringBuilder); byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes); System.out.println("huffmanCodeBytes = " + Arrays.toString(huffmanCodeBytes)); byte[] decode = decode(huffmanCodes, huffmanCodeBytes); System.out.println("赫夫曼解碼后對(duì)應(yīng)的數(shù)組" + new String(decode)); /** * contentBytes=[105, 32, 108, 105, 107, 101, 32, 108, 105, 107, 101, 32, 108, 105, 107, 101, 32, 106, 97, 118, 97, 32, 100, 111, 32, 121, 111, 117, 32, 108, 105, 107, 101, 32, 97, 32, 106, 97, 118, 97] * huffmanCodeBytes = [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28] * 赫夫曼解碼后對(duì)應(yīng)的數(shù)組i like like like java do you like a java */ } //完成數(shù)據(jù)的解壓思路 //1.將huffmanCodeBytes[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28] // 重新轉(zhuǎn)成 赫夫曼編碼對(duì)應(yīng)的二進(jìn)制字符串"101010001011111111001000101111...." //2.赫夫曼編碼對(duì)應(yīng)的二進(jìn)制字符串"101010001011111111001000101111...." => 對(duì)照赫夫曼編碼表 => "i like like like java do you like a java" /** * 完成對(duì)壓縮數(shù)據(jù)的解碼 * * @param huffmanCodes 赫夫曼編碼表 * @param huffmanBytes 赫夫曼編碼得到的字節(jié)數(shù)組 * @return 原來(lái)的字符串對(duì)應(yīng)的數(shù)組 */ public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) { StringBuilder stringBuilder = new StringBuilder(); for (int i = 0; i < huffmanBytes.length; i++) { //判斷是不是最后一個(gè)字節(jié) boolean flag = (i == huffmanBytes.length - 1); stringBuilder.append(byteToBitString(!flag, huffmanBytes[i])); } Map<String, Byte> map = new HashMap<>(); for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) { Byte k = entry.getKey(); String v = entry.getValue(); map.put(v, k); } List<Byte> list = new ArrayList<>(); for (int i = 0; i < stringBuilder.length();) { int count = 1; boolean flag = true; Byte b = null; while (flag) { String key = stringBuilder.substring(i, i + count);//i 不動(dòng)，count移動(dòng)，直到匹配一個(gè)字符 b = map.get(key); if (b == null) { count++; } else { flag = false; } } list.add(b); i += count; } byte[] bytes = new byte[list.size()]; for (int i = 0; i < list.size(); i++) { bytes[i] = list.get(i); } return bytes; } /** * 將一個(gè)byte 轉(zhuǎn)成一個(gè)二進(jìn)制的字符串 * * @param flag 標(biāo)識(shí)是否需要補(bǔ)高位，true標(biāo)識(shí)需要補(bǔ)高位,如果是false表示不補(bǔ)，如果是最后一個(gè)字節(jié)，無(wú)需補(bǔ)高位 * @param b 傳入的byte * @return 該byte對(duì)應(yīng)的二進(jìn)制字符串，（注意是按補(bǔ)碼返回) */ public static String byteToBitString(boolean flag, byte b) { //將b 轉(zhuǎn)成 int int temp = b; //如果temp是正數(shù)還需要補(bǔ)高位 if (flag) { // 按位或 如 256|1=> 1 0000 0000|0000 0001 => 1 0000 0001 temp |= 256; } //返回的是temp二進(jìn)制的補(bǔ)碼 String bitStr = Integer.toBinaryString(temp); if (flag) { //取后8位 return bitStr.substring(bitStr.length() - 8); } else { return bitStr; } } /** * 封裝原始字節(jié)數(shù)組轉(zhuǎn)赫夫曼字節(jié)數(shù)組 * * @param bytes * @return */ public static byte[] huffmanZip(byte[] bytes) { List<Node> nodes = getNodes(bytes); //創(chuàng)建赫夫曼樹(shù) Node hufffmanTreeRoot = createHufffmanTree(nodes); //生成赫夫曼編碼 getCodes(hufffmanTreeRoot, "", stringBuilder); //返回壓縮后的赫夫曼編碼字節(jié)數(shù)組 return zip(bytes, huffmanCodes); } /** * 將字符串對(duì)應(yīng)的byte[] 數(shù)組，通過(guò)赫夫曼編碼表，返回一個(gè)赫夫曼編碼壓縮后的byte[] * * @param bytes 原始字符串對(duì)應(yīng)的byte[] * @param huffmanCodes 生成的赫夫曼編碼 * @return 返回赫夫曼編碼處理后的byte[] */ public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) { //利用huffmanCodes 將 bytes 轉(zhuǎn)成赫夫曼編碼對(duì)應(yīng)的字符串 StringBuilder stringBuilder = new StringBuilder(); for (byte b : bytes) { stringBuilder.append(huffmanCodes.get(b)); } // 將"101010001011111111001000101111...." 轉(zhuǎn)成byte[] // 統(tǒng)計(jì)返回byte[] huffmanCodeBytes 長(zhǎng)度 int len; if (stringBuilder.length() % 8 == 0) { len = stringBuilder.length() / 8; } else { len = stringBuilder.length() / 8 + 1; } //創(chuàng)建 存儲(chǔ)壓縮后的byte[]數(shù)組 byte[] huffmanCodeBytes = new byte[len]; int index = 0; for (int i = 0; i < stringBuilder.length(); i += 8) { String strByte; if (i + 8 > stringBuilder.length()) { strByte = stringBuilder.substring(i); } else { strByte = stringBuilder.substring(i, i + 8); } //將strByte 轉(zhuǎn)成一個(gè)byte ,放入到huffmanCodeBytes huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2); index++; } return huffmanCodeBytes; } //生成赫夫曼樹(shù)對(duì)應(yīng)的赫夫曼編碼表 //思路： //1. 將赫夫曼編碼表存放在Map<Byte,String>,形式如32->01,97->100... static Map<Byte, String> huffmanCodes = new HashMap<>(); //2. 在生成赫夫曼編碼表時(shí)，需要拼接路徑，定義一個(gè)StringBuilder 存儲(chǔ)某個(gè)葉子節(jié)點(diǎn)的路徑 static StringBuilder stringBuilder = new StringBuilder(); /** * 將傳入的node 節(jié)點(diǎn)的所有葉子的赫夫曼編碼得到，并放入huffmanCodes集合 * * @param node 傳入節(jié)點(diǎn) * @param code 路徑：左子節(jié)點(diǎn)是0，右子節(jié)點(diǎn)是1 * @param stringBuilder 用于拼接路徑 */ public static void getCodes(Node node, String code, StringBuilder stringBuilder) { StringBuilder stringBuilder2 = new StringBuilder(stringBuilder); stringBuilder2.append(code); if (node != null) { //判斷當(dāng)前node 是葉子節(jié)點(diǎn)還是非葉子節(jié)點(diǎn) if (node.data == null) {//非葉子節(jié)點(diǎn) //向左遞歸處理 getCodes(node.left, "0", stringBuilder2); //向右遞歸處理 getCodes(node.right, "1", stringBuilder2); } else {//葉子節(jié)點(diǎn) huffmanCodes.put(node.data, stringBuilder2.toString()); } } } //前序遍歷 public static void preOrder(Node root) { if (root != null) { root.preOrder(); } else { System.out.println("赫夫曼樹(shù)不能為空~~"); } } /** * 將字節(jié)數(shù)組轉(zhuǎn)成node集合 * * @param bytes 字節(jié)數(shù)組 * @return */ public static List<Node> getNodes(byte[] bytes) { ArrayList<Node> nodes = new ArrayList<>(); //存儲(chǔ)每個(gè)byte出現(xiàn)的次數(shù) Map<Byte, Integer> counts = new HashMap<>(); for (byte b : bytes) { counts.merge(b, 1, (a, b1) -> a + b1); } //把每個(gè)鍵值對(duì)轉(zhuǎn)成一個(gè)node對(duì)象，并加入到nodes 集合 counts.forEach((k, v) -> nodes.add(new Node(k, v))); return nodes; } /** * 生成赫夫曼樹(shù) * @param nodes 傳入的節(jié)點(diǎn) * @return */ public static Node createHufffmanTree(List<Node> nodes) { while (nodes.size() > 1) { //排序，從小到大 Collections.sort(nodes); //(1)取出權(quán)值最小的節(jié)點(diǎn)(二叉樹(shù)) Node leftNode = nodes.get(0); //(2) 取出權(quán)值第二小的節(jié)點(diǎn)(二叉樹(shù)) Node rightNode = nodes.get(1); //(3) 構(gòu)建一顆新的二叉樹(shù) Node parent = new Node(null, leftNode.weight + rightNode.weight); parent.left = leftNode; parent.right = rightNode; //(4) 從ArrayList中刪除處理過(guò)的二叉樹(shù) nodes.remove(leftNode); nodes.remove(rightNode); //(5) 將parent加入nodes nodes.add(parent); } //nodes 的最后一個(gè)就是赫夫曼樹(shù)的root節(jié)點(diǎn) return nodes.get(0); } } //創(chuàng)建Node，帶數(shù)據(jù)和權(quán)值 class Node implements Comparable<Node> { //存放數(shù)據(jù)本身,比如'a'=>'97'，' ' =>'32' Byte data; //權(quán)值，表示字符出現(xiàn)的次數(shù) int weight; Node left; Node right; public Node(Byte data, int weight) { this.data = data; this.weight = weight; } public void preOrder() { System.out.println(this); if (this.left != null) { this.left.preOrder(); } if (this.right != null) { this.right.preOrder(); } } @Override public int compareTo(Node o) { //從小到大排序 return this.weight - o.weight; } @Override public String toString() { return "Node{" + "data=" + data + ", weight=" + weight + '}'; } }赫夫曼壓縮文件注意事項(xiàng)
如果文件本身就經(jīng)過(guò)壓縮處理的，那么使用赫夫曼編碼再壓縮效率不會(huì)有明顯的變化，比如視頻，ppt等文件。
赫夫曼編碼是按字節(jié)來(lái)處理的，因此可以處理所有的文件(二進(jìn)制文件，文本文件)
如果一個(gè)文件中的內(nèi)容，重復(fù)的數(shù)據(jù)不多，壓縮效果也不會(huì)明顯。
“什么是赫夫曼編碼”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！
當(dāng)前題目：什么是赫夫曼編碼
URL標(biāo)題：http://bm7419.com/article20/ijhhjo.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、Google、企業(yè)網(wǎng)站制作、做網(wǎng)站、商城網(wǎng)站、虛擬主機(jī)
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)
