哈夫曼编码文件压缩与解压

好的，我可以为您讲解哈夫曼编码文件压缩与解压。

哈夫曼编码是一种可变长度编码方式，它通过统计字符出现频率来构建一个最优二叉树结构，将出现频率高的字符用较短的编码表示，出现频率低的字符用较长的编码表示，从而达到压缩文件的目的。

文件压缩的过程就是将文件中的字符通过哈夫曼编码转换为对应的二进制码，从而减少文件的大小。而解压过程则是将二进制码转化为哈夫曼编码所代表的字符，还原原始文件。

在实际应用中，哈夫曼编码常被用于压缩文本文件、音频文件、图片文件等等。通过哈夫曼编码压缩文件，可以节省存储空间并提高传输效率。

需要注意的是，压缩率取决于原始文件的特性，如果文件中的字符种类较少，压缩效果就不会很明显。同时，压缩和解压的过程也会消耗一定的时间和计算资源。

相关问题

用c语言编写哈夫曼编码文件压缩与解压

好的，我可以为您提供哈夫曼编码文件压缩与解压的C语言实现的代码，以下是压缩部分的示例代码：

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

// 哈夫曼树节点结构体定义
typedef struct HuffmanNode {
    unsigned char data; // 字符数据
    int freq; // 字符出现频率
    struct HuffmanNode *left, *right; // 左右子节点指针
} HuffmanNode;

// 哈夫曼编码结构体定义
typedef struct HuffmanCode {
    unsigned char data; // 字符数据
    char *code; // 字符对应编码
} HuffmanCode;

// 哈夫曼树节点优先队列结构体定义
typedef struct PriorityQueue {
    int size; // 队列大小
    int capacity; // 队列容量
    HuffmanNode **nodes; // 指向哈夫曼树节点的指针数组
} PriorityQueue;

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

// 创建新的哈夫曼编码结构体
HuffmanCode newHuffmanCode(unsigned char data, char *code) {
    HuffmanCode hc;
    hc.data = data;
    hc.code = code;
    return hc;
}

// 创建新的哈夫曼树节点优先队列
PriorityQueue *newPriorityQueue(int capacity) {
    PriorityQueue *pq = (PriorityQueue *)malloc(sizeof(PriorityQueue));
    pq->size = 0;
    pq->capacity = capacity;
    pq->nodes = (HuffmanNode **)malloc(capacity * sizeof(HuffmanNode *));
    return pq;
}

// 释放哈夫曼编码结构体内存
void freeHuffmanCode(HuffmanCode hc) {
    free(hc.code);
}

// 释放哈夫曼树节点内存
void freeHuffmanNode(HuffmanNode *node) {
    if (node != NULL) {
        freeHuffmanNode(node->left);
        freeHuffmanNode(node->right);
        free(node);
    }
}

// 释放哈夫曼树节点优先队列内存
void freePriorityQueue(PriorityQueue *pq) {
    for (int i = 0; i < pq->size; i++) {
        freeHuffmanNode(pq->nodes[i]);
    }
    free(pq->nodes);
    free(pq);
}

// 判断优先队列是否为空
int isPriorityQueueEmpty(PriorityQueue *pq) {
    return pq->size == 0;
}

// 判断优先队列是否已满
int isPriorityQueueFull(PriorityQueue *pq) {
    return pq->size == pq->capacity;
}

