基于上下文模型的超長哈夫曼碼校正算法

張永興，吳睿振，賈曉龍，陳靜靜，孫華錦

(浪潮人工智能研究院有限公司，陜西 西安 710077)

0 引 言

隨著大數(shù)據(jù)等前沿科學(xué)技術(shù)的快速發(fā)展，催生數(shù)據(jù)爆發(fā)式的增長，海量數(shù)據(jù)對現(xiàn)有的存儲設(shè)備帶來巨大的壓力。面對持續(xù)增長的海量數(shù)據(jù)，數(shù)據(jù)壓縮成為減輕服務(wù)器存儲負(fù)擔(dān)，降低存儲成本的最有效方法。

數(shù)據(jù)壓縮在不丟失有用信息的前提下，縮減數(shù)據(jù)量以減少存儲空間，提高傳輸、存儲和處理效率。無損數(shù)據(jù)壓縮一般通過兩種方法來實現(xiàn)[1]：一種是通過字典的方式實現(xiàn)壓縮的算法，包括LZ系列算法，這類算法能實現(xiàn)重復(fù)數(shù)據(jù)的搜索功能；另一種是基于統(tǒng)計模型的壓縮算法，如Huffman碼、算術(shù)編碼等，這類算法的核心思想是依照符號出現(xiàn)頻率分配碼長，符號出現(xiàn)頻率越高，其對應(yīng)碼長就越短。

當(dāng)前主流的數(shù)據(jù)壓縮算法通常會把原始數(shù)據(jù)切割分塊，然后對每個數(shù)據(jù)分塊獨立壓縮編碼。壓縮數(shù)據(jù)通常由一系列壓縮塊(compressed blocks)組成，這些壓縮塊對應(yīng)于原始數(shù)據(jù)的連續(xù)塊。最常見的數(shù)據(jù)壓縮算法(Gzip、Zip、Zlib等)會將原始數(shù)據(jù)塊壓縮編碼成一種名為Deflate的壓縮數(shù)據(jù)塊[2]。Deflate是一種將LZ77算法和Huffman Coding結(jié)合起來的無損數(shù)據(jù)壓縮協(xié)議。

LZ系列算法最早由Ziv和Lempel[3-4]在1977年和1978年的兩篇論文中提出。這兩篇論文構(gòu)造了兩個不同類型的數(shù)據(jù)壓縮算法，LZ系列的核心重復(fù)數(shù)據(jù)搜索查詢。基于1977年論文的數(shù)據(jù)壓縮算法都稱為LZ77數(shù)據(jù)壓縮算法。LZ77算法是利用動態(tài)字典實現(xiàn)重復(fù)數(shù)據(jù)的查找：首先利用已有數(shù)據(jù)作為動態(tài)字典，通過檢查字典，判斷當(dāng)前輸入的數(shù)據(jù)是否在滑動窗口內(nèi)的先前數(shù)據(jù)中出現(xiàn)過，隨后對重復(fù)數(shù)據(jù)進(jìn)行編碼。

哈夫曼編碼[5](Huffman coding)是由David A. Huffman于1952年提出的一種基于頻率統(tǒng)計的變長編碼。在數(shù)據(jù)壓縮過程中，通過構(gòu)建Huffman樹來生成源符號的Huffman碼。Huffman樹的高度決定源符號的最長Huffman碼。Deflate協(xié)議限定Huffman碼長不能超過15，因此當(dāng)Huffman樹的高度超過限定值時，需要對Huffman樹“校正”，再生成哈夫曼碼。Zlib等參考軟件代碼里的基于二叉樹搜索的校正算法，需要遍歷搜索整棵Huffman樹，尋找嫁接“節(jié)點”，校正流程時間消耗非常大，而且不利于硬件化實現(xiàn)。

1 Huffman算法原理

Huffman編碼[6]是一種基于數(shù)據(jù)統(tǒng)計的變長編碼算法。哈夫曼編碼已經(jīng)被證明是一種編碼效率最佳的變長編碼方案，所以哈夫曼編碼也被叫做最佳編碼。當(dāng)前哈夫曼編碼被廣泛應(yīng)用于圖像、視頻、文本等不同類型數(shù)據(jù)壓縮編碼中，JPEG、JPEG2000等圖像壓縮格式中運(yùn)用哈夫曼碼編碼圖像數(shù)據(jù)[7-8]，H263視頻編解碼標(biāo)準(zhǔn)[9]中使用哈夫曼碼編碼視頻流數(shù)據(jù)，Gzip[10]、Zlib[11]等數(shù)據(jù)壓縮標(biāo)準(zhǔn)都用到哈夫曼編碼實現(xiàn)文本數(shù)據(jù)壓縮。

