什么是哈夫曼編碼
哈夫曼編碼(Huffman Coding)箍邮，又稱霍夫曼編碼，是一種編碼方式芋绸，哈夫曼編碼是可變字長編碼(VLC)的一種媒殉。Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字摔敛，有時(shí)稱之為最佳編碼，一般就叫做Huffman編碼（有時(shí)也稱為霍夫曼編碼）
為什么哈夫曼編碼能夠?qū)崿F(xiàn)文件的壓縮
如果我們使用的定長編碼方例如ASCII碼全封，8-bit定長編碼马昙，使用8位(一個(gè)字節(jié))代表一個(gè)字符，就會(huì)出現(xiàn)很多的byte出現(xiàn)了相同刹悴，所以我們考慮一種新的編碼方式行楞，變長編碼的方式，原理很簡單土匀，以前是使用的8位表示一個(gè)字符子房，現(xiàn)在該用不固定長度，確定長度的依據(jù)是每個(gè)字符出現(xiàn)的次數(shù)就轧，越是高頻的字符其所用的bit（二進(jìn)制位數(shù)）越短证杭，這樣就實(shí)現(xiàn)了整個(gè)文本的變短，
//舉例我們有這么一個(gè)字符串：
String content = "abbcccddddeeeee";
當(dāng)我們把這段文字發(fā)送給別人時(shí)妒御，會(huì)轉(zhuǎn)換成一段字節(jié)數(shù)組長成下面這個(gè)樣子
字節(jié)數(shù)組：
[97, 98, 98, 99, 99, 99, 100, 100, 100, 100, 101, 101, 101, 101, 101]
二進(jìn)制：
110000111000101100010110001111000111100011110010011001001100100110010011001011100101110010111001011100101
使用哈夫曼編碼過后
先統(tǒng)計(jì)文本每個(gè)字符的 a : 1 b:2 c:3 d:4 e:5
每個(gè)字符對應(yīng)的二進(jìn)制 a->1110 b->1111 c->110 d->10 e->0
二進(jìn)制：
010011011000000101010101111111111
字節(jié)數(shù)組：
[77, -127, 85, -1, 1]
要想學(xué)習(xí)哈夫曼編碼先了解哈夫曼樹的基本概念
- 路徑和路徑長度：在一棵樹中解愤，從節(jié)點(diǎn)往下可以達(dá)到的孩子或者孫子節(jié)點(diǎn)之間的通路，從樹根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的長度稱為路徑長度乎莉，從從根節(jié)點(diǎn)到第L層節(jié)點(diǎn)到路徑長度為L-1
- 節(jié)點(diǎn)的權(quán)及帶權(quán)路徑長度：給節(jié)點(diǎn)值我們就叫做節(jié)點(diǎn)的權(quán)值送讲，節(jié)點(diǎn)帶權(quán)路徑的為： 路徑長度 * 權(quán)值
- 一整個(gè)樹的帶權(quán)路徑長度會(huì)等于所有葉子節(jié)點(diǎn)的帶權(quán)路徑長度之和奸笤，稱為WPL（weighted path length）
- WPL最小時(shí)就叫做哈夫曼樹，因此我們構(gòu)建哈夫曼樹時(shí)應(yīng)該將最大權(quán)值的節(jié)點(diǎn)放在根節(jié)點(diǎn)附近
非最優(yōu)二叉樹1.png
非最優(yōu)二叉樹2
哈夫曼樹.png
1哼鬓、壓縮算法實(shí)現(xiàn)部分
基本思路
- 構(gòu)造樹節(jié)點(diǎn)node
- 用生成的節(jié)點(diǎn)node構(gòu)造哈夫曼樹
- 生成哈夫曼編碼表
- 用哈夫曼編碼表生成壓縮后的字節(jié)數(shù)組
構(gòu)造樹節(jié)點(diǎn)node
這是node類實(shí)現(xiàn)了Comparable借口监右，并且重寫了compareTo可以后續(xù)用于所有node根據(jù)權(quán)值排序
public class Node implements Comparable<Node>{
Byte data; //存放數(shù)據(jù)本身
int weight; //權(quán)值
Node left; //指向左子節(jié)點(diǎn)
Node right; //指向右子節(jié)點(diǎn)
public Node(Byte data, int weight) {
this.data = data;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
// TODO Auto-generated method stub
return this.weight-o.weight;
}
@Override
public String toString() {
return "Node [data=" + data + ", weight=" + weight + "]";
}
}
根據(jù)文本信息轉(zhuǎn)換成Byte數(shù)組，再創(chuàng)建一個(gè)HashMap 遍歷整個(gè)byte數(shù)組key保存當(dāng)前的byte的值异希，value用于統(tǒng)計(jì)相同字節(jié)出現(xiàn)的頻率健盒，再把這個(gè)HashMap中的節(jié)點(diǎn)轉(zhuǎn)換成Node節(jié)點(diǎn)
public static void main(String[] args) {
// TODO Auto-generated method stub
String content = "abbcccddddeeeee";
byte[] contentBytes = content.getBytes();
List<Node> nodes = getNodes(bytes);
}
private static List<Node> getNodes(byte[] bytes) {
// 創(chuàng)建Arrlist
ArrayList<Node> nodes = new ArrayList<Node>();
// 遍歷bytes，統(tǒng)計(jì)byte出現(xiàn)的次數(shù)->map
Map<Byte, Integer> counts = new HashMap();
for (byte b : bytes) {
if (!counts.containsKey(b)) {
counts.put(b, 1);
} else {
counts.put(b, counts.get(b) + 1);
}
}
// 把每一個(gè)鍵對轉(zhuǎn)成一個(gè)Node對象宠互，并加入到nodes集合中
for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
return nodes;
}
用生成的節(jié)點(diǎn)node構(gòu)造哈夫曼樹
- 權(quán)值越大味榛，帶權(quán)路徑長度應(yīng)該最短越接近root節(jié)點(diǎn)，原因是用0和1分別表示二叉樹的左右字節(jié)點(diǎn)可達(dá)路徑予跌，
- 對傳入的list中的node從小到大進(jìn)行排序搏色，拿出第一個(gè)最小的兩個(gè)元素，構(gòu)成新的節(jié)點(diǎn)放入list中
- 對新的節(jié)點(diǎn)不賦值,權(quán)重是兩個(gè)券册，把它的左右節(jié)點(diǎn)初始化為最小的兩個(gè)元素频轿，權(quán)重是兩個(gè)是兩個(gè)子節(jié)點(diǎn)的和
- 重復(fù)以上的步驟直到list中的元素小2時(shí)候停止
示例 String content = "abbcccddddeeeee";
a : 1 b:2 c:3 d:4 e:5
步驟1
步驟2
步驟3
步驟4
具體代碼如下：
// 可以通過list創(chuàng)建哈夫曼樹
/**
* @param nodes 要處理的nodes
* @return 返回root節(jié)點(diǎn)
*/
public static Node createHuffmanTree(List<Node> nodes) {
// 傳入的list中大于1個(gè)節(jié)點(diǎn)時(shí)候才構(gòu)建二叉樹
while (nodes.size() > 1) {
// 對集合里面的元素進(jìn)行排序
Collections.sort(nodes);
// 取出權(quán)值最小的節(jié)點(diǎn)
Node left = nodes.get(0);
Node right = nodes.get(1);
// 構(gòu)建一個(gè)新的二叉樹節(jié)點(diǎn)，并且初始化它的值為null
Node parent = new Node(null, left.weight + right.weight);
// 把兩個(gè)節(jié)點(diǎn)掛在一個(gè)非子節(jié)點(diǎn)上
parent.left = left;
parent.right = right;
// 移除左右兩個(gè)節(jié)點(diǎn)
nodes.remove(left);
nodes.remove(right);
// 把這個(gè)非葉子節(jié)點(diǎn)加入到存放到nodes中
nodes.add(parent);
}
return nodes.get(0);
}
構(gòu)建哈夫曼樹的輸出結(jié)果
Node [data=null, weight=15]
Node [data=null, weight=6]
Node [data=99, weight=3]
Node [data=null, weight=3]
Node [data=97, weight=1]
Node [data=98, weight=2]
Node [data=null, weight=9]
Node [data=100, weight=4]
Node [data=101, weight=5]
生成哈夫曼編碼表
首先要?jiǎng)?chuàng)建huffmanCodes哈夫曼編碼表 烁焙，表的key - node.data(a,b,c) value - 0101航邢，重載getCodes函數(shù)定義一個(gè)StringBuilder用于字符串010101的連接，遞歸處理之前生成好的哈夫曼樹骄蝇，往左走拼接 '0' ,往右走拼接'1'只有當(dāng)我們遍歷到葉子節(jié)點(diǎn)才把它加入huffmanCodes中
// 聲明哈夫曼編碼表膳殷，static修飾，在多個(gè)方法中共同使用
public static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();
// 生成哈夫曼樹對應(yīng)的哈夫曼編碼
// 思路：
// 將哈夫曼編碼存放在map中比較合適 Map<Byte,String>
// e->0 d->10 c->110 b->1111 a->1110
// 為了調(diào)用方便九火，重載getCodes
private static Map<Byte, String> getCodes(Node root) {
if (root == null) {
return null;
}
//處理只有root節(jié)點(diǎn)的特殊情況
if (root.left == null && root.right == null) {
huffmanCodes.put(root.data, "0");
}
// 在生成哈夫曼編碼表時(shí)赚窃，需要去拼接路徑，定義一個(gè)StringBuilder 存儲(chǔ)葉子節(jié)點(diǎn)的路徑
StringBuilder builder = new StringBuilder();
// 處理左子樹
getCodes(root.left, "0", builder);
// 處理右子樹
getCodes(root.right, "1", builder);
return huffmanCodes;
}
/**
* 功能：將傳入的node節(jié)點(diǎn)的所有葉子節(jié)點(diǎn)的哈夫曼得到岔激，并放入huffmanCodes中
*
* @param node //傳入節(jié)點(diǎn)
* @param code //路徑：左子節(jié)點(diǎn)是0 右子節(jié)點(diǎn)1
* @param builder //用于拼接路徑
*/
private static void getCodes(Node node, String code, StringBuilder builder) {
// 重建StringBuilder是為了防治地址引用一值勒极，保持生成字符不共用同一字符串
StringBuilder builder2 = new StringBuilder(builder);
// 將code加入到StringBuilder
builder2.append(code);
if (node != null) { // 如果為空不進(jìn)行處理
// 判斷當(dāng)前是葉子還是非葉子節(jié)點(diǎn)
if (node.data == null) {
// 遞歸處理
// 左邊遞歸
getCodes(node.left, "0", builder2);
// 右邊遞歸
getCodes(node.right, "1", builder2);
} else {
// 找到了葉子節(jié)點(diǎn)
huffmanCodes.put(node.data, builder2.toString());
}
}
}
用哈夫曼編碼表生成壓縮后的字節(jié)數(shù)組
最后一步就是用我們生成好的哈夫曼編碼表對我們的全部文本進(jìn)行生成處理過后的字節(jié)數(shù)組，遍歷整個(gè)字節(jié)數(shù)組用字節(jié)數(shù)組的每個(gè)數(shù)據(jù)去hashmap中匹配010101生成二進(jìn)制字符串虑鼎，因?yàn)楣蚵幋a表對應(yīng)的二進(jìn)制是可變長的辱匿，所以最后字符串的長度可能就不是8的倍數(shù)，要進(jìn)行特殊處理多加一個(gè)字節(jié)炫彩，最后一個(gè)字節(jié)如果不滿8bit匾七，我們在這里要用一個(gè)static int endLen記錄下它的長度，在后面逆向解壓中將要用到 媒楼， 再遍歷整個(gè)字符串?dāng)?shù)組用Byte數(shù)組來封裝好整個(gè)字符串乐尊，1Byte=8bit， 具體的代碼如下：
// 編寫一個(gè)方法划址，將字符串對應(yīng)的byte[]數(shù)組扔嵌，通過生成哈夫曼編碼表限府，返回一個(gè)哈夫曼編碼處理后的byte[]數(shù)組
/**
* @param bytes 原始數(shù)據(jù)要處理的byte數(shù)組
* @param huffmanCode //哈夫曼編碼表
* @return //返回處理后的byte[]
*/
public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCode) {
// 利用huffmanCodes將byte轉(zhuǎn)成哈夫曼對應(yīng)的字符串
StringBuilder builder = new StringBuilder("");
// 遍歷數(shù)組
for (byte b : bytes) {
builder.append(huffmanCodes.get(b));
}
// 將"10101000..." 轉(zhuǎn)成byte[]
// 統(tǒng)計(jì)返回的哈夫曼編碼有多長
int len = (builder.length() % 8) == 0 ? builder.length() / 8 : builder.length() / 8 + 1;
endLen = builder.length() % 8;
// 創(chuàng)建 存儲(chǔ)后的bytes壓縮數(shù)組
byte[] huffmanCodeBytes = new byte[len];
int index = 0;// 記錄是第幾個(gè)byte
for (int i = 0; i < builder.length(); i += 8) {// 因?yàn)槭敲?位對應(yīng)一個(gè)byte，所以步長+8
String strByte;
// 兩種情況i+8超過最后位置和不超過的分別賦值
strByte = i + 8 > builder.length() ? builder.substring(i) : builder.substring(i, i + 8);
// 后面一個(gè)參數(shù)2表示轉(zhuǎn)換成二進(jìn)制
huffmanCodeBytes[index++] = (byte) Integer.parseInt(strByte, 2);
}
return huffmanCodeBytes;
}
處理之后的結(jié)果
處理前的字節(jié)數(shù)組：[97, 98, 98, 99, 99, 99, 100, 100, 100, 100, 101, 101, 101, 101, 101] 長度=15
處理后的字節(jié)數(shù)組：[77, -127, 85, -1, 1] 長度=5
當(dāng)重復(fù)字符較多時(shí)痢缎，壓縮效率還是相當(dāng)可觀的
對整個(gè)壓縮流程創(chuàng)建一個(gè)接口函數(shù)方便調(diào)用
public static void main(String[] args) {
// TODO Auto-generated method stub
String content = "abbcccddddeeeee";
byte[] contentBytes = content.getBytes();
byte[] huffmanCodeBytes = huffmanZip(contentBytes);
}
// 創(chuàng)建一個(gè)接口函數(shù)封裝好實(shí)現(xiàn)的細(xì)節(jié)
/**
*
* @param bytes 原始字符串對應(yīng)的字節(jié)數(shù)組
* @return 返回處理后的字節(jié)數(shù)組
*/
public static byte[] huffmanZip(byte[] bytes) {
System.out.println("處理前的字節(jié)數(shù)組："+Arrays.toString(bytes)+" 長度="+bytes.length);
List<Node> nodes = getNodes(bytes);
// 創(chuàng)建哈夫曼樹
Node huffmanTreeRoot = createHuffmanTree(nodes);
// 對應(yīng)的哈夫曼編碼
Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
// 根據(jù)生成的哈夫曼編碼胁勺，得到壓縮后的數(shù)組
byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
System.out.println("處理后的字節(jié)數(shù)組："+Arrays.toString(huffmanCodeBytes)+" 長度="+huffmanCodeBytes.length);
preOrder(huffmanTreeRoot);
return huffmanCodeBytes;
}
2、解壓算法實(shí)現(xiàn)部分
基本思路
- 字節(jié)數(shù)組轉(zhuǎn)換成二進(jìn)制字符串
- 逆向處理生成好的哈夫曼編碼表
- 根據(jù)逆向生成的哈夫曼表查詢生成原來的字節(jié)數(shù)組
字節(jié)數(shù)組轉(zhuǎn)換成二進(jìn)制字符串
思路就是用flag來標(biāo)識是否時(shí)最后一位独旷，通過之前的endLen得到最后一位如果不滿八位就進(jìn)行特殊處理
代碼處理主要用二進(jìn)制的操作署穗，byte的取值范圍為-128-127，如果出現(xiàn)負(fù)數(shù)則要進(jìn)行補(bǔ)高位
// 完成數(shù)據(jù)轉(zhuǎn)成對應(yīng)的二進(jìn)制字符串'10101000...'
/**
* 將一個(gè)byte 轉(zhuǎn)成一個(gè)二進(jìn)制的字符串
*
* @param b 傳入的是一個(gè)字節(jié)b
* @param flag 標(biāo)志是否為最后一個(gè)字節(jié)嵌洼，true表示不是最后一個(gè)字節(jié)案疲，false表示是最后一個(gè)字節(jié)
* @return 是該b對應(yīng)對二進(jìn)制對字符串，（注意是按照補(bǔ)碼返回）
*/
public static String byteToBitString(boolean flag, byte b) {
// 使用一個(gè)變量保持b
int temp = b; // 將b轉(zhuǎn)成int
temp |= 256;
String str = Integer.toBinaryString(temp);// 返回的是temp對應(yīng)的二進(jìn)制補(bǔ)碼
if (flag || (flag == false && endLen == 0)) {
//字符串的截取麻养，只拿后八位
return str.substring(str.length() - 8);
} else {
//不滿8bit有多少位拿多少位
return str.substring(str.length() - endLen);
}
逆向處理生成好的哈夫曼編碼表
用循環(huán)把編碼表key（a,b,c）-value（0101） 倒轉(zhuǎn)過來
// 把哈夫曼編碼表進(jìn)行調(diào)換褐啡，因?yàn)橐M(jìn)行反向查詢
Map<String, Byte> map = new HashMap<String, Byte>();
for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
根據(jù)逆向生成的哈夫曼表查詢生成原來的字節(jié)數(shù)組
取生成好的010101二進(jìn)制字符串，根據(jù)哈夫曼編碼表查出原來的每個(gè)字節(jié)鳖昌，采用雙指針移動(dòng)的方式去hashmap中查詢备畦，查到了對應(yīng)的字節(jié)，吧它加入到我們的list中许昨，再把list轉(zhuǎn)換成byte數(shù)組進(jìn)行返回
// 編寫一個(gè)方法懂盐，完成對壓縮數(shù)據(jù)對解碼
/**
* @param huffmanCodes 哈夫曼編碼表
* @param huffmanBytes 哈夫曼編碼得到對字節(jié)數(shù)組
* @return 就是原來對字符串對應(yīng)對數(shù)組
*/
public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
// 1.先得到 huffmanBytes 對應(yīng)對二進(jìn)制字符串，形式10101000...
StringBuilder builder = new StringBuilder();
// 2.將byte數(shù)組轉(zhuǎn)成二進(jìn)制的字符串
for (int i = 0; i < huffmanBytes.length; i++) {
byte b = huffmanBytes[i];
// 判斷是不是最后一個(gè)字節(jié)
boolean flag = (i == huffmanBytes.length - 1);
builder.append(byteToBitString(!flag, b));
}
// 創(chuàng)建集合糕档，存放byte
List<Byte> list = new ArrayList<>();
for (int i = 0; i < builder.length();) {
int count = 1; // 小的計(jì)數(shù)器
boolean flag = true;
Byte b = null;
while (flag) {
// 取出一個(gè)bit '1'或者'0'
String key = builder.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 = i + count;
}
// 當(dāng)for循環(huán)結(jié)束以后，list中存放了所有當(dāng)字符
// 把list中的數(shù)據(jù)放入到byte[] 并返回
byte b[] = new byte[list.size()];
for (int i = 0; i < b.length; i++) {
b[i] = list.get(i);
}
return b;
}
所有調(diào)用過程main函數(shù)
public static void main(String[] args) {
// TODO Auto-generated method stub
String content = "abbcccddddeeeee";
byte[] contentBytes = content.getBytes();
byte[] huffmanCodeBytes = huffmanZip(contentBytes);
byte[] source = decode(huffmanCodes, huffmanCodeBytes);
System.out.println("原來的字符串=" + new String(source));
}
壓縮-解壓的處理結(jié)果
處理前的字節(jié)數(shù)組：[97, 98, 98, 99, 99, 99, 100, 100, 100, 100, 101, 101, 101, 101, 101] 長度=15
處理后的字節(jié)數(shù)組：[77, -127, 85, -1, 1] 長度=5
原來的字符串=abbcccddddeeeee
總結(jié)
以上就就是關(guān)于所有哈java實(shí)現(xiàn)夫曼編碼的所有細(xì)節(jié)速那，希望你對此有更清晰的的了解
完整源代碼移步github
聲明
1类垫、如果在文章當(dāng)中發(fā)現(xiàn)有描述錯(cuò)誤的地方，還請您不吝指出琅坡，萬分感謝！
2残家、此文章系本人原創(chuàng)作品榆俺，轉(zhuǎn)發(fā)請注明出處！
