LZ77與LZ78

LZ77與LZ78是以色列電腦科學家亞伯拉罕·藍波(Abraham Lempel) 與傑可布·立夫 (Jacob Ziv) 在1977年以及1978年發表之論文中的兩個無失真資料壓縮演算法。這兩個演算法是大多數LZ演算法變體如LZW、LZSS以及其它一些壓縮演算法的基礎。與最小冗餘編碼器或者行程長度編碼器不同，這兩個都是基於字典的編碼器。LZ77最初是帶有「滑動窗」（Slide window）的壓縮演算法，這ω個演算法後來證明等同於LZ78中首次出現的顯式字典編碼技術。

LZ77

定義

LZ77 對字串 x [1 .. n]的分解是將其拆分並壓縮為非空子串 w₁,w₂,…,w_k，滿足以下條件：

x=w₁w₂…w_k
對於每個 w_j （1 ≤ j ≤ k）存在兩種可能：
- w_j 是一個新字元，未在 w₁…w_j₋₁ 中出現，或者
- w_j 是在 w₁…w_j 中至少出現兩次的最長子串。

這些子串 w_j 被稱為因子或短語。

根據定義我們可以立即知道w₁=x [1]。其中x [1 .. n]表示x中從第i位到第j位的字串。x[i]是字串x [i .. i]的簡寫。

演算法

計算 LZ77 壓縮的演算法核心思想是將已處理的字串字首用作字典。為了限制搜尋時間，實際應用中通常限制字典的大小，因此通常使用滑動窗口（sliding window）。滑動窗口既限制字典大小，也限制要處理的文字範圍（預覽緩衝區）。壓縮過程中，字元逐步從預覽緩衝區移動到字典中。實際應用中，字典緩衝區通常包含數千個字元，而預覽緩衝區則包含約100個字元或更少。

演算法輸出由三元組組成，可以用來恢復原始文字。對於因子 w_j 的三元組形式為 (pos,len,λ)：

pos: w_j 在字典中的先前位置（若無則為0）。
len: 先前出現的長度（若為新字元則為0）。
λ: 匹配失敗的字元，即對於任一 j ≤ k ，λ= [∣w₁w₂…w_j₋₁∣+len+1]。

使用滑動窗口時，pos 是字典的邊界的相對位置，新字元以 (0,0,λ) 表示。此輸出格式無需顯式儲存字典即可重建文字。

Pseudocode LZ77-Compressionsalgorithmus:

    while input buffer is not empty do     
       match := longest repeated occurrence of input that begins in window
       if match exists then
           pos := distance to start of match
           len := length of match
           λ := char following match in input
       else
           pos := 0
           len := 0
           λ := first char of input
       end if
    
       output (pos, len, λ)
   
       discard len + 1 chars from front of window
       s := pop len + 1 chars from front of input
       append s to back of window
repeat

壓縮演算法舉例

我們以字串 aacaacabcabaaac 為例說明 LZ77 壓縮的計算過程。演算法採用字典長度為12（紫色區域）和預覽緩衝區（黃色區域）長度為10的滑動窗口模型。演算法輸出的三元組包括：

(0, 0, a)
(1, 1, c)
(3, 4, b)
(3, 3, a)
(12, 3, end)

其中參數pos是距離字典右邊界的相對距離。

第一個看到的字元未知，因此將第一個 a 編碼為 (0, 0, a)。在第二行，字典中已有 a（標記為綠色），因此 c 被作為新字元記錄。在第三行，LZ77 演算法出現特殊情況：匹配的字串延伸到預覽緩衝區。第4行和第5行與前兩行類似，但在最後一個三元組中添加了結束標記，因為文字已完全壓縮且無後續字元。

LZ77-壓縮帶滑動窗
row	12	11	10	9	8	7	6	5	4	3	2	1	0	1	2	3	4	5	6	7	8	9	output
1	empty												a	a	c	a	a	c	a	b	c	a	$\Longrightarrow$ (0, 0, a )
2	empty											a	a	c	a	a	c	a	b	c	a	b	$\Longrightarrow$ (1, 1, c )
3	empty									a	a	c	a	a	c	a	b	c	a	b	a	a	$\Longrightarrow$ (3, 4, b )
4	empty				a	a	c	a	a	c	a	b	c	a	b	a	a	a	c	end			$\Longrightarrow$ (3, 3, a )
5	a	a	c	a	a	c	a	b	c	a	b	a	a	a	c	end							$\Longrightarrow$ (12, 3, end)
finish

