高級數據結構—赫(哈)夫曼樹及java代碼實現

我們經常會用到文件壓縮,壓縮之後文件會變小,便於傳輸,使用的時候又將其解壓出來。為什麼壓縮之後會變小,而且壓縮和解壓也不會出錯。赫夫曼編碼和赫夫曼樹了解一下。

赫夫曼樹:

它是一種的葉子結點帶有權重的特殊二叉樹,也叫最優二叉樹。既然出現最優兩個字肯定就不是隨便一個葉子結點帶有權重的二叉樹都叫做赫夫曼樹了。

赫夫曼樹中有一個很重要的概念就是帶權路徑,帶權路徑最小的才是赫夫曼樹。

樹的路徑長度是從根結點到每一個結點的長度之和,帶權路徑就是每一個結點的長度都乘以自己權重,記做WPL

假設有abcd數據,權重分別是7 5 2 4。下面構建出來的三棵帶權二叉樹。

A樹:WPL=7*2+5*2+2*2+4*2=36

B樹:WPL=7*3+5*3+2*1+4*2=46

C樹:WPL=7*1+5*2+2*3+4*3=35

顯然C樹的帶權是最小的。而且無構建出比它更小的了。所以C樹就是赫夫曼樹

我們從C樹發現了一個問題,就是要使得樹的帶權路徑最小,那麼權重越大的就應該離根結點越近。所以如果要構建一棵赫夫曼樹,首先一定要將數據按權重排序。這是不是就是之前提到的貪心算法,一定有排序,從局部最優到整體最優。

 

赫夫曼編碼:

我們都知道以前的地下黨發送電報。都是加密了發送,然後使用密碼本來解密。

我們還是發送上面的abcd

顯然計算機的世界都是01,假設我們用三位來表示上面的字符。也就相當於製作一個密碼本

a:000

b:001

c:010

d:011

那麼我要傳輸的就變成了000001010011,然後收到之後按照三位一分來解密就可以了。但是如果數據很多之後。我們可能就不能不用3位來表示了,可能是8位,10位之類了的,那麼這個二進制串的長度也相當可怕了。

再看赫夫曼樹,如果我們將上面的C圖的每一個左分支表示0,右分支表示1

 

那麼現在表示abcd就可以用每個結點長度路徑上的值來表示了

a:0

b:10

c:110

d:111

abcd就可以表示為010110111,就從剛才的00000101001112位縮減到了9位,如果數據量大,這個減少的位數是很可觀的。

但是又有一個問題了,這樣出來的編碼長度不等,其實很容易混淆,所以要設計這種長短不等的編碼,必須任意字符的編碼都不是另一個字符編碼的前綴,這種編碼稱做前綴編碼。顯然通過二叉樹這樣構造出來的編碼,每個葉子結點都不同的編碼。而這棵赫夫曼樹就是我們的密碼本。也就是說編碼於解碼都需要用同樣結構的赫夫曼樹。

解碼:

每次從根開始尋找,找到葉子結點為止,然後又從根開始尋找,比如010110111,

0走左邊,左邊第一個就是葉子結點,所以找到a

回到根繼續尋找,編碼串還剩下10110111,

1走右邊,0走左邊找到b110 ->c, 111->d

一般來說設要編碼的字符集{c1,c2,c3…},設置各個字符出現的頻率{w1,w2,w3…},以各字符作為葉子結點,以相應的頻率作為權重來構造赫夫曼樹。

 

赫夫曼樹的構建

以我們上面的a:7 b:5 c:4 d:2為例。

1.上面從樹的特點來看,首先我們需要按照權重從小到大排序,注意赫夫曼樹的構建是逆向構建的,就是說是從葉子結點往根結點構建。排序:d:2  c:4  b:5  a:7

2.取前面兩個權值最小結點作為新結點n1的兩個子結點,注意二叉樹的左小右大規則。新結點的權重為兩孩子權重之和,將操作過的結點從數據中移除,新結點放進去繼續操作:

n1的權重是 cd權重之和為6新的排序:b:5  n1:6  a:7

3.取出bn1構成新作為新結點n2的兩個子結點剩餘。 新的排序:a:7  n2:11

直到操作到最後兩個結點結束。

 

 

如果遇到操作的兩個結點在已有的數上面還沒有,那就另開一個子樹,等到操作這個新子樹的根結點的時候,再把這棵子樹直接移植過去,比如這個數據來構建a:3 b:24 c:6 d:20 e:34 f:4 g:12

排序:a:3  f:4  c:6  g:12  d:20  b:24  e:34

d:20 b:24 構造出來的子樹就是後面移植上去的

 

代碼實現:

現在就按照上面的邏輯,代碼實現赫夫曼樹的構建和編碼解碼,對比上面的第二個數據驗證結果

