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算法及變體的庫、論文及源代碼列表（頁面存檔備份，存於網際網路檔案館）