李曉明

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

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

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

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

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

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

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

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

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

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

一般而言，給定文本T，先要對(duì)它做一個(gè)掃描，統(tǒng)計(jì)其中每個(gè)符號(hào)出現(xiàn)的頻次。這個(gè)過(guò)程很簡(jiǎn)單，用哈希表來(lái)做這件事，時(shí)間效率相對(duì)于T的長(zhǎng)度就是線性的。哈夫曼編碼算法，則是基于上述過(guò)程的結(jié)果展開(kāi)的。

● 問(wèn)題

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

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

● 算法基本思路

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

沒(méi)錯(cuò)，每個(gè)符號(hào)對(duì)應(yīng)一個(gè)唯一的編碼，于是上面例子的總碼長(zhǎng)就是：

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

這可比按照ASCII編碼的152位省多了。即便我們不用ASCII編碼，對(duì)這5個(gè)符號(hào)用3位定長(zhǎng)編碼，總碼長(zhǎng)也需要19*3=57，比27大不少。但是，細(xì)心的讀者馬上會(huì)意識(shí)到一個(gè)問(wèn)題！按照這個(gè)編碼，那個(gè)文本“SHA HGH SHS HSH HAA”的編碼就是：

100100011000101000100000101

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

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

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

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

● 算法的描述

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

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

● 算法運(yùn)行例子

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

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

101100101110001101101110011110110111001001

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

● 算法性質(zhì)的分析與討論

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

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

此時(shí)，“SHA HGH SHS HSH HAA”的編碼就變成（長(zhǎng)度還是42）：

011011100101101000011001001001100010111111

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

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

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

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

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

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

②對(duì)于一般的圖，深度優(yōu)先搜索的復(fù)雜度是O（n+m），其中n為節(jié)點(diǎn)數(shù)，m為邊數(shù)。這里因?yàn)槭嵌鏄?shù)，m=n-1，因而就是O（n）了。

參考文獻(xiàn)：

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

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

注：作者系北京大學(xué)計(jì)算機(jī)系原系主任。