資料壓縮/順序/熵

熵

熵是不可預測性的度量。瞭解熵不僅有助於您瞭解資料壓縮，還可以幫助您選擇好的密碼並避免容易被猜到的密碼。

例如，1000 位資料代表 1000 次連續拋擲一枚公平硬幣，其熵為 1000 位，因為無法預測接下來是“正面”還是“反面”。1000 位資料代表 1000 次連續拋擲一枚不公平的雙面硬幣，其熵為零 (0) 位，因為硬幣總是會正面朝上。

資訊的熵在某種意義上是其真正包含的資訊量的度量。^[1]

透過去除儲存元素中的一致性，例如冗餘、類似元件、最常用詞等，壓縮會增加檔案的熵，直到檔案中包含的熵過多，無法進一步壓縮。壓縮在縮小檔案大小時，會導致每個檔案長度的熵密度更高。這使得經過適當壓縮的檔案在進行加密傳遞後，比未壓縮的檔案更難在僅密文攻擊中被破解。參見

http://en.wikipedia.org/wiki/Unicity_distance

當然，如果攻擊者可以選擇您加密的明文，它對大多數明文攻擊模式沒有幫助。

同時，解壓縮演算法會向高熵檔案新增越來越多的一致性和順序，直到它有意義。壓縮不是一種好的加密形式的原因之一是，檔案中隱藏著資訊，表明解壓縮程式如何恢復它。事實上，在極端的壓縮中，恢復壓縮文字所需的資料量通常比尚未壓縮的實際剩餘資料所佔的百分比更大。

“	熵總是相對於某個模型而言的。它不是您獲得的特定位串的屬性，而是您可能獲得的位串集的屬性。	”

熵總是相對於某個模型而言的。它不是您獲得的特定位串的屬性，而是您可能獲得的位串集的屬性。對於給定的位集，產生最低熵的模型是最佳預測這些位的模型，因此它以最小的方式壓縮資料。大多數壓縮檔案格式儲存 (a) 我們使用的模型，(b) 該模型的特定引數（如果有），以及 (c) 根據該模型壓縮的資料。某些型別的模型有許多“引數”並且需要大量空間來儲存，因此我們經常使用完全不切實際的模型，但這些模型需要非常少的空間來描述，以便減少最終壓縮檔案的大小（模型描述 + 壓縮資料）。

最簡單的模型之一是“檔案的每個位元組都是通過蒙著眼睛在牆上扔飛鏢獨立隨機生成的。某些字母出現頻率更高，因為它們在牆上的面積更大。”這是 0 階馬爾可夫模型，也稱為每個位元組都被認為是獨立訊息時的夏農熵。使用該模型，任何特定字母 $F_{i}$ 在檔案 F 中的熵 $H(F_{i})$ 為

$H(F_{i})=-log_{2}p(F_{i}),$

（這是使用熵編碼來表示該字母所需的位數）

整個檔案的熵 $H(F)$ 是檔案中每個字母熵的總和（表示整個檔案所需的位數是表示該檔案中每個字母所需的位數的總和）

$H(F)=\sum _{i=1}^{N}{-\log _{2}p(F_{i})},$

在唯一的可能訊息數 n 方面（檔案中任何特定字母都是 n 個可能字母列表中的一個，從 $x_{1}..x_{n}$ 中，任何一個都可能出現 0、1 或 N 次）

$H(F)=\sum _{i=1}^{n}{-p(x_{i})\log _{2}p(x_{i})},$

其中

• $F_{i}$ 是一個唯一的字母，例如 'e'

* $f(x_{i})$ 是檔案中的唯一字母 x_i 出現的次數

• $p(x_{i})$ 是符號 $x_{i}$（例如字元 'e'）在訊息中的機率
• $f(F_{i})$ 是檔案第 i 位置上的字母在檔案中出現的次數（顯然至少為 1）
• $N$ 是檔案的長度（檔案中訊息的總數）
• $n$ 是可能的字元數量，通常 n=257
• $p(k)={\frac {f(k)}{N}}$ 是某個字母 k 出現的機率。