Huffman編碼算法利用符號的頻率分布構(gòu)建Huffman樹，從而生成每個符號相對應(yīng)的哈夫曼碼[5]。Huffman編碼算法的流程如圖1所示，大體可分解為如下三個步驟：

(1)統(tǒng)計源符號中各個符號出現(xiàn)的頻率，并按照頻率對符號進(jìn)行排序。Deflate協(xié)議中的源符號(Source symbols)是原始數(shù)據(jù)LZ77算法搜索查重后輸出的待編碼符號[2]，包括原文字母(Literal)、匹配長度(Match length)、偏移距離(Match distance)。

(2)構(gòu)建源符號的Huffman樹。

(3)利用Huffman樹生成Huffman碼表。

圖1 Huffman編碼流程

Huffman編碼算法的精妙之處在于，該算法完全依照各個符號的頻率，合理精確地為每個符號分配碼長，Huffman編碼是最接近信息熵的變長編碼方案。其中算法原理Huffman編碼的精髓在于構(gòu)建Huffman樹。該文以 “abcdefghacdefghacdefhacdehadehaehaee”字符串為例，詳述Huffman樹的構(gòu)建算法。

構(gòu)建Huffman樹時，需要統(tǒng)計各個符號出現(xiàn)的次數(shù)，按照出現(xiàn)的次數(shù)從小到大對符號進(jìn)行排序。上述字符串由“a”、“b”、“c”、“d”、“e”、“f”、“g”、“h”八個符號組成，按照它們的出現(xiàn)次數(shù)從大到小排序如表1所示，下面詳細(xì)描述Huffman樹的構(gòu)建流程。

表1 源符號排序序列

1.1 Huffman樹構(gòu)建算法

Huffman樹數(shù)學(xué)形式上就是一種二叉樹，文獻(xiàn)[5]中David A. Huffman詳述了Huffman樹的構(gòu)建過程，對源符號(節(jié)點)進(jìn)行多輪迭代排序及合并，構(gòu)建Huffman樹。在每一輪中，會把符號序列中頻率最小的兩個符號合并生成一個新符號(父節(jié)點)，新符號的頻率為兩個符號的頻率相加值，同時需要將這兩個符號移出符號系列。 生成 Huffman樹所需的輪數(shù)與源符號數(shù)目減1。下面以表1所示符號序列為例，詳述整個Huffman樹構(gòu)建流程：

第1輪：原始序列中最小的兩個頻率相加(“1”和“2”)，合并為一個概率為3的節(jié)點，新序列重新排序結(jié)果為 8,7,6,5,4,3(1+2),3；

第2輪： 把第1輪生成新序列中最小的兩個頻率相加(“3”和“3”)，合并為一個概率為6的節(jié)點，新序列重新排序結(jié)果為8,7,6(3+3),6,5,4；

第3輪： 把第2輪生成新序列中最小的兩個頻率相加(“4”和“5”)，合并為一個概率為9的節(jié)點，新序列重新排序結(jié)果為9,8,7,6,6；

第4輪：把第3輪生成新序列中最小的兩個頻率相加(“6”和“6”)，合并為一個概率為12的節(jié)點，新序列重新排序結(jié)果為12,9,8,7；

第5輪：把第4輪生成新序列中最小的兩個頻率相加(“7”和“8”)，合并為一個概率為15的節(jié)點，新序列重新排序結(jié)果為15,12,9；

第6輪：把第5輪生成新序列中最小的兩個頻率相加(“9”和“12”)，合并為一個概率為21的節(jié)點，此時序列中僅剩兩個節(jié)點15，21；

第7輪：把第6輪生成最后的兩個節(jié)點相加，合并為一個概率為36的根節(jié)點。

以上迭代排序及合并流程，可以用圖2形象描述。

圖2 源符號迭代排序流程

