LZ77字典壓縮演算法的中心思想是嘗試識別當前正在壓縮的字元序列中是否已有過相同部分,從而用先前出現的字元串取代重復部分,其輸出為指向先前字元串的「索引」。例如:
該演算法本質上稱為「滑動窗口壓縮」,使用一個虛擬窗口作為字典,正在壓縮的字元串如在窗口內出現,則輸出其位置與長度。使用固定大小窗口進行匹配,而非在全部已編碼信息中尋找匹配,是因為匹配演算法耗時較多,需限制字典大小以保證演算法效率。隨著壓縮進程移動窗口,確保窗口內總是包含最近編碼的信息。對大量信息而言,待編碼字元串通常在最近的上下文中更容易找到匹配串。
LZ77壓縮演算法的基本步驟如下:
以一段字元串為例,我們採用以下步驟進行壓縮:
LZ77演算法通過輸出實際字元解決了窗口內無匹配串的問題,但此方法包含冗餘信息。冗餘表現在兩個方面:一是空索引;二是編碼器可能輸出額外字元,此類字元可能包含在下一個匹配串中。