通常，字元集中的某個特定字母 x_i 在某個特定檔案中不會出現 - 就像字母 'e' 從未出現在 Gadsby (1939) 中一樣。可能存在任意數量的從未實際出現的字母。從未出現的字母不會影響實際出現的任何特定字母的熵，也不會影響它們的總和，即整個檔案在 0 階模型下的熵。當某個字母 x_i 存在於字元集中，但它在某個特定檔案中從未實際使用時，該字母的頻率為零，其機率為零，並且值 $0log_{2}(0)$ 實際上為零。

任何任意檔案，當使用 1 階馬爾可夫模型（“一階模型”）分析時，都會得到一個熵值，該值小於或等於 0 階熵。

我們將在本書後面詳細討論 1 階馬爾可夫模型和更高階馬爾可夫模型（馬爾可夫模型）。

如何進一步壓縮資料

壓縮在某個點變得是如何進一步壓縮已經具有熵的資料，這些資料主要由解壓縮最小資料量的指令組成？

有兩種方法可以嘗試，第一種方法是在不增加檔案長度的情況下注入順序，以便你可以獲得更多的壓縮，而另一種方法則更有爭議，因為它建議在不改變檔案長度的情況下注入熵，以便你可以獲得更多的壓縮。

後一種方法基於一個鮮為人知的科學原理，該原理最早在“一種新型科學”中解釋，該原理表明熵和順序至少在增量或減量型 IV 細胞自動機中是迴圈的。這種方法可能解釋了熱力學第二定律下的自組織現象，這意味著有時當足夠多的熵被注入資料場時，資料會再次自組織成有序狀態。如果我們能跟蹤它為達到自組織水平而經歷過的熵狀態，我們就可以壓縮新的順序，並有希望恢復原始狀態。

熵編碼

統計符號壓縮

字首編碼

霍夫曼編碼

對於壓縮資料中的每個字首程式碼，霍夫曼解壓縮器會在表中查詢壓縮符號，並輸出相應的明文符號。

在以下示例中，我們假設明文符號是某個 8 位位元組。（大多數霍夫曼解壓縮器在其字母表中包含 257 個符號：256 個可能的位元組和一個表示“塊結束”的特殊第 257 個程式碼。一些霍夫曼解壓縮器具有額外的壓縮符號，這些符號解壓縮為常見的位元組對或整個單詞，這會導致更小的壓縮檔案大小）。

程式碼到字母的轉換表從哪裡來？所選的特定源可能是不同霍夫曼壓縮檔案格式之間最大的區別。

• 固定霍夫曼程式碼
• 靜態霍夫曼程式碼（有時稱為“半自適應霍夫曼”）（RFC 1951 對 DEFLATE 的定義稱其為“動態霍夫曼程式碼”）
• 自適應霍夫曼程式碼

（是的，用“靜態”作為“動態”的同義詞很令人困惑。現在改變它還來得及嗎？）

當解壓縮器使用固定霍夫曼程式碼時，它使用硬編碼到解壓縮器中的轉換表，該表永遠不會改變。

當解壓縮器使用靜態霍夫曼程式碼時，它會在壓縮塊的開頭讀取轉換表。然後它使用該資料來解碼塊的其餘部分。大多數霍夫曼的“最優性證明”都假設這種靜態程式碼。

通常，即使在同一個檔案中，一段文字的字母頻率也會略有不同。大多數靜態霍夫曼解壓縮器會觀察一個特殊的第 257 個“塊結束”符號，然後丟棄舊的霍夫曼表並讀取新的靜態壓縮表。解壓縮器使用該表來解碼新的塊。

DEFLATE 和一些其他解壓縮器會在每個塊的開頭放置一些“模型選擇器”元資料。這命令解壓縮器要麼

• (a) 在模型選擇器之後立即獲取靜態霍夫曼表元資料；
• (b) 複製儲存在解壓縮器內的預設固定霍夫曼表；
• (c) 複製原始資料，而不嘗試解壓縮它——這對“不可壓縮”的資料很有用；或者
• (d) 使用完全不同的其他壓縮演算法。

