• 日期: 2025-03-12
  • 标签: 常规
#include <iostream>
#include <cstring>
#include <string>
#include <fstream>
#include <vector>
#include <bitset>
#include <Windows.h>

using namespace std;

// 定义哈夫曼树节点
typedef struct {
    int weight; // 权重
    int parent; // 父节点
    int l_child; // 左子节点
    int r_child; // 右子节点
    char data; // 存储的字符数据
} HTNode, * HuffmanTree;
typedef char** HuffmanCode;

//字符种类数
static int N;

//自定义函数声明
void frequencyRecord(HuffmanTree& HT); // 统计各字符出现频率
void select(HuffmanTree HT, int num, int& child1, int& child2); // 选择最小的两个叶子节点
void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC); // 对各字符进行哈夫曼编码
void zip(HuffmanTree& HT, HuffmanCode& HC, vector<string>& code); // 对文件进行哈夫曼编码压缩
void unzip(HuffmanTree& HT, HuffmanCode& HC, vector<string>& code); // 对哈夫曼编码文件进行解压
void binaryCode(); // 对文件进行二进制编码

//统计该文件中各种字符的频率
void frequencyRecord(HuffmanTree& HT) {
    HuffmanTree TEMP; // 临时存储字符出现频率的哈夫曼树节点数组
    TEMP = new HTNode[130]; // 先定义一个最大的数组，之后筛选出有用的字符出现频率
    for (int i = 0; i < 130; ++i) { // 初始化所有字符出现频率为0
        TEMP[i].weight = 0;
    }
    ifstream originFile('poem.txt'); // 打开文件
    originFile.seekg(0); // 将文件指针移动到文件开头
    if (!originFile) { // 判断是否打开成功
        cout << 'Can't find the file!' << endl;
    }
    else {
        char _data; // 存储读取到的字符
        cin.unsetf(ios::skipws); // 取消忽略空格
        while (!originFile.eof()) { // 读取文件直到文件结束
            if (originFile.get(_data)) { // 读取一个字符
                TEMP[_data].data = _data; // 在对应的哈夫曼树节点中存储该字符
                TEMP[_data].weight++; // 对应的字符出现频率+1
            }
        }
        originFile.close(); // 关闭文件
    }
    for (int i = 0; i < 130; ++i) {
        if (TEMP[i].weight != 0) { // 统计有用的字符种数
            N++;
        }
    }
    HT = new HTNode[2 * N]; // 根据字符种数定义哈夫曼树节点数组
    int k = 1;
    for (int i = 0; i < 130; ++i) { // 将有用的字符出现频率转移至HT数组中
        if (TEMP[i].weight != 0) {
            HT[k++] = TEMP[i];
        }
    }
}

//找出最小的两个叶子节点
void select(HuffmanTree HT, int num, int& child1, int& child2) {
    child1 = child2 = 0;
    int w1 = 0, w2 = 0;
    //Start finding...
    for (int i = 1; i <= num; ++i) {
        if (HT[i].parent == 0) { // 如果该节点为叶子节点
            if (child1 == 0) { // 如果第一个子节点还未被赋值
                child1 = i;
                w1 = HT[i].weight;
                continue;
            }
            if (child2 == 0) { // 如果第二个子节点还未被赋值
                child2 = i;
                w2 = HT[i].weight;
                continue;
            }
            if (w1 > w2 && w1 > HT[i].weight) { // 如果第一个子节点的权重比第二个子节点大，且比当前节点的权重大
                child1 = i;
                w1 = HT[i].weight;
                continue;
            }
            if (w2 > w1 && w2 > HT[i].weight) { // 如果第二个子节点的权重比第一个子节点大，且比当前节点的权重大
                child2 = i;
                w2 = HT[i].weight;
                continue;
            }
        }
    }
    // 使得w1永远小于w2
    int temp;
    if (w1 > w2) {
        temp = child1;
        child1 = child2;
        child2 = temp;
    }
}

