資料壓縮算法—1入門介紹

  資料壓縮，大多數都是涉及算法概念。我們可以通過下圖可以明确資料壓縮領域所涉及的方面。

  首先壓縮算法分為無損壓縮和有損壓縮；

  無損壓縮通過應用于檔案和文本中，主要是熵編碼法和字典編碼，熵編碼中最實用最流行的是霍夫曼編碼的變種，字典編碼最實用最流行的是LZ77和snappy；

  有損壓縮主要應用于音頻、圖像和視訊中，基于傅裡葉變換、小波變換、離散餘弦變換等進行資料降采樣，減少資料量，而後會采用霍夫曼編碼的變種等無損壓縮算法。

  文本會繼續更新各種無損、有損算法原理及其使用例程。

  https://zh.wikipedia.org/wiki/資料壓縮

無損壓縮算法

  無損壓縮算法設計：對原始資料在單字元、單詞或詞組等不同機關上出現的頻率建構統計模型，然後将頻率最高的機關編碼成最短的編碼，但最短的編碼永遠小于整條資訊的熵，即整條資訊所需的位數。

  

什麼是熵

  資料壓縮不僅起源于 40 年代由 Claude Shannon 首創的資訊論，而且其基本原理即資訊究竟能被壓縮到多小，至今依然遵循資訊論中的一條定理，這條定理借用了熱力學中的名詞“熵”( Entropy )來表示一條資訊中真正需要編碼的資訊量：

  考慮用 0 和 1 組成的二進制數位為含有 n 個符号的某條資訊編碼，假設符号 Fn 在整條資訊中重複出現的機率為 Pn，則該符号的熵也即表示該符号所需的位數位為：

  En = - log2( Pn )

  整條資訊的熵也即表示整條資訊所需的位數為：E = ∑En

  舉個例子，對下面這條隻出現了 a b c 三個字元的字元串：

  aabbaccbaa

  字元串長度為 10，字元 a b c 分别出現了 5 3 2 次，則 a b c 在資訊中出現的機率分别為 0.5 0.3 0.2，他們的熵分别為：

  Ea = -log2(0.5) = 1

  Eb = -log2(0.3) = 1.737

  Ec = -log2(0.2) = 2.322

  整條資訊的熵也即表達整個字元串需要的位數為：

  E = Ea * 5 + Eb * 3 + Ec * 2 = 14.855 位

  回想一下如果用計算機中常用的 ASCII 編碼，表示上面的字元串我們需要整整 80 位呢！現在知道資訊為什麼能被壓縮而不丢失原有的資訊内容了吧。簡單地講，用較少的位數表示較頻繁出現的符号，這就是資料壓縮的基本準則。

  細心的讀者馬上會想到，我們該怎樣用 0 1 這樣的二進制數位表示零點幾個二進制位呢？确實很困難，但不是沒有辦法。一旦我們找到了準确表示零點幾個二進制位的方法，我們就有權利向無損壓縮的極限挑戰了。

  

