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

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

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

0 引 言

隨著大數據等前沿科學技術的快速發展，催生數據爆發式的增長，海量數據對現有的存儲設備帶來巨大的壓力。面對持續增長的海量數據，數據壓縮成為減輕服務器存儲負擔，降低存儲成本的最有效方法。

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

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

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

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

1 Huffman算法原理

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

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

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

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

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

圖1 Huffman編碼流程

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

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

表1 源符號排序序列

1.1 Huffman樹構建算法

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

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

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

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

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

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

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

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

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

圖2 源符號迭代排序流程

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

圖3 Huffman樹示意圖

1.2 超長Huffman碼的問題

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

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

Heightmax= Numleaf-1

(1)

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

圖4 Huffman樹圖距離

1.3 超長Huffman碼校正算法

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

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

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

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

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

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

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

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

2.1 超長Huffman碼概率統計實驗

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

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

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

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

(2)

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

表2 參考數據集超長Huffman頻率統計

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

上下文模型是利用上文與下文之間的相似性構建的算法模型。在數據壓縮編碼中，上下文模型有廣泛的應用：H264、HEVC等視頻編解碼標準中采用的CAVLC、CABAC兩種熵編碼方案都是基于上下文模型構建[13-14]；LZ77算法為了搜索重復數據構建的字典也是一種上下文模型。

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

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

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

(3)

式中，Peak為像素的最大值，Peak值與像素的bit數n有關：Peak=2n-1。

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

(4)

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

(5)

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

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

(6)

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

literal_cl1[i])2

(7)

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

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

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

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

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

統計并計算圖6每個子圖中PSNR數據的中值，評估上下文之間總體PSNR取值，計算結果見表3。

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

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

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

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

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

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

第1步：Deflate模塊對LZ77輸出的源數據進行統計排序，并構建Huffman樹。

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

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

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

第3步：常規流程，如前文所述。利用Huffman樹生成常規Huffman碼表，并利用Huffman碼表編碼源數據。同時會利用參考Huffman碼表記錄常規Huffman碼表，即用本次生成的碼表刷新(寫)參考碼表的數值，偽代碼算法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碼表實現校正功能：直接用參考Huffman碼表編碼源數據，即當前塊數據采用與上一個塊相同的Huffman碼表進行數據編碼。校正流程中無需更新參考碼表。

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

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

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

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

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

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

4 結束語

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