信息論入門教程

作者: 阮一峰

日期: 2019年8月 1日

1948年,美國數學家克勞德·香農發表論文《通信的數學理論》(A Mathematical Theory of Communication),奠定了信息論的基礎。

今天,信息論在信號處理、數據壓縮、自然語言等許多領域,起著關鍵作用。雖然,它的數學形式很復雜,但是核心思想非常簡單,只需要中學數學就能理解。

本文使用一個最簡單的例子,幫助大家理解信息論。

一、詞匯的編碼

小張是我的好朋友,最近去了美國。

我們保持著郵件聯系。小張寫信的時候,只使用4個詞匯:狗,貓,魚,鳥。

信的所有內容就是這4個詞的組合。第一封信寫著"狗貓魚鳥",第二封信寫"魚貓鳥狗"。

信件需要二進制編碼,在互聯網傳遞。兩個二進制位就可以表示四個詞匯。

  • 狗 00
  • 貓 01
  • 魚 10
  • 鳥 11

所以,第一封信"狗貓魚鳥"的編碼是00011011,第二封信"魚貓鳥狗"的編碼是10011100

二、詞匯的分布

最近,小張開始養狗,信里提到狗的次數,多于其他詞匯。假定概率分布如下。

  • 狗:50%
  • 貓:25%
  • 魚:12.5%
  • 鳥:12.5%

小張的最新一封信是這樣的。

狗狗狗狗貓貓魚鳥

上面這封信,用前一節的方法進行編碼。

0000000001011011

一共需要16個二進制。互聯網的流量費很貴,有沒有可能找到一種更短編碼方式?

很容易想到,"狗"的出現次數最多,給它分配更短的編碼,就能減少總的長度。請看下面的編碼方式。

  • 狗 0
  • 貓 10
  • 魚 110
  • 鳥 111

使用新的編碼方式,小張的信"狗狗狗狗貓貓魚鳥"編碼如下。

00001010110111

這時只需要14個二進制位,相當于把原來的編碼壓縮了12.5%。

根據新的編碼,每個詞只需要1.75個二進制位(14 / 8)。可以證明,這是最短的編碼方式,不可能找到更短的編碼,詳見后文。

三、編碼方式的唯一性

前一節的編碼方式,狗的編碼是0,這里的問題是,可以把這個編碼改成1嗎,即下面的編碼可行嗎?

  • 狗 1
  • 貓 10
  • 魚 110
  • 鳥 111

回答是否定的。如果狗的編碼是1,會造成無法解碼,即解碼結果不唯一。110有可能是"狗貓",也可能是"魚"。只有"狗"為0,才不會造成歧義。

下面是數學證明。一個二進制位有兩種可能01,如果某個事件有多于兩種的結果(比如本例是四種可能),就只能讓01其中一個擁有特殊含義,另一個必須空出來,保證能夠唯一解碼。比如,0表示狗,1就必須空出來,不能有特殊含義。

同理,兩個二進制位可以表示四種可能:00011011。上例中,0開頭的編碼不能用了,只剩下1011可用,用10表示貓,為了表示"魚"和"鳥",必須將11空出來,使用三個二進制位表示。

這就是,上一節的編碼方式是如何產生的。

四、編碼與概率的關系

根據前面的討論,可以得到一個結論:概率越大,所需要的二進制位越少。

  • 狗的概率是50%,表示每兩個詞匯里面,就有一個是狗,因此單獨分配給它1個二進制位。
  • 貓的概率是25%,分配給它兩個二進制位。
  • 魚和鳥的概率是12.5%,分配給它們三個二進制位。

香農給出了一個數學公式。L表示所需要的二進制位,p(x)表示發生的概率,它們的關系如下。

通過上面的公式,可以計算出某種概率的結果所需要的二進制位。舉例來說,"魚"的概率是0.125,它的倒數為8, 以 2 為底的對數就是3,表示需要3個二進制位。

知道了每種概率對應的編碼長度,就可以計算出一種概率分布的平均編碼長度。

上面公式的H,就是該種概率分布的平均編碼長度。理論上,這也是最優編碼長度,不可能獲得比它更短的編碼了。

接著上面的例子,看看這個公式怎么用。小張養狗之前,"狗貓魚鳥"是均勻分布,每個詞平均需要2個二進制位。

