基于哈夫曼樹的通信數(shù)據(jù)編碼的簡(jiǎn)單實(shí)現(xiàn)

《基于哈夫曼樹的通信數(shù)據(jù)編碼的簡(jiǎn)單實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、基于哈夫曼樹的通信數(shù)據(jù)編碼的簡(jiǎn)單實(shí)現(xiàn)摘要哈夫曼樹是相同個(gè)數(shù)的帶權(quán)結(jié)點(diǎn)所構(gòu)成的所有二叉樹中帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹，將其應(yīng)用于計(jì)算機(jī)通信中數(shù)據(jù)編碼技術(shù)可大大縮短電文代碼的長(zhǎng)度，且避免了電文代碼二義性的產(chǎn)生。本文簡(jiǎn)要介紹了哈夫曼樹的原理、構(gòu)造方法及其在數(shù)據(jù)編碼中的應(yīng)用。關(guān)鍵字：哈夫曼樹帶權(quán)路徑長(zhǎng)度數(shù)字通信數(shù)據(jù)編碼概述數(shù)據(jù)編碼技術(shù)在計(jì)算機(jī)數(shù)字通信中一直占據(jù)著重要的地位。這是因?yàn)?，在?shù)字通信過程中，往往存在以下幾個(gè)問題：信息傳遞的速度和所傳遞信息的可靠性這對(duì)不可調(diào)和的矛盾，所傳遞的數(shù)據(jù)編碼的長(zhǎng)度和數(shù)據(jù)譯碼容易產(chǎn)生的二義性等?；谝陨蠁栴}，使得數(shù)據(jù)編碼技術(shù)的優(yōu)劣在很

2、大程度上影響著通信的質(zhì)量。本文所要介紹的基于哈夫曼樹的通信數(shù)據(jù)編碼技術(shù)主要以數(shù)字通信中所傳遞的數(shù)據(jù)編碼的長(zhǎng)度和數(shù)據(jù)編碼容易產(chǎn)生的二義性這兩個(gè)問題為著眼點(diǎn)，結(jié)合數(shù)據(jù)結(jié)構(gòu)中哈夫曼樹的原理，通過解決上述兩個(gè)問題來提高數(shù)字通信的質(zhì)量。一、哈夫曼樹及其構(gòu)造方法哈夫曼樹又叫最優(yōu)二叉樹，由哈夫曼方法構(gòu)造而得，是數(shù)據(jù)結(jié)構(gòu)中樹形結(jié)構(gòu)的一種特例。當(dāng)一棵二叉樹由n個(gè)帶權(quán)結(jié)點(diǎn)構(gòu)成時(shí)，就存在所謂樹的帶權(quán)路徑長(zhǎng)度的計(jì)算問題，即樹中所有結(jié)點(diǎn)的帶權(quán)路徑之和。由于n個(gè)結(jié)點(diǎn)可以構(gòu)造大量的不同形狀的二叉樹，加之每個(gè)結(jié)點(diǎn)的權(quán)值可能互不相同，因此所有二叉樹的帶權(quán)路徑長(zhǎng)度也各不一樣。最優(yōu)二叉樹就是在這些二

3、叉樹中帶權(quán)路徑最小的二叉樹。我們知道，在處理不同的問題時(shí)，我們的目標(biāo)也互不相同，問題處理過程的設(shè)計(jì)方法也不盡相同。而這些獨(dú)特的設(shè)計(jì)方法可能意味著要符合一定的處理要求。比如上述帶權(quán)路徑長(zhǎng)度最小的二叉樹，以它們?yōu)榛A(chǔ)，設(shè)計(jì)的處理方法可能意味著某種代價(jià)（如時(shí)間、空間等資源）的最小化，于是哈夫曼樹在理論上便有了應(yīng)用價(jià)值。事實(shí)上，將哈夫曼樹應(yīng)用于數(shù)據(jù)編碼技術(shù)中，即把要傳遞的數(shù)據(jù)信息（尤其是字符數(shù)據(jù)）用哈夫曼方法加以編碼，可以使原本長(zhǎng)度很長(zhǎng)的電文代碼大大縮短，得到平均長(zhǎng)度最短的電文代碼，且設(shè)計(jì)出來的二進(jìn)制代碼可以確保譯碼的唯一性。哈夫曼樹的構(gòu)造方法并不復(fù)雜。它的構(gòu)造算法的思

