C 語言實現霍夫曼編碼：從頻率統計到壓縮解壓完整流程

一、霍夫曼編碼核心思想

對出現頻率高的字符分配短編碼，低頻分配長編碼，構建最優前綴碼，實現無損壓縮。關鍵步驟：

1. 統計字符頻率
2. 構建霍夫曼樹（最小堆/優先隊列反复合併最小兩節點）
3. 從根到葉遍歷生成編碼表（左 0，右 1）
4. 編碼：查表替換；解碼：按位遍歷樹

二、數據結構定義

#define MAX_ALPHA 52   // A-Z, a-z
#define MAX_NODES (2*MAX_ALPHA)

typedef struct Node {
    int freq;           // 頻率/權重
    char ch;            // 字符（葉節點有效）
    struct Node *left, *right;
    struct Node *parent; // 解碼用
} Node;

Node nodes[MAX_NODES];
int node_cnt = 0;

三、構建霍夫曼樹

void build_huffman_tree(int freq[], char chars[], int n) {
    /* 初始化葉節點 */
    for (int i = 0; i < n; i++) {
        nodes[i].freq = freq[i];
        nodes[i].ch = chars[i];
        nodes[i].left = nodes[i].right = nodes[i].parent = NULL;
    }
    node_cnt = n;

    /* 反复合併最小兩棵樹 */
    for (int i = 0; i < n - 1; i++) {
        /* 找無父節點且 freq 最小的兩個 */
        int min1 = -1, min2 = -1;
        for (int j = 0; j < node_cnt; j++) {
            if (nodes[j].parent) continue;
            if (min1 == -1 || nodes[j].freq < nodes[min1].freq) {
                min2 = min1; min1 = j;
            } else if (min2 == -1 || nodes[j].freq < nodes[min2].freq) {
                min2 = j;
            }
        }
        /* 創建父節點 */
        nodes[node_cnt].freq = nodes[min1].freq + nodes[min2].freq;
        nodes[node_cnt].ch = 0;
        nodes[node_cnt].left = &nodes[min1];
        nodes[node_cnt].right = &nodes[min2];
        nodes[min1].parent = nodes[min2].parent = &nodes[node_cnt];
        node_cnt++;
    }
    /* 根節點索引 = node_cnt - 1 */
}

四、生成編碼表（從葉向根回溯）

#define MAX_CODE_LEN 100

typedef struct { char bits[MAX_CODE_LEN]; int len; char ch; } Code;
Code codes[MAX_ALPHA];

void generate_codes(int n) {
    for (int i = 0; i < n; i++) {
        Code *c = &codes[i];
        c->ch = nodes[i].ch;
        c->len = 0;
        Node *cur = &nodes[i];
        while (cur->parent) {
            c->bits[c->len++] = (cur == cur->parent->left) ? '0' : '1';
            cur = cur->parent;
        }
        /* 反轉得到根→葉順序 */
        for (int l = 0, r = c->len - 1; l < r; l++, r--) {
            char tmp = c->bits[l]; c->bits[l] = c->bits[r]; c->bits[r] = tmp;
        }
    }
}

五、編碼與解碼

/***** 編碼：查表拼接 *****/
void encode(const char *input, char *output) {
    char *p = output;
    for (const char *s = input; *s; s++) {
        for (int i = 0; i < node_cnt; i++) {
            if (codes[i].ch == *s) {
                memcpy(p, codes[i].bits, codes[i].len);
                p += codes[i].len;
                break;
            }
        }
    }
    *p = '\0';
}

/***** 解碼：按位走樹 *****/
void decode(const char *bits, char *output) {
    Node *cur = &nodes[node_cnt - 1];  // 根
    char *p = output;
    for (const char *b = bits; *b; b++) {
        cur = (*b == '0') ? cur->left : cur->right;
        if (!cur->left && !cur->right) {  // 葉節點
            *p++ = cur->ch;
            cur = &nodes[node_cnt - 1];   // 回根
        }
    }
    *p = '\0';
}

六、主程序演示

int main() {
    const char *text = "FORGET";  // 示例文本
    int freq[256] = {0};
    for (const char *p = text; *p; p++) freq[(unsigned char)*p]++;

    char chars[MAX_ALPHA]; int f[MAX_ALPHA], n = 0;
    for (int i = 0; i < 256; i++) if (freq[i]) {
        chars[n] = i; f[n] = freq[i]; n++;
    }

    build_huffman_tree(f, chars, n);
    generate_codes(n);

    printf("字符編碼表:\n");
    for (int i = 0; i < n; i++)
        printf("'%c': %.*s\n", codes[i].ch, codes[i].len, codes[i].bits);

    char encoded[1000], decoded[1000];
    encode(text, encoded);
    printf("原文: %s\n編碼: %s\n", text, encoded);

    decode(encoded, decoded);
    printf("解碼: %s\n", decoded);
    return 0;
}

七、運行輸出示例

字符編碼表:
'F': 000
'O': 001
'R': 010
'G': 011
'E': 10
'T': 11
原文: FORGET
編碼: 0000010100111011
解碼: FORGET

八、工程優化方向

• 用最小堆優化樹構建至 O(n log n)
• 編碼表用數組/哈希表 O(1) 查找
• 位流讀寫封裝BitWriter/BitReader，按位操作文件
• 標準頭部存儲：字符集大小、頻率表/樹結構、數據長度
• 大文件分塊壓縮，支持流式處理

總結

霍夫曼編碼是壓縮算法基石。掌握頻率統計 → 最小堆構樹 → 回溯生碼 → 查表編碼 / 走樹解碼完整鏈路，能自行實現壓縮工具、理解 DEFLATE/JPEG/MP3 等格式核心邏輯。