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

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

0 引 言

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

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

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

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

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

1 Huffman算法原理

Huffman編碼[6]是一種基于數(shù)據(jù)統(tǒng)計(jì)的變長(zhǎng)編碼算法。哈夫曼編碼已經(jīng)被證明是一種編碼效率最佳的變長(zhǎ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)都用到哈夫曼編碼實(shí)現(xiàn)文本數(shù)據(jù)壓縮。

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

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

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

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

圖1 Huffman編碼流程

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

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

表1 源符號(hào)排序序列

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

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

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

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

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

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

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

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

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

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

圖2 源符號(hào)迭代排序流程

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

圖3 Huffman樹示意圖

1.2 超長(zhǎng)Huffman碼的問(wèn)題

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

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

Heightmax= Numleaf-1

(1)

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

圖4 Huffman樹圖距離

1.3 超長(zhǎng)Huffman碼校正算法

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

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

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

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

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

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

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

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

2.1 超長(zhǎng)Huffman碼概率統(tǒng)計(jì)實(shí)驗(yàn)

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

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

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

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

(2)

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

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

2.2 上下文間Huffman碼表相似性實(shí)驗(yàn)

上下文模型是利用上文與下文之間的相似性構(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è)上下文之間的哈夫曼碼表具有很高的“相似性”，可以利用上文中的正常哈夫曼碼表來(lái)對(duì)下文的源符號(hào)(source symbol)進(jìn)行編碼，從而規(guī)避超長(zhǎng)的哈夫曼碼樹，實(shí)現(xiàn)“校正”超高哈夫曼碼樹的功能。

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

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

(3)

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

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

(4)

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

(5)

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

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

(6)

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

literal_cl1[i])2

(7)

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

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

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

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

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

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

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

之所以統(tǒng)計(jì)計(jì)算中值，而不是均值，是因?yàn)閴K間的Huffman碼表如果完全一致，其MSE的值為0，PSNR取值無(wú)窮大，均值也無(wú)窮大。

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

2.3 基于上下文模型快速校正超長(zhǎng)Huffman碼方案

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

圖7 基于上下文模型校正超長(zhǎng)Huffman碼流程

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

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

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

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

第3步：常規(guī)流程，如前文所述。利用Huffman樹生成常規(guī)Huffman碼表，并利用Huffman碼表編碼源數(shù)據(jù)。同時(shí)會(huì)利用參考Huffman碼表記錄常規(guī)Huffman碼表，即用本次生成的碼表刷新(寫)參考碼表的數(shù)值，偽代碼算法1。參考碼表會(huì)參與下文中超長(zhǎng)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碼表實(shí)現(xiàn)校正功能：直接用參考Huffman碼表編碼源數(shù)據(jù)，即當(dāng)前塊數(shù)據(jù)采用與上一個(gè)塊相同的Huffman碼表進(jìn)行數(shù)據(jù)編碼。校正流程中無(wú)需更新參考碼表。

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

3 上下文模型校正方案的測(cè)試實(shí)驗(yàn)

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

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

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

表4 兩種校正方案的壓縮對(duì)比

4 結(jié)束語(yǔ)

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