三進(jìn)制霍夫曼編碼

三進(jìn)制霍夫曼編碼

ID:41150855

大?。?74.51 KB

頁數(shù):9頁

時(shí)間:2019-08-17

三進(jìn)制霍夫曼編碼_第1頁
三進(jìn)制霍夫曼編碼_第2頁
三進(jìn)制霍夫曼編碼_第3頁
三進(jìn)制霍夫曼編碼_第4頁
三進(jìn)制霍夫曼編碼_第5頁
資源描述:

《三進(jìn)制霍夫曼編碼》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫

1、題目:將霍夫曼編碼推廣至三進(jìn)制編碼,并證明它能產(chǎn)生最優(yōu)編碼?!鶎⒒舴蚵幋a推廣至三進(jìn)制編碼設(shè)一個(gè)數(shù)據(jù)文件包含Q個(gè)字符:A1,A2,……,Aq,每個(gè)字符出現(xiàn)的頻度對(duì)應(yīng)為P:P1,P2,……,Pq。1.將字符按頻度從大到小順序排列,記此時(shí)的排列為排列1。2.用一個(gè)新的符號(hào)(設(shè)為S1)代替排列1中頻度值最小的Q-2k(k為(Q-1)/2取整)個(gè)字符,并記其頻度值為排列1中最小的Q-2k個(gè)頻度值相加,再重新按頻度從大到小順序排列字符,記為排列2。(注:若Q-2k=0,則取其值為2,若Q-2k=1,則取其值為3.)3.對(duì)

2、排列2重復(fù)上述步驟2,直至最后剩下3個(gè)概率值。4.從最后一個(gè)排列開始編碼,根據(jù)3個(gè)概率大小,分別賦予與3個(gè)字符對(duì)應(yīng)的值:0、1、2,如此得到最后一個(gè)排列3個(gè)頻度的一位編碼。5.此時(shí)的3個(gè)頻度中有一個(gè)頻度是由前一個(gè)排列的3個(gè)相加而來,這3個(gè)頻度就取它的一位編碼后面再延長一位編碼,得到二位編碼,其它不變。6.如此一直往前,直到排列1所有的頻度值都被編碼為止。舉例說明如下(假設(shè)Q=9):字符A1A2A3A4A5A6A7A8A9頻度0.220.180.150.130.100.070.070.050.03字符頻度編碼頻度

3、編碼頻度編碼頻度編碼A10.2220.2220.3010.480A20.18000.18000.2220.301A30.15020.15010.18000.222A40.13100.15020.1501A50.10110.13100.1502A60.07120.1011A70.070100.0712A80.05011A90.03012頻度中的黑體為前一頻度列表中斜體頻度相加而得。編碼后字符A1~A9的碼字依次為:2,00,02,10,11,12,010,011,012。構(gòu)造三進(jìn)制霍夫曼編碼偽碼程序如下:HUFF

4、MAN(C)1n←∣C∣2Q←C3fori←1ton-14doallocateanewnodes5left[s]←x←EXTRACT-MIN(Q)6middle[s]←y←EXTRACT-MIN(Q)7right[s]←z←EXTRACT-MIN(Q)8f[s]←f[x]+f[y]+f[z]9INSERT(Q,z)10returnEXTRACT-MIN(Q)※霍夫曼編碼(三進(jìn)制)最優(yōu)性證明在二進(jìn)制霍夫曼編碼中,文件的最優(yōu)編碼由一棵滿二叉樹表示,樹中每個(gè)非葉子結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。在此與之相對(duì)應(yīng),構(gòu)造一棵滿三叉樹來

5、表示三進(jìn)制的霍夫曼編碼,樹中每個(gè)非葉子結(jié)點(diǎn)都有三個(gè)子結(jié)點(diǎn)。對(duì)文件中A中的每個(gè)字符a,設(shè)f(a)表示a在文件中出現(xiàn)的頻度,dT(a)表示字符a的編碼長度,亦即a的葉子在樹中的深度。這樣,編碼一個(gè)文件所需的位數(shù)就是B(T)=∑f(a)dT(a)設(shè)A為一給定文件,其中每個(gè)字符都定義有頻度f[a]。設(shè)x,y和z是A中具有最低頻度的兩個(gè)字符。并設(shè)A'為文件A中移去x,y和z,再加上新的字符s后的文件,亦即A'=A-{x,y,z}∪{s};如A一樣為A'定義f,其中f[s]=f[x]+f[y]+f[z]。設(shè)T'為文件A'上

6、最優(yōu)前綴編碼的任意一棵樹,那么,將T'中葉子節(jié)點(diǎn)s換成具有x,y和z孩子的內(nèi)部節(jié)點(diǎn)所得到的樹T,表示文件A上的一個(gè)最優(yōu)前綴編碼。證明:對(duì)每一個(gè)a∈A-{x,y,z},有dT(a)=dT'(a),故f[a]dT(a)=f[a]dT'(a)。又dT'(x)=dT'(y)=dT'(z)=dT''(s)+1,從而有:f[x]dT'(x)+f[y]dT'(y)+f[z]dT'(z)=(f[x]+f[y]+f[z])(dT''(s)+1)=f[s]dT''(s)+(f[x]+f[y]+f[z])由此可得:B(T)=B(T'

7、)+f[x]+f[y]+f[z]假設(shè)T不表示A的最優(yōu)前綴編碼,那么存在一棵樹T'',有B(T'')#i

8、nclude#includeintSorting(int*x,intn){//排序int*a,b,i,j,r=0;a=x;for(j=0;j

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無此問題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。