原理:頻率高的字元用較短的編碼,頻率低的用較長的編碼。
建樹步驟:
1. 計算每個字元的頻率
2. 建立葉節點,放入優先佇列(最小堆)
3. 取出兩個最小節點合併,新節點頻率 = 兩子頻率之和
4. 重複直到只剩一個節點(根)
編碼:從根到葉,左邊 = 0,右邊 = 1
特性:前綴碼(Prefix-free),無歧義解碼