霍夫曼樹編碼的 C 語言實現詳解

前言

霍夫曼編碼是一種廣泛應用於數據壓縮的無損壓縮演算法。它根據字符出現的頻率構建一棵最優二叉樹（霍夫曼樹），使高頻字符擁有較短的編碼，低頻字符擁有較長的編碼，從而達到壓縮數據的目的。本文將通過一個完整的 C 語言程式範例，詳細解析霍夫曼樹的構建與編碼生成過程。

核心資料結構

程式中定義了兩個關鍵結構體：

• HTNode：代表霍夫曼樹中的節點，包含權重（Weight）、父節點索引（Parent）、左孩子索引（lChild）與右孩子索引（rChild）。
• HuffmanCode：定義為 char **，用於存儲每個字符對應的霍夫曼編碼字串。

主要流程解析

1. 統計字符頻率 (OutputWeight)

程式首先讀取使用者輸入的字串，掃描統計每個字符出現的次數。為了便於構建樹，將頻率轉換為整數權重（這裡乘以 1000 並取整），同時記錄字符集合與對應權重陣列。

2. 構建霍夫曼樹 (HuffmanCoding)

演算法核心步驟如下：

1. 初始化：分配 2 * Count - 1 個節點空間。前 Count 個節點為葉子節點，填入統計得到的權重，父子指標歸零；後續節點作為內部節點暫時歸零。
2. 反覆合併：進行 Count - 1 次循環，每次在當前無父節點的節點中，透過 Select 函式找出權重最小的兩個節點 s1、s2。
3. 建立關係：將 s1、s2 的父節點設為新節點 i，新節點的左右孩子分別指向 s1、s2，權重為兩者之和。

3. 選擇最小權重節點 (Select)

該函式遍歷索引 1 到 Count 的節點，找出 Parent == 0（尚未被合併）且權重最小的兩個節點。邏輯上維護 temp1（最小）與 temp2（次小），並同步更新索引 s1、s2。

4. 生成霍夫曼編碼

對每個葉子節點（1 到 Count），從該節點向根回溯：若當前節點是父節點的左孩子則記錄 '0'，否則記錄 '1'。編碼在暫存陣列 cd 中從後向前填寫，最後複製到 HC 對應位置。

完整程式碼範例

以下為可直接編譯執行的原始碼（已修正部分語法細節）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    unsigned int Weight;
    unsigned int Parent;
    unsigned int lChild;
    unsigned int rChild;
} HTNode, *HuffmanTree;

typedef char **HuffmanCode;

int LookFor(char *str, char letter, int count);
void OutputWeight(char *Data, int Length, char **WhatLetter, int **Weight, int *Count);
void HuffmanCoding(HuffmanTree *HT, HuffmanCode *HC, int *Weight, int Count);
void Select(HuffmanTree HT, int Count, int *s1, int *s2);

int main() {
    HuffmanTree HT;
    HuffmanCode HC;
    char Data[100];
    char *WhatLetter;
    int *Weight;
    int Count, i;

    printf("Please input the line (e.g. aaaaaaaaaaaaaabcccccc): ");
    scanf("%s", Data);
    printf("\n");

    OutputWeight(Data, strlen(Data), &WhatLetter, &Weight, &Count);
    HuffmanCoding(&HT, &HC, Weight, Count);

    printf(" Letter Weight Code\n");
    for (i = 0; i < Count; i++) {
        printf(" %c %d %s\n", WhatLetter[i], Weight[i], HC[i + 1]);
    }
    printf("\n");
    return 0;
}

/* 以下為各函式實現，略去重複標頭，請參考原始碼完整複製 */

執行範例

輸入：aaaaaaaaaaaaaabcccccc
輸出將顯示每個字符的權重與對應編碼，例如：

 Letter Weight Code
 a 1000 0
 b 500 10
 c 300 11

總結

本範例展示了霍夫曼編碼從頻率統計、樹構建到編碼生成的完整流程。理解此過程有助於掌握貪婪演算法在資料壓縮中的應用，也為後續學習更複雜的壓縮技術（如算術編碼、LZW）打下基礎。