第四題 資料傳輸編碼

問題描述

       現代網路通訊時代，資料通訊傳輸時為了節省寶貴的儲存空間，以及縮短資訊傳遞的時間，我們希望能將這串資料以新的方式表示，讓它的容量能接近它真正承載的資訊量，而將不必要的冗餘碼去除。所以去除多餘的編碼，以最節省空間的方式表達特定的資訊，就是所有資料壓縮法的共通目的。
       在數據壓縮的領域裡，Shannon Fano coding 是一種基於一組符號集及其符號出現機率
  1. 對於給定的符號，建立一組符號與符號的出現機率。
  2. 依符號出現機率多寡進行排序，出現機率最多的符號排在最上面。
  3. 將這個表格分為兩部分，依次序，符號出現機率比較多的上半部符號和下半部分開。
  4. 給定上半部的符號一個二進位數字 0，下半部則給定 1。這個數字做為這些符號的新編碼的第一碼。
  5. 對兩部分的表格遞迴地重複實行步驟 3 和 4，也就是繼續分割表格並且給定數字，直到分割到剩下單一符號為止。到此每一個符號都會有一個相對應的碼，就是它的新編碼。舉例說明：
    1. 假設使用者輸入一組 5 個符號「A B 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。經過四次分割，得到了一個新的編碼。

      2. 符號 出現機率 編碼
      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

    2. 新編碼為
      3. 符號 編碼
      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