package com.nijunyang.algorithm.tree;
import java.util.*;
/**
* Description: 哈夫曼樹
* Created by nijunyang on 2020/4/28 21:43
*/
public class HuffmanTree {
private static final byte ZERO = 0;
private static final byte ONE = 1;
HuffmanNode root;
Map<Character, Integer> weightMap; //字符對應的權重
List<HuffmanNode> leavesList; // 葉子
Map<Character, String> leavesCodeMap; // 葉子結點的編碼
public HuffmanTree(Map<Character, Integer> weightMap) {
this.weightMap = weightMap;
this.leavesList = new ArrayList<>(weightMap.size());
this.leavesCodeMap = new HashMap<>(weightMap.size());
creatTree();
}
public static void main(String[] args) {
Map<Character, Integer> weightMap = new HashMap<>();
//a:3  f:4  c:6  g:12  d:20  b:24  e:34
weightMap.put('a', 3);
weightMap.put('b', 24);
weightMap.put('c', 6);
weightMap.put('d', 20);
weightMap.put('e', 34);
weightMap.put('f', 4);
weightMap.put('g', 12);
HuffmanTree huffmanTree = new HuffmanTree(weightMap);
//abcd: 1011001101000
String code = huffmanTree.encode("abcd");
System.out.println(code);
System.out.println("1011001101000".equals(code));
String msg = huffmanTree.decode(code);
System.out.println(msg);
}
/**
* 構造樹結構
*/
private void creatTree() {
PriorityQueue<HuffmanNode> priorityQueue = new PriorityQueue<>();
weightMap.forEach((k,v) -> {
HuffmanNode huffmanNode = new HuffmanNode(k, v);
priorityQueue.add(huffmanNode);
leavesList.add(huffmanNode);
});
int len = priorityQueue.size();//先把長度取出來,因為等下取數據隊列長度會變化
//HuffmanNode實現了Comparable接口,優先隊列會幫我們排序,我們只需要每次彈出兩個元素就可以了
for (int i = 0; i < len - 1; i++) {
HuffmanNode huffmanNode1 = priorityQueue.poll();
HuffmanNode huffmanNode2 = priorityQueue.poll();
int weight12 = huffmanNode1.weight + huffmanNode2.weight;
HuffmanNode parent12 = new HuffmanNode(null, weight12); //父結點不需要數據直接傳個null
parent12.left = huffmanNode1;  //建立父子關係,因為排好序的,所以1肯定是在左邊,2肯定是右邊
parent12.right = huffmanNode2;
huffmanNode1.parent = parent12;
huffmanNode2.parent = parent12;
priorityQueue.add(parent12);  //父結點入隊
        }
root = priorityQueue.poll(); //隊列裏面的最後一個即是我們的根結點
/**
* 遍歷葉子結點獲取葉子結點數據對應編碼存放起來,編碼時候直接拿出來用
*/
leavesList.forEach(e -> {
HuffmanNode current = e;
StringBuilder code = new StringBuilder();
do {
if (current.parent != null && current == current.parent.left) { // 說明當前點是左邊
code.append(ZERO); //左邊0
} else {
code.append(ONE);//左邊1
                }
current = current.parent;
}while (current.parent != null); //父結點null是根結點
code.reverse(); //因為我們是從葉子找回去的 ,所以最後需要將編碼反轉下
            leavesCodeMap.put(e.data, code.toString());
});
}
/**
* 編碼
*/
public String encode(String msg) {
char[] chars = msg.toCharArray();
StringBuilder code = new StringBuilder();
for (int i = 0; i < chars.length; i++) {
code.append(leavesCodeMap.get(chars[i]));
}
return code.toString();
}
/**
* 解碼
*/
public String decode(String code) {
char[] chars = code.toCharArray();
Queue<Byte> queue = new ArrayDeque();
for (int i = 0; i < chars.length; i++) {
queue.add(Byte.parseByte(String.valueOf(chars[i])));
}
HuffmanNode current = root;
StringBuilder sb = new StringBuilder();
while (!queue.isEmpty() ){
Byte aByte = queue.poll();
if (aByte == ZERO) {
current = current.left;
}
if (aByte == ONE) {
current = current.right;
}
if (current.right == null && current.left == null) {
sb.append(current.data);
current = root;
}
}
return sb.toString();
}
/**
* 結點 實現Comparable接口 方便使用優先隊列(PriorityQueue)排序
*/
private class HuffmanNode implements Comparable<HuffmanNode>{
Character data;        //字符
int weight;        //權重
        HuffmanNode left;
HuffmanNode right;
HuffmanNode parent;
@Override
public int compareTo(HuffmanNode o) {
return this.weight - o.weight;
}
public HuffmanNode(Character data, int weight) {
this.data = data;
this.weight = weight;
}
}
}