現代網路通訊時代,資料通訊傳輸時為了節省寶貴的儲存空間,以及縮短資訊傳遞的時間,我們希望能將這串資料以新的方式表示,讓它的容量能接近它真正承載的資訊量,而將不必要的冗餘碼去除。所以去除多餘的編碼,以最節省空間的方式表達特定的資訊,就是所有資料壓縮法的共通目的。
在數據壓縮的領域裡,Shannon Fano coding 是一種基於一組符號集及其符號出現機率:
1. 對於給定的符號,建立一組符號與符號的出現機率。
2. 依符號出現機率多寡進行排序,出現機率最多的符號排在最上面。
3. 將這個表格分為兩部分,依次序,符號出現機率比較多的上半部符號和下半部分開。
4. 給定上半部的符號一個二進位數字 0,下半部則給定 1。這個數字做為這些符號的新編碼
的第一碼。
5. 對兩部分的表格遞迴地重複實行步驟 3 和 4,也就是繼續分割表格並且給定數字,直到
分割到剩下單一符號為止。到此每一個符號都會有一個相對應的碼,就是它的新編碼。
舉例說明:
A.假設使用者輸入一組 5 個符號「AB C D E」和符號的出現機率分別為(0.17, 0.38, 0.16,
0.15, 0.14),要產生新的編碼。所有的符號以它們出現的機率排序再劃分成上下兩部
份。如下表,可在字母 A 與 C 之間劃定分割線,得到了上下兩部份,總出現機率分
別為 0.38+0.17=0.55, 0.16+0.15+0.14=0.45。這樣就在排序好的符號把上下兩部份的差
別降到最小。通過這樣的分割, A 與 B 同時擁有了一個以 0 為開頭的編碼, C,D,E
的編碼則為 1。接著,在 A,B 間建立新的分割線,這樣 A 就成為了編碼為 00,B 的
編碼 01。經過四次分割,得到了一個新的編碼。
符號 | 出現機率 | 編碼 |
B | 0.38 | 0 0 |
A | 0.17 | 0 1 |
C | 0.16 | 1 0 |
D | 0.15 | 1 1 0 |
E | 0.14 | 1 1 1 |
B. 新編碼為
符號 | 編碼 |
B | 0 0 |
A | 0 1 |
C | 1 0 |
D | 1 1 0 |
E | 1 1 1 |
1. 第一行:輸入符號之數量,一個範圍在 3~10 之間的整數。
2. 第二行:輸入所有符號之名稱(每個符號名稱的長度小於 10 個字元),以空格分開。
3. 第三行:輸入每個符號出現的機率(每個符號的機率>=0 且<=1。並且,所有符號的
機率加總<=1),以空格分開。
輸出每一個符號與編碼,格式是 符號:編碼輸入的機率出現問題(正常的機率:每個符號的機率>=0 且<=1。並且,所有符號的機率加總<=1),則輸出-1。
5 A B C D E 0.22 0.28 0.15 0.30 0.05
D:00 B:01 A:10 C:110 E:111
3 a1 a2 a3 0.1 0.88 0.02
a2:0 a1:10 a3:11
3 a1 a2 a3 0.1 0.9 0.2
-1
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |