資料壓縮/字典壓縮

字典壓縮

記住 士兵從麥克風點選中獲得的資訊量？對於某些型別的資料，如果您可以使用未儲存在您正在壓縮的實際資料檔案中的資訊來對資料進行編碼，那麼您可以顯著減少已知形式的儲存和通訊需求，這是有意義的。一些演算法透過包含一個內部資料表來複制此過程，通常稱為字典，因此稱為 *字典壓縮*。

由於它允許在通訊中使用時獲得收益的固有特性，正如麥克風點選示例所示，發射器和接收器之間存在預先理解的程式碼系統，並且在發射器和接收器之間共享。大多數面向通訊網路的壓縮演算法依賴於某種形式的字典壓縮，並非沒有道理。

一個例子是嵌入到壓縮演算法方案中的一個簡單的字典。如果您已經知道特定型別資料的最緊湊的儲存方案，那麼您可以簡單地用更緊湊的狀態替換實際資料。考慮單詞“supercalifragiliciousexpialadocious”。現在假設您的字典中只有 11 個以 super 開頭的單詞，這是第 11 個單詞。嗯，顯而易見的是，Super11 將足夠唯一，以至於在解壓縮時使用相同的字典，您可以毫無資料丟失地恢復完整的單詞。但是對於 A 和 An，卻不太明顯，您可以將有關該單詞的資訊儲存在比除一個字母單詞之外的所有資訊更小的空間中。

現在假設您有網際網路，並且您想要儲存 LaVogue 的一篇文章。您可以在自己的計算機上儲存該檔案，或者，您也可以儲存一個指向該檔案的連結，類似於您主頁上的超文字連結。它是壓縮嗎？也許不是，但您可以稍作延遲即可恢復原始文字，因為它會下載。

壓縮系統包含世界上所有知識的單一伺服器場，並使用它來減少客戶端計算機上的資訊儲存，令人難以置信。更奇妙的是，這樣的系統會產生什麼樣的法律糾紛，以及與恢復最初為專有資訊的壓縮資訊相關的隱私問題和經濟成本。但一個網路感知的壓縮伺服器，可能能夠實現真正激進的壓縮率。本質上，家庭檔案只需要包含觸發特定資料雲解壓縮的金鑰序列。家庭使用者甚至可以壓縮他的壓縮檔案，因為包含指向特定壓縮檔案結構的連結的多個檔案本身可以變成一個包含所有複合檔案壓縮檔案結構的單個檔案。使用者級別的無限壓縮，但在伺服器級別的真正龐大儲存。

使用 4 位編碼的文字壓縮

Pike 的 1981 年壓縮演算法，像幾個早期的文字壓縮演算法一樣，使用了英語單詞的或多或少字面的字典。

Pike 的演算法使用了一個固定的字典，其中包含 205 個最流行的英語單詞和 ASCII 字元。透過使用 4、8 或 12 位的可變長度編碼來表示這些單詞和其餘的 ASCII 字元，以及對大寫字母和單詞之間空格的一些巧妙處理，Pike 的演算法對典型的英語文字實現了 3.87 位元每字元的壓縮率。

在字典中新增更多英語單詞有助於壓縮，但收益遞減。在字典中新增某些非單詞——常見字母對和三元組、常見字首、常見字尾等——有助於壓縮，因為它們可以用來至少部分壓縮字典中沒有的單詞，但新增這些非單詞也會帶來收益遞減。

後來的壓縮演算法保留了短程式碼字代表更長內容的想法，但將其泛化：字典編碼器將程式碼字擴充套件為位元組序列，該序列可能與英語單詞邊界對齊，也可能不對齊。

Smaz

Smaz 是一個簡單的壓縮庫，適用於壓縮非常短的字串，例如 URL 和單個英語句子和簡短的 HTML 檔案。

與 Pike 的演算法非常相似，Smaz 具有一個硬編碼的內建常量程式碼本，其中包含 254 個常見的英語單詞、詞語片段、二元組和小寫字母（除了 j、k、q）。Smaz 解碼器的內部迴圈非常簡單

• 從壓縮檔案中獲取下一個位元組 X。
  • X == 254 嗎？單位元組文字：獲取下一個位元組 L，並將其直接傳遞到解碼文字。
  • 如果 X == 255，則直接將下一個位元組 L 作為字面量字串讀取，然後將接下來的 L+1 個位元組直接傳遞到解碼後的文字中。
  • 如果 X 的值為其他任何值，則在程式碼本中查詢第 X 個“單詞”（該“單詞”可以包含 1 到 5 個字母），並將該單詞複製到解碼後的文字中。
• 重複此過程，直到壓縮檔案中沒有更多壓縮位元組。

由於程式碼本是固定的，因此 Smaz 解碼器無法“學習”新單詞並壓縮它們，無論這些單詞在原始文字中出現多少次。

自適應詞典演算法

大多數詞典演算法都是自適應的：與 Pike 演算法中固定的、硬編碼的詞典不同，解碼器在壓縮文字時，遇到詞典中尚不存在的字母三元組或整個單詞時，會將其新增到詞典中。

如果詞典中存在太多罕見的三元組、音節或單詞，則會增加更常見的三元組、音節或單詞的程式碼字大小，從而降低壓縮率。如果詞典中遺漏了一些三元組、音節或單詞，那麼當它出現時，就無法用簡單的詞典引用來表示，必須使用更多位來拼寫，這也降低了壓縮率。這種平衡行為使得構建一個最佳詞典變得很困難。^[3]

用於初始化資料壓縮演算法的硬編碼詞典對壓縮過程早期階段的壓縮率有很大影響。自適應詞典演算法最終會將特定文字中使用的所有音節和常用單詞新增到詞典中，因此初始硬編碼詞典對大型檔案壓縮後期階段的壓縮率影響很小。^[3]

LZ77 演算法

LZ77 型別的解碼器透過將壓縮檔案中的“複製項”擴充套件成較長的字串來擴充套件壓縮檔案。這使得“重複字串消除”成為可能：僅將字串的第一個副本儲存在壓縮檔案中。所有其他副本都引用先前副本。

這些解碼器具有以下通用演算法

• 下一個專案是字面量嗎？如果是，則將其直接從壓縮檔案複製到解碼文字的末尾。
• 下一個專案是複製項嗎？如果是，則將其分解成“長度”和“距離”。找到從解碼文本當前末尾向前回溯“距離”的文字，並將從該先前解碼文字中複製“長度”個字元到解碼文字的末尾。
• 從頭開始重複，直到壓縮檔案中沒有更多專案。