4、想有些類似于貪心算法，由哈夫曼最早提出。首先給定n個(gè)帶權(quán)結(jié)點(diǎn)，設(shè)其權(quán)值為{,,……,}，這n個(gè)結(jié)點(diǎn)各自獨(dú)立構(gòu)成了n棵二叉樹，并且形成一個(gè)森林F={,,……,}，每一棵二叉樹都只有一個(gè)權(quán)值為的根結(jié)點(diǎn)，無左右子樹。根據(jù)哈夫曼方法，首先從森林F中選擇兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹，作為一棵新二叉樹的左右子樹，把它們的權(quán)值之和作為新二叉樹的根結(jié)點(diǎn)的權(quán)值。然后從森林F中刪除已經(jīng)被選中的兩棵二叉樹，同時(shí)把新構(gòu)成的二叉樹的根結(jié)點(diǎn)加入到森林F中。然后從新構(gòu)成的森林F中再選擇兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹以構(gòu)成新的二叉樹，以此類推，直到森林中只含有一棵二叉樹為止，此時(shí)這棵二叉樹即為所求的

5、最優(yōu)二叉樹，即哈夫曼樹。直觀地看這棵新構(gòu)成的哈夫曼樹，容易發(fā)現(xiàn)，權(quán)值越大的結(jié)點(diǎn)離根結(jié)點(diǎn)越近，而權(quán)值越小的結(jié)點(diǎn)則離根結(jié)點(diǎn)越遠(yuǎn)。這樣就可以保證這棵最優(yōu)二叉樹具有最小帶權(quán)路徑長(zhǎng)度。這里指出一點(diǎn)，若被選中的具有最小權(quán)值的兩棵二叉樹的根結(jié)點(diǎn)的權(quán)值之和，與刪除被選二叉樹后的森林中的一棵或多棵二叉樹的根結(jié)點(diǎn)的權(quán)值相等，則不將這棵新二叉樹插入原森林中，以保證構(gòu)成的最優(yōu)二叉樹的帶權(quán)路徑長(zhǎng)度最小。這是與哈夫曼編碼中的情況不一致的，因?yàn)樵诠蚵幋a時(shí)若采用這種方法將會(huì)導(dǎo)致二進(jìn)制代碼的前綴重碼。下面給出一般情況下的例子：有6棵僅有根結(jié)點(diǎn)而無左右子樹的二叉樹，其權(quán)值為{7，2，5，3，8

6、，4}，則根據(jù)哈夫曼算法可以得到此哈夫曼樹為（圖1）：容易計(jì)算，這棵哈夫曼樹的帶權(quán)路徑長(zhǎng)度WPL（）=2×4+3×4+4×3+8×2+5×2+7×2=72，是眾多二叉樹中帶權(quán)路徑長(zhǎng)度最小的一棵。當(dāng)然，通過觀察29179412758523也容易發(fā)現(xiàn)，最優(yōu)二叉樹也并不唯一。這是因?yàn)槁窂介L(zhǎng)度相等而權(quán)值不同的結(jié)點(diǎn)間可以互換位置圖1而不影響整棵樹的帶權(quán)路徑長(zhǎng)度。下面介紹兩種特例，將n個(gè)帶權(quán)結(jié)點(diǎn)按權(quán)值由小到大排列，得到結(jié)點(diǎn)權(quán)值的序列{,,……,}（≤≤……≤），若≥，則構(gòu)造而得的哈夫曼樹中每一個(gè)結(jié)點(diǎn)的右孩子均為終端結(jié)點(diǎn)。在這種情況下設(shè)計(jì)出來的每個(gè)字的二進(jìn)制編碼的長(zhǎng)度均互不相

7、同（代碼位數(shù)最長(zhǎng)的二個(gè)字相同）。另一種情況是，若由權(quán)值最小兩個(gè)結(jié)點(diǎn)構(gòu)成的新二叉樹的根結(jié)點(diǎn)的權(quán)值，大于等于原森林中任意兩個(gè)（或多個(gè)）二叉樹的權(quán)值（通俗地說，各結(jié)點(diǎn)權(quán)值相對(duì)較大且值互相接近），則構(gòu)造出來的哈夫曼樹是一棵完全二叉樹。從編碼的角度說，最終獲得的代碼長(zhǎng)度最多只有兩種，且長(zhǎng)度相差僅為1?，F(xiàn)給出哈夫曼樹的數(shù)據(jù)結(jié)構(gòu)描述：typedefstructHtnode{intweight;//結(jié)點(diǎn)的權(quán)值//指向雙親和左右孩子的指針intpar;intleft;intright;}Htnode,*HuffTree;現(xiàn)簡(jiǎn)要給出構(gòu)造哈夫曼樹算法：typedefchar**Huf

8、fcode;HuffTr