資料壓縮/多重變換

組合

早期的文字資料壓縮技術被分為兩種看似截然不同的方法

• 固定到可變解壓縮器，將固定大小的“引用”解壓縮為不同長度的明文字串（齊夫和萊姆佩爾），以及
• 可變到固定解壓縮器，將可變長度的“字首碼”或“算術碼”解壓縮為某個固定長度的明文字串（馬爾科夫）。

研究人員正在尋找一種將它們結合起來的方法，以獲得兩者的優勢。

典型的文字段落有幾種不同的模式。一些歸檔軟體應用了一系列不同的變換，每個變換針對文字中的不同模式。

這種變換通常基於對檔案生成方式的某種 模型。

壓縮軟體（尤其是影像壓縮軟體）通常將原始資料透過一個或多個去相關階段——例如卡胡寧-洛夫變換、顏色空間變換、線性濾波、DFT、變換編碼等——“預壓縮”階段——然後將結果饋送到熵壓縮器中。

許多在壓縮中使用的變換，與直覺相反，會產生需要更多位動態範圍來儲存的中間結果。將原始的 24 位 RGB 畫素轉換為 26 位 YCoCg-R 畫素 或將原始的 16 位音訊樣本轉換為 17 位 delta 編碼差異，似乎“浪費”了位，但它提高了網路壓縮效能：在許多情況下，熵壓縮器在得到這種“去相關”的中間資料時，比在得到原始資料時，能得到更小的壓縮檔案大小。（這種變換導致的結果改進通常被稱為“編碼增益”。）

顏色變換

JPEG 2000 可逆顏色變換 (RCT) 是一種類似 YUV 的顏色空間，它不會引入量化誤差，因此它是完全可逆的。

壓縮器將 RGB 轉換為 YCbCr，使用

$Y=\left\lfloor {\frac {R+2G+B}{4}}\right\rfloor ;C_{B}=B-G;C_{R}=R-G;$

然後壓縮影像。

解壓縮器解壓縮影像，然後獲取 YCbCr 畫素，並使用以下公式恢復原始 RGB 影像

$G=Y-\left\lfloor {\frac {C_{b}+C_{r}}{4}}\right\rfloor ;R=C_{R}+G;B=C_{B}+G.$

JPEG 2000 YCbCr 格式中的一個畫素需要 26 位來無損地表示。

影像的紅色、綠色和藍色層通常高度相關。因此，獨立壓縮 R、G 和 B 層最終會將相同資料儲存 3 次。

即使將 24 位/畫素的 RGB 影像“去相關”為 YCbCr 需要 *更多* 位（26 位）來儲存每個畫素，去相關也有助於壓縮管道中的後續階段做得更好。因此，獨立壓縮 Y、Cb 和 Cr 平面通常會導致比獨立壓縮相同檔案的 R、G 和 B 層更小的壓縮檔案。

大多數（但不是全部！）無損顏色空間變換，包括 JPEG 2000 RCT，都是“擴充套件”的。“擴充套件”的顏色空間變換將 24 位 RGB 畫素轉換為需要 *超過* 24 位來無損表示的中間 YCbCr 畫素。

一些無損顏色空間變換是非擴充套件的。“非擴充套件”的顏色空間變換將 24 位 RGB 畫素轉換為需要相同 24 位來無損表示的中間 YCoCg24 畫素。

所有將 24 位 RGB 畫素轉換為小於 24 位/畫素的顏色空間變換都是有損的。（我需要說明為什麼嗎？）。

音訊變換

音樂

…（填寫更多細節）…

大多數現代的有損音訊編解碼器使用修改後的離散餘弦變換 (MDCT) 作為去相關階段（如 Vorbis、AAC 和 AC-3）或作為去相關階段之一（如 MP3 和 ATRAC）。

語音

語音壓縮通常使用一個關於人聲的相對簡單的模型。聲門以某種頻率發出嗡嗡聲。聲道的共振或阻尼了該頻率及其諧波。舌頭和嘴唇偶爾發出嘶嘶的摩擦音和爆破音。

透過以每秒 30 到 50 幀的速度更新線性預測編碼模型，可以以低位元率重建相當清晰的語音聲音。

有幾種方法可以表示線性預測濾波器係數。

雖然原則上線性預測濾波器係數可以直接傳輸，但通常系統被設定成這樣（在熵解碼後）接收到的位元表示反射係數， 對數面積比，線譜對，或濾波器係數的其他表示。

Codec2

... (填寫詳細資訊) ...

DEFLATE