//对各字符进行 Huffman编码，显示每个字符的编码
void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC) {
    int m = 2 * N - 1; // 哈夫曼树节点总数
    for (int i = 1; i <= N; ++i) {
        HT[i].parent = 0; // 初始化父节点
        HT[i].l_child = 0; // 初始化左子节点
        HT[i].r_child = 0; // 初始化右子节点
    }
    for (int i = N + 1; i <= m; ++i) {
        HT[i].weight = 0; // 初始化权重
        HT[i].parent = 0; // 初始化父节点
        HT[i].l_child = 0; // 初始化左子节点
        HT[i].r_child = 0; // 初始化右子节点
        HT[i].data = '#'; // 初始化存储的字符数据
    }
    int child1, child2;
    for (int i = N + 1; i <= m; i++) { // 构建哈夫曼树
        select(HT, i - 1, child1, child2);
        HT[child1].parent = i;
        HT[child2].parent = i;
        HT[i].l_child = child1;
        HT[i].r_child = child2;
        HT[i].weight = HT[child1].weight + HT[child2].weight;
    }
    HC = new char* [N + 1]; // 定义哈夫曼编码数组
    char* cd = new char[N];
    cd[N - 1] = '\0';
    int start, c, f;
    for (int i = 1; i <= N; i++) { // 生成哈夫曼编码
        start = N - 1;
        for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) {
            if (HT[f].l_child == c) cd[--start] = '0';
            else cd[--start] = '1';
        }
        HC[i] = new char[N - start];
        strcpy(HC[i], &cd[start]);
    }
    delete[] cd; // 释放内存
    for (int i = 1; i <= N; i++) { // 输出各字符对应的哈夫曼编码
        if (HT[i].data == '\n') {
            cout << '回车' << ' ' << HC[i] << endl;
        }
        else if (HT[i].data == ' ') {
            cout << '空格' << ' ' << HC[i] << endl;
        }
        else {
            cout << HT[i].data << ' ' << HC[i] << endl;;
        }
    }
}

//将该文件翻译成 Huffman编码文件
void zip(HuffmanTree& HT, HuffmanCode& HC, vector<string>& code) {
    ofstream codeFile('codefile.txt'); // 打开哈夫曼编码文件
    ifstream originFile('poem.txt'); // 打开源文件
    if (!codeFile) {
        cout << 'Can't find the file!' << endl;
    }
    else {
        char _data;
        cin.unsetf(ios::skipws);
        while (!originFile.eof()) {
            if (originFile.get(_data)) {
                for (int i = 1; i <= N; ++i) {
                    if (HT[i].data == _data) {
                        codeFile << HC[i];
                        code.push_back(HC[i]);
                    }
                }
            }
        }
    }
    codeFile.close();
}

//再将 Huffman编码文件翻译成源文件
void unzip(HuffmanTree& HT, HuffmanCode& HC, vector<string>& code) {
    ofstream decodeFile('decodefile.txt');
    if (!decodeFile) {
        cout << 'Can't find the file!' << endl;
    }
    else {
        vector<string>::iterator v = code.begin();
        while (v != code.end()) {
            for (int i = 1; i <= N; ++i) {
                if (HC[i] == *v) {
                    decodeFile << HT[i].data;
                }
            }
            v++;
        }
    }
    decodeFile.close();
}

//显示每个字符以一个字节进行二进制编码后的编码文件
void binaryCode() {
    ofstream binaryFile('binaryfile.txt');
    ifstream originFile('poem.txt');
    originFile.seekg(0);
    if (!originFile) {
        cout << 'Can't find the file!' << endl;
    }
    else {
        char _data;
        cin.unsetf(ios::skipws);
        while (!originFile.eof()) {
            if (originFile.get(_data)) {
                bitset<8> data(_data);
                binaryFile << data;
            }
        }
        originFile.close();
    }
}

