淺談壓縮算法的那些事兒

taotao_2016 2021-09-12

展開全文

來自公眾號：后端研究所

1. 開場白

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

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

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

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

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

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

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

2.1 信息學之父

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

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

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

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

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

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

2.3 信息熵entropy

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

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

舉個不恰當?shù)睦?，我們?jīng)常看娛樂圈八卦新聞的時候，會說信息量很大，上熱搜了等等，那么我們該如何去度量信息量呢？

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

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

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

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

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

簡單翻譯一下：

信息熵是隨著概率連續(xù)變化的；
如果構(gòu)成事件的各個因素的概率相等，那么信息熵隨構(gòu)成因素總數(shù)n的增加而增加，即選擇越多，不確定性越大。
當一個選擇可以分解為兩個連續(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ù)方法。

舉幾個簡單的例子：

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

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

'aaaaaaaaxxxxxxkkkkkkzzzzzzzzzz' 和 '8a6x6k10z'

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

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

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

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

這個和我們平時優(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ī)律，壓縮后的體積就越?。?/section>
p越小，表明文件內(nèi)容越隨機，壓縮后的體積就越大。

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

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)幾率低的字母使用較長的編碼，這使得編碼之后字符串的總長度降低。