建構方法

Ternary Huffman code

用

$0,1,2$ 來編 codeword，首先檢查要編碼的 letter 個數

• if letter 個數: even

  第一次挑 probability 最小的兩個 letter 來 merge

• if letter 個數: odd

  第一次挑三個 probability 最小的 letter 來 merge

接著每次都次挑三個來 merge

∴ 一棵 Ternary Huffman tree 中最多只會出現一個 internal node 具 2 children

*編出來的 code 對應的 code tree 為 ternary tree

特性

Optimal variable length code 的條件

1. 如果有兩個 letter a, b，a 出現的機率比 b 高，則 a 的 code length 比 b 小（用比較短的 code 來編比較常出現的字）
2. 最不常出現的兩個 letter，其 code length 相同（同為 maximal code length）
3. opt code 對應的 tree 中，所有 internal node 都有兩個點
4. $\begin{array}{c}{\sum }_{\forall i:externalnode}{2}^{-𝑙𝑖}=1\hfill \\ \hfill where𝑙𝑖:externalnodei\mathrm{的}length\end{array}$

可參考下方「判斷是否為 Huffman Code 」的題目

---

• Huffman Code 不一定唯一

如果有具相同 probability 的 element，根據 merge 的順序不同，會得到不同的 code tree，因此編出來的 Code 也不同

• Huffman Tree 非 BST，node 大小不需按照順序

因為 Huffman Coding 的重點在於 compression，而不是 search

判斷是否為 Huffman Code

CLRS 題目

---

Reference

NYCU Lecture Notes
Balanced Ternary Huffman encoding