C语言实现哈夫曼编码

前言

哈夫曼编码（Huffman Coding）是一种经典的无损数据压缩算法，由 David Huffman 于 1952 年提出。它的核心思想非常朴素——高频字符用短编码，低频字符用长编码，从而达到整体压缩的效果。

这篇文章将基于我课程设计的实际代码，从数据结构选型开始，逐步讲解哈夫曼树的构建、编码的生成、文件的压缩与解压，以及这个算法固有的局限性。

一、数据结构选型

在设计一个压缩系统之前，首先要回答一个问题：用什么来存储数据？

为什么用顺序表（数组）而不是链表？

哈夫曼树的节点数是确定的——如果有 n 个不同的字符，那么树中总共有 2n - 1 个节点（因为每两个节点合并产生一个新节点）。既然总数确定，用数组来实现顺序存储就比链表更高效：随机访问是 O(1)，而链表每次选取最小权值节点时需要遍历。

三个核心数据结构

频率数组 freq[256]：ASCII 字符共 256 个（如果只考虑单字节），用一个 int 类型的数组记录每个字符出现的次数。数组下标就是字符的 ASCII 码，值是它出现的次数。

int freq[256] = {0};  // 全局变量，所有源文件共享

哈夫曼树节点数组 HuffNode ht[]：用双亲表示法存储树结构。每个节点记录自己的权值、双亲节点下标、左右孩子下标。0 表示不存在。

typedef struct {
    int weight;           // 权值
    int parent, lch, rch; // 双亲、左孩子、右孩子下标，0 表示无
} HuffNode;

编码表 HuffCode hc[]：为每个叶子节点（字符）存储对应的哈夫曼编码，编码用字符串形式存放。

typedef struct {
    char code[256];       // 存放编码字符串，如 "0110"
} HuffCode;

数组大小的确定

频率数组：256 个位置，覆盖所有可能的 unsigned char 值
哈夫曼树数组：最坏情况下 256 个不同字符全部出现，共 2 × 256 - 1 = 511 个节点，定义 MAX * 2 即 512 足够
编码表：同样 256 个位置

二、读取文件与频率统计

一切压缩的前提是知道文件中每个字符出现了多少次。这一步由 ReadFileAndCount() 完成：

int ReadFileAndCount(char *filename) {
    memset(freq, 0, sizeof(freq));  // 清空频率表
    FILE *fp = fopen(filename, "r");
    if (!fp) {
        printf("文件打开失败\n");
        exit(0);
    }
    char ch;
    while ((ch = fgetc(fp)) != EOF) {
        freq[(unsigned char)ch]++;  // 关键：unsigned char 转换
    }
    fclose(fp);

    int n = 0;  // 统计有效字符个数（叶子节点数）
    for (int i = 0; i < 256; i++)
        if (freq[i] > 0)
            n++;
    return n;
}

为什么 `(unsigned char)ch` 而不是直接 `ch`？

C 语言中 char 是有符号的，范围是 -128 ~ 127。当文件包含 ASCII > 127 的字符时（如中文、特殊符号），ch 会被解释为负值。如果用负值作为数组下标，会产生越界错误。

(unsigned char)ch 将字符值映射到 0 ~ 255，与 freq[256] 的下标范围完美对应。这是处理二进制或非纯英文文本时必须留意的一个细节。

叶子节点数 `n` 的含义

n 统计的是 freq[i] > 0 的字符个数，也就是哈夫曼树的叶子节点数量。后面建树、编码、压缩都依赖这个值。

三、构建哈夫曼树

这是整个算法的核心。构建过程是一个自底向上的贪心过程。

选择最小两个节点：`SelectMin()`

void SelectMin(HuffNode ht[], int len, int *s1, int *s2) {
    int i, min1 = 0x7fffffff, min2 = 0x7fffffff;
    *s1 = *s2 = 0;
    for (i = 1; i <= len; i++) {
        if (ht[i].parent == 0) {         // 只考虑尚未被合并的节点
            if (ht[i].weight < min1) {
                min2 = min1; *s2 = *s1;   // 原最小值降为次小值
                min1 = ht[i].weight;
                *s1 = i;
            } else if (ht[i].weight < min2) {
                min2 = ht[i].weight;
                *s2 = i;
            }
        }
    }
}

每次从 parent == 0（即尚未合并到树中）的节点里，挑选权值最小的两个。这个函数的时间复杂度是 O(m)，m 是当前待选节点个数。

建树过程：`CreateHuffTree()`

