標籤: 暫無標籤

哈夫曼樹又稱最優二叉樹,是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度,就是樹中所有的葉結點的權值乘上其到根結點的路徑長度(若根結點為0層,葉結點到根結點的路徑長度為葉結點的層數)。樹的帶權路徑長度記為WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹,相應的葉結點的路徑長度為Li(i=1,2,...n)。可以證明哈夫曼樹的WPL是最小的。

在一般的數據結構的書中,樹的那章後面,著者一般都會介紹一下哈夫曼(HUFFMAN)樹和哈夫曼編碼。哈夫曼編碼是哈夫曼樹的一個應用。哈夫曼編碼應用廣泛,如JPEG中就應用了哈夫曼編碼。

1 哈夫曼 -簡介

哈夫曼在上世紀五十年代初就提出這種編碼時,根據字元出現的概率來構造平均長度最短的編碼。它是一種變長的編碼。在編碼中,若各碼字長度嚴格按照碼字所對應符號出現概率的大小的逆序排列,則編碼的平均長度是最小的。(註:碼字即為符號經哈夫曼編碼后得到的編碼,其長度是因符號出現的概率而不同,所以說哈夫曼編碼是變長的編碼。)

2 哈夫曼 -演算法

構造一棵哈夫曼樹呢,最具有一般規律的構造方法就是哈夫曼演算法。一般的數據結構的書中都可以找到其描述:
  一、對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,...,Tn},其中每棵二叉樹Ti中只有一個權值為Wi的根結點,它的左右子樹均為空。(為方便在計算機上實現演算法,一般還要求以Ti的權值Wi的升序排列。)
  二、在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹,新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。
  三、從F中刪除這兩棵樹,並把這棵新的二叉樹同樣以升序排列加入到集合F中。
  四、重複二和三兩步,直到集合F中只有一棵二叉樹為止。
  用C語言實現上述演算法,可用靜態的二叉樹或動態的二叉樹。若用動態的二叉樹可用以下數據結構:structtree{
  floatweight;"
  union{
  charleaf;"
  structtree*left;"
  };
  structtree*right;"
  };
  structforest{"
  structtree*ti;"
  structforest*next;"
  };
  例:若字母A,B,Z,C出現的概率為:0.75,0.54,0.28,0.43;則相應的權值為:75,54,28,43。

構造好哈夫曼樹后,就可根據哈夫曼樹進行編碼。例如:上面的字元根據其出現的概率作為權值構造一棵哈夫曼樹后,經哈夫曼編碼得到的對應的碼值。只要使用同一棵哈夫曼樹,就可把編碼還原成原來那組字元。顯然哈夫曼編碼是前綴編碼,即任一個字元的編碼都不是另一個字元的編碼的前綴,否則,編碼就不能進行翻譯。例如:a,b,c,d的編碼為:0,10,101,11,對於編碼串:1010就可翻譯為bb或ca,因為b的編碼是c的編碼的前綴。剛才進行哈夫曼編碼的規則是從根結點到葉結點(包含原信息)的路徑,向左孩子前進編碼為0,向右孩子前進編碼為1,當然你也可以反過來規定。

3 哈夫曼 -特點

這種編碼方法是靜態的哈夫曼編碼,它對需要編碼的數據進行兩遍掃描:第一遍統計原數據中各字元出現的頻率,利用得到的頻率值創建哈夫曼樹,並必須把樹的信息保存起來,即把字元0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來,(用4Bytes的長度存儲頻率值,頻率值的表示範圍為0--2^32-1,這已足夠表示大文件中字元出現的頻率了)以便解壓時創建同樣的哈夫曼樹進行解壓;第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼,並把編碼后得到的碼字存儲起來。靜態哈夫曼編碼方法有一些缺點:一、對於過短的文件進行編碼的意義不大,因為光以4BYTES的長度存儲哈夫曼樹的信息就需1024Bytes的存儲空間;二、進行哈夫曼編碼,存儲編碼信息時,若用與通訊網路,就會引起較大的延時;三、對較大的文件進行編碼時,頻繁的磁碟讀寫訪問會降低數據編碼的速度。

因此,後來有人提出了一種動態的哈夫曼編碼方法。動態哈夫曼編碼使用一棵動態變化的哈夫曼樹,對第t+1個字元的編碼是根據原始數據中前t個字元得到的哈夫曼樹來進行的,編碼和解碼使用相同的初始哈夫曼樹,每處理完一個字元,編碼和解碼使用相同的方法修改哈夫曼樹,所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字元所需的時間與該字元的編碼長度成正比,所以動態哈夫曼編碼可實時進行。動態哈夫曼編碼比靜態哈夫曼編碼複雜的多,有興趣的讀者可參考有關數據結構與演算法的書籍。

前面提到的JPEG中用到了哈夫曼編碼,並不是說JPEG就只用哈夫曼編碼就可以了,而是一幅圖片經過多個步驟后得到它的一列數值,對這些數值進行哈夫曼編碼,以便存儲或傳輸。哈夫曼編碼方法比較易懂,大家可以根據它的編碼方法,自己編寫哈夫曼編碼和解碼的程序。

4 哈夫曼 -相關詞條

編碼      磁碟      程序       頻率

5 哈夫曼 -參考資料

http://www.educity.cn/zk/sjjg/200608301518181690.htm

相關評論

同義詞:暫無同義詞