摘 要：衡量一個(gè)算法的優(yōu)劣有許多因素，效率就是其中之一。而效率指的就是算法的執(zhí)行時(shí)間。提高效率是軟件開(kāi)發(fā)必須注重的問(wèn)題。對(duì)同一個(gè)問(wèn)題往往有多個(gè)算法可以解決，在同等條件下，執(zhí)行時(shí)間短的算法其效率是最高的。從霍夫曼樹(shù)的定義以及霍夫曼算法出發(fā)，介紹如何構(gòu)造霍夫曼樹(shù)以及利用霍夫曼算法優(yōu)化程序設(shè)計(jì)的原理，重點(diǎn)討論在判定類問(wèn)題中利用霍夫曼樹(shù)可以建立最佳判定算法，提高程序的執(zhí)行速度。

關(guān)鍵詞：霍夫曼樹(shù)；霍夫曼算法；最佳判定算法；執(zhí)行時(shí)間

中圖分類號(hào)：TP183 文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1004-373X(2008)10-112-02

Generation and Application of Optimal Binary Tree

ZHANG Guangxue

(Shaanxi Spinning and Weaving Clothing Occupation Technology，Xianyang，712000，China)

Abstract：Efficiency is one of factors to judge an algorithm，it refers to execution time of algorithm to improve the efficiency is important problem in software development.In the same condition，it has high efficient in a short execution time.According to Huffman algorithm and Huffman tree，how to build Huffman tree and using Huffman algorithm to optimize the program design are introduced，Huffman tree is applied to build best decision algorithm is discussed too.

Keywords：Huffman tree;Huffman algorithm;best decision algorithm;execution time

1 引 言

衡量一個(gè)算法的優(yōu)劣有許多因素，效率就是其中之一。而效率指的就是算法的執(zhí)行時(shí)間。提高效率是軟件開(kāi)發(fā)必須注重的問(wèn)題。對(duì)同一個(gè)問(wèn)題往往有多個(gè)算法可以解決，在同等條件下，執(zhí)行時(shí)間短的算法其效率是最高的。最優(yōu)二叉樹(shù)最早是由霍夫曼于1952年提出的，所以被稱為霍夫曼樹(shù)，相應(yīng)的算法稱為霍夫曼算法。

霍夫曼樹(shù)又稱最優(yōu)二叉樹(shù)，是指帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)。在軟件開(kāi)發(fā)中，都要解決大量的判定類問(wèn)題，解決這類問(wèn)題的習(xí)慣做法常是自上而下(或自下而上)或由高到低(或由低到高)的逐個(gè)判斷。而大量的判定問(wèn)題中普遍存在著滿足中間條件的多，滿足兩頭條件的少的現(xiàn)象(近似于正態(tài)分布)。利用霍夫曼樹(shù)可以建立最佳判定算法，大大提高程序的執(zhí)行速度。

2 霍夫曼樹(shù)定義及霍夫曼算法

2.1 霍夫曼樹(shù)定義

一般地，假設(shè)有n個(gè)權(quán)值{w1，w2，…，wn}，如何構(gòu)造有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，每個(gè)葉子結(jié)點(diǎn)帶有權(quán)值wi且?guī)?quán)路徑長(zhǎng)度WPL最小，這是一個(gè)很有實(shí)際意義的問(wèn)題，霍夫曼早在1952年就提出一個(gè)帶有一般規(guī)律的算法，很好地解決這個(gè)問(wèn)題，因此人們把這種具有最小路徑長(zhǎng)度的二叉樹(shù)稱為霍夫曼樹(shù)或最優(yōu)二叉樹(shù)，相應(yīng)的算法稱為霍夫曼算法。其中：WPL=∑ni=1wili，wi為第i個(gè)葉子結(jié)點(diǎn)的權(quán)值，li為從根結(jié)點(diǎn)到第i個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度，n為二叉樹(shù)的葉子個(gè)數(shù)。

2.2 霍夫曼算法

(1) 根據(jù)給定的n個(gè)權(quán)值{w1，w2，…，wn}構(gòu)造n棵二叉樹(shù)的集合F={T1，T2，…，Tn}，其中每棵二叉樹(shù)Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左、右子樹(shù)均空；

(2) 在F中選取2棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和；

(3) 在F中刪除這2棵二叉樹(shù)，同時(shí)將新得到的二叉樹(shù)加入F中；

(4) 重復(fù)(2)和(3)，直到F只含一棵二叉樹(shù)為止。這棵二叉樹(shù)便是霍夫曼樹(shù)。

[HTH]例1 給定一組權(quán)值{2，4，7，8，10，12}構(gòu)造霍夫曼樹(shù)。

按霍夫曼算法構(gòu)造的最優(yōu)二叉樹(shù)如下：

其中根結(jié)點(diǎn)上標(biāo)注的數(shù)字代表相應(yīng)結(jié)點(diǎn)的權(quán)值。

3 霍夫曼樹(shù)的應(yīng)用