當解壓縮器使用自適應霍夫曼程式碼時，它會從一些預設的轉換表開始。但是，它會使用透過的每個符號來更新該表。

讓壓縮器和解壓縮器使用相同的程式碼字

為了實現無失真壓縮，當壓縮器用位元串“010”表示位元組“e”時，解壓縮器必須以某種方式知道位元串“010”必須被解碼為位元組“e”。

霍夫曼解壓縮器有幾種方法可以“知道”相應霍夫曼壓縮器使用的符號到位元串對映（有時稱為“頻率表”）

• 固定霍夫曼程式碼，硬編碼到解壓縮器中。避免傳送頻率表，但如果實際機率分佈與假設機率分佈有很大差異，則可能會導致壓縮效果很差——甚至可能會擴充套件檔案。估計的機率分佈僅在壓縮器軟體更改時更改。這具有最低的延遲——前幾個符號可以立即編碼和傳輸。
• 一個動態霍夫曼程式碼，在檔案之前傳送一個頻率表。這要求壓縮器在生成和傳送第一個壓縮程式碼字之前儲存整個檔案，該檔案可能任意長，同時計算符號頻率——這具有最差的延遲。估計的機率分佈每個檔案更改一次。
• 幾個動態霍夫曼程式碼，檔案被分成幾個塊，每個塊之前傳送一個頻率表。這比每個檔案一個表具有更低的延遲。在機率分佈從一個塊到另一個塊發生顯著變化的情況下，儲存所有程式碼字所需的總位數可能少得多——但傳送表的位數開銷可能多得多。此外，壓縮器可能花費大量時間試圖透過“最佳化”檔案分割的確切位置來擠出更多位。估計的機率分佈每個塊更改一次。
  • 一些檔案格式（如 bzip2）不是總是傳送一個完整的頻率表來指示下一個塊的確切頻率，而是有時傳送一個對先前傳送的頻率表的簡短引用，該頻率表（希望）足夠接近下一個塊的頻率，以至於該塊中程式碼字的擴充套件（如果有）可以透過不必傳送完整的頻率表來彌補。
• 自適應霍夫曼壓縮：估計的機率分佈每個符號更改（略微）。經過的字母的機率分佈用於估計未來的機率分佈。這具有第二低的延遲——前幾個符號可以或多或少立即傳輸——但解壓縮器在每個符號上會做更多工作來更新表。

每個檔案和每個塊的動態霍夫曼程式碼可以保證某些符號永遠不會出現在一個塊中，因此有些人編寫程式碼完全從樹中消除這些從未出現的符號，從而減少至少一個出現在壓縮文字中的程式碼字的位數。

許多壓縮演算法（包括固定霍夫曼程式碼和自適應霍夫曼壓縮）以一種無法保證某些符號永遠不會出現的方式估計機率。特別是，如果某個符號非常罕見，以至於它尚未出現在訓練文字中——它迄今為止的頻率為零——那麼將估計的零機率分配給該符號就很誘人。這會導致零頻率問題。

規範霍夫曼程式碼

規範霍夫曼程式碼是一種霍夫曼程式碼，它可以非常簡潔地描述。這使得它非常適合靜態霍夫曼壓縮。一個大型文字檔案可能包含數千個部分，每個部分的字母頻率略有不同。如果我們假裝霍夫曼表開銷不重要，那麼為每個部分提供一個最佳化的霍夫曼表將最大限度地減少儲存該部分所需的位數。唉，霍夫曼表開銷通常很重要。許多壓縮器會花費大量時間來考慮，如果我們 (a) 為幾個連續部分中的每一個使用單獨的霍夫曼表或 (b) 將連續部分合併到一個塊中併為整個塊使用一個折衷的霍夫曼表，那麼總檔案是否會更短。