void CreateHuffTree(HuffNode ht[], int n) {
    int i, s1, s2;
    int total = 2 * n - 1;  // 总结点数
    for (i = n + 1; i <= total; i++) {
        SelectMin(ht, i - 1, &s1, &s2);
        ht[s1].parent = i;
        ht[s2].parent = i;
        ht[i].lch = s1;
        ht[i].rch = s2;
        ht[i].weight = ht[s1].weight + ht[s2].weight;
    }
}

执行过程：

前 n 个位置（1 ~ n）存放叶子节点，各节点的 weight 取自 freq[]
从 n + 1 开始创建内部节点，每个内部节点合并两个权值最小的自由节点
新节点的权值 = 左孩子权值 + 右孩子权值
更新被合并节点的 parent 指向新节点
重复直到只剩一个根节点（下标为 2n - 1）

下图展示了一个简单例子——假设只有 4 个字符 a(频率 5)、b(频率 3)、c(频率 2)、d(频率 1)：

初始叶子节点:         合并过程:                  最终哈夫曼树:
ht[1]: a, w=5        Step1: 选 w=1(d) + w=2(c)         ht[7] (w=11)
ht[2]: b, w=3        → ht[5] w=3, lch=4, rch=3          /      \
ht[3]: c, w=2        Step2: 选 w=3(b) + w=3(ht[5])   ht[6](w=6) ht[1](a,w=5)
ht[4]: d, w=1        → ht[6] w=6, lch=2, rch=5        /      \
                      Step3: 选 w=5(a) + w=6(ht[6])  ht[2](b) ht[5](w=3)
                      → ht[7] w=11, lch=1, rch=6               /      \
                                                            ht[4](d) ht[3](c)

四、生成哈夫曼编码

树构建完成后，每个叶子节点到根节点的路径，就是该字符的哈夫曼编码。

编码逻辑

void CreateHuffCode(HuffNode ht[], HuffCode hc[], int n) {
    char tmp[256];
    int i, cur, p, len;
    for (i = 1; i <= n; i++) {       // 遍历每个叶子节点
        len = 0;
        cur = i;
        p = ht[cur].parent;
        while (p != 0) {             // 从叶子向根回溯
            if (ht[p].lch == cur)
                tmp[len++] = '0';    // 左孩子 → 0
            else
                tmp[len++] = '1';    // 右孩子 → 1
            cur = p;
            p = ht[cur].parent;
        }
        tmp[len] = '\0';
        strrev(tmp);                 // 翻转！因为是从叶子向根收集的
        strcpy(hc[i].code, tmp);
    }
}

为什么需要 `strrev()` 翻转？

回溯是从叶子向根走的，所以收集到的编码是反的。比如在上面的例子中，字符 c 的回溯路径是：

c (ht[3]) → ht[5](右孩子，得1) → ht[6](右孩子，得1)

收集结果为 "11"，翻转后 "11"（恰好回文看不到区别）。但看字符 d：

d (ht[4]) → ht[5](左孩子，得0) → ht[6](右孩子，得1)

收集结果为 "01"，翻转后 "10"。如果不翻转，编码 "01" 和翻转后的 "10" 完全对应了不同的路径。

正确做法：回溯 → 收集 → 翻转 → 存入编码表。

`strrev()` 的手写实现

标准 C 库没有 strrev()，所以自己实现了一个双指针翻转：

char *strrev(char *str) {
    if (str == NULL) return NULL;
    char *start = str;
    char *end = str + strlen(str) - 1;
    char temp;
    while (start < end) {
        temp = *start;
        *start = *end;
        *end = temp;
        start++; end--;
    }
    return str;
}

五、压缩文件

这是整个系统中最复杂的部分。压缩文件的结构如下：

频率表(256×4Byte)->有效位数(4Byte)->二进制编码序列(变长)

步骤 1：拼接编码字符串

// 第一遍：统计总编码长度
int totalBits = 0;
while ((ch = fgetc(fpIn)) != EOF) {
    // 找到 ch 对应的编码，累加 strlen
    totalBits += strlen(hc[idx].code);
}
rewind(fpIn);  // 回到文件开头

// 动态分配足够大的缓冲区
char *bitBuf = (char *)malloc(totalBits + 1);
bitBuf[0] = '\0';

// 第二遍：拼接编码
while ((ch = fgetc(fpIn)) != EOF) {
    strcat(bitBuf, hc[idx].code);  // 把每个字符的编码拼到缓冲区
}

为什么需要两遍遍历？ 第一遍统计总长度，才知道该分配多大内存。如果直接用一个固定大小（比如 char bitBuf[10000]），遇到大文件会溢出。

步骤 2：写入频率表和有效位数

fwrite(freq, sizeof(int), 256, fpOut);    // 频率表：256×4 = 1024 字节
int len = strlen(bitBuf);
fwrite(&len, sizeof(int), 1, fpOut);      // 有效位数：4 字节

