资料压缩期末报告.docVIP

資料壓縮期末報告 Arithmetic coding ﹝算數編碼﹞ 組員張凱鈞 盧祈安 Arithmetic coding﹝算數編碼﹞ 4.1前言、介紹 算數編碼在用來做少量數字集合的編碼特別有用，尤其是對於二元的資料，或者是字元出現機率相差極大的資料。 上一章節有談到霍夫曼編碼的方法，他是以資料出現的機率跟他所含的資料量，建進一個二元樹中，得到即時碼。 舉例來說： 有三個可能出現的資料，機率分別為P(a1)=0.95, P(a2)=0.02, P(a3)=0.03, 建出來的樹如下： 編碼分別為 以連續二字元為一組，根據其機率編出來的碼為 他是以該字串產生的機率，算出該資料的資料量，然後根據資料量的輕重，放入Huffman tree 來做編碼。較常出現的字串編碼較短，較少出現的機率就給長一點的編碼，如此一來可以有效的壓縮資料。只是如果字串的長度愈來愈長時所需的儲存空間就會愈來愈大，以上頭的兩個字串來說就需要9個儲存空間，如果說一字串長度為m，而時，就會需要有的空間需求，這麼大的空間就是一個問題，以平常的資料來算所需的空間量就會過大了，因此就需要另外的一解編方法─算數編碼(Arithmetic coding)而算數編碼的思維比較不同，他是以該字碼出現的機率，將所得資訊分別定在[0,1)區間定下標籤(tag)，利用數字在那個區間出現的唯一性，用連續在同一區間內編碼或者解碼(sequence to be encoded or decoded)，只要輸出代表那個數字所在的標籤，就能夠依照出現機率，找出連續的字串所代表的範圍值。而所得到編碼，只需要一個存浮點數的空間即可存入，這就不太會像霍夫曼編碼一樣需要大量空間來儲存。 4.2算數編碼的介紹 4.2.1如何使用算數編碼 將編碼依照步驟列於下面： 首先將所有字元出現的機率列出來 A = {a1, a2, a3} P (a1) = 0.7 P (a2) = 0.1 P (a3) = 0.2 Fig4-1-1 fig4-1-2 將有可能出現的symbol，依照出現的機率分布對應到 [0~1) 之間(fig4-1-1) 將欲編碼之字串逐字帶入，使要編碼的symbol連續對應到它的區間假設(假設第一個要編碼的symbol為a1----參考(fig4-1-2)將他的區間SPAN開，將有可能出現的symbol依照機率分佈於新區間中 依序將所有的symbol丟入，不斷的SPAN，最後的出的區間即是此串code所屬於的區間(參考下圖)。 它的編碼順序為a1a2a3…最後的區間為0.5460~0.5600這範圍值之間，因此在這範圍之內的字串都能解碼出所要的字串原義。 以下以一個實例說明 編碼BILL GATE這個字串，他出現的機率分布如下： 依照BILL GATE這個順序編碼會得到以下結果 用文字表格表示計算如下 New character Low value high value B 0.2 0.3 I 0.25 0.26 L 0.256 0.258 L 0.2572 0.2576 ^(space) 0.2572 0.25724 G 0.257216 0.25722 A 0.2572164 0.2572168 T 00.2572168 E 0.257216772 0.257216776 S 0.257216775 0.257216776 以上是標籤的產生及編碼方法，不過在書上還說到另一個標籤的範圍可能太大，使用中間點(midpoint)代表這區間的方法，而其數學式如下： 假設，將符號對應到實數，則 由以上的結每一個都會擁有唯一的值(unique value)，這部份在後會說明。 舉例子來說： 假設一個普通的骰子其數字{1,2,3,4,5,6}出現的機率各為六分之一，用上一數學式來求標籤X=2時， 如果是求X= 5時， 可從各自求出的值會一開始所定的標籤值都不同，這就是使用中間點來求出所在範圍值的不同。 以下表可看出各標籤值 Outcome Tag 1 2 0.25 3 4 5 0.75 6 4.2.2算數解碼 解碼的方式要逆運算，反解回去，他的做法就是以最後的出的編碼串對應屬於該字元的區間，開始反解回去，這裡會說明兩種不同的解碼方法，其中第一種是書上的解碼方式，主要是以編碼的同方法來換算回去原始的字串，以下來介紹解碼的方式。 方法一： 假設一編碼過的標籤值為0.772352，以代表upper bound，代表lower bound，k表示現在正在解第幾個解碼值其數值及機率如下： 一開始將範圍定在之間，然