LZ77 滑動視窗壓縮

想像你在抄一本書，抄著抄著發現「這一整句剛剛第三段就出現過了」。與其一字一字重抄，你大可寫一張便條：「往回翻 3 段、照抄 12 個字，然後接著寫『。』」——這樣既省筆墨又完全不失真。LZ77 做的正是這件事：它一邊往前讀字串，一邊回頭在已經讀過的部分找「這段我剛剛見過」，找到就用一組座標 (offset 往回幾格, length 照抄幾個字, nextChar 接著的那個字) 取代原本那串字。重複越多、能照抄的越長，檔案就壓得越小。

這就是 gzip / zlib / PNG 這些日常壓縮格式的底層引擎（合稱 DEFLATE 的第一階段）。下面用固定字串 ababcbababaa 一步步演示：滑動視窗如何切成「搜尋緩衝（已處理）＋前瞻緩衝（未處理）」、每步怎麼在搜尋緩衝裡找到最長匹配、輸出哪些三元組，最右邊還會邊壓邊解把 token 還原回原字串給你看——這正是最強的正確性保證：壓得回去、解得回來，一字不差。

LZ77 每一步「在已讀過的字裡找一段重複子串」，本質就是子字串搜尋 → 字串匹配對比（暴力 / KMP / Rabin-Karp / Z-Function）；實務上正是用類似 Rabin-Karp 的滾動雜湊（rolling hash）建雜湊鏈來加速找匹配。

逐步演示（固定輸入 `ababcbababaa`）

游標 cursor 從 0 出發：每一步在搜尋緩衝 text[0..cursor) 裡找與前瞻緩衝 text[cursor..] 開頭相符的最長匹配，得到回退距離 offset 與匹配長度 length；再取匹配之後緊接的字面字元 nextChar；輸出三元組後，視窗前進 length+1，直到讀完整個字串。

固定示範：text = "ababcbababaa"（n = 12）

已輸出 token 數：0 字元比較次數：0

上排＝整個輸入字串。找到匹配時，下排會把「複製來源」對齊顯示在它原本的位置；綠底格是本步正在被編碼（照抄）的前瞻區段，外框連起「來源字元 ↔ 目標字元」的逐字對應，橘底格是匹配之後要一起輸出的字面字元 nextChar。offset < length 時來源會延伸進前瞻區，這就是重疊複製（run-length）。

滑動視窗

本步匹配

－

已輸出 tokens（offset, length, nextChar）

（尚無）

邊壓邊解：由 tokens 重建的字串

誠實揭露：這是教學版，做了哪些簡化

暴力找最長匹配：每步掃遍整個搜尋緩衝（O(n·w)）。真實壓縮器用雜湊鏈 / 後綴結構加速找匹配，本頁為了看清原理而不加速。
只做第一階段：完整的 gzip = LZ77 + Huffman。本頁只展示 LZ77 產生三元組，未含後續把三元組進一步壓縮的 Huffman 熵編碼。
每步必輸出 nextChar：這是最原始 LZ77 的三元組形式，保證一定能還原；實務變體（如 LZSS）會省略多餘的字面字元以壓得更好。
決定性軌跡：同長度匹配固定偏好最近的回退（最小 offset），固定輸入、無任何隨機，兩次執行完全一致。