資料壓縮/馬爾可夫模型
馬爾可夫演算法是資料壓縮演算法，其具有馬爾可夫假設：明文是由可以被馬爾可夫模型近似的東西生成的——即馬爾可夫鏈、隱馬爾可夫模型、變階馬爾可夫模型或類似的東西。
字典演算法總是可以被馬爾可夫演算法模擬，但反過來則不行。 [1]
完全通用的馬爾可夫模型被用於一些最複雜的演算法，這些演算法具有已知的最佳壓縮率——可惜的是，它們也是使用中最慢的演算法。
也許最簡單的馬爾可夫演算法是 PPP 預測壓縮協議，由 Timo Raita 實現並由 RFC 1978 標準化。 [2]
它檢視（大約）最近解碼的 3 或 4 個位元組，找到該序列最後一次出現的時間，並猜測下一個位元組將與上次相同的後續位元組相同。
預測解壓縮器的內部迴圈類似於這樣
- 預測解碼器讀取一個標誌位元組，其中包含 8 個標誌。每個標誌位對應一個重建的解壓縮資料位元組。
- 對於 8 個標誌位中的每一個
- 如果標誌位為 0，則猜測錯誤。預測解碼器從壓縮資料中讀取一個字面位元組，並將其直接傳遞到解壓縮文字中。同時將該字面位元組儲存在 GuessTable[context] 中，這樣下次可能發生這種情況時，我們就會猜對了。
- 如果標誌位為 1，則猜測正確。從 GuessTable[context] 讀取猜測並將其寫入解壓縮文字中。
- 從我們剛剛寫入解壓縮文字的位元組更新上下文。
- 重複直到沒有更多壓縮位元組可讀取。
在任何給定的上下文中，一個位元組值是最有可能的下一個位元組。預測器將該最有可能的下一個位元組壓縮為 1 位。當出現任何其他位元組時，預測器將其擴充套件為 9 位。即使預測器有一半的時間猜錯，它也可以獲得相當好的壓縮效果。
一階馬爾可夫解壓縮演算法比預測演算法更復雜一些。
解壓縮某個位元組後，一階馬爾可夫解壓縮器會檢視該位元組之前出現過的所有時間。 [3] 在任何給定的 1 位元組上下文中，一個位元組值是最有可能的下一個位元組；某個其他位元組值是下一個最有可能的下一個位元組......等等；通常有幾個位元組在該上下文中只出現過一次——這些是最不可能的下一個位元組值；通常有幾個位元組從未在該上下文中出現過——這些是最不可能的下一個位元組值。
一階馬爾可夫解壓縮器使用一些熵編碼器為每個可能的下一個位元組值分配一個唯一的程式碼字首，使得更可能的位元組被分配一個較短的程式碼字，不太可能的位元組被分配一個較長的程式碼字（可能為 8 位），最不可能的位元組被分配一個更長的程式碼字（超過 8 位）。
在某些情況下，下一個位元組極有可能是一個特定位元組（例如，在英文文字中，'q' 之後的位元組幾乎總是 'u'），一階馬爾可夫壓縮這些情況與預測演算法一樣好。在其他情況下，馬爾可夫壓縮比預測演算法好得多，因為它即使在位元組不完全是最有可能的位元組時也能壓縮“可能”的位元組。
更高階的字母級和單詞級馬爾可夫鏈更擅長預測“可能”的英語短語。有些人透過允許他們構建馬爾可夫鏈來建立“模仿生成器”，但他們不是將特定壓縮程式碼字饋送到解碼器以使馬爾可夫解碼器有足夠的線索來重建某個特定明文，而是將隨機生成的位饋送到馬爾可夫解碼器。 [4]
具有最佳壓縮率的解壓縮演算法通常使用幾種不同的模型，每個模型都對下一個位或位元組進行預測，然後以某種方式將這些預測混合在一起，以獲得最終預測並將其饋送到熵編碼器。只要最終預測不為零或一（永不發生或總是發生），解壓縮器就可以無錯誤地解碼所有檔案（有關詳細資訊，請參閱 零頻率問題）。
可惜的是，到目前為止，我們還沒有找到將這些預測組合在一起的“最佳”方法。人們已經開發了幾種臨時方法來混合預測。一些混合技術似乎“更好”，因為它們產生的壓縮檔案比其他混合技術更小（並且比單獨使用任何一個底層預測更好）。
在我們進入實際的“上下文混合”演算法之前，讓我們看一下 PPM 和 DMC，它們直接使用一個或另一個上下文的預測（而不是混合預測）
部分匹配預測 [5] 也許是最容易理解的混合技術。PPM 保持著不同階數的馬爾可夫模型。PPM(5) 解碼器儘可能使用 5 階馬爾可夫模型。如果無法基於所有 5 個上下文符號進行預測——即最近解碼的 5 個位元組以前從未以該順序出現過——則它會回退到 4 階馬爾可夫模型。如果 4 階模型無法進行預測——即最近解碼的 4 個位元組以前從未以該順序出現過——則它會回退到 3 階馬爾可夫模型。PPM 解碼器最終會找到可以用來壓縮文字的馬爾可夫模型，即使它不得不一直回退到預設的零階馬爾可夫模型。
動態馬爾可夫壓縮是由 Gordon Cormack 和 Nigel Horspool 開發的。 [6] Gordon Cormack 在 1993 年釋出了他用 C 語言編寫的 DMC 實現，並使用非商業許可證。 [7] 動態馬爾可夫壓縮是一種無損資料壓縮演算法，與 PPM 非常相似，但它一次預測一位，而不是一次預測一個位元組。這使其速度變慢，但可以實現略微更好的壓縮。它被用作幾種高度實驗性實現中的模型或子模型。
預測被饋送到算術編碼器中。（因為預測是逐位進行的，所以簡單的霍夫曼編碼而不是算術編碼將不會產生任何壓縮）。
一些模型混合/上下文混合方法包括
上下文樹加權 [8] 是另一種混合技術。
- ↑ Ross Williams. "LZRW4: ZIV AND LEMPEL MEET MARKOV". 1991.
- ↑ RFC 1978
- ↑ 與其逐位元組掃描整個明文，大多數程式設計師使用一種速度快得多的方法，得到相同的結果：程式在解壓縮每個位元組時更新內部雜湊表或二維陣列，然後從該資料結構中直接獲取下一個位元組所需的資料。
- ↑ Jon Bentley. "Generating Text" (Programming Pearls 的第 15.3 節) 2000.
- ↑ 維基百科：部分匹配預測
- ↑ 維基百科：動態馬爾可夫壓縮
- ↑ Gordon V. Cormack. "Dynamic Markov Compression. (DMC) Version 0.0.0". 1993. dmc.c
- ↑ 維基百科：上下文樹加權