霍夫曼樹(shù)的應(yīng)用很廣，在不同的應(yīng)用中葉子結(jié)點(diǎn)的權(quán)值可以有不同的解釋。當(dāng)霍夫曼樹(shù)應(yīng)用到信息編碼中，權(quán)值可看成是某個(gè)符號(hào)出現(xiàn)的頻率；當(dāng)應(yīng)用到判定類問(wèn)題中，可以看成是某類數(shù)據(jù)出現(xiàn)的頻率等。下面介紹霍夫曼樹(shù)在判定類問(wèn)題中的應(yīng)用。

圖1 霍夫曼算法構(gòu)造的的最優(yōu)二叉樹(shù)

利用霍夫曼樹(shù)可以構(gòu)成最佳判定過(guò)程。判定過(guò)程可以看成二叉樹(shù)，以開(kāi)始判斷作為根結(jié)點(diǎn)，判斷的結(jié)果分成二叉，再對(duì)其中的分支作進(jìn)一步的判斷。如果將權(quán)值大的比較放的深度較深，那么整棵比較樹(shù)的權(quán)值就會(huì)加大，因此只有將權(quán)值大的比較放在深度較淺處，將權(quán)值小的比較放在深度較深處，那么整棵比較樹(shù)的權(quán)值就變小，總的判定次數(shù)就比較少。這種優(yōu)化的思想就是盡量降低整棵樹(shù)的權(quán)值，這就是最優(yōu)二叉樹(shù)的原理。

[HTH]例2 編制1個(gè)將百分制轉(zhuǎn)換成5級(jí)分制的程序

此程序(偽程序)只要利用條件語(yǔ)句便可完成。



這是一種自下而上的逐個(gè)判斷，算法效率比較低。由于在實(shí)際中，學(xué)生成績(jī)?cè)?個(gè)等級(jí)上的分布是不均勻的(優(yōu)秀和不及格的學(xué)生遠(yuǎn)遠(yuǎn)少于中等學(xué)生，近似的呈正態(tài)分布)，同時(shí)此程序要反復(fù)執(zhí)行，因此應(yīng)考慮上述程序的質(zhì)量問(wèn)題，即其執(zhí)行所需時(shí)間，可以利用霍夫曼樹(shù)優(yōu)化算法。

假設(shè)成績(jī)分布規(guī)律如表1所示：

表1 成績(jī)分布規(guī)律

圖2 霍夫曼樹(shù)

圖3 判定期過(guò)程

由于每個(gè)判定框都有兩次比較，將兩次比較分開(kāi)就得到下面的判定樹(shù)（見(jiàn)圖4）：

根據(jù)這個(gè)霍夫曼樹(shù)就可以得到優(yōu)化的偽程序。

例3 在學(xué)校職工獎(jiǎng)金計(jì)算系統(tǒng)中，依據(jù)獎(jiǎng)金的發(fā)放辦法，行政人員的獎(jiǎng)金按級(jí)別分為:校級(jí)、處級(jí)、科級(jí)、副科級(jí)、一級(jí)科員、二級(jí)科員。在計(jì)算每個(gè)行政人員的獎(jiǎng)金時(shí)需要進(jìn)行大量的判斷。選擇合適的判斷方法可以大大的提高程序的執(zhí)行速度。按習(xí)慣方法確定行政人員職務(wù)的算法如下(偽程序)：



IF 校級(jí)

THEN a1

這是一種自上而下的逐個(gè)判斷，算法效率比較低，這里可以利用霍夫曼樹(shù)來(lái)優(yōu)化算法，假設(shè)學(xué)校行政人員的分布情況如表2所示：



表2 學(xué)校行政人員的分布情況

行政人員校級(jí)處級(jí)科級(jí)副科級(jí)一級(jí)科員二級(jí)科員

該問(wèn)題對(duì)應(yīng)一組權(quán)值為{5，6，8，13，34，43}的霍夫曼樹(shù)見(jiàn)圖5：

圖4 判定樹(shù)

圖5 霍夫曼樹(shù)

優(yōu)化后的偽程序如下：

算法的效率體現(xiàn)著程序的應(yīng)用價(jià)值，科學(xué)地選用高效率的算法是程序開(kāi)發(fā)必須注重的一個(gè)重要問(wèn)題，利用霍夫曼樹(shù)建立最佳判定算法，可以提高程序的執(zhí)行效率。

參 考 文 獻(xiàn)

［1］李盤(pán)林，李麗雙，李洋，等.離散數(shù)學(xué)［M］.北京:高等教育出版社，1999.

［2］張忠志.離散數(shù)學(xué)［M］.北京:高等教育出版社，2002.

［3］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)［M］.北京:清華大學(xué)出版社，1992.

作者簡(jiǎn)介

張廣學(xué) 男，1965年出生，陜西紡織服裝職業(yè)技術(shù)學(xué)院講師。主要從事離散數(shù)學(xué)的教學(xué)與研究。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。