霍夫曼編碼簡(jiǎn)介

1霍夫曼編碼簡(jiǎn)介

21.1前言1.2霍夫曼編碼1.3有效的譯碼器1.4不等代價(jià)的編碼法1.5錯(cuò)誤更正能力1.7作業(yè)1.2.1靜態(tài)式

1.3.1省空間式1.2.2動(dòng)態(tài)式

1.3.2省時(shí)間式31.2霍夫曼編碼

1.2.1靜態(tài)式

圖1.1先編S7和S8圖1.2合并圖1.1和S6圖1.3合并S5和S4給定一符號(hào)集為，對(duì)應(yīng)的頻率為

4圖1.4最終的霍夫曼樹

符號(hào)碼s100s210s3011s4111s5110s60101s701000s801001圖1.5建成的碼表

霍夫曼編碼的確反應(yīng)了常出現(xiàn)的符號(hào)所編成的碼之長(zhǎng)度較短，而不常出現(xiàn)的符號(hào)所編成的碼之長(zhǎng)度較長(zhǎng)。

51.2.2動(dòng)態(tài)式

給一符號(hào)集且其出現(xiàn)的對(duì)應(yīng)頻率集為，最佳的霍夫曼樹需滿足為最小，這里表示的高度。

將霍夫曼樹上的節(jié)點(diǎn)從下層到上層和從左到右依序描掃，可得遞增數(shù)列，且滿足下式(1.1)圖1.6

二種可能的霍夫曼樹

(a)(b)6假設(shè)。若讀入符號(hào)，則會(huì)變?yōu)?，由圖1.7可知和的父親節(jié)點(diǎn)之頻率變?yōu)?，序列

就不具遞增性了。

圖1.7加入符號(hào)

(a)第一次調(diào)動(dòng)

(b)第二次調(diào)動(dòng)

圖1.8經(jīng)二次調(diào)動(dòng)后的霍夫曼樹

先將x4的子樹和最右邊編號(hào)且頻率為5的子樹對(duì)調(diào)得到圖1.8(a)，接著將x8的子樹和x9的子樹對(duì)調(diào)而得到圖1.8(b)。在圖1.8(b)上加入一個(gè)s2，并不會(huì)破壞霍夫曼編碼的最佳性。

7假設(shè)m為尚未出現(xiàn)過(guò)的字母?jìng)€(gè)數(shù)；令，且k為其在未出現(xiàn)過(guò)字母中的順位，則當(dāng)時(shí)，可用個(gè)位元的來(lái)表示該字母，否則，用e個(gè)位元的來(lái)表示該字母。

動(dòng)態(tài)式霍夫碼的實(shí)作令字母集={A,B,C,D,…,Z,!,;}，一開始。假設(shè)待編碼的訊息為CCHUNG。讀入C

由，且因C為第個(gè)字母，并滿足，所以將C編碼成5(=4+1)位元的，即00010。讀入C用位元‘1’編C即可。圖1.9處理完符號(hào)C后的霍夫曼樹(a)起始霍夫曼樹(b)處理完符號(hào)C后圖1.10處理完CC后的霍夫曼樹8圖1.12處理完CCHU后的霍夫曼樹

圖1.13處理完CCHUN后的霍夫曼樹

讀入H

，且H為第個(gè)字母，又滿足，再加上霍夫曼樹的0，所以H可編碼為000111。讀入U(xiǎn)

，且U為第個(gè)字母，又，所以將U編碼成4位元的，加上霍夫曼樹的00，得U的碼為

001010。

讀入N

N可編成000101101

。

圖1.11處理完CCH后的霍夫曼樹91.3有效的譯碼器

1.3.1省空間式

圖1.4最終的霍夫曼樹

圖1.14建構(gòu)好的單邊成長(zhǎng)霍夫曼樹令，，為單邊成長(zhǎng)霍夫曼樹的之碼。首先令且。根據(jù)式子，得到。

10代表第i層的外部節(jié)點(diǎn)數(shù)，，

內(nèi)部節(jié)點(diǎn)數(shù)之序列為，儲(chǔ)存符號(hào)集的陣列可安排為A[0…7]

。

假設(shè)收方收到的位元字符串為‘010’讀出位元‘0’，，所以需再讀入一個(gè)符號(hào)。讀了‘01’，由可知路徑是停在第二層的內(nèi)部節(jié)點(diǎn)。再讀入第三個(gè)符號(hào)‘0’，因?yàn)椋矣?，所以可知已達(dá)某一樹葉了，譯碼出符號(hào)。定理1.1給一訊息且，在單邊成長(zhǎng)霍夫曼樹上，解碼工作可于的時(shí)間內(nèi)完成。

符號(hào)碼s111s210s3011s4010s5001s60001s700001s800000圖1.15新建的碼表111.3.2省時(shí)間式圖1.4最終的霍夫曼樹

在圖1.4中，從樹根所在的第零層到第二層形成了一個(gè)完全子樹。利用廣先搜尋方法，碰到外部節(jié)點(diǎn)時(shí)，就將對(duì)應(yīng)的符號(hào)存入陣列；若碰到內(nèi)部節(jié)點(diǎn)時(shí)，就存入的值，代表該內(nèi)部節(jié)點(diǎn)左側(cè)且同層的內(nèi)部節(jié)點(diǎn)數(shù)，而代表該內(nèi)部節(jié)點(diǎn)右側(cè)的節(jié)點(diǎn)數(shù)。圖1.4可表示成下列的矩陣型式：

