1. 開場白

好久不見，我是所長大白。

無論是做研究還是實際工作，都需要經(jīng)過長期的積累，才能深刻理解存在的問題、解決方法、瓶頸所在、突破方向等等。

今天和大家聊一下壓縮算法相關(guān)的知識點，廢話不說，馬上開始閱讀之旅吧!

2.壓縮算法的理論基礎(chǔ)

任何適用于工程的算法都有它的數(shù)學(xué)和信息學(xué)理論基礎(chǔ)。

就如同我們寫論文要先做仿真，理論給實踐提供了一定的方向和依據(jù)。

對于壓縮算法來說，我們肯定會問：這是壓縮極限了嗎?還有提升空間嗎?

2.1 信息學(xué)之父

聊到這里，不得不提到信息學(xué)之父克勞德·艾爾伍德·香農(nóng)，來簡單看下他的履歷簡介：

[[421668]]

克勞德·艾爾伍德·香農(nóng)(Claude Elwood Shannon ，1916年4月30日—2001年2月24日)是美國數(shù)學(xué)家、信息論的創(chuàng)始人。

1936年獲得密歇根大學(xué)學(xué)士學(xué)位，1940年在麻省理工學(xué)院獲得碩士和博士學(xué)位，1941年進入貝爾實驗室工作，1956年他成為麻省理工學(xué)院客座教授，并于1958年成為終生教授，1978年成為名譽教授。

香農(nóng)提出了信息熵的概念，為信息論和數(shù)字通信奠定了基礎(chǔ)，他也是一位著名的密碼破譯者。他在貝爾實驗室破譯團隊主要追蹤德國飛機和火箭。

相關(guān)論文：1938年的碩士論文《繼電器與開關(guān)電路的符號分析》，1948年的《通訊的數(shù)學(xué)原理》和1949年的《噪聲下的通信》，1949年的另外一篇重要論文《Communication Theory of Secrecy Systems》。

看完這段介紹，我感覺自己被秒成了粉末了，只能默默打開了網(wǎng)抑云，生而為人，我很遺憾。

2.3 信息熵entropy

熵本身是一個熱力學(xué)范疇的概念，描述了一種混亂程度和無序性。

這是個特別有用的概念，因為自然界的本質(zhì)就是無序和混亂。

舉個不恰當(dāng)?shù)睦?，我們?jīng)?？磰蕵啡Π素孕侣劦臅r候，會說信息量很大，上熱搜了等等，那么我們該如何去度量信息量呢?

前面提到的信息學(xué)之父香農(nóng)就解決了信息的度量問題，讓一種無序不確定的狀態(tài)有了數(shù)學(xué)語言的描述。

在1948年的論文《A Mathematical Theory of Communication》中作者將Entropy與Uncertainty等價使用的。

文中提出了信息熵是信息的不確定性(Uncertainty)的度量，不確定性越大，信息熵越大。

論文地址：http://people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf

在論文的第6章給出信息熵的幾個屬性以及信息熵和不確定性之間的聯(lián)系：

簡單翻譯一下：

• 信息熵是隨著概率連續(xù)變化的;
• 如果構(gòu)成事件的各個因素的概率相等，那么信息熵隨構(gòu)成因素總數(shù)n的增加而增加，即選擇越多，不確定性越大。
• 當(dāng)一個選擇可以分解為兩個連續(xù)選擇時，分解前后的熵值應(yīng)該相等，不確定性相同。

我們假設(shè)一個事件有多種可能的選擇，每個選擇的概率分別記為p1,p2....pn，文章進一步給出了概率和信息熵的公式：

其中k為一個正常量。

經(jīng)過前面的一些分析，我們基本上快懵圈了，太難了。

所以，我們暫且記住一個結(jié)論：信息是可度量的，并且和概率分布有直接聯(lián)系。

3. 數(shù)據(jù)壓縮的本質(zhì)

既然有了理論的支持，那么我們來想一想 如何進行數(shù)據(jù)壓縮呢?

數(shù)據(jù)壓縮可以分為：無損壓縮和有損壓縮。

無損壓縮 適用于必須完整還原原始信息的場合，例如文本、可執(zhí)行文件、源代碼等。

有損壓縮，壓縮比很高但無法完整還原原始信息，主要應(yīng)用于視頻、音頻等數(shù)據(jù)的壓縮。

3.1 數(shù)據(jù)壓縮的定義

壓縮的前提是冗余的存在，消除冗余就是壓縮，用更少的信息來完整表達信息，來看下百科的定義：

數(shù)據(jù)壓縮是指在不丟失有用信息的前提下，縮減數(shù)據(jù)量以減少存儲空間，提高其傳輸、存儲和處理效率，

需要按照一定的算法對數(shù)據(jù)進行重新組織，減少數(shù)據(jù)的冗余和存儲的空間的一種技術(shù)方法。

舉幾個簡單的例子：

• "北京交通大學(xué)的交通信息工程及控制專業(yè)不錯" 和 "北交的交控專業(yè)不錯"

在上述文本中"北京交通大學(xué)"可以用"北交"代替，"交通信息工程及控制專業(yè)"可以用"交控專業(yè)"代替。

• "aaaaaaaaxxxxxxkkkkkkzzzzzzzzzz" 和 "8a6x6k10z"