雖然所有 LZ77 樣式的演算法都具有相同的解碼器結構，但解碼器決定一個專案是字面量還是複製項的方法多種多樣，而且它們從複製項中提取“長度”和“距離”的方法也多種多樣。

許多解碼器演算法將 LZ77 與其他壓縮思想結合起來。截至 2008 年，最流行的基於 LZ77 的壓縮方法稱為 DEFLATE；它將 LZ77 與 Huffman 結合起來。我們在本書的後面章節中討論 DEFLATE，資料壓縮/多重轉換#DEFLATE。

LZSS 和 LZRW1-A

Lempel-Ziv-Storer-Szymanski (LZSS) 由 James Storer 和 Thomas Szymanski 於 1982 年建立。LZRW1-A 由 Ross Williams 於 1991 年發表。

LZSS 和 LZRW1-A 解壓縮器具有非常相似的形式

對於每個複製項，從壓縮檔案中獲取一個“字面量/複製”位。

• 0：字面量：解碼器從壓縮檔案中獲取下一個位元組，並將其直接傳遞到解壓縮文字中。
• 1：複製項：解碼器從壓縮檔案中獲取接下來的 2 個位元組，將其分解成一個 4 位“長度”和一個 12 位“距離”。4 個“長度”位解碼成 3 到 18 個字元的長度。然後找到從解碼文本當前末尾向前回溯“距離”的文字，並將從該先前解碼文字中複製“長度”個字元到解碼文字的末尾。
• 從頭開始重複，直到壓縮檔案中沒有更多專案。

LZJB

LZJB^[4] 解碼器從壓縮檔案中獲取一個“字面量/複製”位。

• 0：字面量：解碼器從壓縮檔案中獲取下一個位元組，並將其直接傳遞到解壓縮文字中。
• 1：複製項：解碼器從壓縮檔案中獲取接下來的 2 個位元組，將其分解成一個 6 位“長度”和一個 10 位“距離”。6 個“長度”位解碼成 3 到 66 個字元的長度。然後找到從解碼文本當前末尾向前回溯“距離”的文字，並將從該先前解碼文字中複製“長度”個字元到解碼文字的末尾。
• 從頭開始重複，直到壓縮檔案中沒有更多專案。

在從控制字中拉取 1 位後，複製項只有一種格式

• LLLLLLdd dddddddd : 從最近解碼位元組之前的 d 位元組處複製 L+3 個位元組。

LZ77

LZ77^[5] 原始 LZ77 解碼器從壓縮檔案中獲取一個“距離/長度/字面量”塊。

LZ77 解碼器演算法為

• 找到從解碼文本當前末尾向前回溯“距離”的文字，並將從該先前解碼文字中複製“長度”個字元到解碼文字的末尾。（有時“長度”為 0，因此此“複製”不會執行任何操作）。
• 然後將壓縮檔案中的字面量字元複製到解碼文字的末尾。
• 從頭開始重複，直到壓縮檔案中沒有更多專案。

BARF

“BARF” 歸檔器^[6]（當它沒有作弊時）使用簡單的位元組級 LZ77 類程式碼。內部迴圈為

• 獲取一個位元組 X。
  • X 在 0...31 範圍內嗎？字面量：將壓縮流中的下一個 X 個字面量位元組複製到解碼文字的末尾。
  • X 在 32...255 範圍內嗎？複製項：複製解碼文字中 X-32 個位置之前的兩個位元組。
• 從頭開始重複，直到壓縮檔案中沒有更多專案。

LZF

LZF 是一種快速壓縮演算法，它需要很少的程式碼空間和工作記憶體（假設我們可以訪問最近解碼的 8 kByte 文字）。

Marc Lehmann 的 LibLZF 被設計為一個非常小、非常快、非常便攜的 LZF 壓縮演算法資料壓縮庫。

[3] LibLZF 原始碼 [4] [5] [6] [7] [8] [9] [10] [11] [12]

LZF 用於 TuxOnIce 和許多其他應用程式。

LZF 解碼器的內部迴圈如下：[13] [14] [15] 對於每個複製項，LZF 解碼器首先從壓縮檔案中獲取一個位元組 X，並將位元組 X 分解為一個 3 位長度和一個 5 位高距離。解碼器有 3 種情況：長度 == 0、長度 == 7 和任何其他長度。

• • 長度 == 0？（即，X 在 0...31 範圍內？）文字：從壓縮流中複製接下來的 X+1 個文字位元組，並將它們直接傳遞到解壓縮流中的當前位置。
  • 長度在 1...6 範圍內？短複製：使用該值作為長度（稍後解釋為 3 到 8 位元組的長度）。
  • 長度 == 7？長複製：獲取一個新的長度位元組並加上 7。新位元組可以具有從 0 到 255 的任何值，因此總和為 7 到 262（稍後解釋為 9 到 264 位元組）。
  • 兩種複製型別：獲取一個低距離位元組，並將其與 5 個高距離位組合起來，得到一個 13 位距離。（這意味著一個 2^13 = 8KByte 的視窗）。
  • 兩種複製型別：找到從當前解碼文字的結尾開始向後“距離”的文字，並將“長度+2”個字元從該先前解碼的文字複製到解碼文字的結尾。
• 從頭開始重複，直到壓縮檔案中沒有更多專案。

每個 LZF“項”都是這 3 種格式之一

• 000LLLLL <L+1>  ; 文字引用
• LLLddddd dddddddd  ; 從最近解碼的位元組之前 d 個位元組複製 L+2 個位元組
• 111ddddd LLLLLLLL dddddddd  ; 從最近解碼的位元組之前 d 個位元組複製 L+2+7 個位元組

FastLZ

FastLZ 由 Ariya Hidayat 開發，是一個免費的、開源的、可移植的即時壓縮庫，用於 FastLZ 演算法。（Ariya Hidayat 顯然是根據 LZF 演算法開發了 FastLZ 演算法？） FastLZ 是 Marc Lehmann 的 LibLZF 的直接替代品。它的壓縮大小和壓縮時間與 LibLZF 幾乎相同，但解壓縮速度顯著提高，大約是 LibLZF 的 2/3。

FastLZ 解碼器的內部迴圈與 LZF 內部迴圈非常相似

