自適應(yīng)霍夫曼編碼

自適應(yīng)霍夫曼編碼院系：信息科學(xué)與工程學(xué)院

專業(yè)：通信與信息系統(tǒng)

學(xué)號(hào)：10S030084

姓名：吳立亮自適應(yīng)霍夫曼編碼10S030084吳立亮一．引言在實(shí)際應(yīng)用中，經(jīng)常使用的字符比較集中，每個(gè)字符使用的頻率相差很大，如果根據(jù)字符使用頻率的高低不同，采用不同長(zhǎng)度的二進(jìn)制位表示字符，即采用變長(zhǎng)編碼方法，使用頻率高的字符編碼短一些，而使用頻率低的字符編碼長(zhǎng)一些，這樣就可以明顯地減少數(shù)據(jù)存儲(chǔ)和通信時(shí)的開(kāi)銷，同時(shí)對(duì)數(shù)據(jù)也能起到保密的作用。二、靜態(tài)霍夫曼編碼的的問(wèn)題哈夫曼編碼技術(shù)是一種比較常用的變長(zhǎng)編碼方法，最早由DavidHuffman提出。它采用的是一種優(yōu)化靜態(tài)編碼方法，由該算法產(chǎn)生的二叉樹(shù)具有最小的加權(quán)路長(zhǎng)之和丫W(wǎng)jLj,其中Wj是哈夫曼樹(shù)中第k個(gè)葉結(jié)點(diǎn)的重量,Lj為該葉結(jié)點(diǎn)到樹(shù)根的距離。假設(shè)原始數(shù)據(jù)中含有k個(gè)各不相同的字符a,a,a，其編碼方式就是為這k個(gè)12k各不相同的字符都靜態(tài)地分配一個(gè)Lj位的“?！薄?”編碼序列（因而稱為靜態(tài)哈夫曼編碼），該序列指明由根結(jié)點(diǎn)到第j個(gè)葉結(jié)點(diǎn)的路徑，“0”表示向左，“1”表示向右，并用該序列替換原始數(shù)據(jù)中的對(duì)應(yīng)字符。靜態(tài)哈夫曼方法的最大缺點(diǎn)就是它需要對(duì)原始數(shù)據(jù)進(jìn)行兩遍掃描:第一遍統(tǒng)計(jì)原始數(shù)據(jù)中各字符出現(xiàn)的頻率，利用得到的頻率值創(chuàng)建哈夫曼樹(shù)并將樹(shù)的有關(guān)信息保存起來(lái)，便于解壓時(shí)使用;第二遍則根據(jù)前面得到的哈夫曼樹(shù)對(duì)原始數(shù)據(jù)進(jìn)行編碼，并將編碼信息存儲(chǔ)起來(lái)。這樣如果用于網(wǎng)絡(luò)通信中，將會(huì)引起較大的延時(shí);對(duì)于文件壓縮這樣的應(yīng)用場(chǎng)合，額外的磁盤訪間將會(huì)降低該算法的數(shù)據(jù)壓縮速度。為此Faller等人提出了自適應(yīng)即動(dòng)態(tài)哈夫曼編碼方法，，它對(duì)數(shù)據(jù)編碼的依據(jù)是動(dòng)態(tài)變化的哈夫曼樹(shù)，也就是說(shuō)，對(duì)第t+1個(gè)字符編碼是根據(jù)原始數(shù)據(jù)中前t個(gè)字符得到的哈夫曼樹(shù)來(lái)進(jìn)行的.壓縮和解壓子程序具有相同的初始化樹(shù)，每處理完一個(gè)字符，壓縮和解壓方使用相同的算法修改哈夫曼樹(shù)，因而該方法不需要為解壓而保存樹(shù)的有關(guān)信息。壓縮和解壓一個(gè)字符所需的時(shí)間與該字符的編碼長(zhǎng)度成正比，因而該過(guò)程可以實(shí)時(shí)進(jìn)行。三、自適應(yīng)霍夫曼編碼為了便于說(shuō)明，我們先進(jìn)行一些定義。原始數(shù)據(jù):需要被壓縮的數(shù)據(jù)壓縮數(shù)據(jù):被壓縮過(guò)的數(shù)據(jù)n:字母表的長(zhǎng)度a:字母表中第j個(gè)字符jt:已處理的原始數(shù)據(jù)中字符的總個(gè)數(shù)k:已處理數(shù)據(jù)中各不相同字符的個(gè)數(shù)顯然1<j,k<n在壓縮開(kāi)始前，需要引進(jìn)一個(gè)空葉結(jié)點(diǎn)，它的重量值始終為。。在以后的壓縮和解壓過(guò)程中，如果kvn,我們用它來(lái)表示n-k個(gè)字母表中還未出現(xiàn)的字符。初始化的哈夫曼樹(shù)中只有一個(gè)根結(jié)點(diǎn)和空葉結(jié)點(diǎn)。