假設(shè)收方收到的位元字符串為0101

首先讀出二個(gè)位元01，接著讀出。第三個(gè)讀入的位元為0，所以推進(jìn)三格，而得到。讀入的第四個(gè)位元為1，所以陣列的指標(biāo)往前推進(jìn)五格，而得到。12給一以‘1’結(jié)尾的碼，如果目前的刀子切在第j層且滿足

，這里n可想成最終的碼數(shù)。令C代表Tj中的一個(gè)碼之平均位元數(shù)1.4不等代價(jià)的編碼法以1結(jié)尾的霍夫曼編碼

圖1.16和

令t為一顆樹，如圖1.16所示。我們?cè)跇涓幥幸坏?，如圖中橫線所示。則和，這里0代表切線(含)上的黑色葉子數(shù)為0，而1代表切線下的黑色葉子數(shù)為1。(1.2)可想成在第j層以下的未建立碼的深度暫時(shí)以j代替。符號(hào)D代表深度；符號(hào)li代表黑色葉節(jié)點(diǎn)；Pi代表黑色葉節(jié)點(diǎn)li的機(jī)率。13建立以‘1’結(jié)尾的碼，相當(dāng)于最終所建立的樹必需滿足為最小。

假設(shè)目前的，令，則擴(kuò)展到下一層，可表示為圖1.18

的所有擴(kuò)展可能(a)(b)(c)(d)14(e)圖1.18的所有擴(kuò)展可能由擴(kuò)展到時(shí)，若屬于的情形，則；若屬于的擴(kuò)展情形，則。

列出動(dòng)態(tài)規(guī)劃中的遞回式起始時(shí)，令，對(duì)而言，我們有對(duì)而言，我們有指的是切線以下所有黑色節(jié)點(diǎn)的頻率和。已知m介于0到n，而q介于0到2b。又已知b介于1到之間。分析后可得到共有組配對(duì)，因?yàn)槊恳粋€(gè)配對(duì)需的時(shí)間來(lái)決定最佳花費(fèi)。故可推得，總共需的時(shí)間以完成‘1’為結(jié)尾的建碼工作。

15不等代價(jià)編碼法之應(yīng)用

A˙－N－˙B－˙˙˙O－－－C－˙－˙P˙－－˙D－˙˙Q－－˙－E˙R˙－˙F˙˙－˙S˙˙˙G－－˙T－H˙˙˙˙U˙˙－I˙˙V˙˙˙－J˙－－－W˙－－K－˙－X－˙˙－L˙－˙˙Y－˙－－M－－Z－－˙˙圖1.19摩斯碼

假設(shè)長(zhǎng)音的‘答’需要二單位的花費(fèi)，而短音的‘嘀’需一個(gè)單位。那么LUCK總共需花費(fèi)。在摩斯碼中，句點(diǎn)‘˙’的音唸成‘嘀’，而較長(zhǎng)的線‘－’唸成長(zhǎng)音的‘答’。例如，‘嘀答嘀嘀嘀嘀答答嘀答嘀答嘀答’代表LUCK。假設(shè)存1需花費(fèi)C單位，而存0需花費(fèi)1單位，利用本節(jié)所敘的動(dòng)態(tài)規(guī)劃方法，這種不等代價(jià)的霍夫曼碼之建置，可于的時(shí)間內(nèi)完成。

161.5錯(cuò)誤更正能力定義1.1矛盾配對(duì)碼(AmbiguousCode-pair)：二個(gè)奇數(shù)等長(zhǎng)度對(duì)稱式霍夫曼碼之間，只有中間位置的位元不同，則該二個(gè)碼稱為矛盾配對(duì)碼。例如，(0010100,0011100)為矛盾配對(duì)碼。

假設(shè)一種對(duì)稱碼，其各個(gè)碼的長(zhǎng)度為L(zhǎng)位元，則共有個(gè)不同的對(duì)稱碼?？紤]一個(gè)完全二分樹T上的長(zhǎng)度L之對(duì)稱碼個(gè)數(shù)，已選定從第一層到第i層為SRVLCs的目標(biāo)碼后，，可被定義如下

(1)，當(dāng)。例如(2)，當(dāng)且最右邊位元為對(duì)稱(3)，當(dāng)為其它狀況17令m(L)代表T在第L層中合法的對(duì)稱碼數(shù)，則(1.3)上式中代表在第i層已選定的對(duì)稱碼個(gè)數(shù)，而代表在第i層被選的對(duì)稱碼其最右邊位元為對(duì)稱之碼數(shù)，這里。令長(zhǎng)度為i的霍夫曼碼之個(gè)數(shù)為n(i)。SRVLC的建構(gòu)如下所示：步驟1：令。步驟2：若，則不變動(dòng)，因?yàn)樵诘趇層仍有多的可用對(duì)稱碼。否則的話，在這一層只有個(gè)SRVLC碼被建立，不足的個(gè)留到下一階段來(lái)建立，因而有步驟3：重覆步驟2直到每一個(gè)原始的霍夫曼碼都找到一對(duì)應(yīng)的

SRVLC。從步驟2中，可知，當(dāng)時(shí)，共有種選擇以建構(gòu)SRVLCs。18式(1.4)中的p(L)代表在L層中的矛盾配對(duì)數(shù)。前面所敘的步驟2可修正如下：計(jì)算。若則不變；否則不足的留給下一層來(lái)建立，使得和。在個(gè)候選碼中選取個(gè)對(duì)稱碼出來(lái)時(shí)，是依后置對(duì)稱串(S