哈夫曼编码压缩比计算

哈夫曼编码的压缩比计算公式为：压缩比 = 原始数据位数 / 压缩后数据位数。其中，原始数据位数指的是未经过压缩的数据所占用的位数，压缩后数据位数指的是经过哈夫曼编码压缩后的数据所占用的位数。由于哈夫曼编码是一种可变字长编码，所以压缩后数据位数会根据不同的数据集而有所不同。一般来说，哈夫曼编码的压缩比比较高，可以达到30%~50%左右。

相关问题

c语言实现哈夫曼编码压缩文件并输出压缩比

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

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

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

// 创建哈夫曼树
HuffmanNode* createHuffmanTree(unsigned char *data, int *freq, int size) {
    // 创建叶子节点数组
    HuffmanNode **nodes = (HuffmanNode**)malloc(size * sizeof(HuffmanNode*));
    for (int i = 0; i < size; i++) {
        nodes[i] = (HuffmanNode*)malloc(sizeof(HuffmanNode));
        nodes[i]->data = data[i];
        nodes[i]->freq = freq[i];
        nodes[i]->left = NULL;
        nodes[i]->right = NULL;
    }

    // 构建哈夫曼树
    while (size > 1) {
        // 找到频率最小的两个节点
        int min1 = 0, min2 = 1;
        if (nodes[min1]->freq > nodes[min2]->freq) {
            int temp = min1;
            min1 = min2;
            min2 = temp;
        }
        for (int i = 2; i < size; i++) {
            if (nodes[i]->freq < nodes[min1]->freq) {
                min2 = min1;
                min1 = i;
            } else if (nodes[i]->freq < nodes[min2]->freq) {
                min2 = i;
            }
        }

        // 创建新节点，将两个最小频率的节点作为子节点
        HuffmanNode *newNode = (HuffmanNode*)malloc(sizeof(HuffmanNode));
        newNode->data = 0;
        newNode->freq = nodes[min1]->freq + nodes[min2]->freq;
        newNode->left = nodes[min1];
        newNode->right = nodes[min2];

        // 删除已经合并的节点
        if (min1 < min2) {
            nodes[min1] = newNode;
            nodes[min2] = nodes[size - 1];
        } else {
            nodes[min2] = newNode;
            nodes[min1] = nodes[size - 1];
        }
        size--;
    }

    // 返回根节点
    return nodes[0];
}

// 生成哈夫曼编码
void generateHuffmanCode(HuffmanNode *root, char *code, int depth, HuffmanCode *codes) {
    if (root->left == NULL && root->right == NULL) {
        // 叶子节点，保存编码
        codes[root->data].data = root->data;
        codes[root->data].code = (char*)malloc((depth + 1) * sizeof(char));
        strcpy(codes[root->data].code, code);
        codes[root->data].code[depth] = '\0';
    } else {
        // 非叶子节点，递归生成编码
        code[depth] = '0';
        generateHuffmanCode(root->left, code, depth + 1, codes);
        code[depth] = '1';
        generateHuffmanCode(root->right, code, depth + 1, codes);
    }
}

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

    // 写入编码表大小
    int codeSize = 0;
    for (int i = 0; i < 256; i++) {
        if (codes[i].code != NULL) {
            codeSize++;
        }
    }
    fwrite(&codeSize, sizeof(int), 1, output);

    // 写入编码表
    for (int i = 0; i < 256; i++) {
        if (codes[i].code != NULL) {
            fwrite(&codes[i].data, sizeof(unsigned char), 1, output);
            int codeLength = strlen(codes[i].code);
            fwrite(&codeLength, sizeof(int), 1, output);
            fwrite(codes[i].code, sizeof(char), codeLength, output);
        }
    }

    // 压缩文件内容
    unsigned char buffer = 0;
    int bitCount = 0;
    unsigned char ch;
    while (fread(&ch, sizeof(unsigned char), 1, input) > 0) {
        int codeLength = strlen(codes[ch].code);
        for (int i = 0; i < codeLength; i++) {
            if (codes[ch].code[i] == '1') {
                buffer |= (1 << (7 - bitCount));
            }
            bitCount++;
            if (bitCount == 8) {
                fwrite(&buffer, sizeof(unsigned char), 1, output);
                buffer = 0;
                bitCount = 0;
            }
        }
    }

    // 写入最后一个字节
    if (bitCount > 0) {
        fwrite(&buffer, sizeof(unsigned char), 1, output);
    }

    fclose(input);
    fclose(output);
}

