資料壓縮/流壓縮

檔案與流壓縮

許多資料壓縮演算法是面向檔案的。它們假設底層傳輸協議已無誤地傳輸了壓縮資料檔案的每個位。

一些資料壓縮演算法被設計用於與流式單向廣播一起使用。例如，幾乎所有地面數字電視使用的 MPEG-2 壓縮演算法。接收機可以在任何時間開啟並開始收聽廣播。為了使接收機能夠在流的中間啟動——或在幾秒鐘的嚴重傳輸錯誤後恢復——這類系統通常將流分解成“塊”。解碼器使用同步標記或校驗和來檢測下一個塊的開始，並從那裡開始解碼。在每個新塊中，它會重新初始化並重新啟動解碼過程。使用靜態每塊字典或靜態哈夫曼表的塊解碼器會忘記舊的字典或表，並在每個塊的開頭讀取新的字典或表。使用自適應字典的塊解碼器會忘記舊的字典，重新初始化預設字典，並開始構建新的字典。

塊大小是在壓縮（更長的塊通常會提供更好的壓縮）和快速重啟（更短的塊允許解壓縮器在發生錯誤或開啟後更快地重啟）之間的一種折衷方案。由於實際上所有錯誤都可以用 CRC 程式碼檢測到，因此流式解碼器知道哪些塊有錯誤，通常會拒絕整個塊。流式音訊解碼器使用各種技術來掩蓋此類錯誤——它們可能會嘗試使用對先前音調將持續的預測來“填補”。為了避免“咔嗒聲”，它們可能會選擇在最後一個有效塊的末尾將音量調低以靜音，在錯誤塊期間播放靜音，然後在下一個有效塊的開頭將音量調回到正常音量。

關於“塊”的替代方案的研究很少。有些人推測，與使用 B 位元組的塊大小相比，使用經過設計的（非阻塞）收斂解碼器，可能能夠實現更好的壓縮以及同樣快的重啟，這種解碼器設計為無論何時開啟解碼器，最終都會在最多 B 位元組後收斂到同一個自適應字典上。自適應塊解碼器在每個塊的開頭幾乎沒有上下文（壓縮效果很差），並在塊的末尾逐漸增加上下文（壓縮效果更好）。非自適應塊解碼器在每個塊的開頭都有字典或哈夫曼表的開銷（實際上，在字典或表期間壓縮率為零，而在塊剩餘部分的資料期間壓縮率很高）。理論上，收斂解碼器在任何時候都具有一定的中間上下文（以及一定的中間壓縮率），沒有字典或表開銷或壓縮率低的時期。

資料包壓縮

當資料作為小資料包交換時，透過使用資料包壓縮，可以在給定的通訊鏈路上傳遞更多同步會話。兩種方法——報頭壓縮和有效載荷壓縮——用於使資料包更小。

資料包頭壓縮

資料包有效載荷壓縮

[待辦：簡單介紹一下“用於分組網路的延遲字典壓縮”和其他分組感知有效載荷壓縮演算法]

我們將在本書中其他地方討論的 PPP 預測壓縮協議 是早期的資料包有效載荷壓縮演算法。

磁帶儲存壓縮

資料壓縮的最早應用之一是壓縮用於備份磁帶的資料。許多磁帶驅動器在其韌體中嵌入了一個數據壓縮演算法的實現。（對於現代計算機，可以透過關閉這種“硬體壓縮”並使用現代“軟體壓縮”演算法來獲得更好的壓縮。軟體壓縮演算法利用了主處理器比磁帶驅動器內部處理器快得多的 CPU 和大得多的 RAM。早期的計算機無法使用軟體壓縮，因為它們的速度不夠快，無法跟上磁帶的速度）。

許多磁帶驅動器製造商使用 LZ 演算法。IBM 和 QIC 使用 ALDC 演算法。 Exabyte 使用 IDRC 演算法。DLT 使用 DLZ1 演算法。

VXA 磁帶備份格式（由 Ecrix 開發，由 Exabyte 生產）使用 ALDC 資料壓縮。

自適應無損資料壓縮演算法 (ALDC) 由 ECMA-222 標準化。

“線性磁帶開放”（LTO）磁帶備份格式（由多個製造商生產）使用 LTO-DC 資料壓縮，也稱為流式無損資料壓縮 (SLDC)。