例如，關於 x 射線的文章中字母 x 的頻率遠高於之前關於黃腹啄木鳥的文章。如果我們假裝霍夫曼表開銷不重要，那麼為每個部分提供一個最佳化的霍夫曼表將最大限度地減少儲存該部分所需的位數。唉，霍夫曼表開銷通常很重要。許多壓縮器會花費大量時間來考慮，如果我們 (a) 為幾個連續部分中的每一個使用單獨的霍夫曼表或 (b) 將連續部分合併到一個塊中併為整個塊使用一個折衷的霍夫曼表，那麼總檔案是否會更短。

“刪除一些尾隨的 1，然後遞增”

解壓縮器需要兩件事來重新生成一段明文：壓縮器使用的確切霍夫曼程式碼和一系列壓縮程式碼字。

給定任何一個霍夫曼程式碼，就可以構造許多其他等效程式碼，所有這些程式碼對於任何特定明文符號都具有完全相同的程式碼字長度，但分配給每個明文符號的確切位模式不同。由於任何特定明文符號都被分配了一個特定長度的程式碼字，這個長度對於任何等效程式碼都是相同的，無論你選擇哪個特定程式碼，任何明文符號序列都將被壓縮成一系列具有完全相同總長度的程式碼字。如果字首程式碼描述的開銷微不足道，那麼使用這些眾多等效程式碼中的哪一個並不重要——隨機選擇一個即可。所有等效程式碼都將該資料壓縮到相同數量的位。

但是，與其隨機選擇一個並將其傳送到解壓縮器，不如透過選擇一個特定的規範霍夫曼程式碼來節省字首程式碼描述中的位數。

僅給定任何字首程式碼中每個符號的程式碼字的長度（以位為單位），就可以構造規範霍夫曼程式碼，該程式碼使每個符號都具有與該原始字首程式碼相同的長度。 使程式碼成為規範霍夫曼 (CH) 程式碼的是，程式碼字按其程式碼長度進行字典排序； 給定的一組機率不會導致唯一的 CH 程式碼；可以自由地重新排序具有相同程式碼長度的符號。

建立規範霍夫曼 (CH) 程式碼的步驟如下

1. 構造一個霍夫曼樹，並丟棄除符號和程式碼字長度之外的所有資訊。
2. 按程式碼長度遞增對符號進行排序。
3. 將具有每個程式碼長度的符號數量以及排序後的符號本身儲存起來。

關於樹的一些內容

每個字首程式碼都可以被認為類似於一棵樹。

樹上的每個葉子都標記著明文字母或其他符號。

每個程式碼字的長度（以位為單位）有時被稱為該符號的路徑長度。

動態霍夫曼：儲存頻率表

（這是對“讓壓縮器和解壓縮器使用相同的程式碼字”的延續，用於動態霍夫曼的常見情況）。

在一個典型的壓縮檔案中，每個壓縮資料塊之前都有一個頭部。對於使用動態霍夫曼壓縮的塊，該塊的頭部會告訴解壓縮器該塊中使用的程式碼字集以及程式碼字到明文符號的對映。

通常，壓縮器和解壓縮器會有一些硬編碼的 S 個明文符號的字母表，它們需要處理。通常 S=258 個符號，即 256 個可能的位元組和一些其他特殊符號，例如塊結束符號。字母表中的每個符號在壓縮資料中都由一個程式碼字表示，其長度為 1 到 MAX_CODEWORD_LENGTH 位。

許多簡單的霍夫曼檔案格式只是將這 258 個位長度的列表儲存為 258 個位元組的塊。每個位置代表一個明文符號——即使那些從未在明文中使用過的符號——通常位置 0 代表 0 位元組，位置 32 (0x20) 代表空格字元，位置 __ (0x65) 代表字母 'e'，位置 255 代表 255 位元組，位置 256 代表一些特殊命令，位置 257 代表塊結束指示符。

每個位置的數字代表與該明文符號對應的程式碼字的長度，以位為單位。(由於我們使用規範霍夫曼程式碼，與每個明文符號對應的程式碼字的長度是解壓縮器重新生成該塊中使用的實際程式碼字集所需的一切)。通常，"0 位"的特殊"長度"被保留用於指示該塊中從未出現過的字母，因此不應包含在霍夫曼樹中。

