極簡高效哈夫曼編碼實作：純 C 函數、無 STL 依賴

前言

本文呈現網路上最簡單、最快速的哈夫曼編碼實作。僅使用標準 C 函數 (memset, memmove, qsort, malloc, realloc, memcpy)，無 STL、MFC 或任何外部庫依賴，極易理解、修改與移植。

背景知識

哈夫曼壓縮為無損、可變長度編碼演算法：高頻符號用短位元碼，低頻符號用長位元碼，常用於文字與程式檔壓縮。

介面設計

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

輸入/輸出均為記憶體緩衝區，不處理檔案 I/O，方便整合。

壓縮核心流程

1. 初始化 511 個節點：前 256 個對應 ASCII 碼，後 255 個作為內部父節點。

   CHuffmanNode nodes[511];
   for (int i=0; i<256; ++i) nodes[i].byAscii = i;

2. 統計頻率：

   for (int i=0; i<nSrcLen; ++i) nodes[pSrc[i]].nFrequency++;

3. 依頻率排序：qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);
4. 建立哈夫曼樹：使用指標陣列 CHuffmanNode *pNodes[256] 模擬佇列，兩兩合併最低頻率節點建立父節點，直到剩一個根節點。

   // 關鍵技巧：預分配 511 節點，前 255 葉節點，後 255 內部節點
   // 佇列索引操作：nParentNode 遞增，nBackNode 遞減
   pNode = &nodes[nParentNode++];
   pNode->pLeft  = PopNode(pNodes, nBackNode--, false);
   pNode->pRight = PopNode(pNodes, nBackNode--, true);
   pNode->pLeft->pParent = pNode->pRight->pParent = pNode;
   pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency;

5. 產生編碼並寫入輸出緩衝區：位元級寫入，利用位移運算高效打包。

   int nDesIndex = 0;
   for (int i=0; i<nSrcLen; ++i) {
       *(DWORD*)(pDesPtr + (nDesIndex>>3)) |= nodes[pSrc[i]].dwCode << (nDesIndex & 7);
       nDesIndex += nodes[pSrc[i]].nCodeLength;
   }

   nDesIndex>>3 定位位元組，nDesIndex&7 定位位元位置。

輸出緩衝區需包含樹資訊 (ASCII 值 + 編碼)，以便解壓時重建樹。

解壓縮流程

較壓縮簡單：以位元流走訪哈夫曼樹，遇葉節點輸出對應 ASCII。

int nDesIndex = 0, nSrcIndex = 0;
while (nDesIndex < nDesLen) {
    DWORD nCode = (*(DWORD*)(pSrc + (nSrcIndex>>3))) >> (nSrcIndex & 7);
    CHuffmanNode *pNode = pRoot;
    while (pNode->pLeft) {
        pNode = (nCode & 1) ? pNode->pRight : pNode->pLeft;
        nCode >>= 1;
        ++nSrcIndex;
    }
    pDes[nDesIndex++] = pNode->byAscii;
}

效能數據

P3 1GHz 處理器下，壓縮 1MB 資料 < 100ms。

原始碼檔案

• Huffman.h / Huffman.cpp

請參考本文附件壓縮包。

結語

純 C 實作、零依賴、高效能，適合嵌入式系統、跨平台專案或教學示範。歡迎開發者根據需求擴充 (如支援 Unicode、檔案流介面等)。