DEFLATE 將 LZ77 與霍夫曼編碼相結合。它在 RFC 1951 中有說明。

它被廣泛用於解碼 ZIP 檔案、gzip 檔案和 PNG 影像檔案。

zlib

"zlib 壓縮資料格式規範" 是一種標準化方式，用於將壓縮資料打包到檔案中，它有一個簡單的標頭檔案，用於指示壓縮型別並幫助檢測最常見的 資料損壞型別。它通常用於儲存用 DEFLATE 壓縮的資料，視窗大小高達 32K。

"zlib 壓縮資料格式規範" 在 RFC 1950 中有說明。

LZX

LZX 檔案格式和壓縮演算法是由 Jonathan Forbes 和 Tomi Poutanen 發明的。LZX 用於流行的獨立 AMIGA 檔案存檔器。Microsoft 壓縮 HTML 幫助 (CHM) 檔案使用 LZX 壓縮。Windows Imaging Format (".WIM") 檔案支援多種資料壓縮方法，包括 LZX。Xbox Live Avatars 使用 LZX 壓縮。

LZX 同時使用 LZ77 樣式的滑動視窗壓縮和動態霍夫曼程式碼，有點類似 DEFLATE 同時使用兩者。LZ77 樣式的視窗大小 (WINDOW_SIZE) 是 2 的冪，至少是 2^15，最大是 2^21。LZX 使用多個霍夫曼樹結構，每個結構都是規範的。

LZX 中最重要的霍夫曼樹是 "主樹"，它由 256 個元素組成，對應所有可能的 ASCII 字元，另外還有 8*NUM_POSITION_SLOTS 個元素，對應匹配項。（NUM_POSITION_SLOTS 的範圍在 30 個槽到 50 個槽之間）。LZX 中第二重要的霍夫曼樹是 "長度樹"，它由 249 個元素組成。其他樹的作用較小。

LZX 壓縮器任意地將一個檔案分成一個或多個塊。每個塊有 3 種類型："逐字塊"、"對齊偏移塊"、"未壓縮塊"。"未壓縮塊" 在標頭檔案中包含更多內容，然後是未壓縮資料的逐字副本。

在 "逐字塊" 和 "對齊偏移塊" 塊的資料部分中，LZX 使用長度受限的霍夫曼碼字；LZX 將每個碼字限制在最多 16 位寬。每個 "逐字塊" 和 "對齊偏移塊" 都有一個更大的標頭檔案，用於提供資訊（以非常緊湊的差分壓縮形式）供解碼器生成用於該塊的各種霍夫曼樹。

標頭檔案被解碼以獲取每個符號的碼字長度，長度為 0 到 16 位（含），其中 "0 位" 表示相應的符號在該塊中從不出現，"16 位" 用於非常罕見出現的符號。使用各種技術將標頭檔案壓縮成相對較少的位。

當 "距離" 值被解碼時，存在一些特殊值。英文文字中兩個長短語 *幾乎* 相同的情況很常見，但中間可能存在一個小小的拼寫錯誤或替換。使用原始 LZ77，結果是 3 個複製項：[到第一部分的長距離 X，第一部分的長度]、[到插入的距離 Y，插入的長度]、[與開始處的第二部分完全相同的長距離 X，第二部分的長度]。LZX 不會重複完全相同的長距離 X 兩次，而是使用一個特殊的 "距離" 值來指示我們正在 "繼續" 複製前面的塊，並在中間進行替換。（特殊距離值最終佔用的位數少於完整長距離）。

• "距離" == 0："重複最近的匹配距離，它本身不是重複距離"
• "距離" == 1："重複第二最近的匹配距離，它本身不是重複距離"
• "距離" == 2："重複第三最近的匹配距離，它本身不是重複距離"
• 距離 == 3：從 1 位元組前開始複製，最近解碼的位元組（位元組上的偽 RLE），最接近的允許值。
• 距離 == 4：從 2 位元組前開始複製，第二最近解碼的位元組（位元組對上的偽 RLE）
• 距離 == 5：從 3 位元組前開始複製
• 距離 == 6：從 4 位元組前開始複製
• ...
• 距離 == 1000：從 998 位元組前開始複製
• ...
• 距離 = x+2：從 x 位元組前開始複製
• ...
• 距離 == WINDOW_SIZE-1（所有位都高）：從 WINDOW_SIZE-3 位元組前開始複製，最遠的複製可能。

解碼器使用塊標頭檔案設定所有樹後，解碼器在逐字塊中的主迴圈為