int main() {
    system('color 02');
    cout << '******************' << endl;
    cout << '*哈夫曼编码解码器*' << endl;
    cout << '******************' << endl;
    Sleep(1000);
    HuffmanTree HT;
    HuffmanCode HC;
    vector<string> code;
    cout << '\n\n\n需要进行编码的文件内容为：\n\n';
    system('more poem.txt');
    Sleep(2000);
    cout << '\n\n正在打开poem.txt进行二进制编码......' << endl;
    Sleep(2000);
    binaryCode();
    cout << '\n\n二进制编码内容为：' << endl;
    Sleep(2000);
    system('more binaryfile.txt');
    Sleep(2000);
    cout << '\n\n正在统计字符权重......' << endl;
    Sleep(2000);
    frequencyRecord(HT);
    HuffmanCoding(HT, HC);
    cout << '\n\n写入编码文件......' << endl;
    Sleep(2000);
    zip(HT, HC, code);
    cout << '\n\n编码结果为：' << endl;
    system('more codefile.txt');
    Sleep(2000);
    cout << '\n\n解码编码文件......' << endl;
    Sleep(2000);
    unzip(HT, HC, code);
    cout << '\n\n解码结果为：' << endl;
    Sleep(2000);
    system('more decodefile.txt');
    cout << '\n\n编码前占用字节空间：' << endl;
    Sleep(1000);
    ifstream file_before('binaryfile.txt', ios::binary | ios::ate);
    auto size_before = file_before.tellg();
    cout << size_before << endl;
    file_before.close();
    cout << '\n\n编码后占用字节空间：' << endl;
    Sleep(1000);
    ifstream file_after('codefile.txt', ios::binary | ios::ate);
    auto size_after = file_after.tellg();
    cout << size_after << endl;
    file_after.close();
    Sleep(1000);
    cout << '\n\n压缩率为：' << (static_cast<double>(size_before - size_after)) / size_before * 100.0 << '%' << endl;
    Sleep(100000);
    return 0;
}

哈夫曼编码原理

哈夫曼编码是一种无损数据压缩算法，其基本原理是：

  • 统计频率： 计算文本中每个字符出现的频率。
  • 构建哈夫曼树： 将字符按照频率降序排列，构建一颗二叉树，叶子节点代表字符，节点的权重为对应字符的频率。
  • 生成编码： 从根节点到每个叶子节点的路径上，左分支用 '0' 表示，右分支用 '1' 表示，形成一个二进制编码。
  • 压缩数据： 将文本中的字符替换为其对应的哈夫曼编码，实现数据压缩。

代码分析

该 C++ 代码实现了以下功能：

  1. 统计字符频率 (frequencyRecord)

    • 使用 ifstream 打开文件 'poem.txt'，并读取文件内容。
    • 使用 TEMP 数组记录每个字符出现的次数，并计算字符种数 N。
    • 将 TEMP 中出现次数不为 0 的字符信息复制到 HT 数组中。

  2. 选择最小两个叶子节点 (select)

    • 遍历 HT 数组，找到两个权重最小的叶子节点，并记录其下标 child1 和 child2。

  3. 构建哈夫曼树和生成哈夫曼编码 (HuffmanCoding)

    • 构建哈夫曼树：根据 select 函数选出的两个节点，将其合并为新的父节点，并将父节点的权重设置为两个子节点权重之和。
    • 生成哈夫曼编码：从根节点到每个叶子节点的路径上，左分支用 '0' 表示，右分支用 '1' 表示，形成一个二进制编码，并存储在 HC 数组中。

  4. 压缩文件 (zip)

    • 打开源文件 'poem.txt' 和编码文件 'codefile.txt'。
    • 读取源文件中的每个字符，并将其对应的哈夫曼编码写入编码文件。

  5. 解压文件 (unzip)

    • 打开编码文件 'codefile.txt' 和解码文件 'decodefile.txt'。
    • 读取编码文件中的每个哈夫曼编码，并将其对应的字符写入解码文件。

  6. 二进制编码 (binaryCode)

    • 打开源文件 'poem.txt' 和二进制文件 'binaryfile.txt'。
    • 读取源文件中的每个字符，将其转换为 8 位二进制数，并写入二进制文件。

总结

这段代码演示了使用 C++ 实现哈夫曼编码的完整流程，并通过实际例子说明了其压缩效果。哈夫曼编码是一种简单高效的压缩算法，在数据压缩领域具有广泛的应用。

C++ 哈夫曼编码实现：高效压缩文本文件

原文地址: https://www.cveoy.top/t/topic/ore5 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录