無失真資料壓縮法之原理及演算法的介紹

masonchung

壓縮演算法介紹(轉載)

) n5 ?7 }* j' j- X

無失真資料壓縮法之原理及演算法的介紹
+ Z* d$ `) q: `! I6 c. j) G
: R5 y5 W1 a* J7 u" Qu910925 林名哲 國立清華大學電機系

摘要
5 N5 b4 l: V; K- P
這篇報告主要是對無失真資料壓縮的理論、原理、演算法做概略性的介紹，並且提出一些簡單的討論、可能的改進方法，以及我對資料壓縮的想法和感想。一開始會從資訊理論的角度切入壓縮方法的主要精神和發展模式，再將壓縮的一般過程做概略式的模組化。演算法上主要會分為最小冗餘法、字典法這兩個部分來分別介紹，並會提到最常見的壓縮演算法（如Huffman Coding，LZ77）。
" D9 b) ]4 p: @: u
4 X& L, E( q- T( p介紹

3 R; c- _  @* ?& ?( v/ L6 Z+ E5 U壓縮向來是計算機科學領域的一門重要學問。在計算機科學的領域裡，我們將大量的資料經由適當的處理過後整理成有條理的資訊。資訊是我們收集和處理資料所希望得到的，也就是說，我們使用各種軟硬體承載大量的資料，最終目的是希望從中獲取有用的資訊。因此，一連串的資料當中真正包含的資訊有多少成了我們關切的問題，這也造成壓縮的必要。當我們在表達資料所用的編碼承載的資訊量比不上它佔有的空間時，為了節省寶貴的儲存空間，以及縮短資訊傳遞的時間，我們就希望能將這串資料以新的方式表示，讓它的容量能接近它真正承載的資訊量，而將不必要的冗餘碼去除。所以去除多餘的編碼，以最節省空間的方式表達特定的資訊，就是所有資料壓縮法的共通目的。

在計算機領域中使用的壓縮法，可以大略的粗分為失真和無失真兩種方式。失真壓縮法常應用在類比資料的壓縮上，藉由捨棄非必要的資料來獲取更大的壓縮率。因為使用數位的方式來表達類比的訊息，本來就有著先天上無法完美呈現的缺陷，所以適當的捨棄不必要的類比訊後是可接受的。這種壓縮方式廣泛應用在音訊和影像的壓縮處理，隨著最近多媒體在電腦上的普及重要性，也隨之提高。
/ u/ y9 P: `* G. N8 J
然而有些資料卻是不可捨棄的，例如銀行的帳戶記錄，公司職員的人事資料，學生成績等等，這些資料不能有絲毫的更動。所以我們在對它進行重新編碼及壓縮時，必須確保爾後能以相對應的方式完整的還原本來的資料。這種方式稱為無失真的壓縮方式，可想而知它的壓縮率比不上失真的壓縮方式，而且必須更精細的去考慮冗餘資料和資訊承載量的問題。但無失真壓縮方式在實用性上不輸給失真壓縮，無論是網路上的資料傳輸，大型系統的備份等等，都可以看到這種技術的存在。無失真壓縮也是這篇報告主要要探討的領域。
3 M$ r  |- J8 P6 _4 e% R5 z
I.                 從資訊理論角度的概觀
5 Q8 }' i/ ~& R* g& W' A" L  R6 p
l    計算資訊的含量

+ B0 T* L4 J( f; \! _6 M: \前面提到，壓縮的主要目的在去除多餘的編碼，以達到用等同於一串資料中資訊的含量的容量來儲存它的目的。然而“一串資料中資訊的含量”卻是一個抽象的觀念，就像是我們若把“10：2”看做一串資料，它可能表示“5”這個數字，也有可能表示“統一獅大勝兄弟象的比數”這個訊息。然而近代的資料壓縮技術是隨著資訊理論（Information Theory）的發展而開始的，而對於資訊的含量，在資訊理論中有一套公式化的計量方式，稱為entropy。

Entropy被定義為：-log2(資料出現的機率)
; S. x$ N* h; j) A& M/ w. q8 G
; I- N1 ?2 ?1 U# k& J: V6 ]  V也就是，我們在考慮一筆特定的資料（可以想做是某個特定的符號）在一連串資料中所搭載的資訊含量時，可藉由計算它的entropy來判定。Entropy就類似它原本在熱學中的意義一樣，越高的entropy代表著越多的資訊承載量。為什麼entropy會這樣定義，是由幾個學理上的公設而來的，在這裡不多加詳述，但我們可以直觀地這麼想：當一個符號在一連串資料中出現越多次時，它包含的資料量越少。或是說，當一個符號一再在資料中出現時，我們若選擇使用較少的容量來表示這個符號，那我們就能節省比較多空間。也就是說，在重新對資料編碼時，出現越多次的資料選用長度較小的碼來表示，出現很少的資料則可以使用長度較長的碼，這樣我們能預期編碼後的資料量能比原本的少，而達壓縮的目的。後面我們會看到大多數的壓縮方式是採用和這種方法類似的精神。
; ?  \3 ?5 U. ]* n% o
Entropy為我們提供了一個估算資料含量的方式，而事實上，我們也可將它想做壓縮的理論下界。也就是說，我們使用各種壓縮法，在最理想的情況下能把資料壓縮到等同於它的entropy的容量。在實際的應用上，我們將會發現即便是最好的壓縮方式也只能最到盡量逼近entropy大小的境界，所以entropy是一個理論上能壓縮到的最小值。

' c- B* t% D0 b( @8 Ol    壓縮法的模型

有了計算資料中資訊含量的方式，我們就知道接下來要討論的所有壓縮法的目標：去除資料中冗餘的代號，用最少的容量（最接近entropy）來表示一連串的資訊。接下來我們來看看如何達到這個目的。一般說來，資料壓縮包含輸入一連串的符號並且將它們轉成適當的編碼，有效的壓縮方法會使得重新編碼後的大小比原來的編碼小。而如何將一個或一組符號轉成特定的碼則必須參考一個模組（model）。模組簡單地說就是一組用來處理輸入資料並決定要將它轉成何種碼的數據資料或規則。一個壓縮程式使用模組來定義特定符號的出現率以做為編碼的依據。有了模組之後我們就可以開始用編碼器（encoder）來將資料重新編碼。在前面我們講壓縮時都是以“編碼”這個字眼來說的，那是由於不同的演算法在編碼方式上有很大的差異，所以我們一般以coding這個字眼來講壓縮的方式（e.g., Huffman coding）但這不代表編碼就是整個壓縮過程的全部，稍後我們會強調選擇模組和編碼在決定壓縮效率上有同等重要的地位。藉由前面所說的我們可以歸結出一個壓縮過程的模型：

輸入資料－＞參考模組－＞編碼－＞輸出資料
; v: t# o  r, t8 N* }# E
* M& z: p$ G' i+ y) |/ k' |即使是不同的壓縮方式，以程序的角度來看仍然不脫離這個模型。
& n* E8 Y# x/ i( s$ `5 B
' @* V) w3 }1 nl    選擇模組

" K' L( o4 T5 }6 Y3 D如果我們將資料壓縮法比喻為一輛汽車，那編碼的方式可說是汽車的輪胎，而模組就是這台汽車的引擎了。由這裡我們可以看出選擇模組甚至比使用適當的編碼方式還重要。甚至我們在計算資料的entropy時，不同的模組也可能造成entropy的差異，這是因為不同的模組使用的統計方式不一樣，造成“資料出現的機率”也不同的。舉個簡單的例子來說，我們在統計一篇英文文章中各字母出現的機率時，如果只考慮個別字母出現的機率，那‘u’這個字母出現的機率可能只有百分之一，如果我們在統計某個字母是否出現時順便去檢查它的前一個字母，那‘u’這個字母在‘q’之後出現的機率可能就高達百分之九十五。再考慮這兩個機率個別的entropy值，我們可以見到使用不同的統計模組對資料壓縮後的大小可能會造成顯著的不同。因此一個好的壓縮方法除了簡潔的編碼方式以外，如何建構一個適當的模組是更重要的。假使今天有兩個人同時以Huffman coding的演算法來寫一個壓縮程式，雖然它們編碼的方式是相同的，但老練的程式設計師也許會選用一個會參考前面幾個符號來計算出現機率的模組，使得最後的壓縮率大為提昇。這就好像兩個人穿著同樣牌子的運動鞋，跑得快的人是因為它的腳比較有力，而不是鞋子不同所造成的。因此模組是壓縮過程中重要的一環。
  W5 l* a& e* O8 N0 ~& A: B$ b
% Y$ B/ F: ~) y* a: d0 u( Zl    編碼
' q5 }/ b2 t! d* O8 X3 \
一但我們經由資訊理論能估計出一個符號所包含資訊的容量之後，接下來就是要把這個符號重新編碼，使得它能切合真正所包含的資訊量。所以，在對資料重新編碼的時候，我們會希望新的碼的長度能盡量接近理論值entropy。我們回頭看一下一般最常用的資訊編碼方式：像是ASCII碼或是EBCDIC碼。無疑地在減少冗贅資料上這兩種編碼方式是不好的，因為在一串訊息中每個符號出現的機率是不同的，將所有符號都以同樣的長度來編碼，顯然的會造成有些資料使用太多的位元，有些資料又用的太少，相較之下形成空間的浪費。從上面的討論中似乎強烈暗示著如果要達到較好的壓縮效果，我們對不同的符號必須使用不同長度的碼來表示。確實，變換長度的編碼方式是許多壓縮演算法使用的手段，我們將在稍後一一介紹。


  X. d9 ?8 @  _
# u2 w+ L! z9 M6 A, mII.                最小冗餘法
! `! [1 l+ T/ ~9 x: `. Z
/ v. m  O" @% Xl     介紹
! }, d' j: O- z. M( b: V* h) v
最小冗餘法（Minimum Redundancy Coding）是跟隨資訊理論發展之後隨之出現的演算法。顯然的它們是由資訊理論裡對資訊含量的定義下手所直接產生出來的方法，最主要的手段就是前述的變動長度編碼，資訊含量就少的符號以較短的資料量來編碼，而且每個碼之間必須獨立不能相混淆。這裡我們介紹兩種常見的演算法：Shannon-Fano演算法和Huffman演算法。值得一提的是有些人可能會把Huffman演算法歸類到統計法裡面去，但我看的資料中統計法主要是強調不同統計方式的演算法，也就是產生模組的差異，所以不把Huffman算在裡面。
# y* H$ n$ k5 \# A7 ]( G
l    Shannon-Fano Algorithm

! r+ q+ y( Y7 T1 W這套演算法是由Claude Shannon和Robert Fano兩個人所提出來的。可說是第一個最小冗餘法的代表。這個演算法的程序如下：

1.     對於給定的符號，建立一個包含此符號出現頻率（或次數）的表格。
' m. x9 c4 d$ ^5 g  Q  O$ N5 t  O
2.     對此符號和次數相對應的表格依次數多寡進行排序，次數出現最多的符號排在最前面。

& P. X9 A) L. ]! s3.     將這個表格分為兩部分，也就是依次序，符號出現次數比較多的前半部符號和後半部分開。

+ Y# X' q4 D5 Z$ s) m4.     給定前半部的符號一個二元數字0，後半部則給定1。這個數字做為這些符號的新編碼的第一碼。
' }: F/ d: l1 Y' a! P
5.     對兩部分的表格遞迴地重複實行步驟3和4，也就是繼續分割表格並且給定數字，直到分割到剩下單一符號為止。到此每一個符號都會有一個相對應的碼，就是它的新編碼。
, L9 Z6 z( O) m5 M6 ^$ b
我們簡單的計算一下這個演算法能壓縮資料的程度。設有一筆資料經統計後含有15個A、7個B、6個C、6個D和5個E，那藉由重新編碼後，A的碼變成00，而B、C、D、E則個別是01、10、110、和111。重新計算壓縮後的資料量，我們知道新的編碼使用89個bits來表示這串資料，而如果我們之前以ASCII碼來表示的話，這39個字元需要花費312個bits，可以看出有顯著的壓縮成果。
! v* ^- h# `; Y5 `
4 M1 C' }. m# G# E. Q) Sl    Huffman Algorithm

Huffman演算法是MIT的David Huffman發明的。這個方法是當初他為了不想考研究所的期末考而著手挑戰的難題，而他想出的這個方法也成為最廣為人知的壓縮法之一。Huffman法和Shannon-Fano法有不少相近的性質，同樣都是獨一編碼和變動長度。然而它們有一個顯著的不同：Shannon-Fano在建構解碼樹時是以由上往下的方式，然而Huffman法卻反之，是由最底層的葉部開始建構起。Huffman演算法如下：

1.     統計每個符號的出現機率，建立數個節點，每個節點包含一個符號和它的出現機率。
# M5 v0 I: c( Y
2.     將節點依機率大小排序好。

3.     將機率最小的兩個節點放在一起，並且產生一個父節點以做為一顆樹，父節點的權重相當於兩個子節點的數字合。
2 z. B/ Z/ c4 V4 x% g# Q' Z
4.     將父節點視為新的節點排入原本的節點中考慮，原本的兩個子節點則不再考慮。
- i! X  x5 c  i- w5 O/ J3 U$ ^3 a
5.     原本的兩個子節點中一個指定二進位1的數字，一個指定0的數字。
8 T. }7 @8 r' ]$ Z
6.     重複2到5的步驟，直到只剩下一個節點可以考慮，這個節點就是整顆編碼樹的根節點。
& f) W. d- c+ Y4 y7 W2 {
藉由以上的程序我們可以建構一顆編碼樹，其中每個樹葉節點都是我們資料中出現的符號，而從樹根走訪至樹葉所會經過的節點中指定的數字就是那個樹葉上的符號所用的編碼。我們重新看一下上一個例子經由Huffman法編碼後，五個字母的字碼分別變為0、100、101、110、111，而總共所花費的空間是87bits，比Shannon-Fano法要少一點。事實上在實際的使用上，Huffman法的表現總是比Shannon-Fano法好一點。而且Huffman法有一個很好的特色：就是前序獨一的性質。我們看看例子裡由Huffman法所編出來的碼，如果是0就一定是A，因為接下來的碼中沒有以0開頭的，所以我們在解碼的時候只要循序讀入個別的位元，藉著走訪編/解碼樹就能到原本的符號，非常的方便。所以Huffman法是一個相當優秀的壓縮編碼。
1 e3 t9 y: R3 D1 C% T3 F' i
III.             字典法

l     介紹

字典法是和最小冗餘法完全不同的編碼方式。字典法不像最小冗餘法基於一種理論的基礎，它提供了直觀易懂的壓縮原理，也就是建立對照目錄的概念。例如我們如果要講某一個單字，可以拿一本共同的字典，然後講說是第幾頁的哪一個字，這樣也可以表示那個單字。簡單的說，字典法就是在壓縮過程中產生一個對照的字典，然後後面出現的符號就去比對前面建立的字典，如果有同樣在字典裡有的符號出現，就以索引的方式來表示它，以此達到壓縮的目的。顯然字典法的效率好壞和它字典建構的方式以及字典大小有很大的關係（就是壓縮法的好壞和模組的關係）。下面我要介紹的是最有名的LZ77法。
- r+ `: z; Z3 @- z) d4 Z
. h% W* I/ e5 ~# r  bl     LZ77 Algorithm

LZ77是由Ziv和Lempel在1977年發表的論文中提出的。它的特點是概念十分的簡單，亦能達到不錯的壓縮效果。它也是使用如前述的一邊讀資料一邊建立字典檔，然後新加入的資料比對前面建立的字典檔的方式。LZ77演算法中主要的資料結構有一個sliding window和一個look-ahead buffer。一開始sliding window中是空的，而look-ahead buffer中遇到的資料會先存起來，隨著看到的資料越來越多，sliding window中可以比對的“單字”也變多了。只要接下來在look-ahead buffer中看到sliding window中出現過的字串，就會把它以（在視窗中的位移位置，字串的字元數，字串之後第一個字元）這種方式存起來，就成了壓縮過的形式。就這樣一直比對到檔案結束，就可以完成編碼的動作。
% J; A3 \" |1 x. y0 H% S


( G6 E  B! K  |3 h$ f0 e結論
$ C! i) {4 N  \- i% Q0 _
資料壓縮是計算機科學領域中的一門重要學問，它是由資訊理論裡提出的一些原理所發展出來的，如今可以應用到非常廣泛的範圍上。我覺得像是冗餘碼的壓縮方式，在一開始看到的時候會覺得十分神奇，因為不是直覺就能想到的壓縮方法。不過在了解他背後的理論架構之後，就會知道這套方法是依循理論理所當然的架構出來的。這讓我想到數學上的研究雖然抽象，但常常是為所有實際利用開了先河，就像是線性代數是很抽象的概念，但是在工程數學上卻能得到很好的應用。我在找各種資料以前也有試著去想一些壓縮的方法，但怎麼想還是只能想到類似字典法的方式，畢竟它和人的直觀思考是比較接近的。不過在看了許多人提出的壓縮法後，會覺得無失真的壓縮實在是個被研究的蠻透徹的學問，理論和實際應用兼備了，感覺起來我也無法再做多少創新。不過我們也許可以用電機領域的角度來思考它，將快速的無失真資料壓縮製作在硬體上，也是一種很好的應用。但這同時也要考慮到一些系統上的考量，應該是蠻有挑戰性的課題，不過我覺得這可能也有人做過了。總之藉由這次報告找的資料不但滿足我對壓縮到底是如何達成的好奇心，也讓我對資訊科學上理論與實際的結合有更深一層的體認。

% C; f; z) s5 H! _3 B3 ~  K& w* @

參考資料

[1] The data compression book, 2nd edition, Mark Nelson, M&T Books, 1996.
- e6 E6 D) O: @/ m& a% _* ~
: t2 i' }5 ]& U; Q[2] Compression and coding algorithms, Alistair Moffat, Andrew Turpin, Kluwer Academic Publishers, 2002.

4 p% o- q# I% [: j0 O2 S+ V# G* A[3] Data compression: techniques and applications hardware and software considerations, Gilbert Held, John Wiley & Sons, 1983.

[4] Mastering algorithms with C, Kyle Loudon, Oreilly & Associates, 1999.

tommywgt

如果我沒記錯的話arithmatic coding是目前被証明能省少最多Redundancy 的方法. 不過從編碼理論上, arithmatic coding離optimal solution似乎還有一段距離.

值得一提的是arithmatic coding是IBM的專利哦, 要收錢的...

masonchung

Arithmatic coding 又分為 fixed length arithmatic coding 和 content adaptive binary arithmatic coding
9 J! @+ i5 R; y前者適合Audio encoding 後者適合 Video encoding

windflowerz

偶最近也在做压缩算法哦，ZLIB就是结合了LZ77和HUFFMAN CODING.其实字典算法还有一种LZW，TIF就是基于这种压缩算法，个人感觉非常简单，因为我最怕数学的东西。

. W" x- e. Y! n3 e4 e( I2 m但是我觉得这篇文章写得不是很好，感觉上很专业，但是很多东西都没有写清楚。比如无损压缩一般是用来压缩文字资料，而有损压缩一般用于音乐和图像的压缩；HUFFMAN CODING是用来寻找最小二叉树的最优算法；LZ77的核心还在于它有两个重要参数，当前项如果前面已经存在过，那么和相对距离是多少，还有就是有多少字符是相同的，如果还没有存在过，那么就直接显示原来的一个字符。
% x: {6 r" f1 r) g" ]1 R
( P+ B7 Q9 ?- D, W& S9 C我觉得下面这两篇文章讲的非常好，都是中文的。ZLIB算法有免费的库还有RFC规范，但真正分析起来很难。

http://www.pconline.com.cn/pcedu/empolder/gj/vc/0403/325402.html
( f" B/ N+ u0 j
http://www.pubcms.com/demo/tech/web/000069.asp

t8810012

It is good material for me. I am studying the related document about this field. Thank you.