關鍵點：

資料流從右側進入滑動窗口。
每次移動時，字典的匹配會避免重複編碼新字元。
當匹配延伸到緩衝區時，演算法會添加標記來終止編碼。

這種方法通過減少冗餘實現更高的壓縮效率。

執行時間分析

該演算法的執行時間為 Θ(n)，因為在壓縮過程中，文字只被遍歷一次。這在字典和預覽緩衝區大小恆定的情況下成立，同時對大型文字進行匹配搜尋的開銷可以忽略不計。然而，在實際應用中，如果沒有額外的資料結構支援，使用普通搜尋方式的實現通常較慢。

LZ77解壓演算法

解壓 LZ77 壓縮檔案比壓縮更簡單，因為無需進行匹配字串的搜尋。其執行時間為線性 Θ(n)，即與原始文字長度相同的步驟數。例如我們解壓 x = (0, 0, a) (1, 1, c) (3, 4, b) (3, 3, a) (12, 3, end):

如果三元組的第一個值為 0，直接將第三個值追加到文字末尾 -> a
第2個三元組中，(1, 1, c) 使用第1行的字元 a（位置1，長度1），然後追加 c -> aac
第3個三元組中，重複字元長度超過了字典長度，需迴圈讀取，隨後追加 b -> aacaacab
第4和第5個三元組中按相同邏輯處理，結束標記被忽略。

解壓後的完整文字為：aacaacabcabaaac。 The pseudocode LZ77 decompression algorithm with a sliding window:

foreach triplet (offset, length, symbol) do

      if length > 0 then
          traverse the previous output backward and output characters until the specified length is   reached,
          restarting at offset in case of overflow;
       end if
       output the symbol
repeat

優點與缺點

LZ77 的一個主要優點是，它可以在完全不了解文字內容的情況下進行壓縮，同時沒有專利限制。其繼任者 LZ78 需要初始字典來重建文字（通常是包含所有單個符號的簡單字典），並且直到2004年部分受專利保護。

但是LZ77 對於小型或非自然語言文字的壓縮效果有限，甚至可能增加資料量。例如，原文字有16個字元，而壓縮結果為15個字元，僅節省了1個字元。儘管如此，LZ77 作為預處理器，與其他壓縮方法（如哈夫曼編碼）結合時，效果顯著。解壓縮

最佳化演算法：無滑動窗

為了更高效地計算 LZ77 壓縮字串，以下的做法是在完整的字串上計算分解因子，無需使用滑動窗。

對於字串的 LZ77 因式分解，可以藉助額外的資料結構實現高效的執行時間。對於一個字串 x，記 SA 為字尾陣列（Suffixarray），ISA 為 x 的反向逆字尾陣列（inverse Suffixarray），即 ISA[i]=j 若且唯若 SA[j]=i。此外，記 lcp(i,j) 為字串 x[SA[i]..n] 和 x[SA[j]..n] 的最長公共字首的長度，其中 n=∣x∣。

計算利用了以下事實：對於字串 x 中的因子 w_j 且滿足 ∣w_j∣>1，為了確定元組位置 pos，只需考慮文字位置 SA[NSV[ISA[j]]] 和 SA[PSV[ISA[j]]]。其中：

NSV[j]=min{i∈{j+1,…,n}∣SA[i]<SA[j]} （NSV 表示 下一個較小值）。
PSV[j]=max{i∈{1,…,j−1}∣SA[i]<SA[j]} （PSV 表示 前一個較小值）。
例如陣列x=[2,1,3,4], 預設陣列x的0位和5位為負無窮。NSV[3]=5，因為x[3]=3, x[4]=4,第三個元素後再無比它更小的數了，只剩下位置5的負無窮。同理，PSV[3]=2。

演算法虛擬碼

演算法 LZ_Factor(i, psv, nsv) 返回需要壓縮的下一個字串的起始位置：PSV和NSV都是計算SA陣列中對應的最大、最小值位置。