這個 S 個數字的列表通常被稱為"頻率表"。有時這個 S 個數字的列表被稱為"克拉夫特向量"，因為它必須滿足w:克拉夫特不等式。

頭部中的這 258 個位元組的塊代表了大量的開銷，尤其是如果壓縮檔案包含許多獨立的塊，每個塊都有自己的頭部。一些霍夫曼壓縮器，例如面向英文單詞的霍夫曼壓縮器，使用大量的符號(英文詞典中每個單詞一個)，需要更長的克拉夫特向量。可以透過設計檔案格式來減少此塊的大小，從而以多種方式獲得更小的壓縮檔案大小，包括

• 使用完全相同的程式碼字到明文符號動態霍夫曼對映，但以更緊湊的形式儲存該對映
  • 使用某種長度限制的霍夫曼壓縮。如果沒有比 15 位更長的程式碼字，那麼我們可以將每個長度儲存在 4 位中，而不是完整的 8 位位元組。
  • 單獨壓縮頻率表，可能使用 RLE 或一些變長程式碼，例如固定霍夫曼壓縮，甚至另一個動態霍夫曼"預表"。
  • 當資料檔案在兩種資料之間交替出現時——例如，英文文字和長數字表——使用簡單的差分壓縮來緊湊地表示後面的表作為對前面某個表的引用，就像 bzip2 中一樣。
  • 當一個數據塊的頻率略微不同於前一個塊時——例如，一篇關於 X 光的文章的字母頻率大致相同，但比一篇關於黃腹吸汁鳥的文章的 'X' 多得多，而 'y' 則少一些——使用差分壓縮來緊湊地表示新表，方法是給出與前一個表的(希望相對較小的)變化，就像 LZX 中一樣。我們在後面的章節資料差異中討論其他型別的差分壓縮。
  • 或以上幾種方法的組合。
• 使用除動態霍夫曼對映以外的其他程式碼字到明文符號對映
  • 自適應霍夫曼：根據已在明文中解碼的字母，動態地估計未來的字母頻率
  • 通用程式碼：...

實現技巧

人們花了很多時間來找出使霍夫曼壓縮和霍夫曼解壓縮真正快速的方法。這些只是用來使解壓縮器(或壓縮器，或兩者)能夠給出與非最佳化程式相同輸出的相同位，同時執行得更快的一些技術。

實現霍夫曼解壓縮器的軟體通常包含 2 個部分

• 設定部分會提取一個緊湊的"頻率表"頭部，並將其擴充套件成某種型別的查詢表，以便使下一部分真正快速
• 將程式碼字轉換為明文符號的內部迴圈。

霍夫曼解壓縮器的內部迴圈會找到與壓縮文字的下一部分匹配的程式碼字，併發出相應的明文符號。即使壓縮 7 位 ASCII 文字，程式碼字也可能超過 32 位長，對齊位並比較如此長的字可能有點麻煩。有三種方法可以避免如此長的比較：(a) 長度限制的霍夫曼程式碼。通常"自然"檔案從未使用過如此長的程式碼字，只有專門設計的，旨在作為最壞情況檔案的程式碼字。一些壓縮器選擇故意將霍夫曼程式碼字的長度限制為某個最大長度。這使得這些最壞情況檔案在壓縮後，比沒有限制時略微長一些；它對壓縮"自然"檔案的長度沒有影響。大多數旨在在硬體中解壓縮的檔案格式(使用 FPGA 解壓縮的影片等)會限制長度，以降低硬體成本。(b) 一個用於處理短程式碼字的短而快的表，並具有一個"長程式碼字"標誌，以及其他用於處理長程式碼字的表。由於最頻繁的霍夫曼程式碼很短，因此解碼器通常可以使用一次對完全適合快取的短而快的表的查詢來快速解碼程式碼字；偶爾解碼器會命中一個帶標記的條目，並且需要花更多時間在其他表中查詢長程式碼。(c) 而不是直接與程式碼字位串進行比較，首先進行一個零計數(到下一個 1 位，或到檔案末尾，以先到者為準)，找到 Z 個零，丟棄這個 1 位，然後是接下來的 n 位。

