LZ77編碼是一種基於字典的、“滑動窗”的無損壓縮算法，廣泛套用於通信、計算機檔案存檔等方面。
基本介紹
- 中文名：LZ77編碼
- 分類：計算機/壓縮技術
- 提出時間：1977年
- 提出人：Ziv和Lempel
簡介,發展背景,基本流程,舉例,
簡介
LZ77算法是由 Lempel-Ziv 在1977發明的，也是GBA內置的壓縮算法。LZ77算法有許多派生算法(這裡面包括 LZSS算法)。它們的算法原理上基本都相同，無論是哪種派生算法，LZ77算法總會包含一個動態視窗（Sliding Window）和一個預讀緩衝器（Read Ahead Buffer）。動態視窗是個歷史緩衝器，它被用來存放輸入流的前n個位元組的有關信息。一個動態視窗的數據範圍可以從 0K 到 64K，而LZSS算法使用了一個4K的動態視窗。預讀緩衝器是與動態視窗相對應的，它被用來存放輸入流的前n個位元組，預讀緩衝器的大小通常在0 – 258 之間。這個算法就是基於這些建立的。用下n個位元組填充預讀快取器（這裡的n是預讀快取器的大小）。在動態視窗中尋找與預讀緩衝器中的最匹配的數據，如果匹 配的數據長度大於最小匹配長度 （通常取決於編碼器，以及動態視窗的大小，比如一個4K的動態視窗，它的最小匹配長度就是2），那么就輸出一對〈長度（length），距離 （distance）〉數組。長度(length)是匹配的數據長度，而距離(distance)說明了在輸入流中向後多少位元組這個匹配數據可以被找到。
值得說的是，LZ77嚴格意義上來說不是一種算法，而是一種編碼理論。同Huffman編碼一樣，只定義了原理，並沒有定義如何實現。基於這種理論來實現的算法才稱為LZ77算法，或者人們更願意稱為LZ77變種。實際上這類算法已經有很多了，比如LZSS、LZB、LZH等。
發展背景
Ziv和Lempel於1977年發表題為“順序數據壓縮的一個通用算法（A Universal Algorithm for Sequential Data Compression ）”的論文，論文中描述的算法被後人稱為LZ77算法。
1978年，二人又發表了該論文的續篇“通過可變比率編碼的 立序列的壓縮（Compression of Individual Sequences via Variable Rate Coding）”，描述了後來被命名為LZ78的壓縮算法。
1982年，Storer J.A, SzymanskiT.G.發表了名為“ Data compression via textual substitution” 論文，提出了改進 LZ77 的 LZSS 算法。
1984年，T. A. Welch 發表了名為“高性能數據壓縮技術（ A Technique for High Performance Data Compression ）”的論文，描述了他在Sperry研究中心的研究成果，這是LZ78算法的一個變種，也就是後來非常有名的LZW算法。1990年後，T.C.Bell等人又陸續提出了許多LZ系列算法的變體或改進版本。
至今，幾乎我們日常使用的所有通用壓縮工具，象ARJ，PKZip，WinZip，LHArc，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR„„甚至許多硬體如網路設備中內置的壓縮算法，無一例外，都可以最終歸結為這兩個以色列人的傑出貢獻。
基本流程
1 、從當前壓縮位置開始，考察未編碼的數據，並試圖在滑動視窗中找出最長的匹配字元串，如果找到，則進行步驟 2 ，否則進行步驟 3.
2 、輸出三元符號組（ off,len,c ）。其中 off 為視窗中匹配字元串相對視窗邊界的偏移，len為可匹配的長度，c 為下一個字元，即不匹配的第一個字元。然後將視窗向後滑動 len+1 個字元，繼續步驟 1.
3 、輸出三元符號組（ 0,0,c ）。其中 c 為下一個字元。然後將視窗向後滑動一個字元，繼續步驟 1.
舉例
例如：（假設一個 10個位元組的動態視窗, 以及一個5個位元組的預讀緩衝器）
文本：A A A A A A A A A A A B A B A A A A A
--------------------- =========
動態視窗 預讀快取器
動 態視窗中包含10個A ，這就是最後讀取的10個位元組。預讀緩衝器包含了 B A B A A。編碼的第一步就是尋找動態視窗與預讀快取器相似長度大於2的位元組部分。在動態視窗中找不到B A B A A，所以B就被按照字面輸出。然後動態視窗滑過1個位元組，現在暫時輸出了一個B。
第二步：A A A A A A A A A A A B A B A A A A A
--------------------- =========
動態視窗 預讀快取器
現 在預讀緩衝器包含A B A A A，然後再和動態視窗進行比較。這時，在動態視窗找到了相似長度為2的A B，因此一對〈長度, 距離〉就被輸出了。長度(length)是2 並且向後距離也是2，所以輸出為<2,2>，然後動態視窗滑過2個位元組。現在已經輸出了B <2,2>。
第三步：A A A A A A A A A A A B A B A A A A A
--------------------- =========
動態視窗 預讀快取器
繼續上面的方法得到輸出結果<5,8>。現在已經輸出了B <2,2> <5,8>。
最終的編碼結果是：A A A A A A A A A A A B <2,2> <5,8>。
但 數組是無法直接用二進制來表示的，LZ77會把編碼每八個數分成一組，每組前用一個前綴標示來說明這八個數的屬性。比如數據流：A B A C A C B A C A按照LZ77的算法編碼為：A B A C<2,2> <4,5>，剛好八個數。按照LZ77的規則，用“0”表示原文輸出，“1”表示數組輸出。所以這段編碼就表示為：00001111B（等於 0FH），因此得到完整的壓縮編碼表示：F A B A C 2 2 4 5。雖然表面上只縮短了1個位元組的空間，但當數據流很長的時候就會突出它的優勢，這種算法在zip格式中是經常用到。
