081. 编写代码实现简单的文件压缩和解压

在C语言中，实现简单的文件压缩和解压可以通过多种方法，其中一种常见的方法是使用霍夫曼编码（Huffman Coding）。霍夫曼编码是一种基于字符频率的压缩算法，能够有效地减少文件的大小。以下是一个简单的实现示例，展示如何使用霍夫曼编码进行文件压缩和解压。

1. 霍夫曼编码的基本原理

霍夫曼编码是一种变长编码方法，根据字符的频率生成一个最优的二叉树（霍夫曼树），然后根据这棵树生成每个字符的编码。频率高的字符分配较短的编码，频率低的字符分配较长的编码，从而实现压缩。

2. 实现步骤

统计字符频率：读取文件，统计每个字符的出现频率。
构建霍夫曼树：根据字符频率构建霍夫曼树。
生成编码表：根据霍夫曼树生成每个字符的编码。
压缩文件：使用编码表将文件内容转换为压缩后的二进制数据。
解压文件：使用霍夫曼树将压缩后的二进制数据解压还原为原始文件。

3. 示例代码

3.1 数据结构

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

#define MAX_TREE_HT 100

// 霍夫曼树节点
typedef struct HuffmanNode {
    char data;
    unsigned freq;
    struct HuffmanNode *left, *right;
} HuffmanNode;

// 优先队列（最小堆）
typedef struct MinHeap {
    int size;
    int capacity;
    HuffmanNode** array;
} MinHeap;

3.2 辅助函数

// 创建一个新的霍夫曼树节点
HuffmanNode* createHuffmanNode(char data, unsigned freq) {
    HuffmanNode* node = (HuffmanNode*)malloc(sizeof(HuffmanNode));
    node->data = data;
    node->freq = freq;
    node->left = node->right = NULL;
    return node;
}

// 创建一个最小堆
MinHeap* createMinHeap(int capacity) {
    MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (HuffmanNode**)malloc(minHeap->capacity * sizeof(HuffmanNode*));
    return minHeap;
}

// 交换两个最小堆节点
void swapHuffmanNode(HuffmanNode** a, HuffmanNode** b) {
    HuffmanNode* t = *a;
    *a = *b;
    *b = t;
}

// 最小堆化
void minHeapify(MinHeap* minHeap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)
        smallest = left;

    if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)
        smallest = right;

    if (smallest != idx) {
        swapHuffmanNode(&minHeap->array[smallest], &minHeap->array[idx]);
        minHeapify(minHeap, smallest);
    }
}

// 检查大小是否为1
int isSizeOne(MinHeap* minHeap) {
    return (minHeap->size == 1);
}

// 提取最小频率的节点
HuffmanNode* extractMin(MinHeap* minHeap) {
    HuffmanNode* temp = minHeap->array[0];
    minHeap->array[0] = minHeap->array[minHeap->size - 1];
    --minHeap->size;
    minHeapify(minHeap, 0);
    return temp;
}

// 插入一个新节点到最小堆
void insertMinHeap(MinHeap* minHeap, HuffmanNode* huffmanNode) {
    ++minHeap->size;
    int i = minHeap->size - 1;

    while (i && huffmanNode->freq < minHeap->array[(i - 1) / 2]->freq) {
        minHeap->array[i] = minHeap->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    minHeap->array[i] = huffmanNode;
}

// 构建最小堆
void buildMinHeap(MinHeap* minHeap) {
    int n = minHeap->size - 1;
    int i;

    for (i = (n - 1) / 2; i >= 0; --i)
        minHeapify(minHeap, i);
}

// 打印霍夫曼树
void printHuffmanCodes(HuffmanNode* root, int arr[], int top) {
    if (root->left) {
        arr[top] = 0;
        printHuffmanCodes(root->left, arr, top + 1);
    }

    if (root->right) {
        arr[top] = 1;
        printHuffmanCodes(root->right, arr, top + 1);
    }

    if (!(root->left) && !(root->right)) {
        printf("%c: ", root->data);
        for (int i = 0; i < top; ++i)
            printf("%d", arr[i]);
        printf("\n");
    }
}

3.3 主函数

int main() {
    char data[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
    int freq[] = { 5, 9, 12, 13, 16, 45 };

    int size = sizeof(data) / sizeof(data[0]);
    HuffmanNode* root = NULL;

    MinHeap* minHeap = createMinHeap(size);

    for (int i = 0; i < size; ++i)
        minHeap->array[i] = createHuffmanNode(data[i], freq[i]);

    minHeap->size = size;
    buildMinHeap(minHeap);

    while (!isSizeOne(minHeap)) {
        HuffmanNode* left = extractMin(minHeap);
        HuffmanNode* right = extractMin(minHeap);

        HuffmanNode* sum = createHuffmanNode('$', left->freq + right->freq);
        sum->left = left;
        sum->right = right;

        insertMinHeap(minHeap, sum);
    }

    root = extractMin(minHeap);

    int arr[MAX_TREE_HT], top = 0;
    printHuffmanCodes(root, arr, top);

    return 0;
}

4. 示例运行

输出：

f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111

5. 注意事项

文件读取和写入：在实际应用中，需要读取文件内容，统计字符频率，并将压缩后的数据写入文件。
编码表生成：根据霍夫曼树生成编码表，用于压缩和解压。
压缩和解压：使用编码表将文件内容转换为压缩后的二进制数据，并将压缩后的数据写入文件。解压时，使用霍夫曼树将压缩后的数据还原为原始文件。
性能优化：在实际应用中，可以进一步优化霍夫曼编码的实现，提高压缩和解压的效率。

6. 总结

通过使用霍夫曼编码，可以在C语言中实现简单的文件压缩和解压。霍夫曼编码是一种高效的压缩算法，能够显著减少文件的大小。在实际开发中，可以根据具体需求选择合适的压缩算法，并优化实现以提高性能。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)