香農-法諾編碼自頂向下(Shannon-Fano Algorithm_A top-down approach)

 

初始符號和計數：

A: 15

B: 7

C: 6

D: 6

E: 5

總計數和排序：

總計數：15 + 7 + 6 + 6 + 5 = 39

根據計數降序排序：A, B, C, D, E

左0右1

第一次分割：

尋找一個分割點，使得兩側的計數總和大致相等。

在這個例子中，A的計數是15，其他四個符號的總計數是24，所以分割點在A之後。

賦碼：A獲得編碼 '0'，剩餘符號獲得編碼 '1'。

組0: A(15)

組1: B(7), C(6), D(6), E(5)

對組0賦予碼'0'，對組1賦予碼'1'。

第二次分割，對組1中的符號進行進一步分割：

組10: B(7), C(6)

組11: D(6), E(5)

對組10賦予碼'10'，對組11賦予碼'11'。

第三次分割，繼續對剩餘的每組符號進行分割：

對於組10：

• 組100: B(7)
• 組101: C(6)

對於組11：

• 組110: D(6)
• 組111: E(5)

最終獲得每個符號的編碼：

• A: 0
• B: 100
• C: 101
• D: 110
• E: 111

每個符號最終都有一個唯一的編碼，並且由於編碼過程中沒有任何一個編碼是另一個編碼的前綴