• 獲取一個位元組 X。將位元組 X 分解為 3 位長度和 5 位高距離。
  • 長度 == 0？（即，X 在 0...31 範圍內？）文字：從壓縮流中複製接下來的 X+1 個文字位元組到解碼文字的結尾。
  • 長度在 1...6 範圍內？複製：使用該值作為長度（稍後解釋為 3 到 8 位元組的長度）。
  • 長度 == 7？複製：獲取一個新的長度位元組並加上 7。新位元組可以具有從 0 到 254 的任何值，因此總和為 7 到 261（稍後解釋為 9 到 263 位元組）。
  • （當新位元組為全 1（255）時，它用作更長長度的轉義...）
  • 獲取一個低距離位元組，並將其與 5 個高距離位組合起來，得到一個 13 位距離。（這意味著一個 2^13 = 8KByte 的視窗）。
  • 如果距離為全 1（0x1FFF）：獲取 2 個新的距離位元組，得到一個完整的 16 位距離，並將其新增到 0x1FFF 全 1 距離。（這意味著一個 2^16 + 2^13 = 64 KByte + 8 KByte 的視窗）
  • 找到從當前解碼文字的結尾開始向後“距離”的文字，並將“長度+2”個字元從該先前解碼的文字複製到解碼文字的結尾。
• 從頭開始重複，直到壓縮檔案中沒有更多專案。

如果壓縮檔案僅使用 2^13-1 視窗內的距離，並且長度小於 2^8+7，那麼 FastLZ 和 LZF 解碼器都將生成相同的解壓縮明文。

每個 FastLZ“項”都是這 5 種格式之一（LZF 格式，以及一些擴充套件）

• 000LLLLL <L+1>  ; 文字引用
• LLLddddd dddddddd  ; 從最近解碼的位元組之前 d 個位元組複製 L+2 個位元組
• 111ddddd LLLLLLLL dddddddd  ; 從最近解碼的位元組之前 d 個位元組複製 L+2+7 個位元組
• LLL11111 11111111 dddddddd dddddddd ; 從最近解碼的位元組之前 d+0x1FFF 個位元組複製 L+2 個位元組
• 11111111 LLLLLLLL 11111111 dddddddd dddddddd ; 從最近解碼的位元組之前 d+0x1FFF 個位元組複製 L+2+7 個位元組

不清楚為什麼 FastLZ 比 LZF 快得多。它的“擴充套件”似乎沒有被使用，因為基準檔案上的壓縮檔案大小並沒有顯著不同。 如果將相同的實現技術（只要可能就使用 16 位複製，專門針對“執行”（偽 RLE）等）應用於 LZF，它會一樣快嗎？ 還是這些“擴充套件”實際上被大量使用，並且它們以某種方式比 LZF 方法更快（但大小大致相同）？

miniLZO

LZO 是一種壓縮資料格式，也是一個用 ANSI C 編寫的可移植無損資料壓縮庫，由 Markus F.X.J. Oberhumer 開發和維護。 LZO 比 LZF 稍微慢一些，但產生的壓縮檔案大小略好。LZO 比 DEFLATE/gzip 快得多 - 它執行時間大約是後者的 1/2 - 並且產生的檔案大小比 DEFLATE/gzip 稍差。 [16]

miniLZO 是 LZO 庫的一個輕量級子集。

LZ4

LZ4 是一種壓縮資料格式，也是一個由 Yann Collet 開發和維護的可移植無損資料壓縮庫。

LZ4 用於許多 壓縮檔案系統 中，包括 OpenZFS、GNU Grub、HAMMER 和 Squashfs。 各種語言和（跨平臺）作業系統的開源實現可供使用，並且有一個活躍的討論組。

LZ4 解碼器的內部迴圈如下：

對於每個複製項，LZF 解碼器首先從壓縮檔案中獲取一個位元組 X，並將位元組 X 分解為一個 4 位文字長度和一個 4 位複製長度。

文字解碼器有 2 種情況：文字長度 == 15 和任何其他長度。

• 文字長度 == 0...14？從壓縮流中複製接下來的文字長度個文字位元組，並將它們直接傳遞到解壓縮流中的當前位置。（如果文字長度欄位為 0，則沒有文字）。
• 文字長度 == 15？長複製：獲取一個新的長度位元組並加上 15。新位元組可以具有從 0 到 254 的任何值，因此總和為 15 到 269 位元組的文字。

（... 說說文字長度 == 15 緊跟著任意數量的額外 255 位元組的特殊情況...）然後從壓縮流中複製總文字位元組，並將它們直接傳遞到解壓縮流中。

在文字位元組（如果有）之後是距離的低位元組，然後是距離的高位元組。（這意味著一個 2^16 = 64KByte 的視窗）。距離為 1 表示“當前位置 - 1 個位元組”；距離為 0xffff 表示“當前位置 - 65535 個位元組”；距離為 0 無效，永遠不會發生。要複製的實際位元組數的解碼方式類似於要複製的實際文字數的解碼方式，只是匹配的最小長度為 4 個位元組。

• 複製長度 == 0...14？長度總和 = 複製長度 + 4 個位元組，即 4 到 18 個位元組。
• 複製長度 == 15？長複製：獲取一個新的長度位元組。長度總和 = 該新的長度位元組 + 複製長度 + 4 個位元組。新位元組可以具有從 0 到 254 的任何值，因此長度總和為 19 到 273 位元組的文字。

（... 說說複製長度 == 7 緊跟著任意數量的額外 255 位元組的特殊情況...）

• 兩種複製型別：找到從當前解碼文字的結尾開始向後“距離”的文字，並將“長度”個字元從該先前解碼的文字複製到解碼文字的結尾。
• 從頭開始重複，直到壓縮檔案中沒有更多專案。

與大多數 LZ77 風格的演算法一樣，LZ4 支援 偽 RLE - 長度總和可以大於偏移距離；匹配可以向前重疊。

偽 RLE 的一個常見情況是距離為“1”，解壓縮器最終會重複最後一個位元組“長度總和”次。

為了確保解碼器永遠不會讀取超出輸入緩衝區，也不會寫入超出輸出緩衝區，每個塊都以一個“塊大小”欄位開頭，該欄位指示該塊中 *壓縮* 資料的位元組數；並且該塊的最後 5 個位元組始終是文字。最後一個複製項不完整，在它的文字之後立即停止。

“LZ4-HC”（“高壓縮”）和“LZ4”使用完全相同的格式和相同的解碼函式；不同之處在於編碼器。

QuickLZ

QuickLZ

LZS

LZS: Lempel–Ziv–Stac 壓縮。LZS 壓縮在各種網際網路協議中被指定，包括 RFC 1967、RFC 1974、RFC 2395 和 RFC 3943。 Stac Electronics 起訴微軟侵犯 LZS 專利。從那以後，其中一些專利已經過期。

