字典編碼

透過偏移量與長度參照重複子字串，以節省空間。

滑動視窗

維持一個滑動視窗以尋找最長的匹配資料。

現代壓縮核心

是 ZIP、GZIP、DEFLATE、PNG 等格式背後的核心演算法。

LZ77 的運作原理

LZ77 維持一段最近出現資料的滑動視窗。對於每一個位置，演算法會在視窗中搜尋與目前前視緩衝區開頭最長匹配的子字串。若找到匹配，就輸出 (偏移量、長度、下一個字元) 的參照；若找不到，則輸出 (0,0,字元) 的文字常值。藉由將重複片段替換為較短參照，即可達到無失真壓縮。

LZ77 範例

Text: "ABCABCABC"
Window=4, Lookahead=4

Position 0: 'A' - no match
  → (0,0,A)

Position 1: 'B' - no match
  → (0,0,B)

Position 2: 'C' - no match
  → (0,0,C)

Position 3: 'ABC' - matches at offset 3
  → (3,3,A)

Position 7: 'BC' - matches at offset 3
  → (3,2,)

Output: (0,0,A)(0,0,B)(0,0,C)(3,3,A)(3,2,)