圖2所示的迭代排序流程，就是構(gòu)建Huffman樹的流程，上述例子最終生成的Huffman樹如圖3所示。

圖3 Huffman樹示意圖

1.2 超長Huffman碼的問題

在構(gòu)建Huffman樹時，Huffman樹的高度通常定義為Huffman樹上葉子節(jié)點的最大碼長。 如圖3所示，Huffman樹的深度為5。根據(jù)Huffman算法原理可知，Huffman樹的深度與源符號的(葉子節(jié)點)的概率分布相關(guān)。

由二叉樹相關(guān)理論可知[12]，理論最大高度Heightmax等于二叉樹的葉子節(jié)點數(shù)目Numleaf-1，即式(1)：

Heightmax= Numleaf-1

(1)

當(dāng)二叉樹呈現(xiàn)出如圖4所示(樹上的字母(“a”- “g”)表示Huffman樹的葉子節(jié)點，樹上數(shù)字表示枝節(jié)點，圖中右側(cè)的數(shù)字表示每個葉子節(jié)點的碼長)的樹形，此時就是理論最大高度的情形。Deflate格式的編碼數(shù)據(jù)塊由三種類型不同的字符集構(gòu)成：原文字母、匹配長度、偏移距離。Deflate協(xié)議中，需要構(gòu)建兩種類型的哈夫曼樹：Literal & length樹和Distance樹。Literal & length樹的源符號總數(shù)為 286，其中值0…255表示原文字母，值256表示塊結(jié)束符，值257…285表示匹配長度，Distance樹的源符號總數(shù)為30。因此，這兩棵樹的理論最大深度為285和29。Deflate協(xié)議中規(guī)定這兩棵哈夫曼樹的最大高度都為15[2]，因此當(dāng)由源符號經(jīng)頻率排序生成的Huffman樹(該文把此階段的Huffman樹稱為原樹)高度超過規(guī)定最大值(15)時，需要先對原樹“修整”，然后再用校正后的Huffman樹生成Huffman碼。Deflate協(xié)議規(guī)定Huffman碼長的最大值，但是沒有規(guī)定校正算法。

圖4 Huffman樹圖距離

1.3 超長Huffman碼校正算法

在Zlib、Gzip等壓縮標(biāo)準(zhǔn)的參考代碼里，使用一種基于二叉樹搜索的校正方案。以圖4為例，假定此樹的規(guī)定最大高度為5，需要對該樹上碼長大于5的葉子節(jié)點進(jìn)行校正。校正流程描述如下：

第1步：遍歷整棵Huffman樹，找到一對碼長最長的兄弟葉子節(jié)點(“a”和“b”)。

第2步：遍歷整棵Huffman樹，找到一個比規(guī)定碼長小1的葉子節(jié)點(“d”)。

第3步：把第1步中兄弟節(jié)點的一個放入父節(jié)點的位置，裁取另一個葉子(把“a”節(jié)點放入“5”節(jié)點位置，裁取“b”節(jié)點)。

第4步：把第1、2步中選取的葉子節(jié)點(“d”與“b”)組合成一對兄弟節(jié)點，它們的父節(jié)點的位置就是“d”的原位置。

上述軟件校正流程如圖5所示，需要遍歷二叉樹找到超長節(jié)點位置跟“嫁接位置”。由于二叉樹無法直接通過索引尋址，需要搜尋二叉樹，通過鏈表尋址方式找到目標(biāo)節(jié)點。要想用硬件化實現(xiàn)上述軟件校正流程，由于硬件很難實現(xiàn)對二叉樹搜索，此外整個搜索流程耗時非常大。某些情形下，Huffman碼樹上超長的葉子節(jié)點可能會存在很多，以上遍歷搜索流程不能并行實現(xiàn)處理，這會加劇校正哈夫曼碼樹的時間消耗，極端情形下，校正Huffman Tree的時間消耗會數(shù)倍于構(gòu)建哈夫曼碼樹的時間消耗。如上所述，二叉樹搜索的校正方案校正超長碼的時間消耗較大，并且不利于硬件實現(xiàn)，因此十分有必要找到一種易于硬件實現(xiàn)的快速校正方案。