LZS 解碼器從壓縮檔案中獲取“文字/複製”位。

• 0：字面量：解碼器從壓縮檔案中獲取下一個位元組，並將其直接傳遞到解壓縮文字中。
• 1: 複製項：解碼器從壓縮檔案中獲取下一個位。
  • 該位選擇從檔案中拉取多少位的“距離”。
    • 1: 解碼器獲取一個 7 位“距離”。
      • 如果此距離是不合理的“0”值，它實際上代表訊息結束。退出迴圈。
    • 0: 解碼器獲取一個 11 位“距離”（這意味著一個 2 kibiByte 滑動視窗）。
  • 然後解碼器從壓縮檔案中獲取“長度”值。
    • 但是，長度不是在固定長度的欄位中編碼，而是在可變長度的模式中編碼。
    • 00 表示長度 2
    • 01 表示長度 3
    • 10 表示長度 4
    • 1100 表示長度 5
    • 1101 表示長度 6
    • 1110 表示長度 7
    • 1111 0000 表示長度 8
    • 1111 0001 表示長度 9
    • 1111 1111 0010 表示長度 25
    • 一般來說，除了上面列出的前 6 個特殊情況外，"1111" 重複 N 次，然後是表示 0...14 範圍內的值的 4 個位 Y，解碼為長度值 (N*15 + Y - 7)。
  • 然後找到從當前解碼文字結束位置向後“距離”的文字，並將“長度”個字元從該先前解碼的文字複製到解碼文字的結束位置。
• 從頭開始重複，直到解碼到特殊的“零距離”值。

LZS 中使用的複雜可變長度編碼技術允許將“最近”的位元組對壓縮成 11 位，甚至將“不太近”的位元組對壓縮成 15 位，只要它們在 2 kibiByte 滑動視窗中。這種可變長度編碼技術是“通用碼”的幾種型別之一，是許多種“固定霍夫曼編碼”表的其中一種，我們將在本維基百科的 熵 章節中討論。

在文字檔案中，重複的位元組對比更長的重複字串更為常見。LZS 在這種常見的冗餘形式上至少提供了 1 位的壓縮。這使 LZS 優於無法壓縮小於 3 個字元的重複字串的壓縮演算法，因此必須按原樣儲存這些短重複，甚至透過一位來擴充套件它們。

Snappy

“Snappy”演算法針對非常高的速度進行了最佳化（即使是以壓縮效果中等為代價）。在基準檔案上，Snappy 比 zlib 快一個數量級，但壓縮檔案比 zlib 大 20% 到 100%。 Snappy 比 LZF 更快。

“Snappy”解壓縮器的內部迴圈解碼總是以以下格式之一的標記位元組開頭的“元素”。

• xxxxxx00 ; 隨後是文字
• xxxxxx01 ; 複製，偏移量為 1 位元組
• xxxxxx10 ; 複製，偏移量為 2 位元組
• xxxxxx11 ; 複製，偏移量為 4 位元組

詳情

• LLLLLL00 <L+1> ; 其中 L 在 0..59 之間：1...60（含）個文字位元組的文字引用。
• LLLLLL00 <L-59> <長度> ; 其中 L 在 60..63 之間：這些特殊的“長度”分別表示 1、2、3 或 4 個實際的長度位元組跟隨標記位元組。這些長度位元組後面是文字本身。

• dddLLL01 dddddddd ; 複製，偏移量為 1 位元組：從最近解碼的位元組前 d 個位元組處複製 L+4 個位元組。（為什麼是 L+4，得到長度 4..11 ? L+3，得到長度 3..10，會得到更好的壓縮嗎？也許甚至是 L+2，允許我們偶爾複製位元組對？）
• LLLLLL10 dddddddd dddddddd ; 複製，偏移量為 2 位元組：從最近解碼的位元組前 d 個位元組處複製 L+1 個位元組。
• LLLLLL11 dddddddd dddddddd dddddddd dddddddd ; 複製，偏移量為 4 位元組：從最近解碼的位元組前 d 個位元組處複製 L+1 個位元組。

PalmDoc

PalmDoc 將 LZ77 與一種簡單的位元組對壓縮方式結合在一起。PalmDoc 演算法：

PalmDoc 檔案的解碼方式如下

• 從壓縮流中讀取一個位元組。如果位元組是
  • 0x00: “1 個文字”將該位元組不加修改地複製到解壓縮流。
  • 0x09 到 0x7f: “1 個文字”將該位元組不加修改地複製到解壓縮流。
  • 0x01 到 0x08: “文字”：將該位元組解釋為 1 到 8 之間的計數，並將該數量的文字從壓縮流不加修改地複製到解壓縮流。
  • 0x80 到 0xbf: “長度、距離”對：丟棄此位元組的 2 個最左邊的位（'10'），並將接下來的 6 位與下一個位元組的 8 位組合，形成一個 14 位的“距離、長度”項。將這 14 位分成 11 位的距離（從解壓縮文字中的當前位置向後），以及 3 位的長度（從該位置複製，複製 n+3 個位元組，3 到 10 個位元組）。
  • 0xc0 到 0xff: “位元組對”：將此位元組解碼為 2 個字元：一個空格字元，以及由該位元組與 0x80 進行異或運算形成的字母。
• 從頭開始重複，直到壓縮檔案中沒有更多位元組。

LZSA

LZSA 是一個位元組對齊壓縮格式的集合，專門針對 8 位系統上的超快速解壓縮而設計。

LZSA1

LZSA1

... [待辦事項：] ...

LZSA2

LZSA2 解壓縮器的內部迴圈解碼總是位元組對齊的壓縮“命令”，以“標記”位元組開頭：

• 標記：XYZ LL MMM

LL 是一個 2 位文字長度，值為 0 到 3。如果 LL 是 00，則沒有文字，此命令僅處理匹配。如果 LL 是 1 或 2，則此標記後面跟 1 或 2 個文字值。如果 LL 是 3，則此標記後面跟“額外文字長度”的半位元組或位元組，解碼為 3 到 0xFFFF 的文字數量，然後這些 3 到 0xFFFF 個文字位元組緊隨“額外文字長度”位元組之後。

處理完文字（如果有）後，解碼器會處理類似 LZ77 的匹配。匹配偏移量根據標記中的 XYZ 位進行解碼。