Algorithmus LZ_Factor(k, psv, nsv):
     i=ISA[k]
     if lcp(k, SA[psv[i]) > lcp(k, SA[nsv[i]]); then
         (pos, len) <- (SA[psv[i]], lcp(k, SA[psv[i]))
     else
         (pos, len) <- (SA[nsv[i]], lcp(k, SA[nsv[i]])
     end if
     if len = 0; then
         pos <- x[k]
     end if
     if k + len > n; then
         print Factor:(pos, len, 'Ende')
     else
         print Factor:(pos, len, x[k+len])
     end if
     return k + max(len, 1)

我們首先直觀地解釋如何計算從位置 k 開始的下一個 LZ 因子:

考慮字串 x=aaaba 且 k=1。在字串 x 的字尾陣列 SA 中，我們從索引 i=ISA[k] 開始，此處i=ISA[1]=2，我們可以查表得到psv[2]=0，nsv[2]=6。而無論是lcp[i,psv]還是lcp[i,nsv]都是0，因此輸出第一個壓縮後的因子Factor(a,0)。下一個需要尋找的位置為 (k+max(len,1))=2.


i	SA	ISA	x[SA[i]..n]	psv[i]	nsv[i]
0	- infinity
1	5	2	a	0	2
2	1	3	aaaba	0	6
3	2	4	aaba	2	6
4	3	5	aba	3	6
5	4	1	b	4	6
6	- infinity

類似地，當k=2時。在字串 x 的字尾陣列 SA 中，我們查詢索引 i=ISA[2]=3，我們可以查表得到SA[psv[3]]=SA[2]=1，nsv[3]=6。此時lcp[2,1]=2，lcp[2,6]=0，因此輸出第二個壓縮後的因子Factor(1,2)。下一個需要尋找的位置為 (k+max(len,1))=4.

當k=4時。在字串 x 的字尾陣列 SA 中，我們查詢索引 i=ISA[4]=5，我們可以查表得到SA[psv[5]]=SA[4]=3，nsv[5]=6。此時lcp[4,3]=0，lcp[4,6]=0，因此輸出第三個壓縮後的因子Factor(b,0)。下一個需要尋找的位置為 (k+max(len,1))=5.

當k=5時。在字串 x 的字尾陣列 SA 中，我們查詢索引 i=ISA[5]=1，我們可以查表得到psv[1]=0，SA[nsv[1]]=SA[2]=1。此時lcp[5,0]=0，lcp[5,1]=1。因為k+len=6>5，因此輸出第四個壓縮後的因子Factor(1,1,end)。

最後我們得到字串x=aaaba的壓縮因子為(a,0)(1,2)(b,0)(1,1,end)。

$NSV$ 和 $PSV$ 可以由 $SA$ 陣列計算得到:

 for i <- 2 to n+1; do
     j <- i-1
     while defined(j) and SA[i] < SA[j]; do
         NSV[j] <- i
         j <- PSV[j]
     end while
     PSV[i] <- j
 end for

最後終 LZ77壓縮演算法對任意字串 $x$ ：

 calculate SA, ISA, NSV and PSV for x
 k <- 1
 while k <= n; do
     k <- LZ_Factor(k, PSV, NSV)
 end while

其它

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.
Anisa Al-Hafeedh et al.: A Comparison of Index-based Lempel-Ziv LZ77 Factorization Algorithms. In: ACM Computing Surveys, Nr. 1, Volume 45, 2012, S. 5:1–5:17
Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Linear Time Lempel-Ziv Factorization: Simple, Fast, Small. In: CPM 2013, Lecture Notes in Computer Science, Volume 7922, Springer, 2013
Mohamed I. Abouelhoda, Stefan Kurtz, Enno Ohlebusch: Replacing suffix trees with enhanced suffix arrays. In: Journal of Discrete Algorithms, Nr. 1, Volume 2, 2004, S. 53–86
Gang Chen, Simon J. Puglisi, William F. Smyth: Fast and Practical Algorithms for Computing All the Runs in a String. In: Combinatorial Pattern Matching, 18th Annual Symposium, CPM 2007, London, Canada, July 9-11, 2007, Proceedings, S. 307–315
Gang Chen, Simon J. Puglisi, William F. Smyth: Lempel-Ziv Factorization Using Less Time and Space. In: Mathematics in Computer Science, Nr. 4, Volume 1, 2008, S. 605–623
Maxime Crochemore, Lucian Ilie: Computing Longest Previous Factor in linear time and applications. In: Information Processing Letters, Nr. 2, Volume 106, 2008, S. 75–80

外部連結

LZ77演算法及變體的庫、論文及原始碼列表（頁面存檔備份，存於網際網路檔案館）