哈夫曼編碼（講義）

1、哈夫曼編碼(講義)1哈夫曼編碼的主要思想信息編碼的主要目的是：源文件=》目標(biāo)文件編碼目標(biāo)：目標(biāo)文件長(zhǎng)度盡可能短。兩類二進(jìn)制編碼：（1）等長(zhǎng)編碼：各個(gè)字符的編碼長(zhǎng)度相等。優(yōu)點(diǎn)：解碼簡(jiǎn)單。缺點(diǎn)：編碼長(zhǎng)度可能不最短。（2）不等長(zhǎng)編碼：各個(gè)字符的編碼長(zhǎng)度不等。優(yōu)點(diǎn)：編碼長(zhǎng)度盡可能地短。缺點(diǎn)：解碼困難、解碼結(jié)果可能不唯一。例如：傳送電文“ABACCDA”–等長(zhǎng)編碼?A：00B：01C：10D：11?編碼結(jié)果00010010101100，長(zhǎng)度為14

2、位。?解碼方以兩位為一字段解碼。–不等長(zhǎng)編碼?原則：出現(xiàn)次數(shù)較多的字符編碼短，次數(shù)較少的字符編碼長(zhǎng)。?A：0B：00C：1D：01?編碼結(jié)果000011010，長(zhǎng)度為9位。?解碼方無(wú)法解碼，因?yàn)榻獯a的結(jié)果不唯一。哈夫曼編碼（同時(shí)滿足代碼長(zhǎng)度短，且解碼唯一）–目標(biāo)：使電文總長(zhǎng)最短。–以字符出現(xiàn)的次數(shù)為權(quán)，構(gòu)造一棵哈夫曼樹(shù)；將樹(shù)中結(jié)點(diǎn)引向其左孩子的分支標(biāo)“0”，引向其右孩子的分支標(biāo)“1”；每個(gè)字符的編碼即為從根到每個(gè)葉子的路徑上得到的0、1

3、序列，這樣得到的編碼稱為哈夫曼編碼。–cd=new[n]分配求編碼的工作空間f(i=1i=ni)逐個(gè)字符求哈夫曼編碼start=n1編碼結(jié)束符位置f(c=if=HT[i].parentf!=0c=ff=HT[f].parent)從葉子到根逆向求編碼if(HT[f].lchild==c)cd[start]=“0”elsecd[start]=“1”HC[i]=new[nstart]為第i個(gè)字符編碼分配空間strcpy(HC[i]從cd復(fù)制編