字首程式碼解壓縮器實現可以透過它們從壓縮流中讀取的位數以及它們如何使用這些位來決定下一步來區分。人們已經透過多種方式實現了"快速"解壓縮器，包括

• 一次一位：一個"簡單"的字首解碼器通常從壓縮流中逐位讀取，一次一位。這可能是最慢的方式。
• 始終一次 max_codelength 位：一個大型查詢表，直接由從壓縮流中讀取的多個位索引
• 一次一個位元組(8 位)：一個大型查詢表，直接由"樹位置"狀態和從壓縮流中讀取的位元組索引
• X 個初始位，然後是 Y 個後續位，每個符號(其中 X 是一個常數，通常選擇為 max_codelength 的一半位數，而 Y 通常根據在最初 X 位中讀取的特定值而變化；X+Y 最多為 max_codelength)
  • 一個由從壓縮流中讀取的某些位索引的第一個查詢表，它會選擇一個由從壓縮流中讀取的更多位索引的第二個索引表
• 任意數量的零位，然後是 F 個尾隨位：(這對規範霍夫曼程式碼有效，但可能對其他字首程式碼沒有用)。
  • 一個大型查詢表，由從壓縮流中讀取的零計數和位索引
  • 一個由壓縮流中的位零計數索引的第一個查詢表，它會選擇一個由從壓縮流中讀取的更多位索引的第二個索引表。

在概念上，最簡單的一個是"一個大型查詢表"方法

• 一個大型查詢表

如果您的最大程式碼長度相對較短，這可能是最快的方法。

一個快速字首程式碼解碼器的快速內部迴圈會一次讀取壓縮資料一個位元組(而不是"簡單"字首解碼器的逐位讀取)。"當前樹位置"和壓縮位元組被用作一個大型表的索引，該表儲存生成的"新樹位置"以及最多 8 個解壓縮的明文符號。

• (new_tree_position, [解壓縮的符號列表]) := lookup_table( current_tree_position, compressed_byte )

任何程式碼字都可以用兩個數字(Z 個初始零的計數，F 個尾隨位的數值)表示。例如，程式碼字"000101"可以用兩個值(3,5)表示。程式碼字"11"可以用兩個值(0,3)表示。

規範霍夫曼程式碼的一個特點是，如果所有明文符號都適合 n 位固定長度程式碼，那麼 Z 可以用 n 位表示，F 也可以用 n 位儲存。(這*不適用於*所有字首程式碼)。(當解壓縮器在壓縮文字中實際進行零計數時，連續的全零程式碼字會導致無限數量的連續零——我在這裡試圖指出的是，任何一個特定程式碼字中初始零的數量可以用 n 位表示)。這允許幾個不同的時間/速度權衡，它們都給出完全相同的輸出檔案。可能最快的內部迴圈類似於以下操作：對於每個符號

• 將零計數到 Z
• 丟棄接下來的 1 位，使"下一個要讀取的位"指標指向*接下來的*位，但提前檢視接下來的 n-1 位並將它們放入 F 中。
• 將 Z 的最低有效 n 位和 F 的 n-1 位打包到 2n-1 位索引中。
• (plaintext_symbol, useful_bits) := lookup_table[index]
• 將"下一個要讀取的位"指標移動 useful_bits 位——對於只有程式碼字中零之後的 1 位的程式碼字(1, 01, 001, 0001 等)可以是 0 位，對於程式碼字中零後的第一個 1 位後面的完整 n-1 位的程式碼字可以是 n-1 位。
• 發出明文符號。

重複此過程，直到我們遇到檔案末尾。

