哈夫曼編碼（講義）

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

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

3、序列，這樣得到的編碼稱為哈夫曼編碼。–cd=new[n]分配求編碼的工作空間f(i=1i=ni)逐個字符求哈夫曼編碼start=n1編碼結束符位置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個字符編碼分配空間strcpy(HC[i]從cd復制編