簡(jiǎn)介
哈夫曼樹(shù)是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹(shù)姚糊，也稱(chēng)為最優(yōu)二叉樹(shù)。
定義：給定 n 個(gè)權(quán)值作為 n 個(gè)葉子節(jié)點(diǎn)浪默，構(gòu)造一顆二叉樹(shù)牡直，若樹(shù)的帶權(quán)路徑長(zhǎng)度達(dá)到最小，則這棵樹(shù)稱(chēng)為哈夫曼樹(shù)纳决。
路徑的長(zhǎng)度：從樹(shù)中的一個(gè)結(jié)點(diǎn)到另外一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成兩個(gè)結(jié)點(diǎn)的路徑碰逸，路徑上的分支數(shù)目稱(chēng)為路徑長(zhǎng)度。
樹(shù)的路徑長(zhǎng)度：從樹(shù)根到每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和阔加，所以我們說(shuō)完全二叉樹(shù)就是這種路徑長(zhǎng)度最短的二叉樹(shù)饵史。
樹(shù)的帶權(quán)路徑長(zhǎng)度：如果在樹(shù)的每個(gè)葉子節(jié)點(diǎn)上賦一個(gè)權(quán)值，那么熟的帶權(quán)路徑長(zhǎng)度就等于根節(jié)點(diǎn)到所有葉子節(jié)點(diǎn)的路徑長(zhǎng)度與葉子節(jié)點(diǎn)權(quán)值乘積的總和胜榔。
如何判斷一棵樹(shù)是否是最優(yōu)二叉樹(shù)胳喷？
帶權(quán)長(zhǎng)度分別為：
WPL1：7*2+5*2+2*2+4*2=36
WPL2：7*3+5*3+2*1+4*2=46
WPL3：7*1+5*2+2*3+4*3=35
第三棵樹(shù)的帶權(quán)路徑最短。所以第三棵就是我們要找的 最優(yōu)二叉樹(shù)（哈夫曼樹(shù)）夭织。
哈夫曼樹(shù)的構(gòu)建
依次取權(quán)重最小的節(jié)點(diǎn)放在樹(shù)的底部吭露，將最小的兩個(gè)連接構(gòu)成新的節(jié)點(diǎn)（新節(jié)點(diǎn)的權(quán)值是兩個(gè)最小節(jié)點(diǎn)權(quán)值之和），然后把新節(jié)點(diǎn)放回需要構(gòu)成的樹(shù)中繼續(xù)進(jìn)行排序尊惰，構(gòu)成哈夫曼樹(shù)讲竿，要存放的所有信息都在葉子節(jié)點(diǎn)上。
| a | b | c | d | e |
|---|---|---|---|---|
| 45 | 42 | 60 | 100 | 75 |
上表中的字母分別帶有權(quán)重弄屡，將其構(gòu)成哈弗曼樹(shù)题禀。
- 先對(duì)表中數(shù)據(jù)進(jìn)行排序
| d | e | c | a | b |
|---|---|---|---|---|
| 100 | 75 | 60 | 54 | 42 |
取出隊(duì)列中的兩個(gè)權(quán)重最小的節(jié)點(diǎn)作為樹(shù)的底部，按照左邊的子樹(shù)永遠(yuǎn)小于右邊的原則進(jìn)行構(gòu)造琢岩。并將新生成的節(jié)點(diǎn)放在隊(duì)列中進(jìn)行重新排序投剥。a=42，b=45担孔，新節(jié)點(diǎn)為 87江锨。
| d | e | c | |
|---|---|---|---|
| 100 | 87 | 75 | 60 |
然后將 87 加入隊(duì)列吃警，形成新的隊(duì)列，并進(jìn)行排序啄育。
| d | e | c | |
|---|---|---|---|
| 100 | 87 | 75 | 60 |
再按照之前的方法將隊(duì)列中最小的兩個(gè)樹(shù)作為樹(shù)的底部酌心，形成一個(gè)新節(jié)點(diǎn)。c=60挑豌，e=75安券，新節(jié)點(diǎn)為 135。
依次重復(fù)以上步驟就可以畫(huà)出該哈夫曼樹(shù)了氓英。
| d | ||
|---|---|---|
| 135 | 100 | 87 |
87 和 d = 100 構(gòu)成新節(jié)點(diǎn) 187侯勉。
| 322 | 135 |
Java 編碼
如上就是構(gòu)造哈夫曼的過(guò)程。接下來(lái)用 java 實(shí)現(xiàn)上面我畫(huà)的那棵哈夫曼樹(shù)铝阐。
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class HuffmanTreeDemo {
public static void main(String[] args) {
List<Node<String>> nodes = new ArrayList<>();
nodes.add(new Node<String>("a", 45));
nodes.add(new Node<String>("b", 42));
nodes.add(new Node<String>("c", 60));
nodes.add(new Node<String>("d", 100));
nodes.add(new Node<String>("e", 75));
Node<String> root = HuffmanTree.createTree(nodes);
HuffmanTree.levelDisplay(root);
}
static class Node<T> implements Comparable<Node<T>> {
public T data;
public int weight;
public Node<T> left;
public Node<T> right;
public Node(T data, int weight) {
super();
this.data = data;
this.weight = weight;
}
@Override
public String toString() {
return "data:" + this.data + ",weight:" + this.weight + "; ";
}
@Override
public int compareTo(Node<T> o) {
if (o.weight > this.weight) {
return 1;
} else if (o.weight < this.weight) {
return -1;
}
return 0;
}
}
static class HuffmanTree<T> {
//參數(shù)是多個(gè)節(jié)點(diǎn)組成的隊(duì)列
public static <T> Node<T> createTree(List<Node<T>> nodes) {
while (nodes.size() > 1) {// 只剩一個(gè)節(jié)點(diǎn)時(shí)址貌，退出循環(huán)
Collections.sort(nodes);
// 使用sort方法對(duì)nodes進(jìn)行排序，CompareTo方法實(shí)現(xiàn)的是降序序列
Node<T> left = nodes.get(nodes.size() - 1);// 取兩個(gè)最小的節(jié)點(diǎn)
Node<T> right = nodes.get(nodes.size() - 2);
// 生成新節(jié)點(diǎn)徘键，新節(jié)點(diǎn)的權(quán)重 = 兩個(gè)權(quán)重最小的節(jié)點(diǎn)的和
Node<T> parent = new Node<T>(null, left.weight + right.weight);
parent.left = left;
parent.right = right;
nodes.remove(left);
nodes.remove(right);
nodes.add(parent);
}
return nodes.get(0);
}
public static void levelDisplay(Node root) {
List<Node> list = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
System.out.println(node.toString());
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
}
}
運(yùn)行結(jié)果
data:null,weight:322;
data:null,weight:135;
data:null,weight:187;
data:c,weight:60;
data:e,weight:75;
data:null,weight:87;
data:d,weight:100;
data:b,weight:42;
data:a,weight:45;
哈夫曼編碼
哈夫曼編碼 (Huffman Coding) 是一種編碼方法练对，哈夫曼編碼是可變字長(zhǎng)編碼(VLC)的一種。
哈夫曼編碼使用變長(zhǎng)編碼表對(duì)源符號(hào)（如文件中的一個(gè)字母）進(jìn)行編碼吹害，其中變長(zhǎng)編碼表是通過(guò)一種評(píng)估來(lái)源符號(hào)出現(xiàn)機(jī)率的方法得到的螟凭，出現(xiàn)機(jī)率高的字母使用較短的編碼，反之出現(xiàn)機(jī)率低的則使用較長(zhǎng)的編碼它呀，這便使編碼之后的字符串的平均長(zhǎng)度螺男、期望值降低，從而達(dá)到無(wú)損壓縮數(shù)據(jù)的目的钟些。
哈夫曼編碼的具體步驟如下：
1）將信源符號(hào)的概率按減小的順序排隊(duì)烟号。
2）把兩個(gè)最小的概率相加蹲姐，并繼續(xù)這一步驟脖苏，始終將較高的概率分支放在右邊渊抽，直到最后變成概率 １。
3）畫(huà)出由概率 １ 處到每個(gè)信源符號(hào)的路徑篙耗，順序記下沿路徑的 ０ 和 １，所得就是該符號(hào)的哈夫曼碼字宪赶。
4）將每對(duì)組合的左邊一個(gè)指定為 0宗弯，右邊一個(gè)指定為 1（或相反）。
根據(jù)哈夫曼樹(shù)可以解決報(bào)文編碼的問(wèn)題搂妻。假設(shè)需要把一個(gè)字符串蒙保，如 “abcdabcaba” 進(jìn)行編碼，將它轉(zhuǎn)換為唯一的二進(jìn)制碼欲主，但是要求轉(zhuǎn)換出來(lái)的二進(jìn)制碼的長(zhǎng)度最小邓厕。
假設(shè)每個(gè)字符在字符串出現(xiàn)頻率為 w逝嚎，其編碼長(zhǎng)度為 L，編碼字符 n 個(gè)详恼，則編碼后二進(jìn)制的總長(zhǎng)度為 W1L1+W2L2+…+WnLn补君，這恰好是哈夫曼樹(shù)的處理原則。因此可以采用哈夫曼的構(gòu)造原理進(jìn)行二進(jìn)制編碼昧互，從而使得電文長(zhǎng)度最短挽铁。
對(duì)于 “abcdabcaba”，共有 a敞掘、b叽掘、c、d 四個(gè)字符玖雁，出現(xiàn)次數(shù)分別為 4够掠、3、2茄菊、1疯潭，相當(dāng)于它們的權(quán)值，將 a面殖、b竖哩、c、d 以出現(xiàn)次數(shù)為權(quán)值構(gòu)造哈夫曼樹(shù)脊僚，得到下左圖的結(jié)果相叁。
從哈夫曼樹(shù)根節(jié)點(diǎn)開(kāi)始，對(duì)左子樹(shù)分配代碼 “0”辽幌，對(duì)右子樹(shù)分配 “1”增淹，一直到達(dá)葉子節(jié)點(diǎn)。然后乌企，將從樹(shù)根沿著每條路徑到達(dá)葉子節(jié)點(diǎn)的代碼排列起來(lái)虑润，便得到每個(gè)葉子節(jié)點(diǎn)的哈夫曼編碼，如下右圖加酵。
從圖中可以看出拳喻，a、b猪腕、c冗澈、d 對(duì)應(yīng)的編碼分別為 0、10陋葡、110亚亲、111，然后將字符串 “abcdabcaba” 轉(zhuǎn)換為對(duì)應(yīng)的二進(jìn)制碼就是0101101110101100100，長(zhǎng)度僅為 19捌归。這也就是最短二進(jìn)制編碼颊亮，也稱(chēng)為哈夫曼編碼。