• 使用主樹從壓縮文字中讀取一個碼字，並將其解碼成一個 "主元素"。
• 如果 "主元素" 小於 256，則將 "主元素" 作為逐字明文位元組發出。
• 如果 "主元素" 大於或等於 256，我們將有一個複製項。
  • 將 "主元素 - 256" 分成兩部分："槽" 和 3 位 "長度"。
  • 如果 "長度" 是特殊的全 1 值 "7"，則使用 "長度樹" 從壓縮文字中讀取另一個碼字，並將其解碼成一個 "長長度"；將其新增到長度中已有的 7。
  • 如果 "槽" 的範圍是 0..3，則將距離設定為與槽相同。
  • 如果 "槽" 的範圍是 4..37，則需要 extra = ((slot >> 1) - 1) 個額外位才能獲得確切的距離。
    • 從壓縮文字中讀取這些額外的原始 "尾部" 位（不使用任何霍夫曼樹，只讀取原始位）。距離（以二進位制形式）是一個隱含的 1 位，後跟 (slot & 1) 位，然後是額外的原始尾部位。
  • 如果距離是 0..2，它表示一個 "重複距離"（如上所述）-- 用我們之前使用的實際距離替換它。
  • 從先前解碼的明文中進行正常的 LZ77 樣式複製：從距離（如上所述）複製 "長度 + 2" 個位元組到解碼的明文中。
• 重複，直到我們解碼了標頭檔案中指定的未壓縮明文應包含的總位元組數。

解碼器使用塊標頭檔案設定所有樹後，解碼器在對齊塊中的主迴圈為

• 使用主樹從壓縮文字中讀取一個碼字，並將其解碼成一個 "主元素"。
• 如果 "主元素" 小於 256，則將 "主元素" 作為逐字明文位元組發出。
• 如果 "主元素" 大於或等於 256，我們將有一個複製項。
  • 將 "主元素 - 256" 分成兩部分："槽" 和 3 位 "長度"。
  • 如果 "長度" 是特殊的全 1 值 "7"，則使用 "長度樹" 從壓縮文字中讀取另一個碼字，並將其解碼成一個 "長長度"；將其新增到長度中已有的 7。
  • 如果 "槽" 的範圍是 0..3，則將距離設定為與槽相同。
  • 如果 "槽" 的範圍是 4..37，則需要 extra = ((slot >> 1) - 1) 個額外位才能獲得確切的距離。
    • 如果 extra > 3，則從壓縮文字中讀取 (extra - 3) 個原始 "尾部" 位（不使用任何霍夫曼樹，只讀取原始位）。然後使用 "對齊樹" 從壓縮文字中讀取另一個碼字，並將其解碼成 3 位（0 到 7）。距離（以二進位制形式）是一個隱含的 1 位，後跟 (slot & 1) 位，然後是 (extra - 3) 個原始尾部位，最後是 3 個對齊位。
    • 如果 extra = 3，則使用 "對齊樹" 從壓縮文字中讀取另一個碼字，並將其解碼成 3 個對齊位（0 到 7）。距離（以二進位制形式）是一個隱含的 1 位，後跟 (slot & 1) 位，然後是 3 個對齊位。
    • 如果 extra 是 1 或 2 位，則從壓縮文字中讀取這些額外的原始 "尾部" 位（不使用任何霍夫曼樹，只讀取原始位）。距離（以二進位制形式）是一個隱含的 1 位，後跟 (slot & 1) 位，然後是額外的原始尾部位。
  • 如果距離是 0..2，它表示一個 "重複距離"（如上所述）-- 用我們之前使用的實際距離替換它。
  • 從先前解碼的明文中進行正常的 LZ77 樣式複製：從距離（如上所述）複製 "長度 + 2" 個位元組到解碼的明文中。（最小複製長度為 2 個位元組）。
• 重複，直到我們解碼了標頭檔案中指定的未壓縮明文應包含的總位元組數。

Microsoft "cabinet" (".CAB") 壓縮存檔檔案格式支援 3 種資料壓縮方法：DEFLATE、LZX 和 Quantum 壓縮。將可執行檔案放入 ".CAB" 存檔的壓縮器可以可選地 "檢測 "CALL" 指令"，將其運算元從相對定址轉換為絕對定址，因此對相同位置的呼叫會產生壓縮器可以匹配的重複字串，從而提高 80x86 二進位制程式碼的壓縮率。"。CAB" 解壓縮器在執行上述 LZX 解壓縮後，如果標頭檔案中的 "預處理" 位被設定為 1，則必須將這些運算元轉換回相對定址。我們將在後面的章節中更詳細地討論這種預處理器/去相關器，以及 可執行檔案壓縮。