由於法律原因，許多資料壓縮演算法專利被描述為此類磁帶備份儲存系統的一部分。

實現細節

結束處理

大多數資料壓縮演算法都是用無限長度的抽象“資料流”來描述的。在實踐中，資料幾乎總是以具有明顯開頭和結尾的有限長度塊的形式出現。壓縮和解壓縮此類資料的系統最終會到達資料塊的末尾。

解壓縮器如何知道何時停止？

有些人認為結束處理是“超出資料壓縮範圍的”。因此，許多程式設計師使用“單一職責原則”嘗試將“結束處理”程式碼與“解壓縮”程式碼分開——“結束處理”被認為是協議棧中其他層的職責。（這些其他層在其他書籍中進行了更詳細的描述，例如 資料編碼理論，通訊網路，序列程式設計 等）。

存檔檔案格式通常將壓縮資料儲存在“容器格式”中，該格式儲存壓縮資料塊以及一些元資料。 有 5 種流行的方法來實現此類存檔格式和流協議。

1. 元資料包括

• 壓縮長度（這使得更容易跳過存檔中的壓縮檔案以僅解壓縮一個所需檔案），以及
• 解壓縮長度（這使得解壓縮器的實現更簡單）

2. 元資料準確描述了*解壓縮*資料中有多少位/位元組/符號/畫素。 解碼容器格式的軟體將此“未壓縮長度”和壓縮資料傳遞給解壓縮器，解壓縮器會準確記錄到目前為止已生成多少位/位元組/符號/畫素，並在生成足夠數量時停止。（有時，允許解壓縮器將幾個額外的位/位元組/符號/畫素解碼到臨時緩衝區中，然後將正確數量複製到最終輸出中會更簡單）。在某些系統中，解壓縮器需要返回它消耗了多少*壓縮*位元組的計數，以便容器處理程式知道從哪裡繼續解碼檔案的下一部分。

3. 壓縮資料儲存在某種“容器格式”中，該格式包含描述*壓縮*資料中到底有多少個有效位數的元資料。 解碼容器格式的軟體將此“壓縮長度”和壓縮資料傳遞給解壓縮器，解壓縮器會準確記錄到目前為止它消耗了多少位。在某些系統中，解壓縮器需要返回它生成的*解壓縮*位元組的計數，以便容器處理程式知道緩衝區中多少個解壓縮位元組是“真實”資料。

4. 壓縮資料儲存在某種“容器格式”中，該格式包含描述*壓縮*資料中有多少位元組的元資料，但最後一個位元組中有效位的數量未知。（通常，壓縮器會用 0 位填充壓縮資料，直到它填滿一個完整的位元組。 解壓縮器必須以某種方式弄清楚“這是一個恰好以一些（有效）零結尾的程式碼字”——特別是全零程式碼字——與“這不是一個真實的程式碼字，而僅僅是零填充”之間的區別。 處理這種區別的軟體在所有情況下都 notoriously 難以完全正確且沒有錯誤）。在某些系統中，解壓縮器需要返回它生成的*解壓縮*位元組的計數，以便容器處理程式知道緩衝區中多少個解壓縮位元組是“真實”資料。

5. 壓縮資料以一種既不知道“壓縮長度”也不知“未壓縮長度”的方式儲存或傳輸，並且解壓縮器必須以某種方式檢測到結束並返回解壓縮資料和“結束點”元資料給其他軟體。

容器格式有時被描述為具有獨立的“元資料部分”和“壓縮資料部分”。 但是，在評估壓縮效率時，我們必須將所有傳遞給解壓縮器的*資料*視為“壓縮大小”或“壓縮率”——包括“壓縮資料部分”和“未壓縮資料大小”、“壓縮大小（位元組）”和“壓縮大小（位）”等資料，這些資料通常被視為“元資料部分”的一部分。

有些人更喜歡這樣設計的壓縮資料格式，即將許多壓縮檔案連線成一個大檔案，然後解壓縮該大檔案，“正常工作”——即它會生成一個大的解壓縮檔案，該檔案與將所有原始解壓縮檔案連線成一個大輸出檔案相同。

進一步閱讀

• 數字電視