> lz77 | sliding | window <
// LZ77 —— 使用滑動視窗與字典參照的無失真壓縮演算法
字典編碼
透過偏移量與長度參照重複子字串，以節省空間。
滑動視窗
維持一個滑動視窗以尋找最長的匹配資料。
現代壓縮核心
是 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,)
為什麼要使用 LZ77？:
- ▸無失真壓縮，不流失任何資訊
- ▸不需要預先了解資料格式
- ▸可依資料重複模式自動調整
- ▸實作相對簡單、易於理解
- ▸是許多現代壓縮演算法的基礎模組
>> 常見問題
什麼是 LZ77？
LZ77 是 Abraham Lempel 與 Jacob Ziv 於 1977 年提出的通用無失真資料壓縮演算法。它會將資料串流中重複出現的片段，以指向先前出現位置的參照來取代，達到壓縮效果。
滑動視窗是如何運作的？
滑動視窗由搜尋緩衝區（已處理資料）與前視緩衝區（待壓縮資料）組成。演算法會在搜尋緩衝區中尋找與前視緩衝區開頭最長的匹配，然後輸出對應的參照或文字常值。
LZ77 與現代壓縮演算法的關係？
LZ77 是許多現代壓縮方案的基礎。ZIP 與 GZIP 所使用的 DEFLATE 將 LZ77 與 Huffman 編碼結合。LZSS 在 LZ77 基礎上減少冗餘，而 LZ78 與 LZW 則以不同方式建構字典，但仍採用類似概念。
建議的視窗大小是多少？
對於一般資料，常見視窗大小約為 32KB 到 64KB。較大的視窗可以找到更多匹配，但會消耗更多記憶體與時間。DEFLATE 採用 32KB 視窗，前視緩衝區通常為 256–512 位元組。最佳大小取決於資料的重複模式。
// 計算範例
| # | Offset | Length | Next | Output |
|---|---|---|---|---|
| 1 | 0 | 0 | a | a |
| 2 | 0 | 0 | b | b |
| 3 | 0 | 0 | r | r |
| 4 | 3 | 1 | c | a + c |
| 5 | 2 | 1 | d | a + d |
| 6 | 7 | 4 | — | abra |
// 程式碼範例
Input abracadabra (positions 0..10)
Token (offset, length, next)
offset = distance back into the window, length = bytes copied
Decode copy `length` bytes starting `offset` back, then append `next`
(the copy may overlap its own output, e.g. (1,5,x) repeats a byte)
Window the sliding search buffer; deflate/gzip use 32 KiB
>> 更多問題
問：(偏移, 長度, 字元) 三元組是什麼意思？
答：偏移表示在已見過的視窗中回退多遠，長度是複製的位元組數，字元是接下來的新位元組。解碼器據此逐步還原輸出。
問：為什麼複製區間可以重疊？
答：偏移小於長度時，複製會讀取剛寫入的位元組，從而表示重複：(1, 5, x) 會把前一個字元輸出 5 次。
問：LZ77 用在哪裡？
答：LZ77 是 DEFLATE（gzip、zlib、PNG、ZIP）的核心，其變體見於 LZ4、Snappy、Zstandard 和 Brotli。視窗大小和搜尋策略決定壓縮率與速度。