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位表示長度，剩餘的兩位用來表示第一個字節是這樣一個兩個字節序列的開頭。
- 直到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.
外部連結[編輯]
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||