在上述文本中有比較明顯的局部重復(fù)，比如a出現(xiàn)了8次，z出現(xiàn)了10次，如果我們在分析了輸入字符的分布規(guī)律之后，確定了"重復(fù)次數(shù)+字符"的規(guī)則，就可以進行替換了。

3.2 概率分布和數(shù)據(jù)編碼

本質(zhì)上來說，數(shù)據(jù)壓縮就是找到待壓縮內(nèi)容的概率分布，再按照一定的編碼算法，將那些出現(xiàn)概率高的部分代替成更短的形式。

所以輸入內(nèi)容重復(fù)的部分越多，就可以壓縮地越小，壓縮率越高，如果內(nèi)容幾乎沒有重復(fù)完全隨機，就很難壓縮。

這個和我們平時優(yōu)化代碼性能的思路非常相似，熱點代碼的優(yōu)化才能帶來更大的收益。

3.3 數(shù)據(jù)壓縮極限

前面提到了，用較短的字符串來替換較長的字符串就實現(xiàn)了壓縮，那么如果對每次替換都使用最短的字符串，應(yīng)該就可以認為是最優(yōu)壓縮了。

所以我們需要找到理論上的最短替換串的長度，換到二進制來說就是二進制的長度，這樣就可以接近壓縮極限了。

我們來分析一下：

• 拋硬幣 只有正面和反面 兩種情況 因此使用1位二進制 0和1 就可以
• 籃球比賽 存在勝/負/平 三種情況 因此需要使用2位二進制 00勝 01負 10平
• 猜生日月份 存在1-12月 12種情況 因此需要使用4位二進制 來表示各個月份
• 如果可能性有n個不同的值，那么替換串就需要log2(n)個二進制位來表示

假定內(nèi)容由n個部分組成，每個部分出現(xiàn)概率分別為p1、p2、...pn，那么替代符號占據(jù)的二進制最少為：

log2(1/p1) + log2(1/p2) + ... + log2(1/pn) = ∑ log2(1/pn) 

可能的情況越多，需要的二進制長度可能就越長，對于n相等的兩個文件，概率p決定了這個式子的大?。?/p>

• p越大，表明文件內(nèi)容越有規(guī)律，壓縮后的體積就越小;
• p越小，表明文件內(nèi)容越隨機，壓縮后的體積就越大。

舉例：有一個文件包含A, B, C個三種不同的字符，50%是A，30%是B，20%是C，文件總共包含1024個字符，每個字符所占用的二進制位的數(shù)學(xué)期望為：

0.5*log2(1/0.5) + 0.3*log2(1/0.3) + 0.2*log2(1/0.2)=1.49 

求得壓縮后每個字符平均占用1.49個二進制位，理論上最少需要1.49*1024=1526個二進制位，約0.1863KB，最終的壓縮比接近于18.63%。

4. 霍夫曼編碼簡介

哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼(有時也稱為霍夫曼編碼)。

霍夫曼編碼使用變長編碼表對源符號進行編碼，其中變長編碼表是通過評估源符號出現(xiàn)的幾率得到的。

出現(xiàn)幾率高的字母使用較短的編碼，出現(xiàn)幾率低的字母使用較長的編碼，這使得編碼之后字符串的總長度降低。

4.1 前綴編碼

霍夫曼編碼除了使用變長碼之外，還使用前綴編碼來確保解碼時的唯一性，舉個例子：

A-0 C-1 B-00 D-01 則編碼后為：000011010

當(dāng)我們對它進行解碼的時候，會發(fā)現(xiàn) 0000 可能對應(yīng)多種解碼方式，如 AAAA、AAB、ABA、BB。

霍夫曼樹中葉子節(jié)點之間不存在父子關(guān)系，所以每個葉子節(jié)點的編碼就不可能是其它葉子節(jié)點編碼的前綴，這是非常重要的。

4.2 霍夫曼樹簡單構(gòu)造

霍夫曼樹是霍夫曼編碼的重要組成部分，我們拿一個具體的例子來看下霍夫曼樹的一點特性。

• 輸入數(shù)據(jù)："boob is bee boy"
• 字符串集合和頻次統(tǒng)計
  • 集合 {b,o,s,i,e,y}
  • 頻次 {b:4,o:3,e:2,i:1,y:1,s:1}
• 總計有6個字符，因此需要3位二進制
• 按照頻率越高字符越短&前綴編碼規(guī)則進行處理
  • b:00
  • o:01
  • e:100
  • i:101
  • y:110
  • s:111
  • 注意：e并不是001，因為這樣不符合前綴編碼 b是e的父節(jié)點

霍夫曼編碼的原理和實現(xiàn)還是比較復(fù)雜的，篇幅有限，后面單獨寫一篇文章詳細介紹。

5. 本文小結(jié)

本文對數(shù)據(jù)壓縮進行了簡要的介紹，說明了數(shù)據(jù)壓縮的本質(zhì)和算法的基本原理，以及霍夫曼樹的一些原理。

數(shù)據(jù)壓縮和分析內(nèi)容的概率分布以及編碼有直接的關(guān)系，但是各個場景下輸入內(nèi)容的側(cè)重點會有所不同，利用機器學(xué)習(xí)來處理數(shù)據(jù)壓縮也是當(dāng)前的一個熱門話題。

篇幅有限，后續(xù)會重點展開一些細節(jié)，這篇就算拋磚引玉開頭篇了。

 

我們下期見。