數據壓縮不僅起源於 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 字節的文件不是也屢見不鮮嗎?
是的,我們可以預先掃描文件中的所有字符,統計出每個字符出現的概率,這種方法在壓縮術語裏叫做“靜態統計模型”。但是,不同的文件中,字符有不同的分布概率,我們要麽先花上大量的時間統計我們要壓縮的所有文件中的字符概率,要麽為每壹個單獨的文件保存壹份概率表以備解壓縮時需要。糟糕的是,不但掃描文件要消耗大量時間,而且保存壹份概率表也使壓縮後的文件增大了不少。所以,在實際應用中,“靜態統計模型”應用的很少。
真正的壓縮程序中使用的大多是壹種叫“自適應模型”的東西。自適應模型可以說是壹臺具有學習功能的自動機。他在信息被輸入之前對信息內容壹無所知並假定每個字符的出現概率均等,隨著字符不斷被輸入和編碼,他統計並紀錄已經出現過的字符的概率並將這些概率應用於對後續字符的編碼。也就是說,自適應模型在壓縮開始時壓縮效果並不理想,但隨著壓縮的進行,他會越來越接近字符概率的準確值,並達到理想的壓縮效果。自適應模型還可以適應輸入信息中字符分布的突然變化,可以適應不同的文件中的字符分布而不需要保存概率表。
上面提到的模型可以統稱為“統計模型”,因為他們都是基於對每個字符出現次數的統計得到字符概率的。另壹大類模型叫做“字典模型”。實際上,當我們在生活中提到“工行”這個詞的時候,我們都知道其意思是指“中國工商銀行”,類似的例子還有不少,但***同的前提是我們心中都有壹本約定俗成的縮寫字典。字典模型也是如此,他並不直接計算字符出現的概率,而是使用壹本字典,隨著輸入信息的讀入,模型找出輸入信息在字典中匹配的最長的字符串,然後輸出該字符串在字典中的索引信息。匹配越長,壓縮效果越好。事實上,字典模型本質上仍然是基於對字符概率的計算的,只不過,字典模型使用整個字符串的匹配代替了對某壹字符重復次數的統計。可以證明,字典模型得到的壓縮效果仍然無法突破熵的極限。
當然,對通用的壓縮程序來說,保存壹本大字典所需的空間仍然是無法讓人忍受的,況且,任何壹本預先定義的字典都無法適應不同文件中數據的變化情況。對了,字典模型也有相應的“自適應”方案。我們可以隨著信息的不斷輸入,從已經輸入的信息中建立合