哈夫曼編碼

編碼方案

． 編碼和解碼
　　數據壓縮過程稱為編碼即將文件中的每個字符均轉換為一個惟一的二進制位串
　　數據解壓過程稱為解碼即將二進制位串轉換為對應的字符

． 等長編碼方案和變長編碼方案
　　給定的字符集C可能存在多種編碼方案
　（） 等長編碼方案
　　等長編碼方案將給定字符集C中每個字符的碼長定為[lg|C|]|C|表示字符集的大小
　【例】設待壓縮的數據文件共有個字符這些字符均取自字符集C={abcdef}等長編碼需要三位二進制數字來表示六個字符因此整個文件的編碼長度為位

　（）變長編碼方案
　　變長編碼方案將頻度高的字符編碼設置短將頻度低的字符編碼設置較長
　【例】設待壓縮的數據文件共有個字符這些字符均取自字符集C={abcdef}其中每個字符在文件中出現的次數(簡稱頻度)見表
     表              字符編碼問題
    
     字符                      a     b     c     d      e      f
     頻度（單位千次）                              
     定長編碼                                  
     變長編碼                                   
    
    　根據計算公式
      (*+*+*+*+*+)*=
　　整個文件被編碼為位比定長編碼方式節約了約％的存儲空間
　注意
　　變長編碼可能使解碼產生二義性產生該問題的原因是某些字符的編碼可能與其他字符的編碼開始部分(稱為前綴)相同
　【例】設ETW分別編碼為則解碼時無法確定信息串是ET還是W

． 前綴碼方案                                     
　　對字符集進行編碼時要求字符集中任一字符的編碼都不是其它字符的編碼的前綴這種編碼稱為前綴(編)碼
　注意
　　等長編碼是前綴碼

．最優前綴碼
　　平均碼長或文件總長最小的前綴編碼稱為最優的前綴碼最優的前綴碼對文件的壓縮效果亦最佳

 
其中
　　pi為第i個字符得概率
　　li為碼長
　【例】若將表所示的文件作為統計的樣本則a至f六個字符的概率分別為對變長編碼求得的平均碼長為優於定長編碼(平均碼長為)

根據最優二叉樹構造哈夫曼編碼

　　利用哈夫曼樹很容易求出給定字符集及其概率(或頻度)分布的最優前綴碼哈夫曼編碼正是一種應用廣泛且非常有效的數據壓縮技術該技術一般可將數據文件壓縮掉％至％其壓縮效率取決於被壓縮文件的特征

． 具體做法
　（）用字符ci作為葉子pi或fi做為葉子ci的權構造一棵哈夫曼樹並將樹中左分支和右分支分別標記為和
　（）將從根到葉子的路徑上的標號依次相連作為該葉子所表示字符的編碼該編碼即為最優前綴碼（也稱哈夫曼編碼）

． 哈夫曼編碼為最優前綴碼
　　由哈夫曼樹求得編碼為最優前綴碼的原因
　　① 每個葉子字符ci的碼長恰為從根到該葉子的路徑長度li平均碼長(或文件總長)又是二叉樹的帶權路徑長度WPL而哈夫曼樹是WPL最小的二叉樹因此編碼的平均碼長(或文件總長)亦最小
　　② 樹中沒有一片葉子是另一葉子的祖先每片葉子對應的編碼就不可能是其它葉子編碼的前綴即上述編碼是二進制的前綴碼

． 求哈夫曼編碼的算法
　（）思想方法
　　給定字符集的哈夫曼樹生成後求哈夫曼編碼的具體實現過程是依次以葉子T[i](≤i≤n)為出發點向上回溯至根為止上溯時走左分支則生成代碼走右分支則生成代碼
　注意
　　① 由於生成的編碼與要求的編碼反序將生成的代碼先從後往前依次存放在一個臨時向量中並設一個指針start指示編碼在該向量中的起始位置（start初始時指示向量的結束位置）
　　② 當某字符編碼完成時從臨時向量的start處將編碼復制到該字符相應的位串bits中即可
　　③ 因為字符集大小為n故變長編碼的長度不會超過n加上一個結束符\bits的大小應為n+

　（）字符集編碼的存儲結構及其算法描述
  typedef struct {
      char ch //存儲字符
      char bits[n+] //存放編碼位串
    }CodeNode
  typedef CodeNode HuffmanCode[n]
  void CharSetHuffmanEncoding(HuffmanTree THuffmanCode H)
     {//根據哈夫曼樹T求哈夫曼編碼表H
      int cpi;//c和p分別指示T中孩子和雙親的位置
      char cd[n+] //臨時存放編碼
      int start //指示編碼在cd中的起始位置
      cd[n]=\ //編碼結束符
      for(i=i<ni++){ //依次求葉子T[i]的編碼
         H[i]ch=getchar()//讀入葉子T[i]對應的字符
         start=n //編碼起始位置的初值
         c=i //從葉子T[i]開始上溯
         while((p=T[c]parent)>=){//直至上溯到T[c]是樹根為止
               //若T[c]是T[p]的左孩子則生成代碼否則生成代碼
            cd[start]=(T[p)child==C)?
            c=p //繼續上溯
           }
         strcpy(H[i]bits&cd[start]) //復制編碼位串
       }//endfor
      }//CharSetHuffmanEncoding
　　文件的編碼和解碼
　　有了字符集的哈夫曼編碼表之後對數據文件的編碼過程是依次讀人文件中的字符c在哈夫曼編碼表H中找到此字符若H[i]ch=c則將字符c轉換為H[i]bits中存放的編碼串
　　對壓縮後的數據文件進行解碼則必須借助於哈夫曼樹T其過程是依次讀人文件的二進制碼從哈夫曼樹的根結點(即T[m])出發若當前讀人則走向左孩子否則走向右孩子一旦到達某一葉子T[i]時便譯出相應的字符H[i]ch然後重新從根出發繼續譯碼直至文件結束
　　文件的編碼和解碼算法【參見練習】

 

From:http://tw.wingwit.com/Article/program/sjjg/201311/22941.html