哈夫曼樹(shù)的在編碼中的應(yīng)用

　　在電文傳輸中，需要將電文中出現(xiàn)的每個(gè)字符進(jìn)行二進(jìn)制編碼。在設(shè)計(jì)編碼時(shí)需要遵守兩個(gè)原則：

　?。?）發(fā)送方傳輸?shù)亩M(jìn)制編碼，到接收方解碼后必須具有唯一性，即解碼結(jié)果與發(fā)送方發(fā)送的電文完全一樣；

　?。?）發(fā)送的二進(jìn)制編碼盡可能地短。下面我們介紹兩種編碼的方式。

　　1. 等長(zhǎng)編碼

　　這種編碼方式的特點(diǎn)是每個(gè)字符的編碼長(zhǎng)度相同（編碼長(zhǎng)度就是每個(gè)編碼所含的二進(jìn)制位數(shù)）。假設(shè)字符集只含有4個(gè)字符A，B，C，D，用二進(jìn)制兩位表示的編碼分別為00，01，10，11。若現(xiàn)在有一段電文為：ABACCDA，則應(yīng)發(fā)送二進(jìn)制序列：00010010101100，總長(zhǎng)度為14位。當(dāng)接收方接收到這段電文后，將按兩位一段進(jìn)行譯碼。這種編碼的特點(diǎn)是譯碼簡(jiǎn)單且具有唯一性，但編碼長(zhǎng)度并不是最短的。

　　2. 不等長(zhǎng)編碼

　　在傳送電文時(shí)，為了使其二進(jìn)制位數(shù)盡可能地少，可以將每個(gè)字符的編碼設(shè)計(jì)為不等長(zhǎng)的，使用頻度較高的字符分配一個(gè)相對(duì)比較短的編碼，使用頻度較低的字符分配一個(gè)比較長(zhǎng)的編碼。例如，可以為A，B，C，D四個(gè)字符分別分配0，00，1，01，并可將上述電文用二進(jìn)制序列：000011010發(fā)送，其長(zhǎng)度只有9個(gè)二進(jìn)制位，但隨之帶來(lái)了一個(gè)問(wèn)題，接收方接到這段電文后無(wú)法進(jìn)行譯碼，因?yàn)闊o(wú)法斷定前面4個(gè)0是4個(gè)A，1個(gè)B、2個(gè)A，還是2個(gè)B，即譯碼不唯一，因此這種編碼方法不可使用。

　　因此，為了設(shè)計(jì)長(zhǎng)短不等的編碼，以便減少電文的總長(zhǎng)，還必須考慮編碼的唯一性，即在建立不等長(zhǎng)編碼時(shí)必須使任何一個(gè)字符的編碼都不是另一個(gè)字符的前綴，這宗編碼稱(chēng)為前綴編碼（prefix code）

　?。?）利用字符集中每個(gè)字符的使用頻率作為權(quán)值構(gòu)造一個(gè)哈夫曼樹(shù)；

　?。?）從根結(jié)點(diǎn)開(kāi)始，為到每個(gè)葉子結(jié)點(diǎn)路徑上的左分支賦予0，右分支賦予1，并從根到葉子方向形成該葉子結(jié)點(diǎn)的編碼

　　例題：

　　假設(shè)一個(gè)文本文件TFile中只包含7個(gè)字符{A，B，C，D，E，F(xiàn)，G}，這7個(gè)字符在文本中出現(xiàn)的次數(shù)為{5，24，7，17，34，5，13}

　　利用哈夫曼樹(shù)可以為文件TFile構(gòu)造出符合前綴編碼要求的不等長(zhǎng)編碼

　　具體做法：

　　1. 將TFile中7個(gè)字符都作為葉子結(jié)點(diǎn)，每個(gè)字符出現(xiàn)次數(shù)作為該葉子結(jié)點(diǎn)的權(quán)值

　　2. 規(guī)定哈夫曼樹(shù)中所有左分支表示字符0，所有右分支表示字符1，將依次從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)所經(jīng)過(guò)的分支的二進(jìn)制位的序列作為該

　　結(jié)點(diǎn)對(duì)應(yīng)的字符編碼

　　3. 由于從根結(jié)點(diǎn)到任何一個(gè)葉子結(jié)點(diǎn)都不可能經(jīng)過(guò)其他葉子，這種編碼一定是前綴編碼，哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度正好是文件TFile編碼的總長(zhǎng)度

　　通過(guò)哈夫曼樹(shù)來(lái)構(gòu)造的編碼稱(chēng)為哈弗曼編碼（huffman code）