注：1.找到一對超長的兄弟節(jié)點(“a”和“b”); 2.找到嫁接位置“d”；3.把“a”節(jié)點放入“5”所示的位置；4.將“b”與“d”組成一對兄弟節(jié)點。

2 基于上下文模型的校正方案

2.1 超長Huffman碼概率統(tǒng)計實驗

由二叉樹理論可知，Deflate協(xié)議中Huffman碼長理論上會超過限定的最大值。為了探究超長Huffman碼的發(fā)生概率，利用Zlib參考代碼設(shè)計如下實驗：

(1)運(yùn)用Zlib代碼壓縮參考數(shù)據(jù)集(Silesia & Canterbury)里面每個文件，統(tǒng)計每個文件分塊數(shù)目block-number。

(2)Zlib代碼中包含校正超長Huffman碼的函數(shù)接口，通過統(tǒng)計調(diào)用校正接口的次數(shù)來統(tǒng)計超長Huffman塊的數(shù)目ultra-block-number。

(3)超長碼的發(fā)生概率計算方法如式(2)：

(2)

上述超長碼概率統(tǒng)計實驗數(shù)據(jù)如表2所示，最后計算得超長Huffman碼的平均發(fā)生概率為35.5%，由此說明超長Huffman碼的出現(xiàn)頻率比較高。所以，有必要找到一種快速校正哈夫曼碼樹的硬件方案。

表2 參考數(shù)據(jù)集超長Huffman頻率統(tǒng)計

2.2 上下文間Huffman碼表相似性實驗

上下文模型是利用上文與下文之間的相似性構(gòu)建的算法模型。在數(shù)據(jù)壓縮編碼中，上下文模型有廣泛的應(yīng)用：H264、HEVC等視頻編解碼標(biāo)準(zhǔn)中采用的CAVLC、CABAC兩種熵編碼方案都是基于上下文模型構(gòu)建[13-14]；LZ77算法為了搜索重復(fù)數(shù)據(jù)構(gòu)建的字典也是一種上下文模型。

假設(shè)上下文之間的哈夫曼碼表具有很高的“相似性”，可以利用上文中的正常哈夫曼碼表來對下文的源符號(source symbol)進(jìn)行編碼，從而規(guī)避超長的哈夫曼碼樹，實現(xiàn)“校正”超高哈夫曼碼樹的功能。

上述校正方案成立的假設(shè)條件是上下文之間的哈夫曼碼表具有很高的“相似性”,為了測試上下文之間的哈夫曼碼表具有很高的相似性，設(shè)計如下實驗，利用PSNR(峰值信噪比，Peak Signal to Noise Ratio)指標(biāo)評價上下文間哈夫曼碼表的相似性。

在圖像視頻領(lǐng)域，PSNR是一種評價圖像質(zhì)量的客觀標(biāo)準(zhǔn)。圖像(視頻)壓縮領(lǐng)域通常為有損壓縮，即編解碼后的影像會跟原始影像不同，編解碼領(lǐng)域一般采用PSNR值作為衡量編解碼算法的性能指標(biāo)[12]。PSNR[15]的計算方法如公式(3)：

(3)

式中，Peak為像素的最大值，Peak值與像素的bit數(shù)n有關(guān)：Peak=2n-1。

MSE為原始影像與編解碼后影像之間的均方差，MSE的計算方法如公式(4)：

(4)

式中，N為圖像中像素的數(shù)目，P為像素值。所以，PSNR也可用公式(5)計算：

(5)

PSNR不僅是一種評價圖像質(zhì)量的指標(biāo)，也是一種判斷圖像相似性的指標(biāo)。事實上從公式的內(nèi)容看，PSNR就是通過計算兩幅圖像(原始圖像與處理后圖像)之間的差異性來評價圖像質(zhì)量的。HEVC、VP9等視頻編解碼標(biāo)準(zhǔn)用PSNR作為評價視頻中前后幀相似性的指標(biāo)[13-14〗，PSNR值越大，相似性越高。在本實驗中，利用PSNR指標(biāo)衡量前后兩個數(shù)據(jù)塊的Huffman樹的相似性計算。

Deflate中Huffman碼長用4bit數(shù)字標(biāo)識，即公式(5)中n取值為4;公式(5)可以轉(zhuǎn)換成公式(6)：

(6)

Deflate協(xié)議中Literal & length的符號數(shù)目為286，Distance的符號數(shù)目為30；所以兩種Huffman碼表的均方差公式分別如下：

literal_cl1[i])2