模型

  從上面的描述，我們明白，要壓縮一條資訊，首先要分析清楚資訊中每個符号出現的機率。不同的壓縮程式通過不同的方法确定符号的出現機率，對符号的機率計算得越準确，也就越容易得到好的壓縮效果。在壓縮程式中，用來處理輸入資訊，計算符号的機率并決定輸出哪個或哪些代碼的子產品叫做模型。

  難道對資訊中字元的出現機率這麼難以估計以至于有各種不同的壓縮模型嗎？對上面的字元串我們不是很容易就知道每個字元的機率了嗎？是的是的，不過上面的字元串僅有 10 個字元長呀，那隻是例子而已。考慮我們現實中要壓縮的檔案，大多數可是有幾十 K 甚至幾百 K 長，幾 M 位元組的檔案不是也屢見不鮮嗎？

  是的，我們可以預先掃描檔案中的所有字元，統計出每個字元出現的機率，這種方法在壓縮術語裡叫做**“靜态統計模型”。但是，不同的檔案中，字元有不同的分布機率，我們要麼先花上大量的時間統計我們要壓縮的所有檔案中的字元機率，要麼為每一個單獨的檔案儲存一份機率表以備解壓縮時需要。糟糕的是，不但掃描檔案要消耗大量時間，而且儲存一份機率表也使壓縮後的檔案增大了不少。是以，在實際應用中，“靜态統計模型”應用的很少。

  真正的壓縮程式中使用的大多是一種叫“自适應模型”的東西。自适應模型可以說是一台具有學習功能的自動機。他在資訊被輸入之前對資訊内容一無所知并假定每個字元的出現機率均等，随着字元不斷被輸入和編碼，他統計并紀錄已經出現過的字元的機率并将這些機率應用于對後續字元的編碼。也就是說，自适應模型在壓縮開始時壓縮效果并不理想，但随着壓縮的進行，他會越來越接近字元機率的準确值，并達到理想的壓縮效果。自适應模型還可以适應輸入資訊中字元分布的突然變化，可以适應不同的檔案中的字元分布而不需要儲存機率表。

  上面提到的模型可以統稱為“統計模型”**，因為他們都是基于對每個字元出現次數的統計得到字元機率的。另一大類模型叫做“字典模型”。實際上，當我們在生活中提到“工行”這個詞的時候，我們都知道其意思是指“中國工商銀行”，類似的例子還有不少，但共同的前提是我們心中都有一本約定俗成的縮寫字典。字典模型也是如此，他并不直接計算字元出現的機率，而是使用一本字典，随着輸入資訊的讀入，模型找出輸入資訊在字典中比對的最長的字元串，然後輸出該字元串在字典中的索引資訊。比對越長，壓縮效果越好。事實上，字典模型本質上仍然是基于對字元機率的計算的，隻不過，字典模型使用整個字元串的比對代替了對某一字元重複次數的統計。可以證明，字典模型得到的壓縮效果仍然無法突破熵的極限。

  當然，對通用的壓縮程式來說，儲存一本大字典所需的空間仍然是無法讓人忍受的，況且，任何一本預先定義的字典都無法适應不同檔案中資料的變化情況。對了，字典模型也有相應的“自适應”方案。我們可以随着資訊的不斷輸入，從已經輸入的資訊中建立合适的字典，并不斷更新這本字典，以适應資料的不斷變化。

  讓我們從另一個角度了解一下自适應模型。Cluade Shannon 曾試圖通過一個“聚會遊戲”(party game)來測定英語的真實資訊容量。他每次向聽衆公布一條被他隐藏起一個字元的消息，讓聽衆來猜下一個字元是什麼，一次猜一個，直到猜對為止。然後，Shannon 使用猜測次數來确定整個資訊的熵。在這個實驗中，一種根據前面出現過的字元估計下一個字元機率的模型就存在于聽衆的頭腦中，比計算機中使用的自适應模型更為進階的是，聽衆除了根據字元出現過的次數外，還可以根據他們對語言的經驗進行猜測。

  

編碼

  通過模型，我們已經确定了對某一個符号該用多少位二進制數進行編碼。現在的問題是，如何設計一種編碼方案，使其盡量精确地用模型計算出來的位數表示某個符号。

  最先被考慮的問題是，如果對 a 用 3 個二進制位就可以表示，而對 b 用 4 個二進制位就可以表示，那麼，在解碼時，面對一連串的二進制流，我怎麼知道哪三個位是 a，哪四個位是 b 呢？是以，必須設計出一種編碼方式，使得解碼程式可以友善地分離每個字元的編碼部分。于是有了一種叫**“字首編碼”**的技術。該技術的主導思想是，任何一個字元的編碼，都不是另一個字元編碼的字首。反過來說就是，任何一個字元的編碼，都不是由另一個字元的編碼加上若幹位 0 或 1 組成。

  看一下字首編碼的一個最簡單的例子：

  符号 編碼

  A  0

  B  10

  C  110

  D  1110

  E  11110

  有了上面的碼表，你一定可以輕松地從下面這串二進制流中分辨出真正的資訊内容了：

  1110010101110110111100010 - DABBDCEAAB

  下一個問題是：象上面這樣的字首編碼隻能表示整數位的符号，對幾點幾位的符号隻能用近似的整數位輸出，那麼怎樣輸出小數位數呢？科學家們用算術編碼解決了這個問題。

  

總結一下

  不同的模型使用不同的方法計算字元的出現機率，由此機率可以得出字元的熵；然後使用不同的編碼方法，盡量接近我們期望得到的熵值。是以，壓縮效果的好壞一方面取決于模型能否準确地得到字元機率，另一方面也取決于編碼方法能否準确地用期望的位數輸出字元代碼。換句話說，壓縮 = 模型 + 編碼。如下圖所示：

      符号      機率      代碼

  輸入 ---------------> 模型 ---------------> 編碼 ---------------> 輸出