壓縮子程序讀進(jìn)一個(gè)字符后，它將該字符加到根結(jié)點(diǎn)的右分枝上，而空葉結(jié)點(diǎn)仍留在左分枝上，然后將該字符以A義11碼方式輸出。解壓子程序?qū)ζ涔蚵鼧?shù)作同樣的調(diào)整。以后每讀進(jìn)一個(gè)字符a。，壓縮子it程序都執(zhí)行以下的步驟：首先它檢查a。是否出現(xiàn)在編碼樹(shù)中，如果是，it壓縮子程序就以靜態(tài)哈夫曼編碼中相同的方式對(duì)a.進(jìn)行編碼;如果a不在itit編碼樹(shù)中，壓縮子程序首先對(duì)空葉結(jié)點(diǎn)進(jìn)行編碼，然后將a輸出，最后編it碼樹(shù)中增加兩個(gè)結(jié)點(diǎn):在空葉結(jié)點(diǎn)的右分枝上加入一個(gè)新結(jié)點(diǎn)，并將a:放在it里面，然后在其左分枝上加入一個(gè)新的空葉結(jié)點(diǎn)。自適應(yīng)哈夫曼編碼的關(guān)鍵就是如何將前t個(gè)字符的哈夫曼樹(shù)調(diào)整成一棵前t+1個(gè)字符的哈夫曼樹(shù)。為解決上述問(wèn)題，分兩步進(jìn)行。第1步把前t個(gè)字符的哈夫曼樹(shù)轉(zhuǎn)換成它的另一種形式，在該樹(shù)中只需在第二步中簡(jiǎn)單把由根到葉結(jié)點(diǎn)a，路徑上的所有結(jié)

it+1點(diǎn)重量加1，就可以變成前t+1個(gè)字符的哈夫曼樹(shù).其過(guò)程就是以葉結(jié)點(diǎn)ait+1為初始的當(dāng)前結(jié)點(diǎn)，重復(fù)地將當(dāng)前結(jié)點(diǎn)與具有同樣重量的序號(hào)最大的結(jié)點(diǎn)進(jìn)行交換，并使后者的父結(jié)點(diǎn)成為新的當(dāng)前結(jié)點(diǎn)，直到遇到根結(jié)點(diǎn)為止。編碼流程見(jiàn)圖1。.所謂交換結(jié)點(diǎn)，是指交換以該結(jié)點(diǎn)為根結(jié)點(diǎn)的二叉樹(shù)（如果該結(jié)點(diǎn)有二叉樹(shù)的話）。葉子結(jié)點(diǎn)重量就是該字符已經(jīng)出現(xiàn)的次數(shù)，空葉點(diǎn)的重量可以理解為字母表中尚未出現(xiàn)的字符出現(xiàn)的次數(shù)（因?yàn)槠渲亓繛?）。圖1自適應(yīng)霍夫曼編碼流程四、結(jié)束語(yǔ)自適應(yīng)哈夫曼編碼數(shù)據(jù)壓縮與復(fù)原方法，它克服了靜態(tài)哈夫曼編碼方法需要進(jìn)行兩遍掃描的缺點(diǎn)，具有較強(qiáng)的實(shí)時(shí)性，對(duì)于網(wǎng)絡(luò)特別是遠(yuǎn)程通信特別適合。參考文獻(xiàn)1方敏,秦曉新,劉本善.動(dòng)態(tài)哈夫