频率表是解压的必要条件——没有频率表，解压方就无法重建哈夫曼树。

步骤 3：8 位一组转二进制写入

unsigned char byte = 0;
int cnt = 0;
for (int i = 0; i < len; i++) {
    byte <<= 1;              // 左移一位，低位补 0
    if (bitBuf[i] == '1')
        byte |= 1;           // 最低位设 1
    cnt++;
    if (cnt == 8) {
        fputc(byte, fpOut);  // 满 8 位，写入
        byte = 0;
        cnt = 0;
    }
}
// 处理不足 8 位的尾部
if (cnt > 0) {
    byte <<= (8 - cnt);      // 左移到高位，右侧补 0
    fputc(byte, fpOut);
}

这是压缩的精髓——把字符 '0' 和 '1' 组成的长字符串（每个字符占 1 字节），压缩成真正的二进制位。例如字符串 "01101001" 占 8 字节 → 压缩后只占 1 字节。

尾部不足 8 位的处理：假设最后剩下 "101"（3 位），将其左移 5 位变为 10100000，作为一个字节写入。解压时通过 len 知道只有前 3 位有效，忽略后面的填充位。

六、解压缩文件

解压是压缩的逆过程。

步骤 1：读取文件头部，重建频率表

fread(tempFreq, sizeof(int), 256, fp);  // 读频率表
fread(&len, sizeof(int), 1, fp);        // 读有效位数

用频率表在内存中重建一棵完全相同的哈夫曼树。

步骤 2：逐位解析，沿树行走

int root = 2 * n - 1;
int p = root;
int count = 0;

while (fread(&ch, 1, 1, fpIn) > 0) {
    for (int i = 7; i >= 0; i--) {   // 从高位到低位逐位解析
        count++;
        if (count >= len + 1) {       // 有效长度到了，停止
            return;
        }
        int bit = (ch >> i) & 1;      // 取出第 i 位
        if (bit == 0)
            p = ht[p].lch;            // 遇 0 走左
        else
            p = ht[p].rch;            // 遇 1 走右

        // 到达叶子节点？
        if (ht[p].lch == 0 && ht[p].rch == 0) {
            fputc(j, fpOut);         // 输出对应字符
            p = root;                // 回到根节点，继续下一个字符
        }
    }
}

核心逻辑：从根节点出发，每读到一个二进制位就沿着树向下走一步。一旦走到叶子节点（左右孩子都为 0），说明找到了一个完整字符，将其写入输出文件，然后回到根节点继续下一个。

为什么需要记录 `len`？

编码序列的尾部可能包含填充的无效位。如果不记录 len，解码器会把填充的 0 当作有效编码继续解析，导致输出多余字符。通过 len 精确控制解码的位数，避免这个问题。

七、实验对比与算法局限

test1.txt：高压缩率场景

test1.txt 内容为大量重复的 a、b、c、d 字符，文件大小约 5.4KB。压缩后文件显著变小。

字符分布极度集中（只有 7 种字符）
编码长度差异大，高频字符（a、b）获得极短编码
节省的空间远大于 1024 字节的频率表开销

test2.txt：低压缩率场景

test2.txt 内容为 "hello world!\nmy name is LiMing.\n"，只有 37 字节。

压缩后的文件反而比原文件更大。原因在于：

频率表 1024 字节 + 有效位数 4 字节 = 1028 字节固定开销
原始文件只有 37 字节
即使用哈夫曼编码把 37 字节压成 10 位，最终文件也至少 1028+ 字节

哈夫曼编码的三大局限

1. 频率表开销不可忽略

无论文件多大，都要写入 256×4=1024 字节的频率表。对小文件来说，这个头部开销可能远超编码本身节省的空间。这是哈夫曼编码不适合压缩小文件的根本原因。

2. 压缩率依赖字符分布

如果文件中 256 种字符几乎均匀出现，每个字符的哈夫曼编码长度接近 8 位，和原始编码没有差别。加上频率表开销，压缩后反而更大。

3. 需要两次遍历文件

第一次统计频率，第二次进行编码。这意味着压缩必须持有完整的文件内容，无法对流式数据进行实时压缩。

八、总结

回顾整个项目，核心流程可以概括为：

读取文件统计频率 → 贪心建树 → 回溯生成编码 → 拼接转换为二进制 → 头部插入频率表

压缩的代价是额外的 1028 字节头部和两次文件遍历，换来的收益是重复字符越多、压缩效果越好。理解这个 trade-off，也就理解了哈夫曼编码为什么至今仍被广泛应用于各种压缩系统（如 JPEG、DEFLATE）中。

完整源代码见 GitHub 仓库：engineer-05/huffman。

前言