LZ77與LZ78
LZ77與LZ78是以色列電腦科學家亞伯拉罕·藍波與傑可布·立夫在1977年以及1978年發表之論文中的兩個無失真數據壓縮演算法。這兩個演算法是大多數LZ演算法變體如LZW、LZSS以及其它一些壓縮演算法的基礎。與最小冗餘編碼器或者行程長度編碼器不同，這兩個都是基於字典的編碼器。LZ77是「滑動窗」（Slide window）壓縮演算法，這個演算法後來證明等同於LZ78中首次出現的顯式字典編碼技術。
LZ77 編輯
LZ77演算法通過使用編碼器或者解碼器中已經出現過的相應匹配數據資訊，替換當前數據從而實現壓縮功能。這個匹配資訊使用稱為長度-距離對的一對數據進行編碼，它等同於「每個給定長度個字元都等於後面特定距離字元位置上的未壓縮數據流。」（「距離」有時也稱作「偏移」。）
編碼器和解碼器都必須儲存一定數量的最近的數據，如最近2 KB、4 KB或者32 KB的數據。儲存這些數據的結構叫作滑動窗口，因為這樣所以LZ77有時也稱作滑動窗口壓縮。編碼器需要儲存這個數據尋找匹配數據，解碼器儲存這個數據解釋編碼器所指代的匹配數據。所以編碼器可以使用一個比解碼器更小的滑動窗口，但是反過來卻不行。
許多關於LZ77演算法的文件都將長度距離對描述為從滑動窗「複製」數據的命令：「在緩衝區中回退距離個字元然後從那點開始複製長度個字元。」儘管對於習慣於指令式編程的人們來說很直觀，但是它仍然使得人們很難理解LZ77編碼的一個特點：也就是說，長度距離對中的長度超過距離這樣一種情況不僅是可接受的而且還是經常出現的情況。作為一個複製命令，就會讓人費解：「回退一個字元然後從那點開始複製七個字元。」但是如果緩衝區中只有一個字元的話那該如何複製七個字元呢？然而將長度距離對看作對於特性的描述就可以避免這種混淆：後面的七個字元與前面的七個完全相同。這就意味着每個字元都可以通過在緩衝區找到確定下來：即使在當前數據對解碼開始的時候所要尋找的字元並不在緩衝區中也可以。通過這個定義，這樣的數據對將是距離字元序列的多次重複，也就是說LZ77成了一個靈活容易的行程長度編碼形式。
儘管所有的LZ77演算法都是根據同樣的基本原理工作，但是如何輸出編碼後的數據可能會大不一樣，例如長度與距離的取值範圍是多少以及如何區分長度距離對和字面符號（即直接用字元本身，而不是用長度距離對表示）。下面是一些實例：
- 在Lempel與Ziv最初1977年論文中描述的演算法每次將數據輸出成三個數值：在緩衝區中找到的最大匹配長度與位置以及緊隨這個匹配的字面符號。如果輸入流中的兩個相鄰字元只能編碼成字面符號的話，那麼長度就是0。
- 在PalmDoc格式中，長度距離對經常用兩位元組序列進行編碼，在這兩位元組的16位元中，11位表示距離，3位表示長度，剩餘的兩位用來表示第一個位元組是這樣一個兩個位元組序列的開頭。
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.