LZ77 與 LZ78 是 Abraham Lempel 與 Jacob Ziv 在 1977 年以及 1978 年發表的論文中的兩個無損數據壓縮演算法。這兩個演算法是大多數 LZ 演算法變體如 LZW、LZSS 以及其它一些壓縮演算法的基礎。與最小冗餘編碼器或者行程長度編碼器不同，這兩個都是基於字典的編碼器。LZ77 是「滑動窗」壓縮演算法，這個演算法後來被證明等同於 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 演算法，這個演算法是 Terry Welch 所開發的一個 LZ78 變體。
文章轉載至 維基百科
留言列表
