總目錄：地址如下看總綱
前置知識：關(guān)于原碼補(bǔ)碼反碼
1、赫夫曼編碼介紹
1、赫夫曼編碼也翻譯為 哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式, 屬于一種程序算法
2、赫夫曼編碼是赫哈夫曼樹在電訊通信中的經(jīng)典的應(yīng)用之一。
3、赫夫曼編碼廣泛地用于數(shù)據(jù)文件壓縮。其壓縮率通常在20%～90%之間，重復(fù)次數(shù)越多，壓縮率越高
4、赫夫曼碼是可變字長編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，稱之為最佳編碼
2、 通訊領(lǐng)域中信息處理方式
1、方式一：定長處理
- i like like like java do you like a java // 共40個(gè)字符(包括空格)
- 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
//對應(yīng)Ascii碼
- 01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001
//對應(yīng)的二進(jìn)制【總的長度是 359 (包括空格)】
2、方式二：變長處理
- i like like like java do you like a java // 共40個(gè)字符(包括空格)
- d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各個(gè)字符對應(yīng)的個(gè)數(shù)
- 0= , 1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d// 特殊規(guī)定編碼
- 說明：按照各個(gè)字符出現(xiàn)的次數(shù)進(jìn)行編碼，原則是出現(xiàn)次數(shù)越多的，則編碼越小，比如 空格出現(xiàn)了9 次， 編碼為0 ,其它依次類推
按照上面給各個(gè)字符規(guī)定的編碼，則我們在傳輸 "i like like like java do you like a java" 數(shù)據(jù)時(shí)，特殊編碼就是
image.png
- 字符的編碼都不能是其他字符編碼的前綴，符合此要求的編碼叫做前綴編碼， 即不能匹配到重復(fù)的編碼
3、方式三：赫夫曼編碼
- i like like like java do you like a java // 共40個(gè)字符(包括空格)
- d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 空格:9 // 各個(gè)字符對應(yīng)的個(gè)數(shù)
- 按照上面字符出現(xiàn)的次數(shù)構(gòu)建一顆赫夫曼樹, 次數(shù)作為權(quán)值
- 構(gòu)成赫夫曼樹的步驟：
1、從小到大進(jìn)行排序, 將每一個(gè)數(shù)據(jù)，每個(gè)數(shù)據(jù)都是一個(gè)節(jié)點(diǎn) ， 每個(gè)節(jié)點(diǎn)可以看成是一顆最簡單的二叉樹
2、取出根節(jié)點(diǎn)權(quán)值最小的兩顆二叉樹
3、組成一顆新的二叉樹, 該新的二叉樹的根節(jié)點(diǎn)的權(quán)值是前面兩顆二叉樹根節(jié)點(diǎn)權(quán)值的和
4、再將這顆新的二叉樹，以根節(jié)點(diǎn)的權(quán)值大小 再次排序
5、不斷重復(fù)以上四個(gè)步驟，直到數(shù)列中，所有的數(shù)據(jù)都被處理，就得到一顆赫夫曼樹
4、圖解：
- 說明：根據(jù)赫夫曼樹，給各個(gè)字符規(guī)定編碼
- 規(guī)則：向左的路徑為0，向右的路徑為1 ，編碼如下：
o: 1000 u: 10010 d: 100110 y: 100111
i: 101 a : 110 k: 1110 e: 1111 j: 0000
v: 0001 l: 001
空格 : 01- 按照上面的赫夫曼編碼，字符串 "i like like like java do you like a java" 字符串對應(yīng)的編碼為 (無損壓縮)：
1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110（長度：133）- 小結(jié)：
1.原來長度是 359 , 壓縮了 (359-133) / 359 = 62.9%
2.此編碼滿足前綴編碼, 即字符的編碼都不能是其他字符編碼的前綴。不會造成匹配的多義性- 圖：
image.png
5、注意事項(xiàng)：
這個(gè)赫夫曼樹根據(jù)排序方法不同，也可能不太一樣，這樣對應(yīng)的赫夫曼編碼也不完全一樣，但是wpl 是一樣的，都是最小的, 比如: 如果我們讓每次生成的新的二叉樹總是排在權(quán)值相同的二叉樹的最后一個(gè)，則生成的二叉樹為:
image.png
3、赫夫曼編碼實(shí)現(xiàn)數(shù)據(jù)壓縮和解壓縮代碼：參考步驟走
/**
* title: 赫夫曼編碼(字符串?dāng)?shù)據(jù)壓縮與解壓)
* @author 阿K
* 2021年1月10日 下午9:49:33
*/
public class HuffmanCode {
public static void main(String[] args) {
/* 第一大步驟測試 ：步驟一 至三，主要實(shí)現(xiàn) 通過字符串的字節(jié)數(shù)組構(gòu)建赫夫曼數(shù)*/
String content = "i like like like java do you like a java";
byte[] contentBytes = content.getBytes();
List<Node> nodes = getNodes(contentBytes);
// System.out.println("有效節(jié)點(diǎn)個(gè)數(shù)為：" + nodes.size());// 12 個(gè)有效節(jié)點(diǎn)
Node root = createHuffmanTree(nodes);
// System.out.println("前序遍歷當(dāng)前赫夫曼樹：");
perOrder(root);
/* 第二大步測試 ：步驟四 ，主要實(shí)現(xiàn) 通過赫夫曼樹生成對應(yīng)的赫夫曼編碼表 */
Map<Byte,String> codes = getCodes(root);
System.out.println(codes);
/* 第三大步測試 ：步驟五 主要實(shí)現(xiàn)，壓縮字符串，生成赫夫曼規(guī)則的字節(jié)數(shù)組 */
// System.out.println(Arrays.toString(zip(contentBytes, huffmanCodes)));;
byte[] huffmanBytes = huffmanZip(contentBytes);
System.out.println(Arrays.toString(huffmanBytes));
/* 第四大步測試 ：步驟六至 七 ，主要實(shí)現(xiàn)，解壓縮字符串，逆向操作 */
byte[] sourceStr = decode(huffmanCodes, huffmanBytes);
System.out.println(new String(sourceStr));
}
// 步驟七內(nèi)容-----------------------------------------------------
// 字符串解壓思路：
// 1.將huffmanCodeBytes [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
//先轉(zhuǎn)成赫夫曼編碼對應(yīng)的二進(jìn)制的字符串 "1010100010111..."
// 2.再將 此二進(jìn)制字符串 對照赫夫曼編碼表(反向) 轉(zhuǎn)成 最初字符串的二進(jìn)制字節(jié)數(shù)組
private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes) {
//1. 先得到 huffmanBytes 對應(yīng)的 二進(jìn)制的字符串 ， 形式 1010100010111...
StringBuilder stringBuilder = new StringBuilder();
// 將 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);
stringBuilder.append(byteToBitString(!flag, b));
}
// 2.把字符串按照指定的赫夫曼編碼進(jìn)行解碼
// 把赫夫曼編碼表進(jìn)行調(diào)換，因?yàn)榉聪虿樵?a->100 100->a
Map<String,Byte> map = new HashMap<>();
for(Map.Entry<Byte, String> entry:huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
// 3.創(chuàng)建用于存放 byte的集合
List<Byte> list = new ArrayList<>();
// 其中 i 在這里充當(dāng)索引，用于掃描 stringBuilder
for (int i = 0; i < stringBuilder.length();) {
int count = 1;// 微型計(jì)算器，用于記錄內(nèi)部的 while循環(huán),與 i相輔相成
boolean flag = true;// 用于控制 while
Byte b = null;// 記錄要存放的字節(jié)
while(flag) {
// 1010100010111...
// 遞增的取出 key 1 ,沒有再移動(dòng) 10 ，101 以此類推
String key = stringBuilder.substring(i,i+count);// i不動(dòng)，count移動(dòng)，指定匹配到一個(gè)字符(0或1)
b = map.get(key);
if(b == null) {
// 說明沒有匹配到
count++;
}else {
// 匹配到
flag = false;
}
}
list.add(b);
i += count; // i 直接移動(dòng)到 count(若 while 中 符合條件的次數(shù) count 達(dá)到則 退出，次數(shù) i也沒必要移動(dòng)，此處 i才是輔助)
}
// 4.以上循環(huán)結(jié)束后，說明已經(jīng)解碼結(jié)束
byte[] bytes = new byte[list.size()];
for (int i = 0; i < list.size(); i++) {
bytes[i] = list.get(i);
}
return bytes;
}
// 步驟六內(nèi)容-----------------------------------------------------
public static String byteToBitString(boolean flag,byte b) {
// 將 b 轉(zhuǎn)成 int
int temp = b;
// 若是正數(shù)，則需要補(bǔ)高位,轉(zhuǎn)換需要 int 類型
if(flag) {
// 按位與 256 1 0000 0000 | 0000 0001 => 1 0000 0001
temp |=256;
}
// 返回的是 temp 對應(yīng)的二進(jìn)制補(bǔ)碼
String str = Integer.toBinaryString(temp);
if(flag) {
return str.substring(str.length()-8);
}
// 若不是正數(shù)直接返回
return str;
}
// 封裝以下步驟(1-5)所有關(guān)于壓縮字符串的代碼
public static byte[] huffmanZip(byte[] bytes) {
List<Node> nodes = getNodes(bytes);
// 根據(jù) nodes 創(chuàng)建的赫夫曼樹
Node huffmanTreeRoot = createHuffmanTree(nodes);
// 對應(yīng)的赫夫曼編碼(根據(jù) 赫夫曼樹)
Map<Byte,String> huffmanCodes = getCodes(huffmanTreeRoot);
// 根據(jù)生成的赫夫曼編碼，壓縮得到壓縮后的赫夫曼編碼字節(jié)數(shù)組
return zip(bytes,huffmanCodes);
}
// 步驟五內(nèi)容-----------------------------------------------------
/**
* 將 原始數(shù)據(jù)(字符串)，通過赫夫曼編碼表，壓縮 成新的字節(jié)數(shù)組返回
*
* eg：huffmanCodeBytes[0] = 10101000(補(bǔ)碼) => byte [推導(dǎo) 10101000=> 10101000 - 1 => 10100111(反碼)=> 11011000= -88 ]
* @param bytes 原始數(shù)據(jù)(字符串)對用的字節(jié)數(shù)組
* @param huffmanCodes 原始數(shù)據(jù)生成的赫夫曼編碼表
* @return 返回壓縮處理后的字節(jié)數(shù)組
*/
private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes) {
// 用于記錄壓縮后的新字節(jié)數(shù)據(jù)(既 通過huffmanCodes 將 bytes 轉(zhuǎn)成字符串)
StringBuilder stringBuilder = new StringBuilder();
for(Byte b:bytes) {
stringBuilder.append(huffmanCodes.get(b));
}
//
// System.out.println(stringBuilder.toString());
// 計(jì)算 huffmanCodeBytes 的長度
// 以下推導(dǎo)出的公式 int len = (stringBuilder.length() + 7)/8
int len;
if(stringBuilder.length()%8==0) {
len = stringBuilder.length()/8;
}else {
len = stringBuilder.length()/8+1;
}
// 創(chuàng)建用于存儲壓縮后的 字節(jié)數(shù)組
byte[] huffmanCodeBytes = new byte[len];
int index = 0;// 記錄是第幾個(gè) byte
for (int i = 0; i < stringBuilder.length(); i+=8) {// 因?yàn)槊课?8 位對應(yīng)一個(gè) byte，所有步長 為8
String strByte;
if(i+8>stringBuilder.length()) {// 不夠8位( 若 i 是 1到7,說明它不夠)
strByte = stringBuilder.substring(i);
}else {
strByte = stringBuilder.substring(i,i+8);
}
// 將 strByte 轉(zhuǎn)成 一個(gè)byte，放入到huffmanCodeBytes
// 二進(jìn)制的補(bǔ)碼 ---》 反碼 ---》 原碼
huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}
// 步驟五內(nèi)容-----------------------------------------------------
// 步驟四內(nèi)容-----------------------------------------------------
// 步驟四：生成赫夫曼樹對應(yīng)的赫夫曼編碼
// 思路：1、將赫夫曼編碼表存放到 Map<Byte,String>
// eg：生成的赫夫曼編碼表{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
static Map<Byte,String> huffmanCodes = new HashMap<>();
// 思路：2、在生成赫夫曼編碼時(shí)，需要記錄路徑(拼接路徑),定義StringBuilder,用于存儲某葉子節(jié)點(diǎn)路徑
static StringBuilder huffmanRoute = new StringBuilder();
/**
* 根據(jù)傳入的 node 節(jié)點(diǎn)的所有葉子節(jié)點(diǎn)的赫夫曼編碼得到，并存入 huffmanCodes 哈希表中
* @param node 獲取編碼表的節(jié)點(diǎn)
* @param code 路徑：規(guī)定 左子節(jié)點(diǎn)為 0，右子節(jié)點(diǎn)為 1
* @param huffmanRoute 用于拼接的路徑
*/
private static void getCodes(Node node,String code,StringBuilder huffmanRoute) {
// 輔助、遞歸的時(shí)候不會改變原始路徑拼接
StringBuilder stringBuilder = new StringBuilder(huffmanRoute);
// 將 code 拼接到 stringBuilder
stringBuilder.append(code);
if(node!=null) {// 若為節(jié)點(diǎn)null，不處理
// 判斷當(dāng)前節(jié)點(diǎn)，是葉子節(jié)點(diǎn) 還是非葉子節(jié)點(diǎn)
if(node.data==null) {// 非葉子節(jié)點(diǎn)
// 向左遞歸
getCodes(node.left, "0", stringBuilder);
// 向右遞歸
getCodes(node.right, "1", stringBuilder);
}
else {// 說明是一個(gè)葉子節(jié)點(diǎn)
// 說明已經(jīng)找到某個(gè)葉子節(jié)點(diǎn)的最后
huffmanCodes.put(node.data, stringBuilder.toString());
}
}
}
// 重載 getCodes ，方便調(diào)用
public static Map<Byte, String> getCodes(Node root) {
if(root==null) {
return null;
}
// 處理 root 的左子樹
getCodes(root.left, "0", huffmanRoute);
// 處理 root 的右子樹
getCodes(root.right, "1", huffmanRoute);
return huffmanCodes;
}
// 步驟四內(nèi)容-----------------------------------------------------
// 步驟三：通過 節(jié)點(diǎn)集合，構(gòu)建出赫夫曼樹
public static Node createHuffmanTree(List<Node> nodes) {
// 循環(huán)四步驟，知道最終只有一個(gè) root節(jié)點(diǎn)
while (nodes.size() > 1) {
// 從小到大排序
Collections.sort(nodes);
// 取出第一顆最小的二叉樹（若是大到小，取第一顆最大）
Node leftNode = nodes.get(0);
// 取出第二顆最小的二叉樹（若是大到小，取第二顆最大）
Node rightNode = nodes.get(1);
// 構(gòu)建一顆新的二叉樹，為以上兩樹的根節(jié)點(diǎn)(此樹沒有data,只有權(quán)值)
Node parent = new Node(null, leftNode.weight + rightNode.weight);
parent.left = leftNode;
parent.right = rightNode;
// 將處理完畢后的兩顆二叉樹，從 nodes 集合中刪除
// 并讓 新構(gòu)建出的二叉樹，加入到 nodes 集合中，---循環(huán)中。。。
nodes.remove(leftNode);
nodes.remove(rightNode);
nodes.add(parent);
}
return nodes.get(0);
}
// 步驟二：將 字節(jié)數(shù)組 byte[] 轉(zhuǎn)為 節(jié)點(diǎn)集合 List，用于后面構(gòu)建赫夫曼樹
public static List<Node> getNodes(byte[] bytes) {
// 創(chuàng)建一個(gè)要返回的節(jié)點(diǎn)集合
List<Node> nodes = new ArrayList<Node>();
// 遍歷 bytes，統(tǒng)計(jì)每一個(gè)字節(jié)出現(xiàn)的次數(shù),用 map<Byte,Integer>接收
// key 為 Ascll 碼值，value 為出現(xiàn)的次數(shù)
Map<Byte, Integer> counts = new HashMap<>();
for (byte b : bytes) {
Integer count = counts.get(b);
if (count == null) {
// 當(dāng)前是第一次進(jìn)來，還沒有這個(gè)數(shù)的次數(shù)（初始化）
counts.put(b, 1);
} else {
counts.put(b, count + 1);
}
}
// 將每個(gè)鍵值對，以 Node 節(jié)點(diǎn)對象的方式存儲 到List集合中
for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
// 返回
return nodes;
}
// 調(diào)用節(jié)點(diǎn)自身的前序遍歷
public static void perOrder(Node root) {
if (root == null) {
System.out.println("抱歉，我TM無法遍歷沒有內(nèi)容的根節(jié)點(diǎn)");
} else {
root.perOrder();
}
}
}
// 步驟一：創(chuàng)建Node節(jié)點(diǎn)(數(shù)據(jù)，權(quán)值，排序)
class Node implements Comparable<Node> {
protected Byte data; // 存放數(shù)據(jù)(字符)本身，比如'a' => 97 ' ' => 32
protected int weight; // 權(quán)值, 表示字符出現(xiàn)的次數(shù)
protected Node left; // 左子樹(默認(rèn)null)
protected Node right; // 右子樹(默認(rèn)null)
@Override
public int compareTo(Node o) {
return this.weight - o.weight;
}
public Node(Byte data, int weight) {
super();
this.data = data;
this.weight = weight;
}
@Override
public String toString() {
return "Node [data=" + data + ", weight=" + weight + "]";
}
// 前序遍歷
public void perOrder() {
System.out.println(this);
if (this.left != null) {
this.left.perOrder();
}
if (this.right != null) {
this.right.perOrder();
}
}
}
4、赫夫曼編碼實(shí)現(xiàn)文件壓縮與解壓
package com.kk.datastructure.tree.availabletree;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.Map;
//import static com.kk.datastructure.tree.availabletree.HuffmanCode;
/**
* title: 赫夫曼實(shí)現(xiàn)文件壓縮，解壓
* @author 阿K
* 2021年1月16日 下午9:05:10
*/
public class HuffmanFileZipDemp {
public static void main(String[] args) {
String s1 = "J:\\caolaoshi.avi";
String s2 = "J:\\caolaoshi.zip";
String s3 = "J:\\caolaoshi(1).avi";
zipFile(s1, s2);
unzipFile(s2,s3);
}
/**
* 文件的解壓
* @param unzipFile
* @param dstFile
*/
public static void unzipFile(String unzipFile,String dstFile) {
// 定義流
FileOutputStream os = null;
FileInputStream is = null;
ObjectInputStream ois = null;
try {
// 初始化
is = new FileInputStream(unzipFile);
// 初始化對象輸入流 --- 用于讀入 赫夫曼表和源文件數(shù)組
ois = new ObjectInputStream(is);
byte[] huffmanBytes = (byte[])ois.readObject();
Map<Byte,String> huffmanCodes = (Map<Byte,String>)ois.readObject();
// 解碼
byte[] bytes = HuffmanCode.decode(huffmanCodes, huffmanBytes);
// 將bytes 數(shù)組寫入到目標(biāo)文件
os = new FileOutputStream(dstFile);
os.write(bytes);
} catch (Exception e) {
e.printStackTrace();
}finally {
try {
os.close();
ois.close();
is.close();
} catch (Exception e2) {
System.out.println(e2.getMessage());
}
}
}
/**
* 文件壓縮方法
* @param srcFile 準(zhǔn)備壓縮的源文件路徑
* @param dstFile 壓縮后輸出的文件李靜
*/
public static void zipFile(String srcFile, String dstFile) {
// 定義流，這里核心使用的是對象流
FileInputStream is = null;
FileOutputStream os = null;
ObjectOutputStream oos = null;
try {
// 初始化流
is = new FileInputStream(srcFile);
// 創(chuàng)建一個(gè)和源文件大小一致的 byte數(shù)組
byte[] b = new byte[is.available()];
// 將文件讀取到字節(jié)數(shù)組中
is.read(b);
// 對源文件字節(jié)數(shù)組進(jìn)行壓縮,得到赫夫曼編碼壓縮文件
byte[] huffmanBytes = HuffmanCode.huffmanZip(b);
// 初始化輸出流，用于輸出到指定路徑
os = new FileOutputStream(dstFile);
// 創(chuàng)建輸出的對象流，方便后續(xù)解壓，畢竟 byte 數(shù)組 就是一個(gè)對象
oos = new ObjectOutputStream(os);
oos.writeObject(huffmanBytes);
// 注意：編碼表也要輸入，后續(xù)要對照這個(gè)進(jìn)行解壓
oos.writeObject(HuffmanCode.huffmanCodes);
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
is.close();
oos.close();
os.close();
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
}
}
5、關(guān)于文件壓縮性能須知
1、如果文件本身就是經(jīng)過壓縮處理的，那么使用赫夫曼編碼再壓縮效率不會有明顯變化, 比如視頻,ppt 等等文件
2、赫夫曼編碼是按字節(jié)來處理的，因此可以處理所有的文件(二進(jìn)制文件、文本文件)
3、如果一個(gè)文件中的內(nèi)容，重復(fù)的數(shù)據(jù)不多，壓縮效果也不會很明顯
6、無聊的測試
image.png
