數據壓縮與信息熵

    1992 年，美國佐治亞州的 WEB Technology 公司，宣布做出了重大的技術突破。

        該公司的 DataFiles/16 軟件，號稱可以將任意大于 64KB 的文件，壓縮為原始大小的 16 分之一。業界議論紛紛，如果消息屬實，無異于壓縮技術的革命。

        許多專家還沒有看到軟件，就斷言這是不可能的。因為根據壓縮原理，你不可能將任意文件壓縮到 16 分之一。事實上，有一些文件是無法壓縮的，哪怕一個二進制位，都壓縮不掉。

        后來，事實果然如此，這款軟件從來沒有正式發布。沒過幾年，就連 WEB Technology 公司都消失了。

        那么，為何不是所有的文件都可以被壓縮？是否存在一個壓縮極限呢，也就是說，到了一定大小，就沒法再壓縮了？

        一、壓縮的有限性

        首先，回答第一個問題：為什么 WEB Technology 公司的發明不可能是真的。

        反證法可以輕易地證明這一點。假定任何文件都可以壓縮到n個二進制位（bit）以內，那么最多有2ⁿ種不同的壓縮結果。也就是說，如果有2ⁿ+1 個文件，必然至少有兩個文件會產生同樣的壓縮結果。這意味著，這兩個文件不可能無損地還原（解壓縮）。因此，得到證明，并非所有文件都可以壓縮到n個二進制位以下。

        很自然地，下一個問題就是，這個n到底是多少？

        二、壓縮原理

        要回答一個文件最小可以壓縮到多少，必須要知道壓縮的原理。

        壓縮原理其實很簡單，就是找出那些重復出現的字符串，然后用更短的符號代替，從而達到縮短字符串的目的。比如，有一篇文章大量使用"中華人民共 和國"這個詞語，我們用"中國"代替，就縮短了 5 個字符，如果用"華"代替，就縮短了 6 個字符。事實上，只要保證對應關系，可以用任意字符代替那些重復出現的字符串。

        本質上，所謂"壓縮"就是找出文件內容的概率分布，將那些出現概率高的部分代替成更短的形式。所以，內容越是重復的文件，就可以壓縮地越小。比如，"ABABABABABABAB"可以壓縮成"7AB"。

        相應地，如果內容毫無重復，就很難壓縮。極端情況就是，遇到那些均勻分布的隨機字符串，往往連一個字符都壓縮不了。比如，任意排列的 10 個阿拉伯數字（5271839406），就是無法壓縮的；再比如，無理數（比如π）也很難壓縮。

        壓縮就是一個消除冗余的過程，相當于用一種更精簡的形式，表達相同的內容。可以想象，壓縮過一次以后，文件中的重復字符串將大幅減少。好的壓縮算法，可以將冗余降到最低，以至于再也沒有辦法進一步壓縮。所以，壓縮已經壓縮過的文件（遞歸壓縮），通常是沒有意義的。

        三、壓縮的極限

        知道了壓縮原理之后，就可以計算壓縮的極限了。

        上一節說過，壓縮可以分解成兩個步驟。第一步是得到文件內容的概率分布，哪些部分出現的次數多，哪些部分出現的次數少；第二步是對文件進行編碼，用較短的符號替代那些重復出現的部分。

        第一步的概率分布一般是確定的，現在就來考慮第二步，怎樣找到最短的符號作為替代符。

        如果文件內容只有兩種情況（比如扔硬幣的結果），那么只要一個二進制位就夠了，1 表示正面，0 表示表示負面。如果文件內容包含三種情況（比如球賽的結果），那么最少需要兩個二進制位。如果文件內容包含六種情況（比如扔篩子的結果），那么最少需要三個二進制位。

        一般來說，在均勻分布的情況下，假定一個字符（或字符串）在文件中出現的概率是p，那么在這個位置上最多可能出現1/p種情況。需要 log₂(1/p)個二進制位表示替代符號。

        這個結論可以推廣到一般情況。假定文件有n個部分組成，每個部分的內容在文件中的出現概率分別為p₁、p₂、...p_n。那么，替代符號占據的二進制最少為下面這個式子。

log₂(1/p₁) + log₂(1/p₂) + ... + log₂(1/p_n)

= ∑ log₂(1/p_n)

</blockquote>

        這可以被看作一個文件的壓縮極限。

        四、信息熵的公式

        上一節的公式給出了文件壓縮的極限。對于n相等的兩個文件，概率p決定了這個式子的大小。p越大，表明文件內容越有規律，壓縮后的體積就越小；p越小，表明文件內容越隨機，壓縮后的體積就越大。

        為了便于文件之間的比較，將上式除以n，可以得到平均每個符號所占用的二進制位。

∑ log₂(1/p_n) / n

= log₂(1/p₁)/n + log₂(1/p₂)/n + ... + log₂(1/p_n)/n

</blockquote>

        由于p是根據頻率統計得到的，因此上面的公式等價于下面的形式。

p₁*log₂(1/p₁) + p₂*log₂(1/p₂) + ... + p_n*log₂(1/p_n)

= ∑ p_n*log₂(1/p_n)

= E ( log₂(1/p) )

</blockquote>

        上面式子中最后的E，表示數學期望。可以理解成，每個符號所占用的二進制位，等于概率倒數的對數的數學期望。

        下面是一個例子。假定有兩個文件都包含 1024 個符號，在 ASCII 碼的情況下，它們的長度是相等的，都是 1KB。甲文件的內容 50% 是a，30%b，20% 是c，則平均每個符號要占用 1.49 個二進制位。

0. 5*log₂(1/0.5) + 0.3*log₂(1/0.3) + 0.2*log₂(1/0.2)

= 1.49

</blockquote>

        既然每個符號要占用 1.49 個二進制位，那么壓縮 1024 個符號，理論上最少需要 1526 個二進制位，約 0.186KB，相當于壓縮掉了 81% 的體積。

        乙文件的內容 10% 是a，10% 是b，......，10% 是j，則平均每個符號要占用 3.32 個二進制位。

0. 1*log₂(1/0.1)*10

= 3.32

</blockquote>

        既然每個符號要占用 3.32 個二進制位，那么壓縮 1024 個符號，理論上最少需要 3400 個二進制位，約 0.415KB，相當于壓縮掉了 58% 的體積。

        對比上面兩個算式，可以看到文件內容越是分散（隨機），所需要的二進制位就越長。所以，這個值可以用來衡量文件內容的隨機性（又稱不確定性）。這就叫做信息熵（information entropy）。

        它是 1948 年由美國數學家克勞德·香農（Claude Shannon）在經典論文《通信的數學理論》中，首先提出的。

        五、信息熵的含義

        想要理解信息熵這個概念，有幾點需要注意。

        （1）信息熵只反映內容的隨機性，與內容本身無關。不管是什么樣內容的文件，只要服從同樣的概率分布，就會計算得到同樣的信息熵。

        （2）信息熵越大，表示占用的二進制位越長，因此就可以表達更多的符號。所以，人們有時也說，信息熵越大，表示信息量越大。不過，由于第一點的原因，這種說法很容易產生誤導。較大的信息熵，只表示可能出現的符號較多，并不意味著你可以從中得到更多的信息。

        （3）信息熵與熱力學的熵，基本無關。這兩個熵不是同一件事，信息熵表示無序的信息，熱力學的熵表示無序的能量（參見我寫的《熵的社會學意義》）。

        （文章完）

來自: 阮一峰的網絡日志

 本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

 轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

 本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

  本文地址：http://www.baiduhome.net/news/view/1860ee3

數據