數(shù)據(jù)壓縮問題

李曉明

在以數(shù)字化和網(wǎng)絡化為技術標志的信息化社會，數(shù)據(jù)越來越多，單個數(shù)據(jù)體的規(guī)模越來越大。30年前，談到數(shù)據(jù)文件的大小，人們主要談KB;20年前，MB流行起來;10年前，GB已進入日常視野;現(xiàn)在，TB也不是望塵莫及。

與應用數(shù)據(jù)規(guī)模日益擴大相生相伴的是存儲技術和通信技術的改進。在它們之間緩沖的，則是數(shù)據(jù)壓縮技術。日常人們接觸多的，當數(shù)各種文件壓縮工具軟件了。每個文件壓縮軟件背后都是某種壓縮技術，常常是基于某種公開的規(guī)則。文獻【1】是關于這方面的一本相當全面的參考書。

數(shù)據(jù)壓縮的目的，是要用較小的空間（數(shù)據(jù)量），準確或近似地表達原本在一個較大空間里表達的信息。各種壓縮技術中的規(guī)則從本質上講都是算法。它們將輸入數(shù)據(jù)，變換為規(guī)模較小的輸出數(shù)據(jù)（如圖1）。無損壓縮，意味著可以從結果中完整恢復原始數(shù)據(jù)，如文本的壓縮。有損壓縮，則允許原始信息在結果中有所丟失，當然應該在可以接受的范圍內，如圖像或視頻的壓縮。本文只討論無損壓縮。

數(shù)據(jù)是信息的表達或編碼。一個數(shù)據(jù)可以被壓縮，一定是它表達所蘊含信息的效率不夠高，或者說有冗余。本文討論文本數(shù)據(jù)的壓縮，所謂文本數(shù)據(jù)，即有一個預先知道的有限字符集C，任何文本T都是由該字符集中的字符構成的字符串，可能很長很長。壓縮的對象是T，但可以運用C的知識（如其中有多少個字符）。例如本篇文章，除去插圖，就是一個字符串（T），它其中的字符源于一個包含漢字、英文字母、標點符號、空格、換行等字符的字符集（C）。

數(shù)據(jù)壓縮概念的出現(xiàn)及其實踐，至少已有500年歷史，文獻【1】中有相關介紹。由于數(shù)據(jù)壓縮既有實用性，也呈現(xiàn)出引人入勝的智力挑戰(zhàn)，幾百年來不斷有人嘗試新的思路。有些思路簡單奇妙，開腦洞。文獻【1】中有下面這樣一個例子：

設字符集C有40個字符（別看很少，但已經(jīng)相當實用了，如可包含26個英文字母、10個數(shù)字、3個標點和1個空格）。在不考慮壓縮的情況下，常規(guī)就是每個字符用1個字節(jié)編碼。如果注意到403=64000<65536=216，會發(fā)現(xiàn)有機會了：對于任何字符串T，總是可以將它的字符按順序三個三個一組，那么全部可能有403<216種。于是我們可以用2個字節(jié)，即16位，給這種“三元組”完整編碼。也就是說，本來需要3個字節(jié)表示的信息，現(xiàn)在用2個就夠了，于是壓縮比為3/2=1.5，而且與T的具體內容無關。是不是相當不錯？

現(xiàn)在人們談計算思維，計算思維有一個特征叫“系統(tǒng)觀”（或系統(tǒng)思維），它對有效理解一些具體技術很有幫助，有些類似于樹木和森林的關系。有了這種觀念，在理解林林總總數(shù)據(jù)壓縮算法細節(jié)的時候就不會迷失方向。下頁圖2是理解數(shù)據(jù)壓縮問題的一種系統(tǒng)觀。理解一個算法為什么能有效工作，與對這樣一個“系統(tǒng)”的理解直接相關。例如，其中的“相關知識”指的是什么？它為什么既和編碼有關，也和解碼有關？從上面討論的例子來看，它至少要包括字符集C，以及2個字節(jié)與3個連續(xù)字符的對應關系。一般地，就是要有字符集和“碼表”（code book）。就這一點而言，是不是和本專欄上一期介紹的加密解密算法有相似之處？

