LZ77與LZ78
LZ77與LZ78是以色列電腦科學家亞伯拉罕·藍波與傑可布·立夫在1977年以及1978年發表之論文中的兩個無失真資料壓縮演算法。這兩個演算法是大多數LZ演算法變體如LZW、LZSS以及其它一些壓縮演算法的基礎。與最小冗餘編碼器或者行程長度編碼器不同，這兩個都是基於字典的編碼器。LZ77是「滑動窗」（Slide window）壓縮演算法，這個演算法後來證明等同於LZ78中首次出現的顯式字典編碼技術。
LZ77
[編輯]LZ77演算法通過使用編碼器或者解TangentGraphic2器中已經出現過的相應匹配資料資訊，替換當前資料從而實現壓縮功能。這個匹配資訊使用稱為長度-距離對的一對資料進行編碼，它等同於「每個給定長度個字元都等於後面特定距離字元位置上的未壓縮資料流。」（「距離」有時也稱作「偏移」。）
編碼器和解碼器都必須儲存一定數量的最近的資料，如最近2 KB、4 KB或者32 KB的資料。儲存這些資料的結構叫作滑動窗口，因為這樣所以LZ77有時也稱作滑動窗口壓縮。編碼器需要儲存這個資料尋找匹配資料，解碼器儲存這個資料解釋編碼器所指代的匹配資料。所以編碼器可以使用一個比解碼器更小的滑動窗口，但是反過來卻不行。
許多關於LZ77演算法的文件都將長度距離對描述為從滑動窗「複製」資料的命令：「在緩衝區中回退距離個字元然後從那點開始複製長度個字元。」儘管對於習慣於指令式編程的人們來說很直觀，但是它仍然使得人們很難理解LZ77編碼的一個特點：也就是說，長度距離對中的長度超過距離這樣一種情況不僅是可接受的而且還是經常出現的情況。作為一個複製命令，就會讓人費解：「回退一個字元然後從那點開始複製七個字元。」但是如果緩衝區中只有一個字元的話那該如何複製七個字元呢？然而將長度距離對看作對於特性的描述就可以避免這種混淆：後面的七個字元與前面的七個完全相同。這就意味著每個字元都可以通過在緩衝區找到確定下來：即使在當前資料對解碼開始的時候所要尋找的字元並不在緩衝區中也可以。通過這個定義，這樣的資料對將是距離字元序列的多次重複，也就是說LZ77成了一個靈活容易的行程長度編碼形式。
儘管所有的LZ77演算法都是根據同樣的基本原理工作，但是如何輸出編碼後的資料可能會大不一樣，例如長度與距離的取值範圍是多少以及如何區分長度距離對和字面符號（即直接用字元本身，而不是用長度距離對表示）。下面是一些實例：
- 在Lempel與Ziv最初1977年論文中描述的演算法每次將資料輸出成三個數值：在緩衝區中找到的最大匹配長度與位置以及緊隨這個匹配的字面符號。如果輸入流中的兩個相鄰字元只能編碼成字面符號的話，那麼長度就是0。
- 在PalmDoc格式中，長度距離對經常用兩位元組序列進行編碼，在這兩位元組的16位元中，11位表示距離，3位表示長度，剩餘的兩位用來表示第一個位元組是這樣一個兩個位元組序列的開頭。
- 直到2004年，最流行的基於LZ77的壓縮方法是同時使用了LZ77與哈夫曼編碼的DEFLATE。字面符號、長度以及用於指示當前資料塊結束的符號都放到一個字母表中。距離可以安全地放到一個單獨的字母表中，由於距離只會出現在一個長度後面，所以它不可能與其它類型的符號混淆。
LZ78
[編輯]LZ77演算法針對過去的資料進行處理，而LZ78演算法卻是針對後來的資料進行處理。LZ78通過對輸入快取資料進行預先掃描與它維護的字典中的資料進行匹配來實現這個功能，在找到字典中不能匹配的資料之前它掃描進所有的資料，這時它將輸出資料在字典中的位置、匹配的長度以及找不到匹配的資料，並且將結果資料添加到字典中。
儘管在最初得到流行，但是後來LZ78的普及逐漸衰減，這可能是由於在剛LZ78出現的一些年份，一部分LZ78演算法獲得了美國專利保護。最流行的LZ78壓縮形式是LZW演算法，這個演算法是泰瑞·衛曲所開發的一個LZ78變體。
參考文獻
[編輯]- Jacob Ziv and Abraham Lempel; A Universal Algorithm for Sequential Data Compression （頁面存檔備份，存於網際網路檔案館），IEEE Transactions on Information Theory, May 1977.