无失真资料压缩法之原理及演算法的介绍.docVIP

無失真資料壓縮法之原理及演算法的介紹 u910925 林名哲 國立清華大學電機系 摘要 這篇報告主要是對無失真資料壓縮的理論、原理、演算法做概略性的介紹，並且提出一些簡單的討論、可能的改進方法，以及我對資料壓縮的想法和感想。一開始會從資訊理論的角度切入壓縮方法的主要精神和發展模式，再將壓縮的一般過程做概略式的模組化。演算法上主要會分為最小冗餘法、字典法這兩個部分來分別介紹，並會提到最常見的壓縮演算法（如Huffman Coding，LZ77）。 介紹 壓縮向來是計算機科學領域的一門重要學問。在計算機科學的領域裡，我們將大量的資料經由適當的處理過後整理成有條理的資訊。資訊是我們收集和處理資料所希望得到的，也就是說，我們使用各種軟硬體承載大量的資料，最終目的是希望從中獲取有用的資訊。因此，一連串的資料當中真正包含的資訊有多少成了我們關切的問題，這也造成壓縮的必要。當我們在表達資料所用的編碼承載的資訊量比不上它佔有的空間時，為了節省寶貴的儲存空間，以及縮短資訊傳遞的時間，我們就希望能將這串資料以新的方式表示，讓它的容量能接近它真正承載的資訊量，而將不必要的冗餘碼去除。所以去除多餘的編碼，以最節省空間的方式表達特定的資訊，就是所有資料壓縮法的共通目的。 在計算機領域中使用的壓縮法，可以大略的粗分為失真和無失真兩種方式。失真壓縮法常應用在類比資料的壓縮上，藉由捨棄非必要的資料來獲取更大的壓縮率。因為使用數位的方式來表達類比的訊息，本來就有著先天上無法完美呈現的缺陷，所以適當的捨棄不必要的類比訊後是可接受的。這種壓縮方式廣泛應用在音訊和影像的壓縮處理，隨著最近多媒體在電腦上的普及重要性，也隨之提高。 然而有些資料卻是不可捨棄的，例如銀行的帳戶記錄，公司職員的人事資料，學生成績等等，這些資料不能有絲毫的更動。所以我們在對它進行重新編碼及壓縮時，必須確保爾後能以相對應的方式完整的還原本來的資料。這種方式稱為無失真的壓縮方式，可想而知它的壓縮率比不上失真的壓縮方式，而且必須更精細的去考慮冗餘資料和資訊承載量的問題。但無失真壓縮方式在實用性上不輸給失真壓縮，無論是網路上的資料傳輸，大型系統的備份等等，都可以看到這種技術的存在。無失真壓縮也是這篇報告主要要探討的領域。 I. 從資訊理論角度的概觀 l 計算資訊的含量 前面提到，壓縮的主要目的在去除多餘的編碼，以達到用等同於一串資料中資訊的含量的容量來儲存它的目的。然而“一串資料中資訊的含量”卻是一個抽象的觀念，就像是我們若把“10：2”看做一串資料，它可能表示“5”這個數字，也有可能表示“統一獅大勝兄弟象的比數”這個訊息。然而近代的資料壓縮技術是隨著資訊理論（Information Theory）的發展而開始的，而對於資訊的含量，在資訊理論中有一套公式化的計量方式，稱為entropy。 Entropy被定義為：-log2(資料出現的機率) 也就是，我們在考慮一筆特定的資料（可以想做是某個特定的符號）在一連串資料中所搭載的資訊含量時，可藉由計算它的entropy來判定。Entropy就類似它原本在熱學中的意義一樣，越高的entropy代表著越多的資訊承載量。為什麼entropy會這樣定義，是由幾個學理上的公設而來的，在這裡不多加詳述，但我們可以直觀地這麼想：當一個符號在一連串資料中出現越多次時，它包含的資料量越少。或是說，當一個符號一再在資料中出現時，我們若選擇使用較少的容量來表示這個符號，那我們就能節省比較多空間。也就是說，在重新對資料編碼時，出現越多次的資料選用長度較小的碼來表示，出現很少的資料則可以使用長度較長的碼，這樣我們能預期編碼後的資料量能比原本的少，而達壓縮的目的。後面我們會看到大多數的壓縮方式是採用和這種方法類似的精神。 Entropy為我們提供了一個估算資料含量的方式，而事實上，我們也可將它想做壓縮的理論下界。也就是說，我們使用各種壓縮法，在最理想的情況下能把資料壓縮到等同於它的entropy的容量。在實際的應用上，我們將會發現即便是最好的壓縮方式也只能最到盡量逼近entropy大小的境界，所以entropy是一個理論上能壓縮到的最小值。 l 壓縮法的模型 有了計算資料中資訊含量的方式，我們就知道接下來要討論的所有壓縮法的目標：去除資料中冗餘的代號，用最少的容量（最接近entropy）來表示一連串的資訊。接下來我們來看看如何達到這個目的。一般說來，資料壓縮包含輸入一連串的符號並且將它們轉成適當的編碼，有效的壓縮方法會使得重新編碼後的大小比原來的編碼小。而如何將一個或一組符號轉成特定的碼則必須參考一個模組（model）。模組簡單地說就是一組用來處理輸入資料並決定要將它轉成何種碼的數據資料或規則。一個壓縮程式使用模組來定義特定符號的出現率以做為編碼的依據。有了模組之後我們就可以