來(lái)自公眾號(hào)：后端研究所

1. 開(kāi)場(chǎng)白

好久不見(jiàn)，我是所長(zhǎng)大白。

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

今天和大家聊一下壓縮算法相關(guān)的知識(shí)點(diǎn)，廢話不說(shuō)，馬上開(kāi)始閱讀之旅吧！

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

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

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

對(duì)于壓縮算法來(lái)說(shuō)，我們肯定會(huì)問(wèn)：這是壓縮極限了嗎？還有提升空間嗎？

2.1 信息學(xué)之父

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

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

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

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

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

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

2.3 信息熵entropy

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

這是個(gè)特別有用的概念，因?yàn)樽匀唤绲谋举|(zhì)就是無(wú)序和混亂。

舉個(gè)不恰當(dāng)?shù)睦樱覀兘?jīng)?？磰蕵?lè)圈八卦新聞的時(shí)候，會(huì)說(shuō)信息量很大，上熱搜了等等，那么我們?cè)撊绾稳ザ攘啃畔⒘磕兀?/p>

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

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

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

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

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

簡(jiǎn)單翻譯一下：

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

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

其中k為一個(gè)正常量。

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

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

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

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

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

• 無(wú)損壓縮 適用于必須完整還原原始信息的場(chǎng)合，例如文本、可執(zhí)行文件、源代碼等。
• 有損壓縮，壓縮比很高但無(wú)法完整還原原始信息，主要應(yīng)用于視頻、音頻等數(shù)據(jù)的壓縮。

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

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

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

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

舉幾個(gè)簡(jiǎn)單的例子：

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

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

• 'aaaaaaaaxxxxxxkkkkkkzzzzzzzzzz' 和 '8a6x6k10z'

在上述文本中有比較明顯的局部重復(fù)，比如a出現(xiàn)了8次，z出現(xiàn)了10次，如果我們?cè)诜治隽溯斎胱址姆植家?guī)律之后，確定了'重復(fù)次數(shù)+字符'的規(guī)則，就可以進(jìn)行替換了。

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

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

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

這個(gè)和我們平時(shí)優(yōu)化代碼性能的思路非常相似，熱點(diǎn)代碼的優(yōu)化才能帶來(lái)更大的收益。

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

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

所以我們需要找到理論上的最短替換串的長(zhǎng)度，換到二進(jìn)制來(lái)說(shuō)就是二進(jìn)制的長(zhǎng)度，這樣就可以接近壓縮極限了。

我們來(lái)分析一下：

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

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

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

可能的情況越多，需要的二進(jìn)制長(zhǎng)度可能就越長(zhǎng)，對(duì)于n相等的兩個(gè)文件，概率p決定了這個(gè)式子的大?。?/p>

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

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

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

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

4. 霍夫曼編碼簡(jiǎn)介

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

霍夫曼編碼使用變長(zhǎng)編碼表對(duì)源符號(hào)進(jìn)行編碼，其中變長(zhǎng)編碼表是通過(guò)評(píng)估源符號(hào)出現(xiàn)的幾率得到的。

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

4.1 前綴編碼

霍夫曼編碼除了使用變長(zhǎng)碼之外，還使用前綴編碼來(lái)確保解碼時(shí)的唯一性，舉個(gè)例子：

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

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

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

4.2 霍夫曼樹(shù)簡(jiǎn)單構(gòu)造

霍夫曼樹(shù)是霍夫曼編碼的重要組成部分，我們拿一個(gè)具體的例子來(lái)看下霍夫曼樹(shù)的一點(diǎn)特性。

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

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

5. 本文小結(jié)

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

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

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

我們下期見(jiàn)。