前面例子的一個重要特點是它的壓縮比是固定的（1.5）。好處就是它提供了一個保證，無論什么文本，都會是這個樣子。不盡如人意之處就是它沒有利用文本自身可能對壓縮有幫助的特點。例如，疊字聯(lián)：“重重喜事，重重喜，喜年年獲豐收;盈盈笑語，盈盈笑，笑頻頻傳捷報?！?2個字，我們能感到某種“冗余”。其中有些字（符號）多次用到，有些則只用了一次。如果按照每字符1字節(jié)編碼，需要32字節(jié)=256位，若按照前面例子中的算法編碼，這里是11組，于是需要22字節(jié)=176位。下面我們將看到，作為本文介紹的重點——哈夫曼編碼算法，充分利用文本自身的特點，對這個例子能給出如表1所示的壓縮編碼結果，總共只需4*3+4*3+4*3+3*3+3*4+2*4+2*4+10*5=123位。

哈夫曼編碼是David A. Huffman于1952年發(fā)明的一種無損編碼方法，當時他還是MIT的一個學生。觀察表1中第三行的編碼數(shù)據(jù)，我們能看到不同字符用到的位數(shù)有所不同，這種方式稱為可變字長編碼，與前面討論的例子不一樣。即便是那種用2個字節(jié)表示3個字符的方式，也可以看成是固定字長的。

該方法的思想很自然，它依據(jù)符號在文本（T）中出現(xiàn)的概率（頻率）來編碼，讓概率較高的編碼較短，概率較低的編碼較長，以期獲得最短的平均編碼長度。下面來看，給定一個文本T，如何生成其中符號的哈夫曼編碼的算法。為方便起見，我會用一個比上述疊字聯(lián)更小一些的例子來解釋其過程。

一般而言，給定文本T，先要對它做一個掃描，統(tǒng)計其中每個符號出現(xiàn)的頻次。這個過程很簡單，用哈希表來做這件事，時間效率相對于T的長度就是線性的。哈夫曼編碼算法，則是基于上述過程的結果展開的。

● 問題

給定字符集合C={C1，C2，…，Cn}和對應出現(xiàn)的頻次f={f1，f2，…，fn}，要將C中的字符編碼，使得總碼長盡量短，即若以Li表示Ci的編碼長度，追求∑fi*Li的極小化。

例如，文本串“SHA HGH SHS HSH HAA”中一共有19個字符（空格也是字符）。若用ASCII碼，每個字符1字節(jié)，整個碼長就是19*8=152（位）。有辦法提供一種不同的編碼，縮短總碼長嗎？

● 算法基本思路

前面已經(jīng)提到，哈夫曼編碼的基本思想是讓出現(xiàn)頻率高的用較短的碼，低的用較長的碼。從而希望能減小∑fi*Li。對上面這個例子而言，有5種不同的字符，S出現(xiàn)4次，H出現(xiàn)7次，A出現(xiàn)3次，G出現(xiàn)1次，空格出現(xiàn)4次，可得字符頻度對應表如表2頭兩行所示。不妨讓我們來立刻嘗試應用一下這種基本思路，給出表2第三行所示編碼。

沒錯，每個符號對應一個唯一的編碼，于是上面例子的總碼長就是：

7*1+4*1+4*2+3*2+1*2=27

這可比按照ASCII編碼的152位省多了。即便我們不用ASCII編碼，對這5個符號用3位定長編碼，總碼長也需要19*3=57，比27大不少。但是，細心的讀者馬上會意識到一個問題！按照這個編碼，那個文本“SHA HGH SHS HSH HAA”的編碼就是：

100100011000101000100000101

回顧圖2所示的系統(tǒng)觀，如果其中的“相關知識”就是表2第一和第三行給出的碼表，你能從這個0/1串中解碼出“SHA HGH SHS HSH HAA”嗎？你會說，那第一個1不就代表S嗎？可是，后面連著的兩個0到底是代表兩個H還是代表一個空格呢？這真的是沒法回答。

這就出現(xiàn)了所謂“前綴碼”問題，即有些字符的編碼是其他字符編碼的前面一部分（前綴），如H的編碼0就是空格編碼00的前綴。這樣的編碼，單個看沒問題，放在一起就有問題了，解碼就有二義性，是不能接受的。這是不定長編碼必須克服的一個基本問題。所給出的碼字，不能出現(xiàn)一個是另一個前綴的情況。因此，我們上面的樸素嘗試失敗了，下面看哈夫曼編碼是怎么做的。

