哈夫曼編碼是最優字長編碼嗎？

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

本文描述在網上能夠找到的最簡單，最快速的哈夫曼編碼。本方法不使用任何擴展動態庫，比如STL或者組件。只使用簡單的C函數，比如：memset，memmove，qsort，malloc，realloc和memcpy。

因此，大家都會發現，理解甚至修改這個編碼都是很容易的。

背景

哈夫曼壓縮是個無損的壓縮算法，壹般用來壓縮文本和程序文件。哈夫曼壓縮屬於可變代碼長度算法壹族。意思是個體符號（例如，文本文件中的字符）用壹個特定長度的位序列替代。因此，在文件中出現頻率高的符號，使用短的位序列，而那些很少出現的符號，則用較長的位序列。

編碼使用

我用簡單的C函數寫這個編碼是為了讓它在任何地方使用都會比較方便。妳可以將他們放到類中，或者直接使用這個函數。並且我使用了簡單的格式，僅僅輸入輸出緩沖區，而不象其它文章中那樣，輸入輸出文件。

bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);

bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);

要點說明

速度

為了讓它(huffman.cpp)快速運行，我花了很長時間。同時，我沒有使用任何動態庫，比如STL或者MFC。它壓縮1M數據少於100ms（P3處理器，主頻1G）。

壓縮

壓縮代碼非常簡單，首先用ASCII值初始化511個哈夫曼節點：

CHuffmanNode nodes[511];

for(int nCount = 0; nCount < 256; nCount++)

nodes[nCount].byAscii = nCount;

然後，計算在輸入緩沖區數據中，每個ASCII碼出現的頻率：

for(nCount = 0; nCount < nSrcLen; nCount++)

nodes[pSrc[nCount]].nFrequency++;

然後，根據頻率進行排序：

qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);

現在，構造哈夫曼樹，獲取每個ASCII碼對應的位序列：

int nNodeCount = GetHuffmanTree(nodes);

構造哈夫曼樹非常簡單，將所有的節點放到壹個隊列中，用壹個節點替換兩個頻率最低的節點，新節點的頻率就是這兩個節點的頻率之和。這樣，新節點就是兩個被替換節點的父節點了。如此循環，直到隊列中只剩壹個節點（樹根）。

// parent node

pNode = &nodes[nParentNode++];

// pop first child

pNode->pLeft = PopNode(pNodes, nBackNode--, false);

// pop second child

pNode->pRight = PopNode(pNodes, nBackNode--, true);

// adjust parent of the two poped nodes

pNode->pLeft->pParent = pNode->pRight->pParent = pNode;

// adjust parent frequency

pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency;

這裏我用了壹個好的訣竅來避免使用任何隊列組件。我先前就直到ASCII碼只有256個，但我分配了511個(CHuffmanNode nodes[511])，前255個記錄ASCII碼，而用後255個記錄哈夫曼樹中的父節點。並且在構造樹的時候只使用壹個指針數組(ChuffmanNode *pNodes[256])來指向這些節點。同樣使用兩個變量來操作隊列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。

接著，壓縮的最後壹步是將每個ASCII編碼寫入輸出緩沖區中：

int nDesIndex = 0;

// loop to write codes

for(nCount = 0; nCount < nSrcLen; nCount++)

{

*(DWORD*)(pDesPtr+(nDesIndex>>3)) |=

nodes[pSrc[nCount]].dwCode << (nDesIndex&7);

nDesIndex += nodes[pSrc[nCount]].nCodeLength;

}

(nDesIndex>>3): >>3 以8位為界限右移後到達右邊字節的前面

(nDesIndex&7): &7 得到最高位.

註意：在壓縮緩沖區中，我們必須保存哈夫曼樹的節點以及位序列，這樣我們才能在解壓縮時重新構造哈夫曼樹（只需保存ASCII值和對應的位序列）。

解壓縮

解壓縮比構造哈夫曼樹要簡單的多，將輸入緩沖區中的每個編碼用對應的ASCII碼逐個替換就可以了。只要記住，這裏的輸入緩沖區是壹個包含每個ASCII值的編碼的位流。因此，為了用ASCII值替換編碼，我們必須用位流搜索哈夫曼樹，直到發現壹個葉節點，然後將它的ASCII值添加到輸出緩沖區中：

int nDesIndex = 0;

DWORD nCode;

while(nDesIndex < nDesLen)

{

nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);

pNode = pRoot;

while(pNode->pLeft)

{

pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;

nCode >>= 1;

nSrcIndex++;

}

pDes[nDesIndex++] = pNode->byAscii;

}