(7)

式(7)為Literal & length碼表均方差公式，其中l(wèi)iteral_cl1[]為上文碼表，literal_cl2[]為下文碼表；

式(8)為Distance碼表的均方差公式，其中dist_cl1[]為上文碼表，dist_cl2[]為下文碼表。

運(yùn)用公式(6)～(8)統(tǒng)計計算測試集中上下文之間兩種Huffman碼表的相似性(PSNR)數(shù)據(jù)。圖6為測試數(shù)據(jù)集中三種典型文件數(shù)據(jù)的上下文之間的PSNR數(shù)值分布圖?！癰ible”、“mr”、“cp.html”分別代表文本、圖像、網(wǎng)頁三種最常見的格式文件：其中“bible”是一個文本數(shù)據(jù)[16]，“mr”是一張醫(yī)療診斷照片[17]，“cp.html”是一個html格式網(wǎng)頁文件[16]。

圖6 上下文之間Huffman碼表相似性(PSNR)散點圖

圖中第1列為上下文之間Literal-Huffman碼表的相似數(shù)據(jù),PSNR的值總體大于30。第2列為上下文之間Distance-Huffman碼表的相似數(shù)據(jù)，PSNR的值總體大于30。說明兩種Huffman樹的上下文間的相似性比較高。

統(tǒng)計并計算圖6每個子圖中PSNR數(shù)據(jù)的中值，評估上下文之間總體PSNR取值，計算結(jié)果見表3。

表3 Huffman碼表上下文間PSNR統(tǒng)計值(中值)

之所以統(tǒng)計計算中值，而不是均值，是因為塊間的Huffman碼表如果完全一致，其MSE的值為0，PSNR取值無窮大，均值也無窮大。

由圖6以及表3可以看出，對于Literal類型的Huffman碼表，三個文件的上下文之間的PSNR中值分別為29.956 0(bible)、32.403 0(mr)、33.772 0(cp.html)?？梢哉J(rèn)為Literal類型碼表PSNR總體取值在30以上。對于Distance類型的Huffman碼表，三個文件的上下文之間的PSNR中值分別為26.392 0(bible)、26.252 0(mr)、29.842 0(cp.html)。由此可以認(rèn)為總體取值在25以上。通常采用以下PSNR經(jīng)驗閾值來評定相似性[9,13-14]：PSNR如果大于35，接近一致；PSNR如果大于25，高度一致。PSNR如果小于15，相似性較低。因此可以認(rèn)定，上下文之間的兩種哈夫曼碼表都具有很高的相似性，即上下文之間哈夫曼碼表具有高度相似性的假設(shè)成立。

2.3 基于上下文模型快速校正超長Huffman碼方案

基于上下文模型設(shè)計了一種快速校正超長Huffman碼的硬件方案(如圖7所示)，在常規(guī)Deflate編碼方案中添加一組參考Huffman碼表(該文采用的上下文模型)。參考Huffman碼表用來保存最新的常規(guī)的Huffman碼表，當(dāng)發(fā)現(xiàn)哈夫曼樹超長時，會直接運(yùn)用參考Huffman碼表編碼源數(shù)據(jù)，編碼流程中會對參考Huffman碼表更新。

圖7 基于上下文模型校正超長Huffman碼流程

第1步：Deflate模塊對LZ77輸出的源數(shù)據(jù)進(jìn)行統(tǒng)計排序，并構(gòu)建Huffman樹。

第2步：Huffman樹構(gòu)建完成后，判斷Huffman樹的最大節(jié)點深度是否超出限定值。

如果原樹的高度不超過限定值，此時不需要校正Huffman樹，執(zhí)行常規(guī)編碼流程(第3步)。

如果原樹高度超出限定值，此時需要執(zhí)行校正流程(第4步)。

第3步：常規(guī)流程，如前文所述。利用Huffman樹生成常規(guī)Huffman碼表，并利用Huffman碼表編碼源數(shù)據(jù)。同時會利用參考Huffman碼表記錄常規(guī)Huffman碼表，即用本次生成的碼表刷新(寫)參考碼表的數(shù)值，偽代碼算法1。參考碼表會參與下文中超長Huffman碼的校正。

