阿摩線上測驗
15.若以霍夫曼編碼(Huffman Coding)編碼字串，其中出現次數分別為：
A / 5 , B / 12 , C / 33, D / 19, E / 40, F / 41
請問B的編碼為何?
(A) 11
(B) 011
(C) 0100
(D) 0101
答案：登入後查看
統計： A(2), B(8), C(14), D(56), E(0) #2330609
統計： A(2), B(8), C(14), D(56), E(0) #2330609
詳解 (共 3 筆)
hchungw
#6433562
答案是 (D) 0101。
簡要說明：
-
建立權重序列
-
A 5, B 12, C 33, D 19, E 40, F 41
-
-
依霍夫曼演算法自下而上合併最小兩節點
合併步驟 被合併節點 (權重) 合併後權重 ① A (5) + B (12) → * 17 ② 17 + D (19) → * 36 ③ C (33) + 36 → * 69 ④ E (40) + F (41) → * 81 ⑤ 69 + 81 → * 150 ㅤㅤ -
由根節點向下標 0 / 1 產生碼字
-
左子樹標 0，右子樹標 1
-
路徑：
-
F：11
-
E：10
-
C：00
-
D：011
-
A：0100
-
B：0101
-
-
因此 B 的編碼為 0101。
from collections import Counter
import heapq
import heapq
class Node:
"""霍夫曼樹節點"""
def __init__(self, char, freq):
self.char = char # 字元；中繼節點為 None
self.freq = freq # 權重（出現次數）
self.left = None # 左子
self.right = None # 右子
"""霍夫曼樹節點"""
def __init__(self, char, freq):
self.char = char # 字元；中繼節點為 None
self.freq = freq # 權重（出現次數）
self.left = None # 左子
self.right = None # 右子
# 供 heapq 排序用（最小權重在前）
def __lt__(self, other):
return self.freq < other.freq
def __lt__(self, other):
return self.freq < other.freq
def build_huffman_tree(freq_map):
"""由 {字元: 次數} 建立霍夫曼樹，回傳根節點"""
heap = [Node(ch, freq) for ch, freq in freq_map.items()]
heapq.heapify(heap)
while len(heap) > 1:
n1 = heapq.heappop(heap) # 最小權重
n2 = heapq.heappop(heap) # 第二小權重
parent = Node(None, n1.freq + n2.freq)
parent.left, parent.right = n1, n2
heapq.heappush(heap, parent)
n1 = heapq.heappop(heap) # 最小權重
n2 = heapq.heappop(heap) # 第二小權重
parent = Node(None, n1.freq + n2.freq)
parent.left, parent.right = n1, n2
heapq.heappush(heap, parent)
return heap[0] # 樹根
def generate_codes(node, prefix="", codes=None):
"""遞迴走訪樹，收集每個字元的霍夫曼碼"""
if codes is None:
codes = {}
if node.char is not None: # 葉子
codes[node.char] = prefix or "0" # 特例：只有一個字元時給 '0'
else:
generate_codes(node.left, prefix + "0", codes)
generate_codes(node.right, prefix + "1", codes)
return codes
if __name__ == "__main__":
# 題目給定的字元頻率
freq = {"A": 5, "B": 12, "C": 33, "D": 19, "E": 40, "F": 41}
# 1. 建樹
root = build_huffman_tree(freq)
root = build_huffman_tree(freq)
# 2. 產生碼字
codes = generate_codes(root)
codes = generate_codes(root)
# 3. 列印結果
for ch in sorted(codes):
print(f"{ch}: {codes[ch]}")
for ch in sorted(codes):
print(f"{ch}: {codes[ch]}")
# 驗證題目：B 的編碼
print("\nB 的霍夫曼碼 =", codes["B"])
print("\nB 的霍夫曼碼 =", codes["B"])
ㅤㅤ
ㅤㅤ
0
0
空条承太郎
#5662893
彩色圖解，請用。
0
0
