l040: 資料傳輸編碼(109-4)
標籤 : 萊恩盃
通過比率 : 1人/2人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-11-01 00:32

內容

       現代網路通訊時代,資料通訊傳輸時為了節省寶貴的儲存空間,以及縮短資訊傳遞的時間,我們希望能將這串資料以新的方式表示,讓它的容量能接近它真正承載的資訊量,而將不必要的冗餘碼去除。所以去除多餘的編碼,以最節省空間的方式表達特定的資訊,就是所有資料壓縮法的共通目的。
       在數據壓縮的領域裡,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。經過四次分割,得到了一個新的編碼。

符號出現機率編碼
B0.38 0 0
A0.170 1
C0.161 0
D0.151 1 0
E0.141 1 1


B. 新編碼為

符號編碼
B0 0
A0 1
C1 0
D1 1 0
E1 1 1



輸入說明

1. 第一行:輸入符號之數量,一個範圍在 3~10 之間的整數。
2. 第二行:輸入所有符號之名稱(每個符號名稱的長度小於 10 個字元),以空格分開。
3. 第三行:輸入每個符號出現的機率(每個符號的機率>=0 且<=1。並且,所有符號的
機率加總<=1),以空格分開。

輸出說明

輸出每一個符號與編碼,格式是 符號:編碼輸入的機率出現問題(正常的機率:每個符號的機率>=0 且<=1。並且,所有符號的機率加總<=1),則輸出-1。

範例輸入 #1
5
A B C D E
0.22 0.28 0.15 0.30 0.05
範例輸出 #1
D:00
B:01
A:10
C:110
E:111
範例輸入 #2
3
a1 a2 a3
0.1 0.88 0.02
範例輸出 #2
a2:0
a1:10
a3:11
範例輸入 #3
3
a1 a2 a3
0.1 0.9 0.2
範例輸出 #3
-1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (16%): 1.0s , <1K
公開 測資點#1 (16%): 1.0s , <1K
公開 測資點#2 (17%): 1.0s , <1K
公開 測資點#3 (17%): 1.0s , <1K
公開 測資點#4 (17%): 1.0s , <1K
公開 測資點#5 (17%): 1.0s , <1K
提示 :
標籤:
萊恩盃
出處:
南台科技大學資工系 109-04 [管理者: zero(管理員) ]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」