給定字符集合和頻數(shù)集合，哈夫曼編碼的過程可以形象地看成是自底向上建立一棵二叉樹的過程。每個葉節(jié)點對應一個待編碼的字符，該二叉樹的每一條邊用0或1標記。一旦這棵樹建立完成，葉節(jié)點（也就是字符）的編碼就是從根到達它的每一條邊上標記的序列。這樣，一個葉節(jié)點離根越遠，它的碼字就越長。因此，建樹過程是哈夫曼編碼算法的核心，如下所述。

從字符頻數(shù)集合f={f1，f2，…，fn}開始，不妨想象它們是某一棵二叉樹的n個葉節(jié)點，每一次取其中兩個最小的——fi和fj，向上形成二叉樹的一個“內部節(jié)點”，命名為fij，讓它也有一個頻數(shù)fij=fi+fj，放到f中，同時從f中去掉fi和fj。如此這般繼續(xù)考察f，不斷形成新的內部節(jié)點，可以由兩個葉節(jié)點、兩個內部節(jié)點或一個葉節(jié)點和一個內部節(jié)點產生，這完全取決于f中元素的頻率值，直到最后剩兩個元素，構成樹根。在這個過程中，不難想象每次都有兩條向上的邊，將它們一個標記為0，另一個標記為1。

● 算法的描述

為了強調二叉樹建立的意象，在圖3所示的算法描述中引入了“節(jié)點”（node）的概念，將它看成是一種抽象數(shù)據(jù)，包括node.value，node.left和node.right幾個要素。哈夫曼樹，就是由若干相互關聯(lián)的節(jié)點構成的集合，記為H。這樣，圖3描述的算法就離程序實現(xiàn)很近了。

樹建好之后，就可以來生成每個字符的編碼了。從根節(jié)點開始，采用數(shù)據(jù)結構課上學過的深度優(yōu)先搜索即得。例如，約定從一個節(jié)點到左子節(jié)點的邊的標號為0，往右子節(jié)點的為1，按序記住搜索路徑邊上的編號，每到達一個葉節(jié)點就相當于完成了一個字符的編碼。

● 算法運行例子

我們用表2的例子，“SHA HGH SHS HSH HAA”，根據(jù)表中頭兩行符號與頻次的對應關系，運行上述算法，得到的哈夫曼樹如圖4所示。

基于該樹，得到每個符號的哈夫曼編碼（碼表）如表3所示。按照這樣的編碼，“SHA HGH SHS HSH HAA”就是：

101100101110001101101110011110110111001001

其長度=7*2+4*2+4*2+3*3+1*3=42，比前面那個有問題的27要長不少，但與最節(jié)省的3位等長碼相比也要好不少（42/57≈73.7%）?，F(xiàn)在你要想的是，如果給你這樣一長串碼和表3前兩行所示碼表，你能準確無誤地給出（解碼出）“SHA HGH SHS HSH HAA”嗎？

● 算法性質的分析與討論

這是一個正確的算法嗎？看建樹過程，那個while循環(huán)為什么能夠結束？假設n≥2，那么開始總能在f中找到兩個元素，使循環(huán)的第一輪進行下去。我們看到，每一輪循環(huán)，在第13、14行，f都是增加一個元素，減少兩個元素，即凈減少一個元素，做了n-1次后，其中就剩下一個元素了，循環(huán)不再執(zhí)行，程序結束。也就是說，恰好執(zhí)行n-1次，創(chuàng)建了n-1個非葉節(jié)點（這與滿二叉樹的性質是相符的，即n個葉節(jié)點的滿二叉樹有n-1個非葉節(jié)點）。最終在H里面就有2n-1個節(jié)點。循環(huán)中新節(jié)點的創(chuàng)建部分讓我們看到那些節(jié)點之間的關系是滿二叉樹。

取決于具體實現(xiàn)細節(jié)，得到的哈夫曼編碼可能不唯一，但其∑fi*Li是一樣的，而且都有高頻字符編碼不長于低頻字符編碼的性質。也就是說，對同一個字符串T，不同的人對其中的符號做哈夫曼編碼，給出的碼表可能是不同的（從而對T的編碼也就不同），但都是正確的！例如，表4也是一個對我們例子中的符號進行哈夫曼編碼得到的碼表。

