# B7 X' | F/ `1 o x/ a1. 對於給定的符號,建立一個包含此符號出現頻率(或次數)的表格。 ) _* r! B& T& s) x2 g/ G ( W2 |, v7 N) F2. 對此符號和次數相對應的表格依次數多寡進行排序,次數出現最多的符號排在最前面。5 [# M; d5 `+ o; p% T
3 l8 F) c' k1 G4 W4 X% U) T) T3. 將這個表格分為兩部分,也就是依次序,符號出現次數比較多的前半部符號和後半部分開。9 v- L; P1 u0 C6 N$ A
( H, J4 x$ G$ q, E/ Q# h; k9 i( U" h4. 給定前半部的符號一個二元數字0,後半部則給定1。這個數字做為這些符號的新編碼的第一碼。3 l4 o+ P1 n0 E
+ F+ ]! ]! y9 m+ A5. 對兩部分的表格遞迴地重複實行步驟3和4,也就是繼續分割表格並且給定數字,直到分割到剩下單一符號為止。到此每一個符號都會有一個相對應的碼,就是它的新編碼。 0 l0 E* V' {! q% i/ L9 l: g , ~$ B: L: x" o- G$ @# S我們簡單的計算一下這個演算法能壓縮資料的程度。設有一筆資料經統計後含有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,可以看出有顯著的壓縮成果。 / C5 H0 q! D: d$ v ? / N1 s. g- H9 f3 zl Huffman Algorithm ' S7 s4 v. b4 R% R8 j. O2 C# _ C3 O; [7 G8 t, F7 x% M& J5 \
Huffman演算法是MIT的David Huffman發明的。這個方法是當初他為了不想考研究所的期末考而著手挑戰的難題,而他想出的這個方法也成為最廣為人知的壓縮法之一。Huffman法和Shannon-Fano法有不少相近的性質,同樣都是獨一編碼和變動長度。然而它們有一個顯著的不同:Shannon-Fano在建構解碼樹時是以由上往下的方式,然而Huffman法卻反之,是由最底層的葉部開始建構起。Huffman演算法如下: 7 U+ R, G- D) ?, V2 H. G 9 P3 [7 t' G1 j1. 統計每個符號的出現機率,建立數個節點,每個節點包含一個符號和它的出現機率。 - f1 f8 A4 p; p) J; [% h* p0 [* J6 S# j
2. 將節點依機率大小排序好。3 Y% o7 S6 h! D7 t1 p7 |
% N9 v8 w2 e9 J' c2 f% p- y
3. 將機率最小的兩個節點放在一起,並且產生一個父節點以做為一顆樹,父節點的權重相當於兩個子節點的數字合。 ; y9 G! m1 |! x8 G" n3 m8 h, g9 a. w V
4. 將父節點視為新的節點排入原本的節點中考慮,原本的兩個子節點則不再考慮。 ( L. D$ a8 q6 P% d3 ~/ y! y1 t. c; ~3 z+ u# F7 I1 o8 k
5. 原本的兩個子節點中一個指定二進位1的數字,一個指定0的數字。7 r) O' R# V1 Q" b) {1 @1 w/ f
$ |0 H) O; R8 a! ]! ~
6. 重複2到5的步驟,直到只剩下一個節點可以考慮,這個節點就是整顆編碼樹的根節點。 " x* u0 h. N7 d/ ~1 S# W L& `0 t2 p {4 H+ x# M, S' V9 ~3 M! ]
藉由以上的程序我們可以建構一顆編碼樹,其中每個樹葉節點都是我們資料中出現的符號,而從樹根走訪至樹葉所會經過的節點中指定的數字就是那個樹葉上的符號所用的編碼。我們重新看一下上一個例子經由Huffman法編碼後,五個字母的字碼分別變為0、100、101、110、111,而總共所花費的空間是87bits,比Shannon-Fano法要少一點。事實上在實際的使用上,Huffman法的表現總是比Shannon-Fano法好一點。而且Huffman法有一個很好的特色:就是前序獨一的性質。我們看看例子裡由Huffman法所編出來的碼,如果是0就一定是A,因為接下來的碼中沒有以0開頭的,所以我們在解碼的時候只要循序讀入個別的位元,藉著走訪編/解碼樹就能到原本的符號,非常的方便。所以Huffman法是一個相當優秀的壓縮編碼。 * J' ]' e* W& `/ |. _
" A, P: o- G z2 ]III. 字典法 3 h0 t+ ]: x+ X6 v* V% a C* d
" w9 Y; `5 V/ h, x
l 介紹 8 ?: Z3 k* E# u6 Z A; h0 c$ d. a2 W4 D * e9 k' j, p" c& P$ B字典法是和最小冗餘法完全不同的編碼方式。字典法不像最小冗餘法基於一種理論的基礎,它提供了直觀易懂的壓縮原理,也就是建立對照目錄的概念。例如我們如果要講某一個單字,可以拿一本共同的字典,然後講說是第幾頁的哪一個字,這樣也可以表示那個單字。簡單的說,字典法就是在壓縮過程中產生一個對照的字典,然後後面出現的符號就去比對前面建立的字典,如果有同樣在字典裡有的符號出現,就以索引的方式來表示它,以此達到壓縮的目的。顯然字典法的效率好壞和它字典建構的方式以及字典大小有很大的關係(就是壓縮法的好壞和模組的關係)。下面我要介紹的是最有名的LZ77法。3 ?! Z: v( f7 ?% M, B
% R4 H' X( g& |- T" _l LZ77 Algorithm 2 @6 u. ] F; J$ c. L! M6 f) R $ l6 c# e1 F" ^; RLZ77是由Ziv和Lempel在1977年發表的論文中提出的。它的特點是概念十分的簡單,亦能達到不錯的壓縮效果。它也是使用如前述的一邊讀資料一邊建立字典檔,然後新加入的資料比對前面建立的字典檔的方式。LZ77演算法中主要的資料結構有一個sliding window和一個look-ahead buffer。一開始sliding window中是空的,而look-ahead buffer中遇到的資料會先存起來,隨著看到的資料越來越多,sliding window中可以比對的“單字”也變多了。只要接下來在look-ahead buffer中看到sliding window中出現過的字串,就會把它以(在視窗中的位移位置,字串的字元數,字串之後第一個字元)這種方式存起來,就成了壓縮過的形式。就這樣一直比對到檔案結束,就可以完成編碼的動作。. T3 Z5 e; @. }4 J2 I1 K# Y
$ n3 S) Q: H" X6 G
/ \1 J1 O5 f1 v4 f* \+ _
0 i& d# @; a3 H0 ^' [
結論 0 _) T8 Q* u: {
4 h$ d D) U% K
資料壓縮是計算機科學領域中的一門重要學問,它是由資訊理論裡提出的一些原理所發展出來的,如今可以應用到非常廣泛的範圍上。我覺得像是冗餘碼的壓縮方式,在一開始看到的時候會覺得十分神奇,因為不是直覺就能想到的壓縮方法。不過在了解他背後的理論架構之後,就會知道這套方法是依循理論理所當然的架構出來的。這讓我想到數學上的研究雖然抽象,但常常是為所有實際利用開了先河,就像是線性代數是很抽象的概念,但是在工程數學上卻能得到很好的應用。我在找各種資料以前也有試著去想一些壓縮的方法,但怎麼想還是只能想到類似字典法的方式,畢竟它和人的直觀思考是比較接近的。不過在看了許多人提出的壓縮法後,會覺得無失真的壓縮實在是個被研究的蠻透徹的學問,理論和實際應用兼備了,感覺起來我也無法再做多少創新。不過我們也許可以用電機領域的角度來思考它,將快速的無失真資料壓縮製作在硬體上,也是一種很好的應用。但這同時也要考慮到一些系統上的考量,應該是蠻有挑戰性的課題,不過我覺得這可能也有人做過了。總之藉由這次報告找的資料不但滿足我對壓縮到底是如何達成的好奇心,也讓我對資訊科學上理論與實際的結合有更深一層的體認。& ~0 y2 s! F: A+ F; G, w0 \, F
+ l, `7 W1 U/ A0 ^$ ~ $ `. n8 i0 T+ R) z# y# q% n* y8 f: {, E1 Q/ @3 ?) X0 `: c
參考資料 3 G& T3 r' ?$ @9 y. A3 o$ O% i. q1 Y$ |# r4 e
[1] The data compression book, 2nd edition, Mark Nelson, M&T Books, 1996. ; n) ]5 S) P! I8 o L# P9 P( g0 t( O2 q1 i
[2] Compression and coding algorithms, Alistair Moffat, Andrew Turpin, Kluwer Academic Publishers, 2002." H% j! p; x! b. A: V; n$ U
/ }8 f+ P; j% E0 r* d[3] Data compression: techniques and applications hardware and software considerations, Gilbert Held, John Wiley & Sons, 1983. 2 \* p6 D" O" z5 \2 z! x9 \) |+ e" _) F
[4] Mastering algorithms with C, Kyle Loudon, Oreilly & Associates, 1999.作者: tommywgt 時間: 2007-2-8 05:23 PM 標題: arithmatic coding 如果我沒記錯的話arithmatic coding是目前被証明能省少最多Redundancy 的方法. 不過從編碼理論上, arithmatic coding離optimal solution似乎還有一段距離.. e0 b3 F- [3 L- X- f7 {
* R9 u3 @4 w3 F& n
值得一提的是arithmatic coding是IBM的專利哦, 要收錢的...作者: masonchung 時間: 2007-2-8 10:33 PM
Arithmatic coding 又分為 fixed length arithmatic coding 和 content adaptive binary arithmatic coding7 J) z" X- j2 I* u4 s* B- {
前者適合Audio encoding 後者適合 Video encoding作者: windflowerz 時間: 2007-5-12 04:11 AM
偶最近也在做压缩算法哦,ZLIB就是结合了LZ77和HUFFMAN CODING.其实字典算法还有一种LZW,TIF就是基于这种压缩算法,个人感觉非常简单,因为我最怕数学的东西。 9 ^0 o% V* T& C" T1 A, ^" C; r4 h% M- A& I. m& N
但是我觉得这篇文章写得不是很好,感觉上很专业,但是很多东西都没有写清楚。比如无损压缩一般是用来压缩文字资料,而有损压缩一般用于音乐和图像的压缩;HUFFMAN CODING是用来寻找最小二叉树的最优算法;LZ77的核心还在于它有两个重要参数,当前项如果前面已经存在过,那么和相对距离是多少,还有就是有多少字符是相同的,如果还没有存在过,那么就直接显示原来的一个字符。 : F: i% D! f9 w5 e' q0 _5 W6 A3 y" S; E$ G" `
我觉得下面这两篇文章讲的非常好,都是中文的。ZLIB算法有免费的库还有RFC规范,但真正分析起来很难。 , U) R& z; D4 M+ h; h8 |* P3 E$ p' f2 m7 p( ^1 E3 E3 x% o http://www.pconline.com.cn/pcedu/empolder/gj/vc/0403/325402.html & y6 v2 a6 L1 g8 k7 R0 B( \ 2 n' b' \/ h8 Vhttp://www.pubcms.com/demo/tech/web/000069.asp作者: t8810012 時間: 2007-6-22 04:48 PM
It is good material for me. I am studying the related document about this field. Thank you.