H = 0.25 x 2 + 0.25 x 2 + 0.25 x 2 + 0.25 x 2
= 2

養狗之后,"狗貓魚鳥"不是均勻分布,每個詞平均需要1.75個二進制位。

H = 0.5 x 1 + 0.25 x 2 + 0.125 x 3 + 0.125 x 3
= 1.75

既然每個詞是 1.75 個二進制位,"狗狗狗狗貓貓魚鳥"這8個詞的句子,總共需要14個二進制位(8 x 1.75)。

五、信息與壓縮

很顯然,不均勻分布時,某個詞出現的概率越高,編碼長度就會越短。

從信息的角度看,如果信息內容存在大量冗余,重復內容越多,可以壓縮的余地就越大。日常生活的經驗也是如此,一篇文章翻來覆去都是講同樣的內容,摘要就會很短。反倒是,每句話意思都不一樣的文章,很難提煉出摘要。

圖片也是如此,單調的圖片有好的壓縮效果,細節豐富的圖片很難壓縮。

由于信息量的多少與概率分布相關,所以在信息論里面,信息被定義成不確定性的相關概念:概率分布越分散,不確定性越高,信息量越大;反之,信息量越小。

六、信息熵

前面公式里的H(平均編碼長度),其實就是信息量的度量。H越大,表示需要的二進制位越多,即可能發生的結果越多,不確定性越高。

比如,H1,表示只需要一個二進制位,就能表示所有可能性,那就只可能有兩種結果。如果H6,六個二進制位表示有64種可能性,不確定性大大提高。

信息論借鑒了物理學,將H稱為"信息熵"(information entropy)。在物理學里,表示無序,越無序的狀態,熵越高。

七、信息量的實例

最后,來看一個例子。如果一個人的詞匯量為10萬,意味著每個詞有10萬種可能,均勻分布時,每個詞需要 16.61 個二進制位。

log?(100, 000) = 16.61

所以,一篇1000個詞的文章,需要 1.6 萬個二進制位(約為 2KB)。

16.61 x 1000 = 16,610

相比之下,一張 480 x 640、16級灰度的圖片,需要123萬個二進制位(約為 150KB)。

480 x 640 x log?(16) = 1,228,800

所以,一幅圖片所能傳遞的信息遠遠超過文字,這就是"一圖勝千言"吧。

上面的例子是均勻分布的情況,現實生活中,一般都是不均勻分布,因此文章或圖片的實際文件大小都是可以大大壓縮的。

八、參考鏈接

(完)

留言(17條)

這篇文章講得非常生動,精辟。

這種編碼是前綴編碼,可以使用哈夫曼算法實現。

全文就差一個“哈夫曼編碼”來做結論
看前面感覺會引出這個,結果沒寫。//sad

確實。看著看著以為后面會說哈夫曼。

通俗易懂

看得我津津有味,結果沒看懂

我竟然看懂了,通俗易懂的描述了,信息量為什么是以信息的不確定性(信息熵)為單位的。大神畢竟大神!!

通俗易懂 感謝

感覺自己通信原理白學了。。。

小張那個動物再后面加幾個的話,編碼應該怎么排呢?

香農的公式似乎只適用于二分的概率,生活中常見的不規律的概率可能行不通

引用陳一的發言:

香農的公式似乎只適用于二分的概率,生活中常見的不規律的概率可能行不通

按照你的說法,阮老師文引出中香農公式的“貓狗鳥魚”本身就不是二分概率,至少叫四分概率。
我的理解是香農的公式適用于二進制編碼,假如是n進制,香農公式可以改寫成L=LOGn(1/Px),這里的n是編碼用的進制,跟幾分概率沒有關系。

其實所有通信類的書上都會有信息論的這些內容,但好像從沒有一本書能講的像阮老師博客這么清楚,書上一般都是直接給出熵的定義,然后就基本完事了。唉,大道至簡,最煩那些故作高深的書和人。

DDD領域模型驅動能出片文章嗎

之前一直不理解熵的定義, 看了老師的博客, 恍然大悟

信息熵的引出簡單明了,解釋了我接觸這個概念以來的困惑!

阮老師寫的真好!秒懂!原先學的時候一直不明白香農的那個公式到底啥意思,現在秒懂了~

我要發表看法

«-必填

«-必填,不公開

«-我信任你,不會填寫廣告鏈接

体彩7位数