# 霍夫曼編碼介紹
## 介紹

霍夫曼編碼是美國計算機科學家大衛．霍夫曼在1952年提出的一種無失真資料壓縮編碼（在保留完整資訊的前提下進行壓縮）。藉由根據字頻的大小選定不同編碼長度，來減少編碼總長的期望值，達到資料壓縮的目的。由於霍夫曼編碼是個二進制的編碼，所以字元集與編碼的對應可以用一個01-Trie來表達，也就是可以使用一個二元樹來表達。


> 本圖由[此網站](https://www.csfieldguide.org.nz/en/interactives/huffman-tree/)生成

上圖即是一個霍夫曼樹，基於文本"can you can a can with a cucumber"。首先，由觀察可以得知所有字元皆在樹的葉子上，這是因為要避免一個字元的編碼同時是另一個字元編碼的前綴，導致有多種解碼結果。此外，可以觀察到頻率較高的字元(如'空白'、'c')擁有更短的編碼，如此能夠有效地降低編碼的總長。

## 如何建立霍夫曼樹
以下將基於"to be or not to be"的文本進行建樹。
首先，統計各字元的出現頻率

' ':5次
'o':4次
't':3次
'b':2次
'e':2次
'r':1次
'n':1次

接著建立節點儲存字元與其出現次數，如下所示：


將最小的兩個節點合併至一個新的父節點，次數為兩個子節點的和。在這個例子，合併'r'與'n'，如下所示：


重複以上的步驟，直到生成一棵樹：
最後將向左的箭頭標0，向右標1，就完成了。

如果有仔細觀察步驟，會發現一顆霍夫曼樹可能因為有多個字頻相同的字元而有不唯一的建立方式，但是在不同的建立方式下編碼長度仍會是相同的。

## 參考資料
https://medium.com/@bhch3n/huffman-coding-%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%B7%A8%E7%A2%BC-3879df5ecddc

https://www.csfieldguide.org.nz/en/interactives/huffman-tree/

https://www.itread01.com/content/1546823004.html

https://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81

https://xken831.pixnet.net/blog/post/459581308-%E9%9C%8D%E5%A4%AB%E6%9B%BC%28huffman%29%E6%A8%B9-

https://ithelp.ithome.com.tw/articles/10208835