• XYZ
• 00Z 5 位偏移量：讀取一個半位元組 + Z 以獲取偏移量
• 01Z 9 位偏移量：讀取一個位元組 + Z 以獲取偏移量
• 10Z 13 位偏移量：讀取一個半位元組 + 一個位元組 + Z 以獲取偏移量
• 110 16 位偏移量：讀取 2 個位元組以獲取偏移量
• 111 重複偏移量：重複使用先前命令的偏移量值。

MMM 是一個 3 位匹配長度，值為 0 到 7。最小匹配長度為 2 個位元組（編碼為“000”）。如果 M 為 0 到 6，則實際匹配長度為 2 到 8。如果 M 為 7，則“額外匹配長度”的半位元組或位元組（緊隨文字位元組之後，如果有）將解碼為 2 到 0xFFFF 的匹配長度。

對於大小最佳化的解壓縮器，相同的程式碼可以用於解碼兩種型別的長度 - 匹配偏移量半位元組或位元組，以及文字長度半位元組或位元組。

字典演算法

固定位元組對編碼

最簡單的字典演算法是使用固定位元組對字典（二元組字典）的位元組對編碼。

簡單的位元組對編碼，也稱為雙平鋪編碼或 DTE，通常用於壓縮影片遊戲 ROM 中的文字。

位元組對解碼器假設英文文字只使用相對較小的字母和符號“字母表”。位元組對解碼器假設某些位元組從未出現在英文文字中（“高”位元組 0x80 到 0xFF 和其他一些位元組）。當壓縮文字中出現“不可能”的位元組時，解碼器在固定字典中查詢該位元組，併發出相應的位元組對。否則，解碼器將壓縮位元組原封不動地複製到明文。通常，0x00 位元組標記壓縮字串的結尾，因此標準 C 字串處理例程可以重複用於處理壓縮文字。字典應包含明文中使用頻率最高的字母對（“th”、“he”、“t”等）。該演算法有多種不同的實現方式，每種實現方式都使用不同的（不相容的）字典。

位元組對編碼

DTE 可以一步解碼 - 壓縮文字的每個位元組要麼是代表自身的“正常”可列印字元，要麼是代表兩個“正常”可列印字元的“不可列印”位元組。遞迴位元組對編碼放寬了此限制：使用遞迴位元組對編碼，“不可列印”位元組代表兩個位元組。有時這兩個位元組都是正常的可列印字元，就像 DTE 一樣。有時一個或兩個位元組可能是（其他）“不可列印”位元組，需要重複解碼過程，直到只剩下可列印字元。

SCZ 位元組對編碼

SCZ 是由 Carl Kindman 開發的一種動態位元組對演算法和壓縮格式，他以 LGPL 許可釋出了其中一種實現及其測試套件。

SCZ 壓縮格式是一系列段。每個段都有幾個位元組的頭部和尾部，包括迭代次數和校驗和，圍繞著一個重複壓縮的塊。

SCZ 解碼器的內部迴圈給定一個包含 256 個條目的字典和一個特殊的轉義符號。內部迴圈掃描“壓縮段資料”塊，並生成一個新的解壓縮塊，類似於這樣

• 從壓縮塊中讀取下一個位元組。
• 如果讀取的位元組是特殊的轉義位元組，則丟棄轉義位元組並讀取以下壓縮位元組作為文字位元組，並將該文字位元組寫入解壓縮塊。
• 否則，在字典中查詢該位元組。
  • 如果該位元組是“標記字元”，則字典包含一個位元組對來替換它 - 將這兩個位元組寫入解壓縮塊。
  • 否則，字典表明該位元組是一個文字位元組 - 將讀取的位元組寫入解壓縮塊。
• 重複此操作，直到壓縮塊中沒有更多資料。

“轉義位元組”使得能夠壓縮一個檔案，該檔案具有多次重複的位元組對，即使該檔案已經使用所有 256 個可能的位元組值 - 壓縮器故意將一些罕見的位元組擴充套件為兩個位元組（轉義位元組和罕見的位元組），以便重新使用該罕見的位元組作為“標記位元組”來表示該位元組對（將這兩個位元組的每個例項壓縮為一個位元組）。

SCZ 解碼器的中間迴圈給定一個迭代次數和一個數據塊。中間迴圈生成相應的明文，類似於這樣

• 如果迭代次數為零，則塊的其餘部分是完全解壓縮的資料 - 完成！
• 從壓縮塊中讀取頭部
  • 從壓縮塊中讀取一個位元組；此位元組成為新的轉義符號。
  • 讀取符號計數 N，並將 N 個字典條目讀入字典。（每個條目是 3 個位元組：儲存在壓縮文字中的“標記”位元組，以及它在解壓縮文字中表示的兩個位元組）。
• 將轉義符號、字典和壓縮塊的其餘部分（壓縮段資料）傳遞給內部迴圈，將其解壓縮為一個解壓縮塊。
• 將（現在為空的）壓縮塊與解壓縮塊交換。
• 遞減迭代次數並從頭開始重複。

SCZ 解碼器的外部迴圈將檔案分解成一系列段，將每個段分解成一個頭部（其中包含迭代次數等）、一個壓縮資料塊（外部迴圈將其傳遞給內部迴圈進行解碼）和一個尾部（其中包含用於檢測問題的校驗和）。

LZ78 演算法

LZ78

LZW

基於字典的技術的一個著名例子是 LZW 資料壓縮，因為它透過將本質上無限長的字串替換為通常大小在 9 到 16 位之間的程式碼來執行。

LZW 演算法，如 GIF 檔案格式中所使用的那樣，可能是最著名和最具爭議的壓縮演算法。

在將一個程式碼字解碼為一個包含一個或多個字母的“詞”並將這些字母發出到明文流時，LZW 解壓縮器會將一個新的“詞”新增到字典中。新詞是由先前解碼的詞與當前程式碼字表示的詞的第一個字母連線而成的。

更大的程式碼字允許使用更大的字典，這通常會提高壓縮率。

GIF

GIF 檔案格式通常以 9 位程式碼字開頭，並在必要時逐漸增加程式碼字的寬度，直到最大程式碼字寬度為 12 位。許多 GIF 實現靜態分配一個包含 2^12 = 4096 個字典條目的字典，每個可能的程式碼字對應一個條目。

LZMW

LZMW（1985 年）由 V. Miller 和 M. Wegman 開發，是對 LZW 的修改。

在將一個程式碼字解碼為一個包含一個或多個字母的“詞”並將這些字母發出到明文流時，LZMW 解壓縮器會將一個新的“詞”新增到字典中。新詞是由先前解碼的詞與當前程式碼字表示的整個詞（可能是同一個詞）連線而成的。這允許字典條目比 LZW 更快地增長。

