霍夫曼演算法（Huffman Algorithm）編碼步驟
- 計算頻率：計算每個符號出現的頻率。
- 構建霍夫曼樹：將所有符號按照頻率從小到大排列，然後構建霍夫曼樹。
- 分配碼字：根據霍夫曼樹分配每個符號的霍夫曼碼。
- 編碼訊息：使用霍夫曼碼編碼訊息。
- 計算總位元數：計算編碼後訊息的總位元數。
步驟 1：計算頻率
訊息 "AABCDBCACCFEDEFAC" 中各符號的出現次數如下：
- A: 5
- B: 2
- C: 4
- D: 2
- E: 2
- F: 2
步驟 2：構建霍夫曼樹
- 將每個符號當作一個節點，並按照頻率構建一個最小堆：
- [(A, 5), (B, 2), (C, 4), (D, 2), (E, 2), (F, 2)]
- 依次取出兩個最小頻率的節點合併成一個新的節點，將新的節點重新插入堆中，直到所有節點合併成一棵樹。
具體過程如下：
- 合併 (B, 2) 和 (D, 2)，得到新節點 (BD, 4)
- 合併 (E, 2) 和 (F, 2)，得到新節點 (EF, 4)
- 合併 (C, 4) 和 (BD, 4)，得到新節點 (CBD, 8)
- 合併 (A, 5) 和 (EF, 4)，得到新節點 (AEF, 9)
- 最後合併 (CBD, 8) 和 (AEF, 9)，得到根節點 (CBD|AEF, 17)
步驟 3：分配碼字
根據霍夫曼樹分配碼字（左分支為0，右分支為1）：
- A: 10
- B: 000
- C: 01
- D: 001
- E: 110
- F: 111
步驟 4：編碼訊息
將訊息 "AABCDBCACCFEDEFAC" 編碼：
- A: 10
- A: 10
- B: 000
- C: 01
- D: 001
- B: 000
- C: 01
- A: 10
- C: 01
- C: 01
- F: 111
- E: 110
- D: 001
- E: 110
- F: 111
- A: 10
- C: 01
編碼後的訊息：
1010000010010000101001101001101110110111110
步驟 5：計算總位元數
各符號編碼長度如下：
- A: 2 bits
- B: 3 bits
- C: 2 bits
- D: 3 bits
- E: 3 bits
- F: 3 bits
計算總位元數：
A (5) * 2 bits = 10 bits
B (2) * 3 bits = 6 bits
C (4) * 2 bits = 8 bits
D (2) * 3 bits = 6 bits
E (2) * 3 bits = 6 bits
F (2) * 3 bits = 6 bits
總位元數 = 10 + 6 + 8 + 6 + 6 + 6 = 42 bits
最終結果
-
各符號的霍夫曼碼：
- A: 10
- B: 000
- C: 01
- D: 001
- E: 110
- F: 111
-
編碼後的訊息：
1010100000101000101001101001101110110111110
-
總位元數：
阿摩線上測驗
登入