這忽略了全零碼字的特殊情況處理。許多哈夫曼編碼器，例如 DEFLATE，設計了一個具有“偽”條目的哈夫曼表，這樣壓縮後的文字永遠不會使用全零碼字；因此解壓縮器永遠不必處理這種複雜情況。這還忽略了對對映到某些特殊命令而不是對映到文字明文符號的碼字的特殊處理。這需要一個大小為 2^(2n-1) 的查詢表。對於一個典型的哈夫曼程式碼，其中 n=9 位，能夠處理所有 2^8 位元組和一些其他特殊符號，使用這種實現型別的規範哈夫曼程式碼需要一個大小為 2^(17) = 131 072 個條目的查詢表。如果一個明文符號被對映到一個比最大碼長更小的碼長，那麼該表中的多個條目會對映到同一個符號。還有其他實現方式，它們使用的 RAM 少得多。其他實現甚至可能更快，因為它們允許更多的工作記憶體適合快取。

通常，對於alphabet_size個明文符號，最壞情況下的最大“壓縮”哈夫曼碼長度為alphabet_size - 1位。

對於 257 個明文符號，最壞（不太可能）的情況是最大位長為 2 個字元，它們被“壓縮”為 256 位，因此最大零計數（除了當我們有 1 個或多個連續的全零程式碼時）為 255。

處理文字結束通常很麻煩，因為壓縮的位字串通常儲存在某個整數個位元組中，即使壓縮的位字串通常*不*是 8 位的倍數。大多數哈夫曼解壓縮器使用以下兩種技術之一來處理文字結束

• 壓縮器和解壓縮器都在樹中包含一個特殊的文字結束符號（在進行二進位制位元組定向壓縮時為第 257 個符號，或者在壓縮以 null 結尾的 C 字串時為 null 位元組）。由於它只出現一次，它的頻率為 1，因此表示它的程式碼在長度上與一個或多個最長可能的長度符號繫結在一起。
  • 解壓縮器在看到文字結束符號時立即返回，並忽略該符號之後的任何填充位，這些位填充了最後一個儲存位元組。或者，
  • 壓縮器告訴解壓縮器使用多少個有效輸入位元組來儲存壓縮的位字串。解壓縮器強制表示文字結束符號的程式碼為全零符號。解壓縮器模擬在最後一個有效輸入位元組之後讀取零位——可能在某些其他有效符號的末尾讀取一些零位——最終讀取全零文字結束符號。
• 一些解壓縮器沒有特殊的文字結束符號。
  • 壓縮器告訴解壓縮器輸入壓縮位字串表示多少個輸出符號，並且解壓縮器在發出正好那麼多符號後立即返回。或者，
  • 壓縮器告訴解壓縮器使用多少個有效輸入位元組來儲存輸入壓縮位字串。有時最後一個有效符號在最後一個位元組的末尾乾淨地結束，並且解壓縮器返回。其他時候，有一些剩餘位不夠長，無法構成完整的有效碼字——所有具有該字首的碼字都更長。當剩餘位全部為零時，丟棄這些剩餘的零位並返回。（這種技術*假設*全零程式碼至少有 8 位長——當樹中至少有 2^7+1 = 129 個符號並且使用規範哈夫曼程式碼時，這總是正確的。如果您少於 129 個符號，您必須使用其他技術來處理文字結束）。

改進哈夫曼

原始的哈夫曼演算法對於對具有已知機率分佈的無關符號流進行符號級編碼是最佳的。

但是，可以使用幾種演算法來壓縮比哈夫曼演算法更小的某些型別的檔案。這些演算法利用哈夫曼最優性證明中的一種或多種注意事項

• 無關符號：大多數真實資料檔案在符號之間存在一些互資訊。可以透過“去相關”符號，然後對這些去相關符號使用哈夫曼演算法，從而比純哈夫曼做得更好。
• 符號級：一些壓縮演算法，例如範圍編碼，透過放寬二進位制哈夫曼的限制，即每個輸入符號必須編碼為整數個位，從而比二進位制哈夫曼提供更好的壓縮。
• 已知機率分佈：通常接收器不知道確切的機率分佈。因此，典型的哈夫曼壓縮演算法首先發送頻率表，然後傳送壓縮資料。一些“自適應”壓縮演算法，例如極性樹編碼，可以比哈夫曼獲得更好的壓縮，因為它們收斂到機率分佈，或者適應不斷變化的機率分佈，而無需明確傳送頻率表。