// 向优先队列中插入哈夫曼树节点
void insertIntoPriorityQueue(PriorityQueue *pq, HuffmanNode *node) {
    int i = pq->size;
    while (i > 0 && pq->nodes[(i - 1) / 2]->freq > node->freq) {
        pq->nodes[i] = pq->nodes[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    pq->nodes[i] = node;
    pq->size++;
}

// 从优先队列中删除哈夫曼树节点
HuffmanNode *removeFromPriorityQueue(PriorityQueue *pq) {
    HuffmanNode *minNode = pq->nodes[0];
    pq->size--;
    pq->nodes[0] = pq->nodes[pq->size];
    int i = 0;
    while (i * 2 + 1 < pq->size) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int min = left;
        if (right < pq->size && pq->nodes[right]->freq < pq->nodes[left]->freq) {
            min = right;
        }
        if (pq->nodes[i]->freq > pq->nodes[min]->freq) {
            HuffmanNode *temp = pq->nodes[i];
            pq->nodes[i] = pq->nodes[min];
            pq->nodes[min] = temp;
            i = min;
        } else {
            break;
        }
    }
    return minNode;
}

// 构建哈夫曼树
HuffmanNode *buildHuffmanTree(unsigned char *data, int *freq, int size) {
    PriorityQueue *pq = newPriorityQueue(size);
    for (int i = 0; i < size; i++) {
        HuffmanNode *node = newHuffmanNode(data[i], freq[i]);
        insertIntoPriorityQueue(pq, node);
    }
    while (pq->size > 1) {
        HuffmanNode *left = removeFromPriorityQueue(pq);
        HuffmanNode *right = removeFromPriorityQueue(pq);
        HuffmanNode *parent = newHuffmanNode(0, left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        insertIntoPriorityQueue(pq, parent);
    }
    HuffmanNode *root = removeFromPriorityQueue(pq);
    freePriorityQueue(pq);
    return root;
}

// 递归生成哈夫曼编码
void generateHuffmanCode(HuffmanNode *node, char *code, int depth, HuffmanCode *hcTable) {
    if (node->left == NULL && node->right == NULL) {
        code[depth] = '\0';
        hcTable[node->data] = newHuffmanCode(node->data, strdup(code));
        return;
    }
    code[depth] = '0';
    generateHuffmanCode(node->left, code, depth + 1, hcTable);
    code[depth] = '1';
    generateHuffmanCode(node->right, code, depth + 1, hcTable);
}

// 哈夫曼编码文件压缩函数
void compressFile(const char *inputFileName, const char *outputFileName) {
    // 打开输入文件
    FILE *inputFile = fopen(inputFileName, "rb");
    if (inputFile == NULL) {
        fprintf(stderr, "Error: Cannot open file '%s'\n", inputFileName);
        exit(EXIT_FAILURE);
    }

    // 统计文件中每个字符出现的频率
    int freq[UCHAR_MAX + 1] = { 0 };
    unsigned char buffer[1024];
    int bytesRead;
    while ((bytesRead = fread(buffer, 1, sizeof(buffer), inputFile)) > 0) {
        for (int i = 0; i < bytesRead; i++) {
            freq[buffer[i]]++;
        }
    }

    // 构建哈夫曼树
    int dataSize = 0;
    for (int i = 0; i <= UCHAR_MAX; i++) {
        if (freq[i] > 0) {
            dataSize++;
        }
    }
    unsigned char *data = (unsigned char *)malloc(dataSize * sizeof(unsigned char));
    int *freqCopy = (int *)malloc(dataSize * sizeof(int));
    int j = 0;
    for (int i = 0; i <= UCHAR_MAX; i++) {
        if (freq[i] > 0) {
            data[j] = (unsigned char)i;
            freqCopy[j] = freq[i];
            j++;
        }
    }
    HuffmanNode *root = buildHuffmanTree(data, freqCopy, dataSize);
    free(data);
    free(freqCopy);

    // 生成哈夫曼编码
    HuffmanCode hcTable[UCHAR_MAX + 1];
    char code[CHAR_BIT + 1];
    generateHuffmanCode(root, code, 0, hcTable);

    // 重置文件指针
    fseek(inputFile, 0L, SEEK_SET);

    // 打开输出文件
    FILE *outputFile = fopen(outputFileName, "wb");
    if (outputFile == NULL) {
        fprintf(stderr, "Error: Cannot open file '%s'\n", outputFileName);
        exit(EXIT_FAILURE);
    }

    // 写入哈夫曼树节点数和每个字符出现的频率
    int nodeCount = dataSize * 2 - 1;
    fwrite(&nodeCount, sizeof(int), 1, outputFile);
    for (int i = 0; i <= UCHAR_MAX; i++) {
        if (hcTable[i].code != NULL) {
            fwrite(&hcTable[i].data, sizeof(unsigned char), 1, outputFile);
            fwrite(&freq[i], sizeof(int), 1, outputFile);
        }
    }

    // 逐个字符将其哈夫曼编码写入输出文件
    char bitBuffer = 0;
    int bitCount = 0;
    while ((bytesRead = fread(buffer, 1, sizeof(buffer), inputFile)) > 0) {
        for (int i = 0; i < bytesRead; i++) {
            for (int j = 0; j < strlen(hcTable[buffer[i]].code); j++) {
                if (hcTable[buffer[i]].code[j] == '1') {
                    bitBuffer |= 1 << bitCount;
                }
                bitCount++;
                if (bitCount == CHAR_BIT) {
                    fwrite(&bitBuffer, sizeof(char), 1, outputFile);
                    bitBuffer = 0;
                    bitCount = 0;
                }
            }
        }
    }
    if (bitCount > 0) {
        fwrite(&bitBuffer, sizeof(char), 1, outputFile);
    }

    // 释放内存并关闭文件
    fclose(inputFile);
    fclose(outputFile);
    freeHuffmanNode(root);
    for (int i = 0; i <= UCHAR_MAX; i++) {
        freeHuffmanCode(hcTable[i]);
    }
}

以下是解压部分的示例代码：

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

// 哈夫曼树节点结构体定义
typedef struct HuffmanNode {
    unsigned char data; // 字符数据
    int freq; // 字符出现频率
    struct HuffmanNode *left, *right; // 左右子节点指针
} HuffmanNode;

// 哈夫曼编码结构体定义
typedef struct HuffmanCode {
    unsigned char data; // 字符数据
    char *code; // 字符对应编码
} HuffmanCode;

// 读取哈夫曼树节点数和每个字符出现的频率
void readNodeCountAndFreq(FILE *inputFile, int *nodeCount, int *freq) {
    fread(nodeCount, sizeof(int), 1, inputFile);
    for (int i = 0; i <= UCHAR_MAX; i++) {
        freq[i] = 0;
    }
    unsigned char data;
    int f;
    for (int i = 0; i < *nodeCount; i++) {
        fread(&data, sizeof(unsigned char), 1, inputFile);
        fread(&f, sizeof(int), 1, inputFile);
        freq[data] = f;
    }
}

// 重建哈夫曼树
HuffmanNode *rebuildHuffmanTree(FILE *inputFile, int *nodeCount) {
    if (*nodeCount == 1) {
        unsigned char data;
        fread(&data, sizeof(unsigned char), 1, inputFile);
        return newHuffmanNode(data, 0);
    }
    HuffmanNode *nodes[*nodeCount];
    for (int i = 0; i < *nodeCount; i++) {
        unsigned char data;
        fread(&data, sizeof(unsigned char), 1, inputFile);
        nodes[i] = newHuffmanNode(data, 0);
    }
    for (int i = 0; i < *nodeCount - 1; i++) {
        int leftIndex, rightIndex;
        fread(&leftIndex, sizeof(int), 1, inputFile);
        fread(&rightIndex, sizeof(int), 1, inputFile);
        nodes[i]->left = nodes[leftIndex];
        nodes[i]->right = nodes[rightIndex];
    }
    return nodes[*nodeCount - 1];
}

// 从输入文件中读取一个比特
int readBit(FILE *inputFile, char *bitBuffer, int *bitCount) {
    if (*bitCount == 0) {
        fread(bitBuffer, sizeof(char), 1, inputFile);
        *bitCount = CHAR_BIT;
    }
    int bit = (*bitBuffer >> (*bitCount - 1)) & 1;
    (*bitCount)--;
    return bit;
}

// 哈夫曼编码文件解压函数
void decompressFile(const char *inputFileName, const char *outputFileName) {
    // 打开输入文件
    FILE *inputFile = fopen(inputFileName, "rb");
    if (inputFile == NULL) {
        fprintf(stderr, "Error: Cannot open file '%s'\n", inputFileName);
        exit(EXIT_FAILURE);
    }

    // 读取哈夫曼树节点数和每个字符出现的频率
    int nodeCount;
    int freq[UCHAR_MAX + 1];
    readNodeCountAndFreq(inputFile, &nodeCount, freq);

    // 重建哈夫曼树
    HuffmanNode *root = rebuildHuffmanTree(inputFile, &nodeCount);

    // 重置文件指针
    fseek(inputFile, 0L, SEEK_SET);
    fread(&nodeCount, sizeof(int), 1, inputFile);
    fseek(inputFile, nodeCount * (sizeof(unsigned char) + sizeof(int)) + sizeof(int), SEEK_CUR);

    // 打开输出文件
    FILE *outputFile = fopen(outputFileName, "wb");
    if (outputFile == NULL) {
        fprintf(stderr, "Error: Cannot open file '%s'\n", outputFileName);
        exit(EXIT_FAILURE);
    }

    // 解压文件
    HuffmanNode *node = root;
    unsigned char buffer[1024];
    char bitBuffer = 0;
    int bitCount = 0;
    int bytesRead;
    while ((bytesRead = fread(buffer, 1, sizeof(buffer), inputFile)) > 0) {
        for (int i = 0; i < bytesRead; i++) {
            int bit = readBit(inputFile, &bitBuffer, &bitCount);
            if (bit == 0) {
                node = node->left;
            } else {
                node = node->right;
            }
            if (node->left == NULL && node->right == NULL) {
                fwrite(&node->data, sizeof(unsigned char), 1, outputFile);
                node = root;
            }
        }
    }

    // 释放内存并关闭文件
    fclose(inputFile);
    fclose(outputFile);
    freeHuffmanNode(root);
}

以上是哈夫曼编码文件压缩与解压的C语言实现示例代码，您可以根据需要进行修改和优化。

哈夫曼编码实现文件压缩解压

哈夫曼编码是一种无损数据压缩算法，可以用于文件压缩和解压缩。下面我将介绍如何使用Python实现哈夫曼编码的文件压缩和解压缩。

1. 哈夫曼编码实现文件压缩

首先，我们需要构建哈夫曼编码树。可以使用优先队列来实现。具体步骤如下：

- 遍历文件，统计每个字符出现的频率。
- 将每个字符和它的频率作为叶子节点插入到优先队列中。
- 从优先队列中取出两个频率最小的节点，将它们作为左右子节点构建一个新节点，并将新节点插入到优先队列中。
- 重复上述步骤，直到队列中只剩下一个节点，这个节点就是哈夫曼编码树的根节点。

接着，我们可以使用深度优先遍历来生成每个字符的哈夫曼编码。具体步骤如下：

- 从根节点开始，如果当前节点是叶子节点，则输出它的字符和哈夫曼编码。
- 如果当前节点有左子节点，则在哈夫曼编码的末尾添加0，并进入左子节点。
- 如果当前节点有右子节点，则在哈夫曼编码的末尾添加1，并进入右子节点。

最后，我们可以使用生成的哈夫曼编码来压缩文件。具体步骤如下：

- 遍历文件，将每个字符替换为它的哈夫曼编码。
- 将所有哈夫曼编码连接起来，每8个位表示一个字节，将其写入压缩文件中。
- 将哈夫曼编码表写入压缩文件中。

下面是实现代码：

import heapq
import os

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None
    
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(freq_dict):
    heap = []
    for char, freq in freq_dict.items():
        heapq.heappush(heap, HuffmanNode(char, freq))
    
    while len(heap) > 1:
        node1 = heapq.heappop(heap)
        node2 = heapq.heappop(heap)
        new_node = HuffmanNode(None, node1.freq + node2.freq)
        new_node.left = node1
        new_node.right = node2
        heapq.heappush(heap, new_node)
    
    return heap[0]

def generate_huffman_codes(node, code, code_dict):
    if node.char is not None:
        code_dict[node.char] = code
        return
    
    generate_huffman_codes(node.left, code + '0', code_dict)
    generate_huffman_codes(node.right, code + '1', code_dict)

def compress_file(input_file, output_file):
    # Step 1: Build frequency dictionary
    freq_dict = {}
    with open(input_file, 'rb') as f:
        byte = f.read(1)
        while byte:
            if byte in freq_dict:
                freq_dict[byte] += 1
            else:
                freq_dict[byte] = 1
            byte = f.read(1)
    
    # Step 2: Build huffman tree
    root = build_huffman_tree(freq_dict)
    
    # Step 3: Generate huffman codes
    code_dict = {}
    generate_huffman_codes(root, '', code_dict)
    
    # Step 4: Compress input file
    with open(input_file, 'rb') as f_in, open(output_file, 'wb') as f_out:
        # Write huffman code table
        for char, code in code_dict.items():
            f_out.write(bytes([len(code)]))
            f_out.write(bytes([char]))
            f_out.write(code.encode('utf-8'))
        
        # Write compressed data
        byte = f_in.read(1)
        bits = ''
        while byte:
            bits += code_dict[byte]
            while len(bits) >= 8:
                byte_out = int(bits[:8], 2)
                f_out.write(bytes([byte_out]))
                bits = bits[8:]
            byte = f_in.read(1)
        if len(bits) > 0:
            byte_out = int(bits + '0' * (8 - len(bits)), 2)
            f_out.write(bytes([byte_out]))

2. 哈夫曼编码实现文件解压缩

文件解压缩的过程与文件压缩的过程相反。具体步骤如下：

- 读取哈夫曼编码表，生成字符与哈夫曼编码的对应关系。
- 读取压缩文件，将每个字节转换为8位二进制数。
- 遍历二进制数，从哈夫曼编码表中查找对应的字符。
- 将解压后的字符写入解压文件中。

下面是实现代码：

def decompress_file(input_file, output_file):
    # Step 1: Read huffman code table
    code_dict = {}
    with open(input_file, 'rb') as f:
        byte = f.read(1)
        while byte:
            code_len = int.from_bytes(byte, byteorder='big')
            char = f.read(1)
            code = f.read(code_len).decode('utf-8')
            code_dict[code] = char
            byte = f.read(1)
    
    # Step 2: Decompress input file
    with open(input_file, 'rb') as f_in, open(output_file, 'wb') as f_out:
        # Skip huffman code table
        f_in.seek(sum([2 + len(code) for code in code_dict.keys()]))
        
        # Read compressed data
        byte = f_in.read(1)
        bits = ''
        while byte:
            bits += bin(int.from_bytes(byte, byteorder='big'))[2:].rjust(8, '0')
            byte = f_in.read(1)
        
        # Write decompressed data
        while len(bits) > 0:
            for code, char in code_dict.items():
                if bits.startswith(code):
                    f_out.write(char)
                    bits = bits[len(code):]
                    break

综上所述，我们可以使用以上代码实现哈夫曼编码的文件压缩和解压缩。