Pages

2011年8月30日 星期二

[演算法] LZ77壓縮技術研究與心得

以下簡單記錄我對LZ77資料壓縮技術的理解。



簡介
LZ77壓縮技術,是一種運用Dictionary Method的無失真壓縮技術,其基本的精神為記錄”重複性多的資料位置座標”來減低檔案大小。解壓縮過程為先讀入檔案Stream資料並記錄其位置,之後從檔案一直讀進Stream並與之前已經讀入的資料作比對,遇到之前的有重複的資料片段,就記錄下之前那筆資料與目前所處理的重複資料片段之間的相對位移量(offset)。如此解壓縮時就可以根據相對位移去從以前的已經讀過的資料去取出重複的資料,因此可壓縮檔案大小。
Sliding Window
LZ77使用Sliding Window的觀念。Sliding Window可以用一個Queue實現,如下圖所示,將一個Window分隔為兩部分,左邊部分是已經處理完的資料,稱為search buffer,右邊是仍待處理的資料串,稱為look-ahead buffer。資料從右邊一個個讀入,從左邊滑出。好像用一個Window鏡片由左到右滑過一份文件一樣:
clip_image001
Sliding Window示意圖
Token資料結構
LZ77建立一種token的資料結構,來維護檔案中的每筆資料。以上圖的Sliding Window為例,在look-ahead buffer裡目前處理到’A’這個字元,壓縮演算法會從左邊的search buffer裡搜尋有 'A' 這個字元所在位置,並且與look-ahead buffer中的 'A' 開頭以下接續的字元比對,盡可能找出與look-ahead buffer裡相同最長字串,也就是 "ABC" 。而token即儲存這個 "ABC" 字串位置的資料結構。
Token裡儲存著三筆資訊,分別為:位移(offset)、比對出的最大相同字串長度,以及緊接在這個相同字串後的字元。
從search buffer最右邊往左搜尋,一直往左找到 "ABC" 是最長的相同字串,而這個 "ABC" 中的A是search buffer從右數過來第8個字元,所以offset就是8, "ABC" 長度是3,於是token資料裡就儲存著:(8, 3, '_' )的訊息。接著,就將look-ahead buffer裡的 "ABC_" 四個字元往左shift到search buffer內。下一次就從 'U' 這個字元開始繼續往下處理。
因此由token內所維護的前兩筆資料( '8' 跟 '3' ),在解壓縮這個token時,就先將offset往左第八個字元( 'A' )輸出到output stream,並將那個字元以下的3個字元都輸出,且由token儲存的第三個資訊得知最後要output的字元是 '_' 。
並且LZ77壓縮演算法從search buffer中比對字元時,可以往右比對到look-ahead buffer裡的字元,最長可以比對到look-ahead buffer長度減一的位置。由上圖為例,search buffer可以往右比對到look-ahead buffer中從右數過來第一個 '0' 的位置(包括 '0' )。
因此在重複性高的文件裡,可大大壓縮資料量。然而此演算法在比對重複字串時,只能在Window範圍內比對,故控制Window範圍勢必會影響整個壓縮的效率。
心得
今年我暑假偶而會閱讀一些有趣的演算法。目前對於資料壓縮的演算法只對Huffman Code比較熟悉。據我所知ZIP壓縮技術是由Huffman Code跟LZ77一起結合改良出的演算法,希望透過學習不久就可實作出一些解壓縮的程式來玩玩。