【数据结构与算法】-（11）霍夫曼编码（HuffmanCoding）

发布日期: 2021-01-17

文章字数: 1.8k

阅读时长: 7 分

阅读次数:

【数据结构与算法】-（1）基础篇

【数据结构与算法】-（2）线性表基础

【数据结构与算法】-（3）循环链表（单向）

【数据结构与算法】-（4）双向链表和双向循环链表

【数据结构与算法】-（5）链表面试题解析

【数据结构与算法】-（6）栈

【数据结构与算法】-（7）队列

【数据结构与算法】-（8）栈之算法题

【数据结构与算法】-（8.1）字符串去重算法

【数据结构与算法】-（8.2）字符串搜索算法和RK&BP算法

【数据结构与算法】-（8.3）KMP算法

【数据结构与算法】-（9）二叉树与顺序表实现

【数据结构与算法】-（10）线索化二叉树

文章字数: 约4.5k
阅读时长: 25 分钟

一、概念

1.1 霍夫曼编码的定义

霍夫曼编码（Huffman Coding）是一种被广泛使用的数据压缩编码算法，由美国计算机科学家大卫·霍夫曼（David A. Huffman）在1952年发明。这种编码方式是一种变长编码方法，其核心思想是：对出现频率高的字符使用较短的编码，对出现频率低的字符使用较长的编码，以此来达到压缩数据的目的。

1.2 霍夫曼编码的特点

变长编码：不同字符的编码长度可以不同
前缀编码：任一字符的编码都不是其他字符编码的前缀
最优性：在变长编码中，霍夫曼编码是最优的

1.3 霍夫曼树

霍夫曼编码的关键在于构建霍夬曼树。霍夫曼树是一种特殊的二叉树，具有以下特点：

树中每个叶节点代表一个字符及其出现频率
树中每个非叶节点的权值等于其左右子树权值之和
树的带权路径长度最小

二、霍夫曼树的存储结构

2.1 节点结构

霍夫曼树的节点结构通常包含以下信息：

typedef struct {
    unsigned int weight;  // 权值（频率）
    unsigned int parent, lchild, rchild;  // 父节点、左子节点、右子节点
} HTNode, *HuffmanTree;

2.2 霍夫曼编码表

为了方便编码和解码，我们还需要一个霍夫曼编码表：

typedef char** HuffmanCode;

三、霍夫曼编码的实现

3.1 构建霍夫曼树

构建霍夫曼树的过程是一个自底向上的过程，主要步骤如下：

将所有叶子节点（即待编码的字符）按照权值（频率）从小到大排序
取出权值最小的两个节点，生成一个新节点作为它们的父节点，新节点的权值为两个子节点权值之和
从序列中删除这两个节点，将新节点加入序列
重复步骤2和3，直到只剩一个节点，这个节点就是霍夫曼树的根节点

void CreateHuffmanTree(HuffmanTree *HT, int n, int *w) {
    if (n <= 1) return;
    int m = 2 * n - 1;  // 霍夫曼树总节点数
    *HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));  // 0号单元未用
    HuffmanTree p = *HT;
    
    // 初始化叶子节点
    for (int i = 1; i <= n; ++i) {
        p[i].weight = w[i - 1];
        p[i].parent = 0;
        p[i].lchild = 0;
        p[i].rchild = 0;
    }
    
    // 初始化非叶子节点
    for (int i = n + 1; i <= m; ++i) {
        p[i].weight = 0;
        p[i].parent = 0;
        p[i].lchild = 0;
        p[i].rchild = 0;
    }
    
    // 构建霍夫曼树
    for (int i = n + 1; i <= m; ++i) {
        int s1, s2;
        Select(*HT, i - 1, &s1, &s2);  // 选择两个权值最小的节点
        p[s1].parent = i;
        p[s2].parent = i;
        p[i].lchild = s1;
        p[i].rchild = s2;
        p[i].weight = p[s1].weight + p[s2].weight;
    }
}

其中，Select 函数用于选择权值最小的两个节点：

void Select(HuffmanTree HT, int n, int *s1, int *s2) {
    int min1 = UINT_MAX, min2 = UINT_MAX;
    *s1 = *s2 = 0;
    for (int i = 1; i <= n; 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;
            }
        }
    }
}

3.2 生成霍夫曼编码

生成霍夫曼编码的过程是从叶子节点出发，向根节点回溯，记录路径的过程。通常约定向左子树走记为0，向右子树走记为1。

void HuffmanCoding(HuffmanTree HT, int n, HuffmanCode *HC) {
    *HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));
    char *cd = (char*)malloc(n * sizeof(char));  // 临时存放编码
    cd[n - 1] = '\0';
    
    for (int i = 1; i <= n; ++i) {
        int start = n - 1;  // 编码结束符位置
        int c = i;
        int f = HT[i].parent;
        while (f != 0) {
            --start;
            if (HT[f].lchild == c)
                cd[start] = '0';
            else
                cd[start] = '1';
            c = f;
            f = HT[f].parent;
        }
        (*HC)[i] = (char*)malloc((n - start) * sizeof(char));
        strcpy((*HC)[i], &cd[start]);
    }
    free(cd);
}

四、霍夫曼编码的应用

4.1 数据压缩

霍夫曼编码最常见的应用是数据压缩。通过对高频字符使用短编码，低频字符使用长编码，可以显著减少数据的存储空间。

void Compress(const char* input, const char* output, HuffmanCode HC) {
    FILE *in = fopen(input, "r");
    FILE *out = fopen(output, "wb");
    
    int ch;
    unsigned char buf = 0;
    int buf_len = 0;
    
    while ((ch = fgetc(in)) != EOF) {
        char *code = HC[ch];
        for (int i = 0; code[i]; ++i) {
            buf = (buf << 1) | (code[i] - '0');
            if (++buf_len == 8) {
                fputc(buf, out);
                buf = 0;
                buf_len = 0;
            }
        }
    }
    
    if (buf_len) {
        buf <<= (8 - buf_len);
        fputc(buf, out);
    }
    
    fclose(in);
    fclose(out);
}

4.2 数据解压

解压过程是编码的逆过程，需要利用霍夫曼树从根节点开始，根据读取的位进行左右子树的选择，直到到达叶子节点。

void Decompress(const char* input, const char* output, HuffmanTree HT, int root) {
    FILE *in = fopen(input, "rb");
    FILE *out = fopen(output, "w");
    
    int p = root;
    unsigned char ch;
    while (fread(&ch, sizeof(char), 1, in) > 0) {
        for (int i = 0; i < 8; ++i) {
            if (ch & (1 << (7 - i)))
                p = HT[p].rchild;
            else
                p = HT[p].lchild;
            
            if (HT[p].lchild == 0 && HT[p].rchild == 0) {
                fputc(p, out);
                p = root;
            }
        }
    }
    
    fclose(in);
    fclose(out);
}