C语言中的文件压缩和解压缩技术是什么？

2023-12-15 11:41:42

文件压缩和解压缩是计算机领域中常用的技术，通过压缩可以减小文件的体积，从而更高效地存储和传输数据。在C语言中，有多种文件压缩和解压缩的技术和算法可供选择。本文将介绍一些常见的压缩和解压缩技术，以及在C语言中如何实现它们。

1. 文件压缩的原理

文件压缩的基本原理是通过一定的算法和技术，将文件中的冗余信息去除或者用更紧凑的方式表示，从而减小文件的大小。压缩算法可以分为两大类：

1.1 无损压缩

无损压缩是指通过压缩算法压缩文件，然后再解压缩还原为原始文件时，不会损失任何信息。常见的无损压缩算法有：

Run-Length Encoding (RLE)：基于相同连续数据的重复次数进行编码。例如，"AAAABBBCCDAA" 可以表示为 "4A3B2C1D2A"。
Huffman编码：根据字符出现的频率来构建可变长度的编码，使得频率高的字符用较短的编码表示，频率低的字符用较长的编码表示。
Lempel-Ziv算法系列：包括LZ77、LZ78和LZW等，通过字典压缩方法，将文件中的重复序列用较短的标记表示。

1.2 有损压缩

有损压缩是指在压缩文件时，可能会损失一些信息，但在实际应用中，损失的信息对整体的影响不大。常见的有损压缩算法有：

JPEG（Joint Photographic Experts Group）：主要用于压缩图像文件，采用离散余弦变换（DCT）进行频域压缩。
MP3（MPEG-1 Audio Layer III）：用于压缩音频文件，采用梅尔频率倒谱系数（MFCC）等方法进行频域压缩。

视频压缩算法：包括H.264、HEVC等，主要用于压缩视频文件，采用运动估计、变换编码等技术。

2. C语言中的文件压缩

在C语言中，实现文件压缩通常需要借助相关的库或者手动实现压缩算法。下面以Huffman编码为例，演示在C语言中如何实现文件压缩。

2.1 Huffman编码压缩

Huffman编码的基本步骤包括构建哈夫曼树和生成编码表。以下是一个简单的C语言程序，用于对文件进行Huffman编码压缩：

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

#define MAX_TREE_NODES 256

// 哈夫曼树节点
struct HuffmanNode {
    char data;
    int frequency;
    struct HuffmanNode *left, *right;
};

// 优先队列节点
struct PriorityQueueNode {
    struct HuffmanNode *data;
    struct PriorityQueueNode *next;
};

// 优先队列
struct PriorityQueue {
    struct PriorityQueueNode *front;
};

// 创建哈夫曼树节点
struct HuffmanNode* createHuffmanNode(char data, int frequency) {
    struct HuffmanNode* node = (struct HuffmanNode*)malloc(sizeof(struct HuffmanNode));
    node->data = data;
    node->frequency = frequency;
    node->left = node->right = NULL;
    return node;
}

// 创建优先队列节点
struct PriorityQueueNode* createPriorityQueueNode(struct HuffmanNode* data) {
    struct PriorityQueueNode* node = (struct PriorityQueueNode*)malloc(sizeof(struct PriorityQueueNode));
    node->data = data;
    node->next = NULL;
    return node;
}

// 创建空的优先队列
struct PriorityQueue* createPriorityQueue() {
    struct PriorityQueue* queue = (struct PriorityQueue*)malloc(sizeof(struct PriorityQueue));
    queue->front = NULL;
    return queue;
}

// 插入节点到优先队列
void insert(struct PriorityQueue* queue, struct HuffmanNode* data) {
    struct PriorityQueueNode* newNode = createPriorityQueueNode(data);
    if (queue->front == NULL || data->frequency < queue->front->data->frequency) {
        newNode->next = queue->front;
        queue->front = newNode;
    } else {
        struct PriorityQueueNode* temp = queue->front;
        while (temp->next != NULL && temp->next->data->frequency < data->frequency) {
            temp = temp->next;
        }
        newNode->next = temp->next;
        temp->next = newNode;
    }
}

// 构建哈夫曼树
struct HuffmanNode* buildHuffmanTree(char data[], int frequency[], int size) {
    struct PriorityQueue* queue = createPriorityQueue();

    for (int i = 0; i < size; i++) {
        insert(queue, createHuffmanNode(data[i], frequency[i]));
    }

    while (queue->front->next != NULL) {
        struct HuffmanNode* left = queue->front->data;
        dequeue(queue);
        struct HuffmanNode* right = queue->front->data;
        dequeue(queue);

        struct HuffmanNode* merged = createHuffmanNode('$', left->frequency + right->frequency);
        merged->left = left;
        merged->right = right;

        insert(queue, merged);
    }

    struct HuffmanNode* root = queue->front->data;
    dequeue(queue);
    free(queue);

    return root;
}

// 生成Huffman编码表
void generateHuffmanCodes(struct HuffmanNode* root, int arr[], int top, int codeTable[][MAX_TREE_NODES]) {
    if (root->left) {
        arr[top] = 0;
        generateHuffmanCodes(root->left, arr, top + 1, codeTable);
    }

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

    if (!root->left && !root->right) {
        for (int i = 0; i < top; i++) {
            codeTable[root->data][i] = arr[i];
        }
        codeTable[root->data][top] = -1; // 结束标记
    }
}

// 从优先队列中出队一个节点
void dequeue(struct PriorityQueue* queue) {
    if (queue->front == NULL) {
        return;
    }
    struct PriorityQueueNode* temp = queue->front;
    queue->front = queue->front->next;
    free(temp);
}