LZX DELTA

LZX DELTA (LZXD) 是 LZX 的變體，經過修改以支援有效的增量壓縮（修補）。

LZX DELTA 解壓縮器接收某個明文檔案的舊版本（必須與壓縮器使用的舊版本完全相同）和 LZXD 壓縮的補丁檔案，並使用它們生成該明文檔案的新版本。

LZXD 和 LZX 之間的主要區別在於，視窗預先載入了參考檔案，解壓縮器將輸出檔案的第一個位元組解碼到視窗中，該位置緊接在參考檔案的最後一個位元組之後。正常的 LZX 複製項的距離最大為回到輸出檔案的第一個位元組的完整距離；LZXD 允許距離遠得多，以允許從參考檔案中進行復制。

LZXD 支援更多 "槽"，最多 290 個槽，它們被編碼到主樹中。這允許 LZXD 複製項從更遠的過去獲取內容，使其能夠利用非常長的參考檔案。

LZXD 還支援更大的 "長度" 值。與 LZX 具有 0 到 7 的 "短長度" 一樣，其中 "7" 用作轉義符，以從 7 到 255 獲取 "長長度"，LZXD 使用相同的 "短長度" 和 "長長度"，並更進一步，使用 "257" 的長長度作為轉義符，以獲得 "超長長度"，可以在單個複製中複製 32 KByte。

LZARI

LZARI 使用 LZSS 預處理器，然後進行算術編碼。LZARI 由奧村晴彥開發。

LZH

LZH 使用 LZSS 預處理器，然後進行霍夫曼編碼。LZH 由吉崎春康為 LHA 歸檔器開發，基於 LZARI。

LZB

LZB 壓縮器使用 LZSS 預處理器，然後對“匹配長度”和“偏移量”進行 Elias gamma 編碼。（此附加步驟使 LZB 比單獨的 LZSS 具有更好的壓縮率，但執行速度更慢）。

LZB 的壓縮率與 LZH 和 LZARI 大致相同，但更簡單、更快， 因為像 Elias gamma 編碼這樣的通用程式碼比霍夫曼編碼或算術編碼（分別）更簡單、更快速地解碼。

LZMA

Lempel-Ziv-Markov 鏈演算法 (w:LZMA) 使用一種類似於 LZ77 的壓縮演算法，其輸出透過範圍編碼進行編碼。

LZMA 是開源 7-Zip 檔案歸檔器中使用的壓縮方法之一。

LZMA 的類似 LZ77 的壓縮部分與 LZX 的類似 LZ77 的壓縮部分有許多相似之處。LZMA 不使用霍夫曼程式碼——而是使用上下文編碼的二元算術程式碼。

LZHAM

LZHAM（LZ、霍夫曼、算術、馬爾可夫）是 Richard Geldreich, Jr. 的通用無損資料壓縮庫。LZHAM 的不穩定/實驗版本和“位元流相容性”穩定版本都根據 MIT 許可釋出。

LZW 和霍夫曼編碼

有些人將 LZW 和霍夫曼編碼結合在一起。

此類系統的解碼器從壓縮檔案中讀取一系列霍夫曼程式碼。解碼器將每個可變長度的霍夫曼程式碼解碼成一箇中間固定長度的 12 位索引。對於典型的純文字檔案，這些 12 位數字中有一些的使用頻率遠高於其他數字，因此被分配了小於 12 位的霍夫曼程式碼。然後，解碼器使用 LZW 解碼器來恢復與該中間索引相關的原始可變長度的純文字（1 個或多個字元）。

實施技巧

許多壓縮檔案格式必須使用熵解碼器解壓縮，然後進行一系列轉換——一種 維基百科：管道（軟體）。

有 4 種方法可以實現此類解壓縮器（以及相應的壓縮器）

• 多遍壓縮：每個內部轉換從某個臨時檔案讀取所有輸入，並將所有輸出寫入某個臨時檔案，然後下一階段開始。
• 幾乎同時執行每個階段
  • 使用協程或執行緒或程序或 Unix 管道。遺憾的是，這些技術在許多嵌入式系統環境中不受支援。
  • 使用解壓縮函式呼叫“向下”以獲取更多資料。外部應用程式僅直接呼叫最終轉換階段，該階段呼叫某個中間轉換階段，該階段呼叫另一箇中間轉換階段，該階段呼叫管道開始處的熵解碼器，該解碼器呼叫從檔案獲取位元組的例程。外部應用程式反覆呼叫該最終轉換階段，直到所有資料都被處理。
  • 使用解壓縮函式返回“向上”以獲取更多資料。外部應用程式直接依次呼叫每個階段。每個階段從其輸入緩衝區讀取資料，更新其內部狀態，並將資料寫入其輸出緩衝區。該輸出緩衝區是下一階段的輸入緩衝區。外部應用程式反覆迴圈遍歷所有階段，直到所有資料都被處理。

