哈夫曼樹及哈弗曼編碼

哈姆曼樹的建構：

赫夫曼樹的外結點和内結點的差別：外節點是攜帶了關鍵資料的結點， 而内部結點沒有攜帶這種資料， 隻作為導向最終的外結點所走的路徑而使用，是以，我們主要關心的是赫夫曼樹的外結點上， 而不是内結點。

我們為擴充二叉樹的外結點（葉子結點）定義兩條屬性： 權值（w）和路徑長度(l)。同時規定帶權路徑長度（WPL）為擴充二叉樹的外結點的權值和路徑長度乘積之和：

路徑長度：

路徑長度指的是路徑上分支的數目。

節點的權：

節點的權指的是為樹中的每一個節點賦予的一個非負的值，如上圖中每一個節點中的值。

節點的帶權路徑長度：

節點的帶權路徑長度指的是從根節點到該節點之間的路徑長度與該節點權的乘積。

樹的帶權路徑長度：

樹的帶權路徑長度指的是所有葉子節點的帶權路徑長度之和。

由n個權值構造一顆有n個葉子結點的二叉樹， 則其中帶權路徑長度WPL最小的二叉樹， 就是赫夫曼樹，或者叫做最優二叉樹。

建構過程分四步：

• 根據給定的n個權值{w1, w2, w3 … wn }構成n棵二叉樹的集合， 每棵二叉樹都隻包含一個結點
• 在上面的二叉樹中選出兩顆根結點權值最小的樹， 同時另外取一個新的結點作為這兩顆樹的根結點， 設新節點的權值為兩顆權值最小的樹的權值和， 将得到的這顆樹也加入到樹的集合中
• 在2操作後， 從集合中删除權值最小的那兩顆樹
• 重複2和3，直到集合中的樹隻剩下一棵為止， 剩下的這顆樹就是我們要求得的赫夫曼樹。

對于同一組權值的葉結點， 構成的赫夫曼樹可以有多種形态， 但是最小WPL值是唯一的。

哈弗曼編碼：

哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，該方法完全依據字元出現機率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼（有時也稱為霍夫曼編碼）

哈夫曼樹─即最優二叉樹，帶權路徑長度最小的二叉樹，經常應用于資料壓縮。 在計算機資訊進行中，“哈夫曼編碼”是一種一緻性編碼法（又稱“熵編碼法”），用于資料的無損耗壓縮。這一術語是指使用一張特殊的編碼表将源字元（例如某檔案中的一個符号）進行編碼。這張編碼表的特殊之處在于，它是根據每一個源字元出現的估算機率而建立起來的（出現機率高的字元使用較短的編碼，反之出現機率低的則使用較長的編碼，這便使編碼之後的字元串的平均期望長度降低，進而達到無損壓縮資料的目的）。這種方法是由David.A.Huffman發展起來的。 例如，在英文中，e的出現機率很高，而z的出現機率則最低。當利用哈夫曼編碼對一篇英文進行壓縮時，e極有可能用一個位(bit)來表示，而z則可能花去25個位（不是26）。用普通的表示方法時，每個英文字母均占用一個位元組（byte），即8個位。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。若能實作對于英文中各個字母出現機率的較準确的估算，就可以大幅度提高無損壓縮的比例。

根據Huffman樹的結構，我們可以利用Huffman樹對每一個字元編碼，Huffman編碼是一種字首編碼，即一個字元的編碼不是另一個字元編碼的字首。規定如下：

• 将權值小的最為左節點，權值大的作為右節點
• 左孩子編碼為0，右孩子編碼為1

代碼如下：

#include<stdio.h>
#include<string.h>
#define MAX 100000


//-----哈夫曼樹的存儲表示-----
typedef struct
{
	int weight;//結點的權值 
	int parent,lchild,rchild;//結點的雙親，左孩子，右孩子 
}HTNode,*HuffmanTree;//動态配置設定數組存儲哈夫曼樹 

void Select(HuffmanTree &HT,int m,int &s1,int &s2)
{
        int m1,m2;
		m1=m2=MAX;//m1、m2中存放兩個無父結點且結點權值最小的兩個結點 
        s1=s2=1;
        //找出兩個其雙親域為0且權值最小的兩個結點，傳回他們在HT中的序号s1和s2 
        for (int j=1; j<=m; j++)
        {
            if (HT[j].weight < m1 && HT[j].parent==0)//如果說這個值比m1要小，則将其指派給m1 
            {
                m2=m1; //找到比m1小的數，将m1的值（對應權值）給m2 
                s2=s1; // 對應序号指派給m2 
                m1=HT[j].weight;
                s1=j; 
            }
            /*這裡講究的是m1和m2誰先比較的順序 ，這裡比較完了 m1之後，m1已經找到比他小的值之後才會把自己原來
			的值賦給m2，然後繼續比較,不小于m1了，再看是否比m2要小，即次小數*/ 
            else if (HT[j].weight < m2 && HT[j].parent==0)//如果不比m1小，看他是否比m2小，找出次小數 
            {
                m2=HT[j].weight;
                s2=j;
            }
        } 
}