LZAP

LZAP（1988 年）由 James Storer 開發，是對 LZMW 的修改。

在將一個程式碼詞解碼為一個或多個字母的“單詞”並將這些字母輸出到明文流時，LZAP 解壓縮器至少會向字典中新增 1 個，通常更多的新“單詞”。新單詞是先前匹配與當前匹配的每個初始子字串的串聯。（“AP”指的是“所有字首”。）例如，如果先前的匹配是“com”，當前的匹配是“press”，那麼 LZAP 解壓縮器會向字典中新增 5 個新的“單詞”：“comp”、“compr”、“compre”、“compres”和“compress”，而 LZW 僅新增“comp”，LZMW 僅新增“compress”。

這使得字典中的單詞數量增長速度遠遠快於 LZW 或 LZMW。

LZWL 和基於單詞的 LZW

2005 年，Jan Lánský 引入了基於音節的壓縮。

LZWL 壓縮器使用音節檢測器將明文分成音節。 當 LZWL 解壓縮器從壓縮文字中提取“短語索引”時，它會向字典中新增一個新短語——由整個先前短語與當前短語的第一個音節串聯而成。當 LZWL 解壓縮器從壓縮文字中提取特殊的“空音節”短語索引時，它會向字典中新增一個新的音節——在緊隨其後的壓縮文字中以字元為單位進行編碼。

類似的“基於單詞的 LZW”將明文分成英文單詞（通常情況下，交替出現的字母數字字元和非字母數字字元的最大字串）。

基於字元的壓縮在較小的檔案上似乎能獲得更好的壓縮效果；基於單詞的壓縮在較大的檔案上似乎能獲得更好的壓縮效果。一些研究人員建議，基於音節的壓縮方法可能會在中等大小的檔案（如 HTML 頁面）上獲得更好的壓縮效果。

LZW 實現技巧

解壓縮器使用的字典並不真正需要為每個字典條目儲存一個文字字串。由於每個字典條目都是由某個先前字典條目與單個字串聯而成的，因此解壓縮器只需要為每個條目儲存一個整數和一個字元：某個先前字典條目的索引，以及一個文字字尾字元。

這種緊湊的字典也適用於 LZAP。對於 LZMW，每個條目不再儲存單個字尾字元，而是儲存第二個整數：指向某個（可能相同）先前字典條目的索引。

對於解碼器來說，通常將任何值為小於 256 的程式碼詞進行特殊情況解碼，並立即輸出它所代表的文字位元組，而不是經過查詢字典中該程式碼詞的過程，會更簡單、更快。

一些 LZW 壓縮器使用雜湊表來快速將接下來的幾個明文字元對映到字典條目。這與用於加速 LZ77 風格壓縮器的雜湊表的工作原理基本相同。

LZW 和其他 LZ78 變體的某些實現使用了一種特殊的搜尋樹，利用了字典結構。

LZX

（我們將在後面的章節中討論 LZX，資料壓縮/順序/熵#LZX）

簡化偏移 Lempel-Ziv (ROLZ)

上面提到的 LZ77 的 LZ77 變體對一個線性、未編碼、固定長度的偏移進行編碼。在任何特定解碼時刻，該偏移的可能值通常包含許多永遠不會被使用的值。例如，一旦解壓縮器提取了長度為 4 的複製長度，它可能會在文字中看到數十個“the ”和“and ”的複製，但它知道壓縮器總是會選擇最新的一個——所有選擇其他“the ”或“and ”複製的值將永遠不會出現。

如果我們能夠以某種方式“跳過”這些不可能的偏移，我們就可以用更少的位數對偏移進行編碼，並且仍然能夠使用與上述 LZ77 編碼器相同的（偏移量，長度）短語。

此外，偏移量的許多可能值極不可能出現。例如，一旦解碼器完成了一個以“ch”結尾的短語的輸出，在正常的英文文字中，下一個字元幾乎永遠不會是另一個子音。因此，所有指向以某個子音開頭的短語的偏移量幾乎永遠不會被使用。透過跳過這些極不可能出現的偏移，我們可以用更少的位數對下一個短語的偏移量進行編碼，並且幾乎總是能夠複製與上述 LZ77 編碼器相同的（偏移量，長度）短語。（在一些罕見的情況下，上述 LZ77 編碼器選擇了 ROLZ 演算法認為“不可能”的某些短語並跳過，迫使我們複製其他較短的短語；但希望在這些情況下犧牲幾個位數可以彌補在幾乎所有其他情況下節省的幾個位數）。

“簡化偏移”是指與使用線性、未編碼、固定長度的偏移量相比，我們減少了壓縮檔案中用於選擇特定偏移量的位數。我們並不意味著最大可能的偏移量會減少——事實上，大多數 ROLZ 壓縮器可以從比線性、未編碼偏移量的典型 2^10 或 2^12 位元組限制更遠的偏移量複製短語。

使用線性、未編碼、固定長度偏移量以外的其他方法，必然需要在解碼時進行更多計算，將該壓縮選擇值轉換為已解碼文字中的實際位置。這又是速度和壓縮率之間的另一種權衡。

Ross Williams 指出，所有 LZ77 和 LZ78 演算法都可以轉換為馬爾可夫演算法的形式。

Malcolm Taylor 在 WinRK 壓縮套件中編寫了第一個 ROLZ 實現。Ilia Muraviev 編寫了第一個開源的 ROLZ 壓縮實現。

LZRW3-a 在 LZRW 系列“快速”資料壓縮器中，LZRW3-a(8) 在大型文字基準測試中提供了最佳壓縮效果。與大多數其他 ROLZ 壓縮器不同，它完全忽略了最近解碼的明文上下文位元組。LZRW3-a 解碼器的內部迴圈首先從壓縮檔案中獲取一個“文字/複製”位。

• 0：文字：解碼器從壓縮檔案中獲取下一個位元組，它代表它本身。將其直接傳遞到解壓縮文字中。每個文字位元組都是“有趣的”，因此指向該位元組的指標最終會被新增到“之前解碼文字中 2^12 個有趣位置的表中”。希望下次可以將該位元組透過該指標作為長短語的一部分複製，而不是再次費力地用文字拼寫出來。
• 1：複製項：解碼器從壓縮檔案中獲取接下來的 2 個位元組，它們代表一個短語。解碼器將其分解為 4 位“長度”和 12 位選擇器。
• 4 個“長度”位被解碼為 3 到 18 個字元的長度。
  • 它使用該 12 位選擇器從“之前解碼文字中 2^12 個有趣位置的表中”選擇一個位置，並從該位置複製長度個字元到解碼文字的末尾。此外，在表中新增指向該短語開頭的指標。
