本文是對Haffman算法進行的一次實踐。根據ascii碼文件中各ascii字符出現的頻率情況創建Haffman樹，再將各字符對應的哈夫曼編碼寫入文件中。同時，亦可根據對應的哈夫曼樹，將哈夫曼編碼文件解壓成字符文件.
關鍵詞: Haffman算法,壓縮，解壓縮
Abstract:
This article is a practice of haffman algorithm. First, I create the haffman tree based on the appearance frequency of each ascii character in the files ,then I output each ascii character’s corresponding haffman code to the zipped file. And I also make the program could unzip the haffman zipped files into the ascii files.
Key Words: Haffman Algorithm,Zip,UnZip
前言:
Haffman算法是個簡單而高效的貪心算法，主要用來創建最優二叉樹.可以在通訊時，對於出現頻率較高的字符，用較少的比特數便可以進行通訊.從而節省通訊線路的資源消耗。
該算法在各類數據結構, 算法,組合數學，離散數學，圖論等主題的書籍中都有所涉及。故本文不再贅述，本文致力於用Haffman算法實現壓縮與解壓縮,采用的語言為C語言，編譯環境VC++6.0.
下面給出1中實現的Haffman樹的結構及創建算法，有兩點說明:
這裡的Haffman樹采用的是基於數組的帶左右兒子結點及父結點下標作為存儲結點的二叉樹形式，這種空間上的消耗帶來了算法實現上的便捷。
由於對於最後生成的Haffman樹，其所有葉子結點均為從一個內部樹擴充出去的，所以，當外部葉子結點數為m個時，內部結點數為m-1.整個Haffman樹的需要的結點數為2m-1.
/*Code1: Haffman Algorithm*/#define MAXCHAR 30000#define MAXNODE 300#define MAXNUM 150#define InfoType charstruct HtNode{ EBTreeType ww; char info; int parentIndex; int llinkIndex; int rlinkIndex;};struct HtTree{ struct HtNode ht[MAXNODE]; int rootIndex;};typedef struct HtTree* PHtTree;PHtTree haffmanAlgorithm(int m,EBTreeType* w){ PHtTree pht; int i,j; int firstMinIndex,secondMinIndex; int firstMinW,secondMinW; pht=(PHtTree)malloc(sizeof(struct HtTree)); assertF(pht!=NULL,"in haffman algorithm,mem apply failure\n"); /*Initialize the tree array*/ for(i=0;i<2*m-1;i++) { pht->ht[i].llinkIndex=-1; pht->ht[i].rlinkIndex=-1; pht->ht[i].parentIndex=-1; if(i<m) { pht->ht[i].ww=w[i]; pht->ht[i].info=(char)i; } else pht->ht[i].ww=-1; } for(i=0;i<m-1;i++)//new Inner Node Num:m-1 { firstMinW=MAXCHAR; firstMinIndex=-1; secondMinW=MAXCHAR; secondMinIndex=-1; for(j=0;j<m+i;j++) { if(pht->ht[j].ww<firstMinW&&pht->ht[j].parentIndex==-1) { //trans minFirst info to minSecond info secondMinIndex=firstMinIndex; secondMinW=firstMinW; //set new first min node. firstMinIndex=j; firstMinW=pht->ht[j].ww; } else if(pht->ht[j].ww<secondMinW&&pht->ht[j].parentIndex==-1) /*update second node info*/ { secondMinW=pht->ht[j].ww; secondMinIndex=j; } } //Construct a new node. m+i is current new node's index pht->ht[firstMinIndex].parentIndex=m+i; pht->ht[secondMinIndex].parentIndex=m+i; pht->ht[m+i].ww=firstMinW+secondMinW; pht->ht[m+i].llinkIndex=firstMinIndex; pht->ht[m+i].rlinkIndex=secondMinIndex; pht->rootIndex=m+i; } return pht;}壓縮過程的實現:
壓縮過程的流程是清晰而簡單的:
創建Haffman樹
打開需壓縮文件
將需壓縮文件中的每個ascii碼對應的haffman編碼按bit單位輸出à4文件壓縮結束。
其中，步驟1和步驟3是壓縮過程的關鍵。
步驟1:這裡所要做工作是得到Haffman數中各葉子結點字符出現的頻率並進行創建.統計字符出現的頻率可以有很多方法:如每次創建前掃描被創建的文件，“實時”的生成各字符的出現頻率;或者是創建前即做好統計.本文采用後一種的方案,統計了十篇不同的文章中字符出現的頻率。當前，也可以根據被壓縮文件的特性有針對性的進行統計，如要壓縮C語言的源文件，則可事先對多篇C語言源文件中出現的字符進行統計,這樣，會創建出高度相對較“矮”的Haffman樹，從而提高壓縮效果。
創建Haffman樹的算法前文已有陳述，這裡就不再重復了。
步驟3: 將需壓縮文件中的每個ascii碼對應的haffman編碼按bit單位輸出.
這是本壓縮程序中最關鍵的部分:
這裡涉及“轉換”和“輸出”兩個關鍵步驟:
“轉換”部分大可不必去通過遍歷Haffman樹來找到每個字符對應的哈夫曼編碼，可以將每個Haffman碼值及其對應的ascii碼存放於如下所示的結構體中：
typedef struct{ char asciiCode; unsigned long haffCode; int haffCodeLen;}HaffCode;創建由該結構體結點所組成的，長度為128的一維數組codeList128且codeList中的下標和asciiCode滿足下面的順序存放關系:
codeList[i].asciiCode=i;這樣的話，查找某個字符inChar的haffman編碼的工作便變得相當輕松了,如下:
sHaffCode=codeList[inChar].haffCode;
數組codeList128的創建可以采用某種遍歷方式下的按找到的字符進行置數的方式，十分的方便:
