若字串aaaaabbbbcccdde依霍夫曼法編碼，則「e」最少需要幾個位元？

C3正確答案

答案與詳解

正確答案

霍夫曼編碼依字元頻率建構二元樹，頻率越低編碼越長。統計頻率後逐步合併最小頻率節點，可推導出「e」位於樹的第 3 層，需 3 個位元。

e(1)與d(2)合併為節點ed(3)；ed(3)再與c(3)合併為ced(6)；同時a(5)與b(4)合併為ab(9)；最後ced(6)與ab(9)合併為根節點(15)。從根節點走到 e 需經過 3 個分支，故需 3 位元。

載入中…

步驟	當前節點與頻率	合併動作	產生新節點
初始	a(5), b(4), c(3), d(2), e(1)	無	無
1	a(5), b(4), c(3), e(1), d(2)	合併最小的 e(1) 與 d(2)	ed(3)
2	a(5), b(4), c(3), ed(3)	合併最小的 c(3) 與 ed(3)	ced(6)
3	a(5), b(4), ced(6)	合併最小的 a(5) 與 b(4)	ab(9)
4	ced(6), ab(9)	合併最後兩個節點	root(15)