444
技術社區[雲棲]
《偉大的計算原理》一信息的測量
本節書摘來華章計算機《偉大的計算原理》一書中的第3章 ，［美］彼得 J. 丹寧（Peter J. Denning）
克雷格 H. 馬特爾（Craig H. Martell）著 羅英偉 高良才 張 偉 熊瑞勤 譯 更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看。
信息的測量
香農設計了一個用於測量信息源中所含信息的方法，因為他想知道信息源中最短碼的長度。編碼的位數量並不能作為一個衡量標準，正如我們在上文中所看到的，單個信息源可以用任意數量的不同編碼來表示。他的結論是一個好的衡量標準應該是消息集合中最短編碼的長度，若編碼再短一些則無法傳輸消息源的所有信息。
他認為衡量信息不應該依賴人類所觀察到的編碼的含義，而應該忽略信息的上下文，尋求編碼、傳輸和解碼的固定工作機製。郵政服務遵循相似的準則：他們的分發和傳輸係統從不依賴於所運輸的信封中的內容。香農非凡的洞察力表現在“將信息的接收等同於不確定性的減少”。他定義信息為判斷信息源正在傳送哪個消息所需要回答的是非（yes-no）問題的最小數量。我們越了解某個信息源可能會發送什麼消息，那麼看到這條消息時所獲得的信息量就越少。
假設你知道某人將會隻回答一個是非問題，但提前無法得知回答者的答案，那麼回答者通過回答解決了你的不確定性。香農認為回答者隻給了你一位的信息（1或0），即從兩種可能答案中選擇其中一個。當答案有兩個以上時，需要更多的位來區分發送的消息。
假設我們想在電話簿中找到含有某個朋友名字的那一頁，那麼需要多少位來對頁數進行編碼呢？一個聰明的方法回答了這個問題：我們從中間打開電話簿，然後詢問哪一半含有朋友的名字（由於使用字母順序編寫電話簿，這個問題就很容易回答）。然後我們把含有名字的那一半電話簿再分割成兩半，詢問同樣的問題。重複這個步驟，直到隻剩一頁，這個朋友的名字就應該在那一頁上。這個重複的問題（“哪一半”或者說“是否在左邊一半”）讓我們快速定位。對於一本有512頁的電話簿，第一個問題留下了256頁來搜索，第二個問題留下128頁，然後64，32，16，8，4，2，最後是1。需要9個“哪一半”問題來尋找包含名字的那一頁。因此，當找到包含朋友名字的那一頁時，我們獲取了9位的信息量。
在構建編碼時，人們需要思考消息的發生概率。塞繆爾·莫斯（Samuel Morse）發明了莫斯密碼，並將之應用於19世紀30年代他參與發明的電報中。他分配最短的編碼（單個點）來表示字母e，因為e是在英文中使用最頻繁的字母（大約12%）。他將最長的編碼分配給字母j，因為j是最少使用的字母之一（約0.15%）。這樣的分配減少了傳輸的平均長度。圖3.4說明了用以識別一個消息的問題可以用來定義信息編碼，以及關於消息發生概率的先驗知識會減少編碼量。
假設我們有一長度為Li、概率為Pi的碼字集合。那麼編碼的平均長度就是
對於圖3.4中的編碼，公式計算出第一種編碼的平均長度是2位，而第二種編碼的平均長度是1.75位。
在最優編碼中，碼字的長度即最小的L是多少呢？香農在他1948年論文的附錄中回答了這個問題。他表示最優碼字的長度是以2為底的碼字出現概率的對數的相反數，即-log2Pi。因此，最優編碼的平均長度是
這個公式和熱力學的熵公式具有同樣的形式，也有著相似的解釋。熵是衡量係統狀態的混亂程度或是不確定性的指標。一個係統的狀態越混亂，熵就越高。最大的混亂度發生在所有的狀態都有同等發生概率的情況下，最大的有序度則發生在某一種狀態非常確定而其他的狀態都絕不會發生的情況下。
香農認為熵是信息源中固有信息的衡量標準。一個信息源由一組可能的消息和消息發生的概率構成。熵隻取決於消息的概率而不是它們的編碼，熵可以確定最短可能編碼的平均長度。任何更短的編碼都將導致混淆從而無法得到唯一的解碼結果。如下麵的例子：
**A：1
B：0
C：01
D：10
**
圖3.4 香農將一個消息中的信息量定義為將該消息從消息源中篩選出來需要回答的是非問題數，這些問題是用來減少“哪個是被發送消息”的不確定性的。試想，如果我們要從四個人中發現被某任務選中的人，則可以使用一個簡單的決策樹（上圖），我們問：“是Alice或者Bob嗎？”如果答案為是，則決策選擇左邊的子樹。再問一個問題“是Alice嗎？”，答案就揭曉了。每個個體的編碼就是指向他/她的是非問題答案的路徑。如果知道某個個體被選中的概率（下圖括號裏的數字），那麼我們可以構造一個等級決策樹，從而使得編碼長度不等。例如，如果Alice是最有可能被選中的，我們就把編碼1分配給他。Bob是下一個最有可能的，則分配編碼為01，然後是Charlie和Diana，他們有相同的選中概率，則都被編碼為3位
如果以上這些消息出現的概率分別是0.5、0.25、0.125和0.125，平均編碼長度就是1.25位。然而，接收方對於1001代表ABBA，ABC，DBA還是DC卻無法分辨。這條消息的熵（根據上麵的公式計算得出）是H = 1.75，界定了編碼是否能夠解析的閾值。這條編碼的平均長度是1.25位，低於此閾值，所以編碼無法解析。
哈夫曼（Huffman）編碼是一種快速在熵閾值內進行位編碼的方法（圖3.5）。
圖3.5 1951年麻省理工學院的大衛·哈夫曼（David Huffman）設計了一套編碼算法，在已知消息概率的情況下，此編碼算法能夠使得平均編碼長度最小。該算法首先將每個消息都視為一棵單獨的樹。然後不斷地將兩棵具有最小概率的樹進行合並，合並後樹的概率為兩棵子樹的概率和。對於一個具有n條消息的編碼，需要n次合並，形成最後的樹。在本例中，Charlie和Diana首先合並，然後他們合並後的樹和Bob合並，最後和Alice合並。樹中的每條路徑定義了每一條消息的二進製位編碼。哈夫曼的方法所生成的編碼能夠將平均編碼長度控製在熵閾值範圍內。若所有的消息具有相等的概率，則生成圖3.3前麵所示的編碼，若概率不相等，則生成後麵這種編碼
從另外一個角度來看，熵的閾值定義了信道是否可信。如果消息源每隔T秒傳送一則新消息，最短編碼的平均長度是H，那麼這個消息源就產生了每秒傳送H / T位的需求。如果信道的帶寬是H / T位每秒或者更高，那麼發送方所傳送的所有位都能夠到達接收端。若信道的帶寬小於H /T位每秒，某些位就可能丟失，接收端就無法恢複原始消息。
文件壓縮是信息論的一個重要應用，因為其可以減少存儲空間和縮短傳輸時間。在大部分計算機程序中都使用標準碼來表示文本，包括傳統的固定長度編碼ASCII和現代的變長編碼Unicode。這兩種情況下每個字母都使用了相同長度的編碼，因而，通過尋找重複模式並基於文件上下文用更短的編碼代替這些模式，文本文件可被大幅壓縮。例如，一個包含很多字母“e”的文件，可以用新的更短小的編碼替換它的編碼來壓縮文件。新的編碼取決於“e”在文件中的出現頻率——在“e”頻繁出現的文件中，這個編碼可能是3位，而在“e”不那麼頻繁出現的文件中，這個編碼可能是5位。文件壓縮算法會生成一個新編碼到原始編碼的轉換表。“.zip”和“.rar”格式就采用了這種策略。這種壓縮策略的設計也不會將信息“壓縮”至低於熵的閾值。因為若是低於閾值，則無法保證完全恢複原始信息，這種策略被稱為無損壓縮。
另一種策略是有損壓縮。有損壓縮方法具有更大的壓縮率，但無法完全恢複原始文件。例如，MP3音頻壓縮通過丟棄絕大部分人聽不到的頻率來壓縮音頻，其壓縮率大約為10，但是沒法恢複丟棄的頻率。JPEG圖像壓縮舍棄了部分人眼基本會忽略的顏色信息位，當然也沒法恢複這些原始的圖像位。這些壓縮方案使得DVD、在線電影和唱片等能夠以更低廉的價格賣給消費者。這些方法在感知質量上的小小損失，對於減少文件大小而言通常被認為是一種很好的折中。
最後更新：2017-06-26 12:02:28