基本介紹
- 赫夫曼編碼也翻譯為(哈夫曼編碼)Huffman Coding，又稱為霍夫曼編碼，是一種編碼方式，屬于一種程序算法。
- 赫夫曼編碼是赫夫曼樹在電訊通訊中的經(jīng)典的應(yīng)用場景之一。
- 赫夫曼編碼廣泛的用于數(shù)據(jù)文件壓縮。其壓縮率通常在20%~90%之間。
- 赫夫曼碼是可變字長編碼(VLC)的一種.Hufuuman于1952年提出一種編碼方法，稱之為最佳編碼。
原理剖析
在通信領(lǐng)域中信息的處理方式1：定長編碼
如: i like like like java do you like a java 共40個字符，包括空格，其對應(yīng)的ASCII碼,與二進制編碼如下圖
按照二進制來傳遞信息，總的長度是359(包含空格)
在通信領(lǐng)域中信息的處理方式2：變長編碼
i like like like java do you like a java 共40個字符，包括空格。變長編碼處理如下圖
字符的編碼都不能是其他字符編碼的前綴，符合此要求的編碼叫做前綴編碼，即不能匹配到重復(fù)的編碼。
在通信領(lǐng)域中信息的處理方式3：赫夫曼編碼
i like like like java do you like a java 共40個字符，包括空格。變長編碼處理如下圖
按照上面字符出現(xiàn)的次數(shù)構(gòu)建一顆赫夫曼樹，次數(shù)作為權(quán)值。
根據(jù)赫夫曼樹，給各個字符，規(guī)定編碼(前綴編碼),向左的路徑為0 向右的路徑為1：編碼如下：
按照上面的赫夫曼編碼，我們的"i like like like java do you like a java" 字符串對應(yīng)的編碼(注意這里我們使用的無損壓縮)如下圖。
說明：
原來的長度是359，壓縮了(359-133)/359=62.9%
此編碼滿足前綴編碼，即字符的編碼都不能是其他字符編碼的前綴。不會造成匹配的多義性。
赫夫曼編碼是無損壓縮!!
注意：
這個赫夫曼樹根據(jù)排序方法不同，也可能不一樣，這樣對應(yīng)的赫夫曼編碼也不完全一樣，但是wpl是一樣的，都是最小的，比如我們讓每次生成的新的二叉樹總是排在權(quán)值相同的二叉樹的最后一個，則生成的二叉樹為：
創(chuàng)建對應(yīng)的赫夫曼樹
根據(jù)赫夫曼編碼壓縮數(shù)據(jù)的原理，需要創(chuàng)建"i like like like java do you like a java" 對應(yīng)的赫夫曼樹
思路：
先創(chuàng)建Node節(jié)點，Node {data{存放數(shù)據(jù)}，weight(權(quán)值),left,right};
得到"i like like like java do you like a java" 對應(yīng)的byte[] 數(shù)組;
編寫一個方法，將準(zhǔn)備構(gòu)建赫夫曼樹的node節(jié)點放到List
可以通過集合List
赫夫曼樹應(yīng)用案例
將一串字符串進行壓縮與解壓縮
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);
//生成赫夫曼樹
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("赫夫曼解碼后對應(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]
* 赫夫曼解碼后對應(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)成 赫夫曼編碼對應(yīng)的二進制字符串"101010001011111111001000101111...."
//2.赫夫曼編碼對應(yīng)的二進制字符串"101010001011111111001000101111...." => 對照赫夫曼編碼表 => "i like like like java do you like a java"
/**
* 完成對壓縮數(shù)據(jù)的解碼
*
* @param huffmanCodes 赫夫曼編碼表
* @param huffmanBytes 赫夫曼編碼得到的字節(jié)數(shù)組
* @return 原來的字符串對應(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++) {
//判斷是不是最后一個字節(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 不動，count移動，直到匹配一個字符
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;
}
/**
* 將一個byte 轉(zhuǎn)成一個二進制的字符串
*
* @param flag 標(biāo)識是否需要補高位，true標(biāo)識需要補高位,如果是false表示不補，如果是最后一個字節(jié)，無需補高位
* @param b 傳入的byte
* @return 該byte對應(yīng)的二進制字符串，（注意是按補碼返回)
*/
public static String byteToBitString(boolean flag, byte b) {
//將b 轉(zhuǎn)成 int
int temp = b;
//如果temp是正數(shù)還需要補高位
if (flag) {
// 按位或 如 256|1=> 1 0000 0000|0000 0001 => 1 0000 0001
temp |= 256;
}
//返回的是temp二進制的補碼
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)建赫夫曼樹
Node hufffmanTreeRoot = createHufffmanTree(nodes);
//生成赫夫曼編碼
getCodes(hufffmanTreeRoot, "", stringBuilder);
//返回壓縮后的赫夫曼編碼字節(jié)數(shù)組
return zip(bytes, huffmanCodes);
}
/**
* 將字符串對應(yīng)的byte[] 數(shù)組，通過赫夫曼編碼表，返回一個赫夫曼編碼壓縮后的byte[]
*
* @param bytes 原始字符串對應(yīng)的byte[]
* @param huffmanCodes 生成的赫夫曼編碼
* @return 返回赫夫曼編碼處理后的byte[]
*/
public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
//利用huffmanCodes 將 bytes 轉(zhuǎn)成赫夫曼編碼對應(yīng)的字符串
StringBuilder stringBuilder = new StringBuilder();
for (byte b : bytes) {
stringBuilder.append(huffmanCodes.get(b));
}
// 將"101010001011111111001000101111...." 轉(zhuǎn)成byte[]
// 統(tǒng)計返回byte[] huffmanCodeBytes 長度
int len;
if (stringBuilder.length() % 8 == 0) {
len = stringBuilder.length() / 8;
} else {
len = stringBuilder.length() / 8 + 1;
}
//創(chuàng)建 存儲壓縮后的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)成一個byte ,放入到huffmanCodeBytes
huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}
//生成赫夫曼樹對應(yīng)的赫夫曼編碼表
//思路：
//1. 將赫夫曼編碼表存放在Map<Byte,String>,形式如32->01,97->100...
static Map<Byte, String> huffmanCodes = new HashMap<>();
//2. 在生成赫夫曼編碼表時，需要拼接路徑，定義一個StringBuilder 存儲某個葉子節(jié)點的路徑
static StringBuilder stringBuilder = new StringBuilder();
/**
* 將傳入的node 節(jié)點的所有葉子的赫夫曼編碼得到，并放入huffmanCodes集合
*
* @param node 傳入節(jié)點
* @param code 路徑：左子節(jié)點是0，右子節(jié)點是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é)點還是非葉子節(jié)點
if (node.data == null) {//非葉子節(jié)點
//向左遞歸處理
getCodes(node.left, "0", stringBuilder2);
//向右遞歸處理
getCodes(node.right, "1", stringBuilder2);
} else {//葉子節(jié)點
huffmanCodes.put(node.data, stringBuilder2.toString());
}
}
}
//前序遍歷
public static void preOrder(Node root) {
if (root != null) {
root.preOrder();
} else {
System.out.println("赫夫曼樹不能為空~~");
}
}
/**
* 將字節(jié)數(shù)組轉(zhuǎn)成node集合
*
* @param bytes 字節(jié)數(shù)組
* @return
*/
public static List<Node> getNodes(byte[] bytes) {
ArrayList<Node> nodes = new ArrayList<>();
//存儲每個byte出現(xiàn)的次數(shù)
Map<Byte, Integer> counts = new HashMap<>();
for (byte b : bytes) {
counts.merge(b, 1, (a, b1) -> a + b1);
}
//把每個鍵值對轉(zhuǎn)成一個node對象，并加入到nodes 集合
counts.forEach((k, v) -> nodes.add(new Node(k, v)));
return nodes;
}
/**
* 生成赫夫曼樹
* @param nodes 傳入的節(jié)點
* @return
*/
public static Node createHufffmanTree(List<Node> nodes) {
while (nodes.size() > 1) {
//排序，從小到大
Collections.sort(nodes);
//(1)取出權(quán)值最小的節(jié)點(二叉樹)
Node leftNode = nodes.get(0);
//(2) 取出權(quán)值第二小的節(jié)點(二叉樹)
Node rightNode = nodes.get(1);
//(3) 構(gòu)建一顆新的二叉樹
Node parent = new Node(null, leftNode.weight + rightNode.weight);
parent.left = leftNode;
parent.right = rightNode;
//(4) 從ArrayList中刪除處理過的二叉樹
nodes.remove(leftNode);
nodes.remove(rightNode);
//(5) 將parent加入nodes
nodes.add(parent);
}
//nodes 的最后一個就是赫夫曼樹的root節(jié)點
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 +
'}';
}
}
赫夫曼壓縮文件注意事項
如果文件本身就經(jīng)過壓縮處理的，那么使用赫夫曼編碼再壓縮效率不會有明顯的變化，比如視頻，ppt等文件。
赫夫曼編碼是按字節(jié)來處理的，因此可以處理所有的文件(二進制文件，文本文件)
如果一個文件中的內(nèi)容，重復(fù)的數(shù)據(jù)不多，壓縮效果也不會明顯。
原文地址：https://www.toutiao.com/i6935060748938920481/