將軟體從“呼叫向下以獲取更多資料”的 API 轉換為“返回向上以獲取更多資料”的 API 很困難。

加密

由於先加密後壓縮不會使檔案變小，因此許多人使用先壓縮後加密。

由於現代 CPU 處理資料的速度快於從旋轉磁碟或大多數外部快閃記憶體驅動器讀取資料的速度，因此有可能在比讀取和寫入包含相同資料的普通純文字檔案所需的時間更短的時間內讀取和寫入壓縮的加密檔案。

一些人正在研究同時壓縮和加密的演算法。

一些研究人員透過嘗試壓縮加密資料來測試加密演算法。許多加密演算法專門設計用於產生“與隨機噪聲無法區分”的密文。 當嘗試實施此類演算法時，如果壓縮產生的壓縮輸出檔案小於加密的輸入檔案，則表明加密軟體存在缺陷——要麼是實現中的錯誤，要麼是安全演算法的正確實現。

實施技巧

一些使用無失真壓縮的人更喜歡使用“冪等”（有沒有更好的術語？）壓縮軟體，即使壓縮時間稍微長一些。 換句話說，他們期望當你用“最大壓縮”（通常是“-9n”）壓縮一個檔案以建立一個壓縮檔案，然後解壓縮它，然後重新壓縮它時，他們期望得到的第二個壓縮檔案與第一個壓縮檔案相同。

（這“冪等”是否與其他人所說的“確定性”相同？ ）

這通常要求每個轉換實現（至少在傳遞“-9n”選項時）都是冪等的。一些非冪等的因素（因此應避免，至少在傳遞“-9n”選項時）是

• 一些壓縮器在壓縮檔案中儲存原始檔名和未壓縮檔案的日期戳。為了冪等，要麼壓縮器必須省略名稱和日期戳（這就是“-n”通常做的事情），要麼解壓縮器必須恢復原始名稱和日期戳。
• 顏色轉換（如果有）應該是可逆的（無損）
• 對於任何給定的解壓縮演算法實現，幾乎總是有很多不同的方法來表示原始檔案——有很多壓縮檔案會產生完全相同的輸出檔案。（例外是“雙射壓縮”。）當試圖獲得“最大壓縮”時，我們選擇最短的方法——但即使那樣，通常也會有幾種方法會得到相同的壓縮檔案大小。為了冪等，壓縮器的實現必須始終選擇相同的方法。

一些資訊理論術語

(待辦事項: 將上面的“冪等”替換為“非漂移有損”，如下定義？或者有更好的術語？)

一些資訊理論專家 將變換分類為 4 類損耗

• 雙射 (ED = 1 且 DE = 1)
• 冪等 (無損但不是雙射: ED = 1 但 DE !=1)。幾乎所有為文字或可執行程式碼設計的壓縮演算法都屬於此類。
• 非漂移有損 (EDE = E)。大多數為音訊、影片和靜止影像設計的壓縮演算法都屬於此類。量化是非漂移有損變換。從初始影像 I0 開始，第一個編碼/解碼迴圈會得到一張稍微不同的影像 I1（希望只有正常人不太可能注意到的差異）。從 I1 開始，編碼/解碼生成 I2，然後編碼/解碼 I2 生成 I3，不會產生更多損失: I1 == I2 == I3 == I4 ...
• 一般情況: 退化。每個編碼/解碼迴圈通常都會生成一張略微不同的影像（例如一系列傳真傳輸或使用物理紙張影印機進行多代複製）。

有些變換已知不能完全消除所有冗餘。特別是，研究人員設計了特殊的 LZ77 編碼器和 LZW 編碼器，這些編碼器在選擇複製副本時對額外的“冗餘位”進行編碼，這種方法是向後相容的: 標準 LZ77 或 LZW 解碼器可以提取原始檔案。特殊的 LZ77 或 LZW 解碼器可以提取原始檔案以及這些額外的“冗餘位”。這些額外位可用於 Reed-Solomon 或其他形式的糾錯，或用於儲存有關原始檔案的資訊，例如公鑰簽名或訊息身份驗證程式碼。

網路稀疏化

網路稀疏化在資料壓縮中有應用。