• 從頭開始重複，直到壓縮檔案中沒有更多專案。

LZRW3-a(8) 試圖（近似地）保留每個在明文中出現的 3 位元組短語的最近 8 個例項。（解壓縮器將指標新增到哪個分割槽以及當分割槽已滿時用於丟棄舊指標的偽隨機替換的具體細節超出了本文件的範圍）。（實際上，解壓縮器將 12 位程式碼擴充套件為 20 位未編碼偏移量到 1 MB 明文緩衝區中）。（細節太多）

LZRW4 (Ross Williams, 1991) 可以被看作是一種 ROLZ 演算法。與每個短語的線性、未編碼偏移量不同，偏移量由一個 5 位值表示。在每個短語的開頭，LZRW4 解碼器對前兩個字元進行雜湊運算，以獲得一個分割槽號。5 位值選擇上下文選擇的 partition 中的 32 個指標之一。它指向 1 MB 明文緩衝區中以前解碼的位置。（實際上，解壓縮器已將 5 個編碼位擴充套件為 20 位未編碼偏移量）。然後解壓縮器從壓縮文字中提取 3 位，並將其解碼為 8 個可能的長度值（2、3、4、5、6、7、8、16），然後將選定的（偏移量、長度）短語複製到明文。然後更新上下文分割槽。由於“複製項”只有 9 位（標誌位 + 偏移量選擇器 + 長度），因此它可以很好地壓縮常見的位元組對。文字項也是 9 位（標誌位 + 文字八位位元組）。（為了提高速度，Williams 不會在分割槽表中儲存指向 *每個* 2 位元組上下文的指標，而只會儲存在短語 *末尾* 出現的 2 位元組上下文）。（為了減少記憶體使用，Williams 不會使用 2^16 個分割槽來跟蹤 *確切的* 2 位元組上下文，而是將前 2 個位元組的上下文雜湊為一個 12 位上下文，具有 2^12 個分割槽）。（細節太多……）

也許“縮減偏移量”的最極端形式是將偏移量縮減為 0 位。ROLZ 的這種特殊情況稱為 LZP。

LZP

LZP 壓縮由 Charles Bloom 發明。 LZP 解壓縮器檢查當前上下文（可能是前 3 個位元組），在明文中找到該上下文的最近出現（或某種近似），並且僅使用該一個固定偏移量。這給了我們一個非常短的壓縮短語（一個標誌位 + 一個匹配長度）。在某些情況下，該一個固定偏移量與 LZ77 將使用的偏移量相同——在這些情況下，我們節省了很多位，因為我們沒有儲存偏移量。在其他情況下，該一個固定偏移量與 LZ77 將使用的偏移量不完全相同，而是一個更大的偏移量，它為我們提供了完全相同的複製短語——同樣，我們也節省了很多位。不可避免地，有時該一個固定偏移量提供的有用位元組比 LZ77 選擇的偏移量少——在最壞的情況下，為 0 個有用位元組。LZP 需要比 LZ77 在這種情況下所需的更多位來編碼這些位元組。但總的來說，LZP 通常比 LZ77 壓縮得更好。

一些實現確保上下文表始終準確地指向每個 3 位元組上下文的最近出現——這要求在解壓縮器發出的每個位元組上更新上下文表。許多 LZP 實現透過僅在短語或文字的開頭更新表來近似此操作，跳過在該短語期間複製的所有位元組的更新。這加快了解壓縮速度，並且 Arturo San Emeterio Campos 聲稱它實際上提高了較長檔案的壓縮率，儘管它損害了較短檔案的壓縮率。

LZP 解碼器的工作方式如下

• 在上下文表中查詢當前上下文以獲取 Position。如果此上下文 *從未* 出現過，那麼我們有一個文字。否則，從壓縮檔案中獲取一個“文字/複製”位。
• （無論哪種情況，請記住 Position，但更新上下文表以指向解壓縮文字中的當前位置。下次我們有相同上下文時，我們將獲得此位置，而不是那個較早的 Position）
• 0：字面量：解碼器從壓縮檔案中獲取下一個位元組，並將其直接傳遞到解壓縮文字中。
• 1: 複製項：解碼器從壓縮檔案中獲取一些位並將它們解碼為長度。從此上下文之前出現的位置開始，將以前解碼文字中的“長度”個字元複製到解碼文字的末尾。然後從壓縮檔案中獲取下一個文字位元組，並將其直接傳遞到解壓縮文字中。
• 從頭開始重複，直到壓縮檔案中沒有更多專案。

一些文件 描述了 LZP 的位元組級版本

• 在上下文表中查詢當前上下文以獲取 Position。（記住 Position，但更新上下文表以指向解壓縮文字中的當前位置。下次我們有相同上下文時，我們將獲得此位置，而不是那個較早的 Position）。
• 從壓縮文字中獲取下一個位元組。
• 如果此上下文 *從未* 出現過，*或者* 獲取的位元組不是轉義位元組，那麼我們有一個文字；否則，我們有一個複製項。（壓縮器應該為轉義位元組選擇一個在明文中很少出現的的值）。
• 文字：將其直接傳遞到解壓縮文字中。
• 複製項：丟棄轉義位元組，並獲取長度位元組。從此上下文之前出現的位置開始，將以前解碼文字中的“長度”個字元複製到解碼文字的末尾。然後從壓縮檔案中獲取下一個文字位元組，並將其直接傳遞到解壓縮文字中，即使它恰好是轉義位元組。（有時長度將為 0，例如當解壓縮文字 *需要* 包含我們用作轉義位元組的特殊位元組時）。
• 從開頭重複，直到壓縮檔案中沒有更多專案。

統計 Lempel Ziv

統計 Lempel-Ziv 最初由 Yu Fan Ho 提出，作為他在 Sam Kwong 博士指導下攻讀計算機科學碩士學位的研究課題。他們最初將其作為個人數字助理的應用發表。 後來 Yu Fan Ho 將其應用於手機鈴聲，在壓縮率和解壓縮速度方面優於其他可用的無失真壓縮器。統計 Lempel Ziv 對旋律資料的應用已獲得專利。