// 计算文件大小
long long getFileSize(const char *filename) {
    FILE *file = fopen(filename, "rb");
    fseek(file, 0, SEEK_END);
    long long size = ftell(file);
    fclose(file);
    return size;
}

int main() {
    // 读取文件内容
    const char *filename = "input.txt";
    FILE *file = fopen(filename, "rb");
    fseek(file, 0, SEEK_END);
    int fileSize = ftell(file);
    fseek(file, 0, SEEK_SET);
    unsigned char *data = (unsigned char*)malloc(fileSize * sizeof(unsigned char));
    fread(data, sizeof(unsigned char), fileSize, file);
    fclose(file);

    // 统计字符频率
    int freq[256] = {0};
    for (int i = 0; i < fileSize; i++) {
        freq[data[i]]++;
    }

    // 创建哈夫曼树
    HuffmanNode *root = createHuffmanTree(data, freq, 256);

    // 生成哈夫曼编码
    char code[256];
    HuffmanCode codes[256];
    memset(code, 0, sizeof(code));
    generateHuffmanCode(root, code, 0, codes);

    // 压缩文件
    compressFile("input.txt", "output

写一个程序，为给定的英文文本构造一套哈夫曼编码，并计算压缩比

为了编写一个程序为给定的英文文本构造哈夫曼编码并计算压缩比，我们可以遵循以下步骤：

1. **数据预处理**：
- 收集文本并统计每个字符的频率，将字符及其对应的频率存储在一个字典或映射中。

import collections

def preprocess_text(text):
    char_freq = collections.Counter(text)
    return char_freq

2. **构建哈夫曼树**：
- 使用字符频率创建一个哈夫曼树生成器，如HuffmanNode类，包含合并节点和优先级函数。
- 通过递归合并最小频次的节点直到只剩下一个根节点（即空节点）。

class HuffmanNode:
    def __init__(self, freq=None, char=None, left=None, right=None):
        self.freq = freq
        self.char = char
        self.left = left
        self.right = right
    
    # 合并两个节点
    def merge(self, other):
        if self.freq < other.freq:
            return HuffmanNode(other, other.char, self, other.left)
        else:
            return HuffmanNode(self, self.char, other.left, other)

# 构建哈夫曼树
def build_huffman_tree(freqs):
    nodes = [HuffmanNode(freq=freq, char=char) for char, freq in freqs.items()]
    while len(nodes) > 1:
        nodes.sort(key=lambda x: x.freq)
        new_node = nodes.pop(0).merge(nodes.pop(0))
        nodes.append(new_node)
    return nodes[0]

3. **编码过程**：
- 根据哈夫曼树生成编码规则，从左到右遍历，遇到分支走左边记为0，右边记为1。

def generate_codes(root, code=""):
    if not root.left and not root.right:
        return {root.char: code}
    left_code = generate_codes(root.left, code + "0")
    right_code = generate_codes(root.right, code + "1")
    return {**left_code, **right_code}

huffman_tree = build_huffman_tree(preprocess_text(text))
huffman_codes = generate_codes(huffman_tree)

4. **计算压缩比**：
- 将原始文本替换为哈夫曼编码后的形式。
- 计算压缩前后的字节数，压缩比等于压缩后除以压缩前的字节数。

def compress(text, huffman_codes):
    compressed_text = ""
    for char in text:
        compressed_text += huffman_codes[char]
    return compressed_text

compressed_data = compress(text, huffman_codes)
original_size = len(text.encode())
compressed_size = len(compressed_data)

compression_ratio = original_size / compressed_size