這讓人想起許多演算法壓縮比“最佳”固定位長編碼碼字長度 更小的檔案的方式，方法是利用固定位長編碼最優性證明中的注意事項

固定位長編碼對於將具有已知有限字母大小 A 的符號流符號級編碼到固定長度的碼字中是最佳的。固定位長編碼的最佳碼字長度為 $L=\left\lceil log_{2}A\right\rceil$.

• 有限字母：固定位長編碼對於無限字母是無用的；“通用程式碼”（如下所述）可以輕鬆地處理此類字母。
• 符號級：一些壓縮演算法，例如 LZW，具有比固定位長編碼更好的壓縮效果的固定長度碼字，方法是使用一些碼字來表示符號對或更長的符號字串。
• 固定長度碼字：可變長度程式碼通常提供更好的壓縮效果。

字首碼

哈夫曼編碼、夏農-範諾編碼和極性樹編碼都將一些相對較小的已知符號字母對映到字首碼。

“通用程式碼”將無限大的已知字母——通常是所有正整數的集合，或所有整數的集合——對映到字首程式碼。

通用程式碼

存在許多“通用程式碼”，它們是一種字首程式碼。

任何特定的字首程式碼（包括任何通用程式碼）都可以看作是針對特定對應頻率分佈的某種哈夫曼程式碼。

典型的音訊資料和典型的音訊資料預測殘差大約具有拉普拉斯分佈。影像壓縮和幾何壓縮的預測誤差編碼通常會產生近似於拉普拉斯分佈的結果。 使用一般哈夫曼程式碼對拉普拉斯分佈進行編碼會得到一個字首程式碼，該程式碼等效於使用戈倫布程式碼。戈倫布程式碼比一般哈夫曼程式碼更簡單、更快地進行壓縮和解壓縮。如果音訊資料“足夠接近”拉普拉斯分佈，則戈倫布程式碼可能會提供比一般哈夫曼程式碼更好的網路壓縮效果，因為戈倫布解碼器只需要 1 個引數的開銷，而一般哈夫曼解碼器則需要一個機率哈夫曼表的開銷。

萊斯編碼是戈倫布編碼的一個子集，它在壓縮和解壓縮方面速度更快。由於萊斯程式碼非常接近拉普拉斯分佈的哈夫曼程式碼，因此它們的壓縮效果幾乎與一般哈夫曼程式碼一樣好。

待辦事項：新增一些關於斐波那契程式碼（一種“通用程式碼”）的文字。

音訊壓縮

傅立葉變換

感知編碼

“Gerzon/Craven 定理表明，最優去相關訊號的電平由原始訊號譜的平均值給出，當以 dB 對線性頻率作圖時。... 此 dB 平均值可能比原始訊號具有明顯更小的功率，因此資料速率降低。... 在實踐中，任何一段音樂資料可以“白化”的程度取決於內容和預測濾波器中允許的複雜性。”

典型的音訊資料和典型的音訊資料預測殘差（去相關後）大約具有拉普拉斯分佈，因此它們通常使用戈倫布解碼器或萊斯解碼器而不是一般哈夫曼解碼器進行解碼。

一些音訊解碼器可以被告知在使用它們壓縮效果良好的音樂段落中使用萊斯解碼器，並在稍後被告知在使用萊斯解碼器壓縮效果不佳的音樂段落（例如純正弦波音調或所有值等機率的白噪聲）中切換到其他解碼器。

在一些音訊應用中，特別是雙向電話通訊，端到端延遲至關重要。電話服務的推薦最大時延為 150 毫秒(Wikipedia:1 E-1 s)。這排除了許多流行的壓縮演算法。我們將在本書的 Data_Compression/Evaluating_Compression_Effectiveness#latency 部分更詳細地討論延遲。

算術編碼

算術編碼

上下文自適應二進位制算術編碼

...

組合

參見 資料壓縮/多重變換