算法1：Huffman碼表參考算法。

for index = 0 : max_symbol

Ref-Huff-table [index].length ← Huff-table [index].length

Ref-Huff-table [index].code ← Huff-table [index].code

end

第4步：校正流程(圖)，利用參考Huffman碼表實現(xiàn)校正功能：直接用參考Huffman碼表編碼源數(shù)據(jù)，即當(dāng)前塊數(shù)據(jù)采用與上一個塊相同的Huffman碼表進(jìn)行數(shù)據(jù)編碼。校正流程中無需更新參考碼表。

如上所述，在校正流程中，直接利用上文中已生成的常規(guī)Huffman碼表編碼下文的源數(shù)據(jù)，因此該校正方案會將校正Huffman樹的時間消耗降為零，可以提高Deflate的壓縮效率。

3 上下文模型校正方案的測試實驗

上文中提出一種基于上下文模型的校正方案，該方案具有校正效率快的優(yōu)點，同時還需要獲取該方案的數(shù)據(jù)壓縮性能(壓縮比，Ratio)。為此，實驗中選用常見的兩個壓縮測試數(shù)據(jù)集Canterbury和Silesia[16-18]測試評估上下文校正方案的壓縮性能。這兩組測試數(shù)據(jù)集既有文本、圖像、網(wǎng)頁等傳統(tǒng)類型的數(shù)據(jù)文件，也包含數(shù)據(jù)庫、多媒體、程序文件等新型數(shù)據(jù)文件。運(yùn)用兩種方案(上下文模型與二叉樹搜索方案)壓縮數(shù)據(jù)集內(nèi)的所有文件(表2中所示的不存超長塊的文件無需再測試)，通過對比兩種方案的壓縮比，評估上下文模型校正方案的性能。表4為測試實驗的數(shù)據(jù)統(tǒng)計。

表4對比兩種校正方案的壓縮性能。第1列(文件名)與第2列(Size)表示測試集內(nèi)文件名及其文件大??；第3列為運(yùn)用軟件算法壓縮文件得到的壓縮比(Ratio)；第4列用上下文模型方案壓縮得到各個測試文件的壓縮比；第5列(Delta)代表兩種方案之間的壓縮比差值(第4列數(shù)字減去第2列數(shù)字)；第6列(Delta-rate)的數(shù)據(jù)含義為該方案與軟件方案相比，壓縮比的增長率(Delta/Ratio軟件)；最后一行的數(shù)據(jù)為總體數(shù)據(jù)的均值。

由第5列、第6列的數(shù)據(jù)可以直觀看出，與軟件方案相比，上下文校正方案對于壓縮性影響非常?。簤嚎s比僅僅下降0.009 4，下降的百分率為0.372%。如果從壓縮比較評估，設(shè)計的基于上下文模型的校正方案對于壓縮性能的影響幾乎忽略不計。在基于上下文模型的校正方案中，規(guī)避掉超長Huffman碼，直接使用參考碼表參與Deflate編碼，與軟件校正方案相比，上下文校正方案省去“搜索”、“嫁接”等環(huán)節(jié)，因此該方案的校正時間為零。此外軟件方案“搜索”、“嫁接”等子流程，不易用硬件實現(xiàn)，而基于上下文模型的校正方案易于硬件化實現(xiàn)。

表4 兩種校正方案的壓縮對比

4 結(jié)束語

提出一種基于上下文模型校正超長Huffman碼的方案，方案會利用參考Huffman碼表保存上文中生成的Huffman碼表，參考Huffman碼表會用于編碼下文的存在超長Huffman碼的數(shù)據(jù)塊。論文中所述基于上下文模型的校正方案可以快速實現(xiàn)對超長Huffman碼的校正，并且易于通過硬件電路實現(xiàn)。與此同時，相對Zlib等軟件代碼中校正方案，將該校正方案用于數(shù)據(jù)壓縮，測試數(shù)據(jù)的整體壓縮比下降僅為0.009 4，下降率僅僅為0.372%，由此可以認(rèn)為數(shù)據(jù)的壓縮效果幾乎沒有區(qū)別。綜上，基于上下文模型校正超長Huffman碼的方案是一種快速的硬件校正方案。