//--------建構哈夫曼樹--------- 
void CreatHuffmanTree(HuffmanTree &HT,int n)
{
	//構造哈夫曼樹
	int m,i,s1,s2;
	if(n<=1) return;
	m=2*n-1;
	HT=new HTNode[m+1];//0單元未用，是以需要動态配置設定m+1個單元，HT[m]表示根節點 
	for(i=1;i<=m;i++)//将1-m号單元中的雙親，左孩子，右孩子的下标都初始化為0 
	{
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	 } 
	for(i=1;i<=n;i++)//輸入前n個單元中葉子結點的值 
	{
		printf("請輸入第%d個葉子結點的權值：\n",i);
		scanf("%d",&HT[i].weight);
	 } 	
//--------初始化工作結束，下面開始建立哈夫曼樹----------
    for(i=n+1;i<=m;i++)
	{
        //通過n-1次選擇，删除，合并來建立哈夫曼樹 
        //在HT[K](1<=K<=I-1)中選擇兩個其雙親域為0且權值最小的節點 ，并傳回他們在HT中的序号s1和s2
		Select(HT,i-1,s1,s2);
        //得到新節點i,從森林中删除s1,s2,将s1,s2的雙親由0改成i
	    HT[s1].parent=i;
		HT[s2].parent=i;
       // s1,s2分别作為i的左右孩子
		HT[i].lchild=s1;
		HT[i].rchild =s2;
		//i的權值為左右孩子的權值之和  
		HT[i].weight=HT[s1].weight+HT[s2].weight;			
	 } 
	 printf("\n------------------------------------------------------------------------\n"); 
	 printf("結點\t\t權值\t\tparent\t\tlchild\t\trchild");
	 printf("\n");
	 for(i=1;i<=m;i++)
	 {
	 	printf("%d\t\t%d\t\t%d\t\t%d\t\t%d",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);	
        printf("\n");
	 }
        
} 
 
 //------哈夫曼編碼表的存儲表示-----
typedef char **HuffmanCode;//動态配置設定數組存儲哈夫曼編碼表
HuffmanCode HC;
 
 
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
 {
 	//從葉子到根逆向求每個字元的哈夫曼編碼，存儲在編碼表HC中
 	 int i;
 	 char *cd;
	 HC=new char *[n+1];//配置設定存儲n個字元編碼的編碼表空間 
	 cd=new char[n];//配置設定臨時存儲每個字元編碼的編碼表空間 
	 cd[n-1]='\0';//編碼結束符
	
	 for(i=1;i<=n;++i)//逐個字元求解n個字元編碼 
	 {
	 	int start=n-1;//start開始時指向最後,即編碼結束符位置 
	 	int c=i;int f=HT[i].parent;//f指向結點c的雙親結點 
	 	while(f!=0)//從葉子結點開始向上回溯直至根結點 
	 	{
	 		--start;//回溯一次start向前指一個位置 
	 		if(HT[f].lchild==c) cd[start]='0';//結點c是f的左孩子，則生成代碼0 
	 		else cd[start]='1';//結點c是f的右孩子，則生成代碼1
	 		c=f;f=HT[c].parent;	//繼續向上回溯 		
		 }//求出第i個字元的編碼 
		 HC[i]=new char[n-start];//為第i個字元編碼配置設定空間  
		 strcpy(HC[i],&cd[start]);//将求得的編碼從臨時空間cd複制到HC的目前行中 
	  }
	 delete cd;//釋放臨時空間
	 printf("\n\n");
	 printf("結點\t\t權值\t\t編碼");
	 printf("\n");
     for(i=1;i<=n;i++)
     {
     	printf("%d\t\t%d\t\t%s",i,HT[i].weight,HC[i]); 
     	printf("\n"); 
	 }

 }
 
  
main()
{
	  int n;
	  HuffmanTree HT;
      printf("請輸入初始葉子結點的數目：\n");
	  scanf("%d",&n);
      CreatHuffmanTree(HT,n);
      CreatHuffmanCode(HT,HC,n);
}