// 压缩文件
void compressFile(char inputFile[], char outputFile[]) {
    FILE *input, *output;
    input = fopen(inputFile, "rb");
    output = fopen(outputFile, "wb");

    if (input == NULL || output == NULL) {
        printf("File open error\n");
        return;
    }

    char data[MAX_TREE_NODES];
    int frequency[MAX_TREE_NODES] = {0};

    // 统计字符频率
    int ch;
    while ((ch = fgetc(input)) != EOF) {
        data[ch]++;
        frequency[ch]++;
    }

    struct HuffmanNode* root = buildHuffmanTree(data, frequency, MAX_TREE_NODES);
    int arr[MAX_TREE_NODES];
    int codeTable[MAX_TREE_NODES][MAX_TREE_NODES];

    generateHuffmanCodes(root, arr, 0, codeTable);

    // 写入压缩后的数据
    fseek(input, 0, SEEK_SET);
    while ((ch = fgetc(input)) != EOF) {
        int i = 0;
        while (codeTable[ch][i] != -1) {
            fprintf(output, "%d", codeTable[ch][i]);
            i++;
        }
    }

    fclose(input);
    fclose(output);
}

int main() {
    compressFile("input.txt", "compressed.bin");
    return 0;
}

上述程序中，首先统计输入文件中每个字符的频率，然后构建Huffman树，生成Huffman编码表，最后使用编码表将输入文件中的数据进行压缩，并将结果写入输出文件。

2.2 文件解压缩

文件解压缩的过程与压缩相反，需要根据压缩时生成的编码表将压缩文件还原为原始文件。以下是一个简单的C语言程序，用于对Huffman编码压缩后的文件进行解压缩：

#include <stdio.h>

#define MAX_TREE_NODES 256

// 哈夫曼树节点
struct HuffmanNode {
    char data;
    struct HuffmanNode *left, *right;
};

// 从优先队列中出队一个节点
void dequeue(struct PriorityQueue* queue);

// 优先队列节点
struct PriorityQueueNode {
    struct HuffmanNode *data;
    struct PriorityQueueNode *next;
};

// 优先队列
struct PriorityQueue {
    struct PriorityQueueNode *front;
};

// 创建哈夫曼树节点
struct HuffmanNode* createHuffmanNode(char data) {
    struct HuffmanNode* node = (struct HuffmanNode*)malloc(sizeof(struct HuffmanNode));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// 创建优先队列节点
struct PriorityQueueNode* createPriorityQueueNode(struct HuffmanNode* data) {
    struct PriorityQueueNode* node = (struct PriorityQueueNode*)malloc(sizeof(struct PriorityQueueNode));
    node->data = data;
    node->next = NULL;
    return node;
}

// 创建空的优先队列
struct PriorityQueue* createPriorityQueue() {
    struct PriorityQueue* queue = (struct PriorityQueue*)malloc(sizeof(struct PriorityQueue));
    queue->front = NULL;
    return queue;
}

// 插入节点到优先队列
void insert(struct PriorityQueue* queue, struct HuffmanNode* data) {
    struct PriorityQueueNode* newNode = createPriorityQueueNode(data);
    if (queue->front == NULL) {
        newNode->next = queue->front;
        queue->front = newNode;
    } else {
        struct PriorityQueueNode* temp = queue->front;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// 从优先队列中出队一个节点
void dequeue(struct PriorityQueue* queue) {
    if (queue->front == NULL) {
        return;
    }
    struct PriorityQueueNode* temp = queue->front;
    queue->front = queue->front->next;
    free(temp);
}

// 构建哈夫曼树
struct HuffmanNode* buildHuffmanTreeFromFile(FILE* input) {
    int ch;
    struct PriorityQueue* queue = createPriorityQueue();

    while ((ch = fgetc(input)) != EOF) {
        struct HuffmanNode* node = createHuffmanNode(ch);
        insert(queue, node);
    }

    while (queue->front->next != NULL) {
        struct HuffmanNode* left = queue->front->data;
        dequeue(queue);
        struct HuffmanNode* right = queue->front->data;
        dequeue(queue);

        struct HuffmanNode* merged = createHuffmanNode('$');
        merged->left = left;
        merged->right = right;

        insert(queue, merged);
    }

    struct HuffmanNode* root = queue->front->data;
    dequeue(queue);
    free(queue);

    return root;
}

// 解压缩文件
void decompressFile(char inputFile[], char outputFile[]) {
    FILE *input, *output;
    input = fopen(inputFile, "rb");
    output = fopen(outputFile, "w");

    if (input == NULL || output == NULL) {
        printf("File open error\n");
        return;
    }

    struct HuffmanNode* root = buildHuffmanTreeFromFile(input);
    struct HuffmanNode* current = root;

    int bit;
    while ((bit = fgetc(input)) != EOF) {
        if (bit == '0') {
            current = current->left;
        } else if (bit == '1') {
            current = current->right;
        }

        if (current->left == NULL && current->right == NULL) {
            fprintf(output, "%c", current->data);
            current = root;
        }
    }

    fclose(input);
    fclose(output);
}

int main() {
    decompressFile("compressed.bin", "output.txt");
    return 0;
}

在这个解压缩程序中，首先从压缩文件中读取位（'0'或'1'），根据Huffman树的结构逐步还原原始文件中的字符，并将结果写入输出文件。

文章来源:https://blog.csdn.net/weixin_68551689/article/details/135011439
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！