漫畫：“哈夫曼編碼” 是什麼鬼？

在上一期，我們介紹了一種特殊的數據結構 “哈夫曼樹”，也被稱為最優二叉樹。沒看過的小夥伴可以點擊下方鏈接：

漫畫：什麼是 “哈夫曼樹” ？

那麼，這種數據結構究竟有什麼用呢？我們今天就來揭曉答案。

計算機系統是如何存儲信息的呢？

計算機不是人，它不認識中文和英文，更不認識圖片和視頻，它唯一“認識”的就是0（低電平）和1（高電平）。

因此，我們在計算機上看到的一切文字、圖像、音頻、視頻，底層都是用二進制來存儲和傳輸的。

從狹義上來講，把人類能看懂的各種信息，轉換成計算機能夠識別的二進制形式，被稱為編碼。

編碼的方式可以有很多種，我們大家最熟悉的編碼方式就屬ASCII碼了。

在ASCII碼當中，把每一個字符表示成特定的8位二進制數，比如：

顯然，ASCII碼是一種等長編碼，也就是任何字符的編碼長度都相等。

為什麼這麼說呢？讓我們來看一個例子：

假如一段信息當中，只有A，B，C，D，E，F這6個字符，如果使用等長編碼，我們可以把每一個字符都設計成長度為3的二進制編碼：

如此一來，給定一段信息 “ABEFCDAED”，就可以編碼成二進制的 “000 001 100 101 010 011 000 100 011”，編碼總長度是27。

但是，這樣的編碼方式是最優的設計嗎？如果我們讓不同的字符對應不同長度的編碼，結果會怎樣呢？比如：

如此一來，給定的信息 “ABEFCDAED”，就可以編碼成二進制的 “0 00 10 11 01 1 0 10 1”，編碼的總長度只有14。

哈夫曼編碼(Huffman Coding)，同樣是由麻省理工學院的哈夫曼博所發明，這種編碼方式實現了兩個重要目標：

1.任何一個字符編碼，都不是其他字符編碼的前綴。

2.信息編碼的總長度最小。

哈夫曼編碼的生成過程是什麼樣子呢？讓我們看看下面的例子：

假如一段信息裡只有A，B，C，D，E，F這6個字符，他們出現的次數依次是2次，3次，7次，9次，18次，25次，如何設計對應的編碼呢？

我們不妨把這6個字符當做6個葉子結點，把字符出現次數當做結點的權重，以此來生成一顆哈夫曼樹：

這樣做的意義是什麼呢？

哈夫曼樹的每一個結點包括左、右兩個分支，二進制的每一位有0、1兩種狀態，我們可以把這兩者對應起來，結點的左分支當做0，結點的右分支當做1，會產生什麼樣的結果？

這樣一來，從哈夫曼樹的根結點到每一個葉子結點的路徑，都可以等價為一段二進制編碼：

上述過程藉助哈夫曼樹所生成的二進制編碼，就是哈夫曼編碼。

現在，我們面臨兩個關鍵的問題：

首先，這樣生成的編碼有沒有前綴問題帶來的歧義呢？答案是沒有歧義。

因為每一個字符對應的都是哈夫曼樹的葉子結點，從根結點到這些葉子結點的路徑並沒有包含關係，最終得到的二進制編碼自然也不會是彼此的前綴。

其次，這樣生成的編碼能保證總長度最小嗎？答案是可以保證。

哈夫曼樹的重要特性，就是所有葉子結點的（權重 X 路徑長度）之和最小。

放在信息編碼的場景下，葉子結點的權重對應字符出現的頻次，結點的路徑長度對應字符的編碼長度。

所有字符的（頻次 X 編碼長度）之和最小，自然就說明總的編碼長度最小。

<code>
private
 Node root;

private
 Node[] nodes;



 

public
 
void
 
createHuffmanTree
(
int
[] weights)
 
{

 

Queue nodeQueue = 
new
 PriorityQueue 
<>();

    nodes = 
new
 Node[weights.length];



 

for
(
int
 i=
0
; inew Node(weights[i]);

        nodeQueue.add(nodes[i]);

}



 

while
 (nodeQueue.size() > 
1
) {

 

Node left = nodeQueue.poll();

Node right = nodeQueue.poll();

 

Node parent = 
new
 Node(left.weight + right.weight, left, right);

        nodeQueue.add(parent);

}

    root = nodeQueue.poll();

}



 

public
 String 
convertHuffmanCode
(
int
 index)
 
{

return
 nodes[index].code;

}



 

public
 
void
 
encode
(Node node, String code)
{

if
(node == 
null
){

return
;

}

    node.code = code;

    encode(node.lChild, node.code+
"0"
);

    encode(node.rChild, node.code+
"1"
);

}



public
 
static 
 
class
 
Node
 
implements
 
Comparable
<
Node
>
{

int
 weight;

 

String code;

Node lChild;

Node rChild;



public
 
Node
(
int
 weight)
 
{

this
.weight = weight;

}



public
 
Node
(
int
 weight, Node lChild, Node rChild)
 
{

this
.weight = weight;

this
.lChild = lChild;

this
.rChild = rChild;

}



 

public
 
int
 
compareTo 
(Node o)
 
{

return
 
new
 Integer(
this
.weight).compareTo(
new
 Integer(o.weight));

}

}



public
 
static
 
void
 
main
(String[] args)
 
{

char
[] chars = {
'A'
,
'B'
,
'C'
,
'D'
,
'E'
,
'F'
};

int
[] weights = {
2
,
3
,
7
,
9
,
18
, 
25
};

HuffmanCode huffmanCode = 
new
 HuffmanCode();

    huffmanCode.createHuffmanTree(weights);

    huffmanCode.encode(huffmanCode.root, 
""
);

for
(
int
 i=
0
; i":" + huffmanCode.convertHuffmanCode(i));

}

}/<code>

這段代碼中，Node類增加了一個新字段code，用於記錄結點所對應的二進制編碼。

當哈夫曼樹構建之後，就可以通過遞歸的方式，從根結點向下，填充每一個結點的code值。