LZ77與LZ78

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

## LZ77

### 定義

LZ77 對字串 x 1 .. n的分解是將其拆分並壓縮為非空子串 w1,w2,…,wk，滿足以下條件：

- x=w1w2…wk
- wj 是一個新字符，未在 w1…wj−1 中出現，或者
- wj 是在 w1…wj 中至少出現兩次的最長子串。

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

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

### 演算法

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

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

- pos: wj 在字典中的先前位置（若無則為0）。
- len: 先前出現的長度（若為新字符則為0）。
- λ: 匹配失敗的字符，即對於任一 j ≤ k，λ= ∣w1w2…wj−1∣+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行與前兩行類似，但在最後一個三元組中添加了結束標記，因為文本已完全壓縮且無後續字符。

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），即 ISAi=j 若且唯若 SAj=i。此外，記 lcp(i,j) 為字串 xSAi..n 和 xSAj..n 的最長公共前綴的長度，其中 n=∣x∣。

計算利用了以下事實：對於字串 x 中的因子 wj 且滿足 ∣wj∣>1，為了確定元組位置 pos，只需考慮文本位置 SANSVISAj 和 SAPSVISAj。其中：

- NSVj=min{i∈{j+1,…,n}∣SAi5，因此輸出第四個壓縮後的因子Factor(1,1,end)。

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

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

```pascal
 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$：

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

## 其它

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變體。

## 外部連結

- LZ77演算法及變體的庫、論文及原始碼列表