"主題:資料壓縮[@more@]一．前言
資料壓縮（data compression）在我們現今生活中是件相當頻繁的事情，壓縮過後的檔案會較易於傳輸，最常見的就是利用msn傳檔案、學校ICAN上傳作業、e-mail夾帶檔案等等，這些都與資料壓縮脫離不了關係。
資料壓縮為何被發明？因為早期的硬體設備的容量都很小，所以能儲存的資料也就跟著變小。但若要花更多金錢去升級硬體，對一般大眾又很不划算。所以，便產生出一種機制，那就是把資料作處理讓資料變小，來達到不用升級硬體也能儲存的資料量大增，這種機制便稱為資料壓縮。什麼是資料壓縮？在我們日常生活中其實就一直在壓縮資料，舉個最口語簡單好懂的例子，我們常在講電話的時候，都會“長話短說”這就是一種壓縮資料！把一長串的話，用幾句話來表達，這樣就充分發揮壓縮資料的精神了。資料為什麼可以壓縮？同樣一data有很多種表達方式，只是每一種表達方式不一樣，但是它們卻有相同的意義，但這些data常常含有一些不相關或者重複的敘述，一般稱為“data redundancy”(資料累贅，例如：編碼累贅)，這便是data可以壓縮的主要原因。 二．各類壓縮法簡述 １. 即時碼的產生（instantaneous code）看命名不難看出意思，意即，當我們一接收到一個代表某符號的編碼之後，我們就“即刻”可以解碼得到原來的符號，因此被稱為即時碼。比方說，有三種符號X,Y,Z分別代表０,10,11則當我們收到０時就可以馬上知道代表X，10表Y，11表Z，這就是所謂的即時碼。再來我們要以何種方式來產生一組即時碼呢？假設我們有四種符號，分別為0、10、110、111首先在解碼時只要一遇到位元“０”就為符號“０”，剩餘編成的位元串都必須以位元“１”開始。我們先以一個“１”當樹根，建一顆Tree ０ １ 葉片 ＼ ／ ０ １ 葉片 ＼ ／ １ 樹根再由樹根往各個樹葉前進，將經過的“０”或“１”串起來，這樣就可以分別得到不同的即時碼了。 ２. 霍夫曼編碼（Huffman Encoding）Huffman壓縮的過程大略為下：１. 先將所有符號依照出現的機率高低重新排列。２. 依次將出現機率最低的兩個符號結合成一個新的符號，而這個新符號稱為節點，而此節點內含之前兩個符號的機率和，此節點可再與其他未成節點的符號再度結合成新的節點，依此類推，最後可以得到一顆Tree。３. 最後就是找編碼了，由樹根出發，前進到每個葉片（符號）每遇到一個節點則左邊的分枝分配一個“０”而右邊的分枝分配一個“１”最後再將經過的路徑中遇到的“０”與“１”串起來就可以得到該符號的編碼了。 樹葉S1[0.5] S2[0.25] S3[0.125] S4[0.125]| | | | | | ０ | | | | | | | [0.25]----------1------- 節點 | 0 | 0 | | | [0.5]--------1------ 節點 | | [1.0]--------1------ 樹根最後得到的編碼方式為：S1=0，S2=10，S3=110，S4=111。 ３. Shannon-Fano壓縮法此法與Huffman只差在三步驟之第二步驟：（所以在此只寫出相異處）步驟2.依次將符號分割為機率和相同或接近的兩組符號。各組符號各合成一個節點，該節點內含該組符號的機率總合。往第一組分枝分配一個“０”，往第二組的分枝分配一個“１”。依此類推，一直一分為二，最終會得到一個樹狀結構，其中每個節點內含該節點之後的兩個節點機率值得總合。若依上面的例子，最終得到的結果與Huffman是相同的！不同的只是建立樹的演算法不同而已，Huffman方法是由上往下（樹葉往樹根），而Shannon-Fano方法剛好相反，它是由下往上的（樹根往樹葉）。當然實做上兩種壓縮法還是有些微的差異，但只差異影響不大就是了。 ４. Arithmetic壓縮法算數編碼主要是在於將一個訊息很有技巧的轉換成一個介於0和1之間的實數。若訊息越長，則代表該訊息的實數就會跟著變長，也就是說訊息的位元數也會跟著變多，相對的解壓縮時則利用一步一步逐一的還原壓縮碼所對應的訊息中的各個符號。其編碼演算法步驟為：１. lowç0.0 ; highç1.0;２. 讀入下一個符號，c;３. rangeçhigh-low;４. 查範圍表，另c的範圍為１<=r<=h; 設定highçlow+range*h ; lowçlow+range*l;５. 如果輸入符號還未完全編碼，則再回到第二步，否則繼續執行;６. print low;這演算法裡的範圍表，是編碼之前需要先完成的一項工作，舉個例子，“good＂這個訊息的機率分佈為：
| 符號 | 機率 | 範圍 |
| d | 0.25 | 0.0<=r<0.25 |
| g | 0.25 | 0.25<=r<0.5 |
| o | 0.5 | 0.5<=r<1.0 |
算數編碼的編碼過程是根據輸入符號將實數之可能範圍逐漸縮小。算數編碼看起來好像比Huffman編碼複雜，但是實際程式碼差不了多少。算數編碼的壓縮結果比Huffman編碼還要好，可是為什麼還是無法完全取代Huffman編碼？因為算數編碼不管在編碼或解碼時，皆需要用到乘除法的運算，因此速度比較慢。各類壓縮法，只列舉以上幾個。 三．探討Huffman編碼在之前大略講過Huffman編碼的演算法，以及建樹過程，那麼我們可以發現一個問題，雖然建立Huffman編碼樹的演算法雖然很簡單，但是我們也不希望每編碼一個符號就重做一次建立Huffman樹的工作。我先介紹一種adaptive coding（適應性編碼）此編碼不是只適用於Huffman編碼，原則上，大部分的編碼方法都可以在稍事調整後使用適應性編碼。Adaptive Huffman Coding:：當資料串流到達時，如果統計數字是要動態地收集及更新。程式碼大概如下：Initial_code();while not EOF //(end of file){get(c);encode(c);update_tree(c);}initial_code( )給每一個符號一些事先決定的編碼，不需要預先知道每一個符號的出現頻率。update_tree( )架構一個可調整的Huffman tree，基本上要完成兩件事情：1.將符號的出現頻率次數增加(包含任何新出現的符號)。2.變更Huffman Tree的架構。以下開始說明此update_tree( )：首先要介紹一個性質“sibling property”(兄弟性質)，一顆Huffman樹只是一顆在每個節點，包括樹葉與內節點，加上加權值得二元樹。除了樹根外，每一個節點都有一個兄弟節點與其共有一個父親節點。如果一棵樹的節點可以按照加權值從小排到大而且每個節點又與自己的兄弟相鄰的話，我們便稱這棵樹具有兄弟性質。定理：一棵二元樹是Huffman樹<=>遵守兄弟性質［Knuth 1985］
舉例子來講，加權值分別為，Ａ＝１、Ｂ＝２、Ｃ＝２、Ｄ＝２、Ｅ＝１０共五個節點所造的樹如下：
1.Ａ（１）＼ 5.（３）＼2.Ｂ（２）／ ＼ 7.（７）＼ 3.Ｃ（２）＼ ／ ＼ 6.（４）／ 9.（１７） 4.Ｄ（２）／ ／ 8.Ｅ（１０） ／ 此圖不難看出加權值為由小到大排列且兄弟節點都相鄰，此顆樹即為遵守兄弟性質的Huffman樹。此性質提供我們修改Huffman樹的方法與原則：只要我們保持住兄弟性質我們就可以確定Huffman樹經過修改後仍然是Huffman樹。修改、或更新一棵Huffman樹包括兩個重要的步驟。 第一個步驟是頻率的增加，這個很容易了解，例如，要增加某個符號的頻率，我們得從屬於該符號的樹葉開始，把它的頻率加一，然後往上找它的父親節點。依序的修改各個節點的加權值，這個程序一直在往上做到樹根的加權值也加一為止。我們依照上一個圖來舉個簡單的例子： 1.Ａ（２）＼ 5.（４）＼2.Ｂ（２）／ ＼ 7.（８）＼ 3.Ｃ（２）＼ ／ ＼ 6.（４）／ 9.（１８） 4.Ｄ（２）／ ／
8.Ｅ（１０） ／
修改的部分分別有１、５、７、９這幾個編號，１（A 之頻率）即代表要修改的頻率，之後依序修改５、７、９各個節點裡的加權值
第二個步驟要做的就是：如果增加加權值的動作使得兄弟性質不在滿足時我們得做調整的動作，否則它就不再是一棵Huffman樹了。
還是一樣我們取上一個圖形來舉例：
1.Ａ（３）＼ 5.（５）＼2.Ｂ（２）／ ＼ 7.（９）＼ 3.Ｃ（２）＼ ／ ＼ 6.（４）／ 9.