此時，“SHA HGH SHS HSH HAA”的編碼就變成（長度還是42）：

011011100101101000011001001001100010111111

我們還需要問哈夫曼編碼為什么是無前綴碼。這從哈夫曼編碼樹的定義及編碼生成的過程容易看到。首先，由于二叉樹的節(jié)點有層次，以及每個節(jié)點兩個分支上的標記不同，每一個葉節(jié)點的編碼就是唯一的。由于編碼都是針對葉節(jié)點的，于是從根節(jié)點到一個葉節(jié)點的路徑就不可能另一條路徑的前綴。即一個字符的編碼不可能是另一個的前綴。正確性的另一方面是問如此產生的編碼是否最優(yōu)？即在無前綴碼的條件下，∑fi*Li是否不可能更小。結論是肯定的，證明超出了本文范疇。有興趣的讀者可參閱文獻【2】。

這個算法的效率如何呢？在建樹部分，基本就是一個兩重循環(huán)。外循環(huán)執(zhí)行n-1次，內循環(huán)就是在f中找兩個最小的元素。于是可以說復雜性為O（n2）①。在碼字生成部分，深度優(yōu)先遍歷一棵有n個葉節(jié)點的二叉樹，復雜性為O（n）②。這里，也可以請讀者考慮，如果在生成哈夫曼樹的過程中保留適當?shù)男畔ⅲ坏┩瓿?，就可以直接輸出碼表，后面這個碼字生成的步驟就可以省去了。這樣的做法在本欄目前面的文章中曾多次用到，是算法設計的一種技巧。

另外，前面提到應用哈夫曼編碼還有一項前期預處理工作，即對原始數(shù)據(jù)（字符串）進行掃描，得到字符集C和頻次集f，其時間消耗與原始數(shù)據(jù)量（T的長度）成正比。

從上面的討論中，讀者可能得到了哈夫曼編碼“很好”的印象。的確，哈夫曼編碼有很好的性能（編碼長度和算法效率都很好），也應用在許多實際軟件中（如zip）。我們能否也看到一點“缺點”呢？此時，值得回到圖2所示的系統(tǒng)觀。假設有A和B兩個人，A總會有一些文本發(fā)送給B，他們決定采用數(shù)據(jù)壓縮的方式，A將文件壓縮，發(fā)送給B，B解壓后得以看到原文。如果采用哈夫曼編碼，每次A發(fā)給B的，除了壓縮后的文件，還要有類似于表3或表4前面兩行那樣的碼表。這是因為，按照我們描述的算法，輸入是字符出現(xiàn)的頻次表，那是取決于具體文本的。這意味著，同樣的字符，在文本T1和T2中對應的編碼很可能不一樣！于是，B為了能夠解壓，既需要有壓縮后的文本，也需要有與該文本相適應的碼表（對應圖2中的“相關知識”）。由于碼表本身也要占存儲占帶寬，若T不足夠大，綜合起來就不一定合適了。這種情況在最開始提到的那個例子中就不會出現(xiàn)。在那里，B只要最開始收到一次碼表就可以了，今后用的都是相同的。

在實踐中應對這樣一種狀況的方法是假設人們生成的文件中有各種各樣的內容，但用字的頻率分布是基本穩(wěn)定的（大量統(tǒng)計表明的確也是）。于是就可以一次性確定字頻表，生成哈夫曼編碼，用于后面所有文件的壓縮。這樣，哈夫曼樹只需要構建一次生成一個碼表，而接收方也就不用每次都需要接收新的碼表了?？梢韵氲剑@里的代價就是損失一些壓縮比。

注釋：①利用先進的數(shù)據(jù)結構實現(xiàn)頻數(shù)集合f，便于查找其中兩個最小的數(shù)，能做到O（nlogn）。

②對于一般的圖，深度優(yōu)先搜索的復雜度是O（n+m），其中n為節(jié)點數(shù)，m為邊數(shù)。這里因為是二叉樹，m=n-1，因而就是O（n）了。

參考文獻：

[1]David Salomon.Data Compression（The Complete Reference），4th ed[M].Berlin：Springer，2007.

[2]王曉東.算法設計與分析（第3版）[M].北京：清華大學出版社，2014，11.

注：作者系北京大學計算機系原系主任。