傳統的基於 LZ 的技術利用了資料的重複特性。解壓縮過程可以透過根據壓縮資料中的索引從搜尋視窗複製重複資料來簡單地完成。在視窗中找不到的資料在壓縮資料中保持未壓縮狀態。然後將未壓縮資料移入搜尋視窗，以進行下一個重複，依此類推。資料無條件地移入視窗，而不考慮統計資訊。由於搜尋視窗的大小有限，因此當視窗已滿時，第一個進入的資料將無條件地移出。視窗很可能被無用（非重複）資料佔用，而有用（要重複）的資料則被剔除。為了提高壓縮率，應該使用更大的搜尋視窗，因此解壓縮器需要更多記憶體。

統計 Lempel Ziv 是一種類似於 LZ 的無失真壓縮演算法，但它也考慮了統計資訊來識別應該放入字典（搜尋視窗）中的有用資料。與 LZ77 相比，它提高了壓縮率，因為可以將更多有用資料儲存在字典中。字典的大小可以更小，以儲存有用資料，因此解壓縮器所需的記憶體更少。由於並非所有資料都必須移入視窗，因此解壓縮器所需的處理能力更少。

ACB

Buyanovsky 的關聯編碼 (ACB) 從類似 LZ77 的壓縮器開始，並做了很多事情來消除 (偏移量、長度) 專案中的大量冗餘。

Tunstall 程式碼

霍夫曼演算法給出了一種固定到可變長度的程式碼，該程式碼（在某些約束下）是最佳的。

Tunstall 演算法給出了一種可變到固定的長度程式碼，該程式碼（在某些約束下）是最佳的。

實現技巧和竅門

壓縮格式技巧和竅門

大多數資料壓縮解壓縮演算法最自然地用將壓縮檔案作為未區分的位流（位流）讀取來描述。大多數程式語言一次一個位元組地執行檔案 I/O。

因此，解壓縮實現通常會保留一個單獨的“位緩衝區”（最初為空）。 當您想要讀取一個位時，如果位緩衝區為空，則從壓縮位元組流中讀取一個（位元組對齊的）位元組，將最後未使用的 7 位儲存在位緩衝區中，並使用第一個位。 否則從位緩衝區讀取下一個位。

許多檔案格式旨在儘可能保持“8 位對齊”（有些甚至嘗試保持“16 位對齊”），以透過減少位移位的數量來加速處理。

通常在解壓縮時，您已經讀取了一些奇數個位，抽象解壓縮演算法會提到類似“讀取下一個 8 位並將該字面位元組直接傳遞到輸出”的內容。 有三種可能的方式來設計檔案格式來處理“讀取下一個 8 位”

• “無差異位流”：獲取位緩衝區中的剩餘位，重新載入位緩衝區，並獲取更多位，然後移位和對齊以重新組裝位元組。
• 丟棄位緩衝區中剩餘的“填充位”，並簡單地從壓縮位元組流中讀取下一個（位元組對齊的）位元組。 比位流方法更快，但未使用的位會損害壓縮率，因此我們不再討論這種方法。
• “位元組對齊”：暫時忽略位緩衝區；直接從壓縮位元組流中讀取（位元組對齊的）位元組。（僅在解壓縮演算法讀取一兩位或七位時才使用位緩衝區）。

與無差異位流格式相比，壓縮文字的位元組對齊格式具有完全相同的位元組數和完全相同的位；位只是以略微不同的順序排列。 因此，選擇位元組對齊格式可以獲得完全相同的壓縮率，並且通常可以提高速度。

壓縮器實現提示和技巧

緩慢的樸素方法

實現 LZ77 樣式（偏移量，長度）壓縮器的顯而易見的方法是，針對我們最終寫入壓縮檔案的每個短語，掃描整個視窗以查詢與以下明文的匹配。 然後選擇最長（和最近）的匹配。

實現 LZ78 樣式（字典條目）壓縮器的顯而易見的方法是，針對我們最終寫入壓縮檔案的每個字典索引，掃描整個字典以查詢與以下明文的匹配。

對於長度為 N 的檔案，這對於每個壓縮短語都是 O(N)。 這需要 O(N^2) 來壓縮長度為 N 的檔案。（Schlemiel 畫家的演算法）。（我假設 LZ77 視窗至少覆蓋了檔案的一半，並假設壓縮率大致恆定）。 這是非常慢的。

加速

大多數 LZ77 樣式和 LZ78 樣式壓縮器實現使用加速技巧：每當它們輸出壓縮短語時，它們都會執行一些 O(1) 的“額外”工作來更新一些資料結構——通常是 Trie 或雜湊表。 然後，他們不再順序掃描整個視窗以查詢匹配，而是查詢該資料結構中的以下明文（通常是接下來的 3 個位元組）。

Trie

一些 LZ77 樣式和 LZ78 樣式壓縮器實現使用 Trie 資料結構.

雜湊表

大多數 LZ77 樣式和 LZ78 樣式壓縮器實現使用 雜湊表。 然後，他們不再順序掃描整個視窗以查詢匹配，而是查詢雜湊表中的以下明文（通常是接下來的 3 個位元組）。 在雜湊表中，搜尋立即成功或失敗，時間複雜度為 O(1)，因此壓縮整個檔案只需要 O(N)。 速度快得多。

許多 LZ77 樣式壓縮器有意透過兩種方式犧牲最大可能的壓縮率：（a）一些壓縮器只在每個短語更新一次雜湊表，而不是每個位元組更新一次。（b）一些壓縮器使用直接索引快取——一個非常簡單的雜湊表，沒有衝突檢測——表只記住具有該雜湊索引的單個最新專案——而不是記住具有該雜湊索引的*所有*專案的標準雜湊表。 通常，（a）或（b）中的每一個都會降低壓縮率幾個百分點，但可以將壓縮器的速度大致提高兩倍或三倍。 許多 LZ77 樣式壓縮器同時執行 (a) 和 (b)，降低壓縮率幾個百分點，但速度大約提高四倍或十倍。

偽 RLE

RLE 可以使用大多數 LZ77 型別的解壓縮器中的重疊副本模擬（“偽 RLE 模式”）。 解壓縮器必須使用一種能夠正確處理這種重疊副本的方法——特別是，解壓縮器不能對這種重疊副本使用 memcpy() 或 memmove()。 在某些機器上，只需對所有副本使用相同的“一次複製一個位元組”copy_bytes() 例程更快。 在其他機器上，程式設計師發現 memcpy() 比這快得多，如果解壓縮器包含額外程式碼，可以針對每個複製項判斷它是否重疊，並在 memcpy() 不起作用時僅使用較慢的 copy_bytes()，則可以減少總解壓縮時間。