哈夫曼树实现文件压缩与解压缩c++

哈夫曼树是一种有效的数据压缩算法，可以通过构建哈夫曼树来实现文件的压缩和解压缩。

哈夫曼树的构建过程主要分为两步：统计字符频率和构建哈夫曼树。

首先，在压缩文件之前，需要统计每个字符在文件中出现的频率。可以遍历文件中的每个字符，使用一个哈希表来记录每个字符出现的频率。

然后，根据字符的频率构建哈夫曼树。先将每个字符及其频率作为一个节点插入优先队列（最小堆），按照频率进行排序。接下来，从优先队列中取出频率最小的两个节点作为左右子节点，新建一个父节点，将两个子节点连接到父节点上，并将父节点重新插入优先队列。重复这个过程，直到队列中只剩下一个节点，即构建出哈夫曼树。

完成哈夫曼树的构建后，可以通过遍历哈夫曼树的路径来生成每个字符的编码。从根节点开始，左子节点表示0，右子节点表示1，递归地沿着树的路径进行编码。将每个字符及其对应的编码存入编码表中。

在压缩文件时，可以使用编码表将文件中的字符逐个替换为对应的编码，从而将文件压缩为较小的二进制文件。在解压缩时，根据编码表将编码逐个转换回原始字符，恢复原始文件。

哈夫曼树算法能够根据字符频率生成可变长度的编码，使得出现频率高的字符使用更短的编码，提高压缩效率。通过哈夫曼树实现的文件压缩和解压缩可以有效地减小文件的大小，方便存储和传输。

相关问题

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

哈夫曼编码是一种基于字符频率的压缩算法，可以在不丢失数据的情况下有效地减小文件大小。哈夫曼编码的压缩过程需要先建立哈夫曼树，再根据哈夫曼树生成每个字符的编码表，最后将原文件中的字符替换为对应的编码即可。解压过程则是将编码转换为原字符，最终还原原始文件。

以下是一个简单的哈夫曼树编码文件压缩与解压缩的实现示例，使用 C++ 语言编写。

### 哈夫曼树的构建

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>

using namespace std;

// 哈夫曼树节点
struct Node {
    char ch;
    int freq;
    Node *left, *right;

    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// 比较器，用于优先队列中的排序
struct cmp {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

// 构建哈夫曼树
Node* buildHuffmanTree(string str) {
    // 统计字符频率
    unordered_map<char, int> freqMap;
    for (char c : str) {
        freqMap[c]++;
    }

    // 将所有字符及其频率转化为哈夫曼树节点并加入优先队列
    priority_queue<Node*, vector<Node*>, cmp> pq;
    for (auto it = freqMap.begin(); it != freqMap.end(); it++) {
        pq.push(new Node(it->first, it->second));
    }

    // 构建哈夫曼树
    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        Node* parent = new Node('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }

    // 返回根节点
    return pq.top();
}

### 哈夫曼编码的生成

// 生成哈夫曼编码表
void generateEncodingTable(Node* root, unordered_map<char, string>& encodingTable, string code) {
    if (!root) return;

    if (!root->left && !root->right) {
        encodingTable[root->ch] = code;
        return;
    }

    generateEncodingTable(root->left, encodingTable, code + "0");
    generateEncodingTable(root->right, encodingTable, code + "1");
}

### 文件压缩

#include <fstream>
#include <bitset>

// 压缩文件
void compressFile(string inputFile, string outputFile) {
    // 读取原文件
    ifstream ifs(inputFile, ios::binary);
    string str((istreambuf_iterator<char>(ifs)), (istreambuf_iterator<char>()));
    ifs.close();

    // 构建哈夫曼树并生成编码表
    Node* root = buildHuffmanTree(str);
    unordered_map<char, string> encodingTable;
    generateEncodingTable(root, encodingTable, "");

    // 将编码表写入压缩文件头部
    ofstream ofs(outputFile, ios::binary);
    for (auto it = encodingTable.begin(); it != encodingTable.end(); it++) {
        ofs << it->first << it->second << endl;
    }

    // 将压缩后的内容写入压缩文件
    string compressedStr;
    for (char c : str) {
        compressedStr += encodingTable[c];
    }
    while (compressedStr.length() % 8 != 0) compressedStr += "0"; // 补齐到8的倍数
    for (int i = 0; i < compressedStr.length(); i += 8) {
        bitset<8> bits(compressedStr.substr(i, 8));
        ofs << char(bits.to_ulong());
    }
    ofs.close();
}

### 文件解压

#include <sstream>

// 解压文件
void decompressFile(string inputFile, string outputFile) {
    // 读取压缩文件
    ifstream ifs(inputFile, ios::binary);
    stringstream ss;
    ss << ifs.rdbuf();
    string compressedStr = ss.str();
    ifs.close();

    // 从压缩文件头部读取编码表
    unordered_map<string, char> decodingTable;
    int i = 0;
    while (i < compressedStr.length() && compressedStr[i] != '\n') {
        char c = compressedStr[i++];
        string code;
        while (i < compressedStr.length() && compressedStr[i] != '\n') {
            code += compressedStr[i++];
        }
        decodingTable[code] = c;
        i++; // 跳过换行符
    }

    // 解压缩内容
    string decompressedStr;
    string code;
    for (; i < compressedStr.length(); i++) {
        bitset<8> bits(compressedStr[i]);
        code += bits.to_string();
        if (decodingTable.find(code) != decodingTable.end()) {
            decompressedStr += decodingTable[code];
            code.clear();
        }
    }

    // 写入解压后的内容
    ofstream ofs(outputFile, ios::binary);
    ofs << decompressedStr;
    ofs.close();
}

以上就是一个简单的哈夫曼树编码文件压缩与解压缩的实现方法。需要注意的是，在实际应用中，还需要考虑一些细节问题，例如文件读写、编码表的存储方式和压缩文件头部的格式等。

利用哈夫曼压缩与解压缩文件的C++代码

以下是利用哈夫曼压缩与解压缩文件的C++代码：

#include <iostream>
#include <fstream>
#include <queue>
#include <unordered_map>
#include <bitset>

using namespace std;

class HuffmanNode {
public:
    char c;
    int freq;
    HuffmanNode* left;
    HuffmanNode* right;
    HuffmanNode(char c, int freq) : c(c), freq(freq), left(nullptr), right(nullptr) {}
    ~HuffmanNode() { delete left; delete right; }
};

struct cmp {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

class HuffmanTree {
public:
    HuffmanNode* root;
    HuffmanTree() : root(nullptr) {}
    ~HuffmanTree() { delete root; }
    void build(unordered_map<char, int>& freq) {
        priority_queue<HuffmanNode*, vector<HuffmanNode*>, cmp> pq;
        for (auto& p : freq) {
            pq.push(new HuffmanNode(p.first, p.second));
        }
        while (pq.size() > 1) {
            auto a = pq.top(); pq.pop();
            auto b = pq.top(); pq.pop();
            pq.push(new HuffmanNode('\0', a->freq + b->freq));
            a->left = b;
            a->right = a->left;
        }
        this->root = pq.top();
    }
};

unordered_map<char, int> getFreq(const string& filename) {
    unordered_map<char, int> freq;
    ifstream ifs(filename, ios::binary);
    if (!ifs) {
        cerr << "Error: cannot open file " << filename << endl;
        exit(1);
    }
    char c;
    while (ifs.get(c)) {
        freq[c]++;
    }
    return freq;
}

void encode(const string& filename, const unordered_map<char, string>& codes) {
    ifstream ifs(filename, ios::binary);
    if (!ifs) {
        cerr << "Error: cannot open file " << filename << endl;
        exit(1);
    }
    string outputFilename = filename + ".huffman";
    ofstream ofs(outputFilename, ios::binary);
    if (!ofs) {
        cerr << "Error: cannot create file " << outputFilename << endl;
        exit(1);
    }
    ofs << codes.size() << endl;
    for (auto& p : codes) {
        ofs << p.first << " " << p.second << endl;
    }
    char c;
    string bits;
    while (ifs.get(c)) {
        bits += codes.at(c);
        while (bits.size() >= 8) {
            bitset<8> byte(bits.substr(0, 8));
            ofs.put(static_cast<char>(byte.to_ulong()));
            bits.erase(0, 8);
        }
    }
    if (bits.size() > 0) {
        bits += string(8 - bits.size(), '0');
        bitset<8> byte(bits);
        ofs.put(static_cast<char>(byte.to_ulong()));
    }
}

void decode(const string& filename) {
    ifstream ifs(filename, ios::binary);
    if (!ifs) {
        cerr << "Error: cannot open file " << filename << endl;
        exit(1);
    }
    string outputFilename = filename.substr(0, filename.find_last_of('.'));
    ofstream ofs(outputFilename, ios::binary);
    if (!ofs) {
        cerr << "Error: cannot create file " << outputFilename << endl;
        exit(1);
    }
    int n;
    ifs >> n;
    ifs.ignore();
    unordered_map<string, char> codes;
    for (int i = 0; i < n; i++) {
        char c;
        string code;
        ifs >> c >> code;
        codes[code] = c;
    }
    string bits;
    char c;
    while (ifs.get(c)) {
        bits += bitset<8>(static_cast<unsigned char>(c)).to_string();
    }
    if (bits.size() > 0) {
        int padding = stoi(bits.substr(bits.size() - 8), nullptr, 2);
        bits.erase(bits.size() - padding, padding);
    }
    HuffmanNode* node = new HuffmanNode('\0', 0);
    HuffmanNode* p = node;
    for (char bit : bits) {
        if (bit == '0') {
            p = p->left == nullptr ? p->left = new HuffmanNode('\0', 0) : p->left;
        } else {
            p = p->right == nullptr ? p->right = new HuffmanNode('\0', 0) : p->right;
        }
        if (p->left == nullptr && p->right == nullptr) {
            ofs.put(p->c);
            p = node;
        }
    }
    delete node;
}

int main(int argc, char* argv[]) {
    if (argc != 3) {
        cerr << "Usage: " << argv[0] << " compress/decompress filename" << endl;
        return 1;
    }
    if (string(argv[1]) == "compress") {
        auto freq = getFreq(argv[2]);
        HuffmanTree tree;
        tree.build(freq);
        unordered_map<char, string> codes;
        function<void(HuffmanNode*, string)> dfs = [&](HuffmanNode* node, string code) {
            if (node->left == nullptr && node->right == nullptr) {
                codes[node->c] = code;
            }
            if (node->left != nullptr) {
                dfs(node->left, code + "0");
            }
            if (node->right != nullptr) {
                dfs(node->right, code + "1");
            }
        };
        dfs(tree.root, "");
        encode(argv[2], codes);
    } else if (string(argv[1]) == "decompress") {
        decode(argv[2]);
    } else {
        cerr << "Usage: " << argv[0] << " compress/decompress filename" << endl;
        return 1;
    }
    return 0;
}

代码中使用了一个 `HuffmanNode` 类来表示哈夫曼树的节点，使用了一个 `HuffmanTree` 类来表示哈夫曼树，使用了一个 `unordered_map` 来存储每个字符的出现频率，使用了一个优先队列来构建哈夫曼树，使用了一个递归函数来生成哈夫曼编码，使用了一个 `bitset` 来进行位运算，使用了一个文件流来读取和写入文件，使用了一些 C++11 的新特性。在使用时，运行程序时需要指定压缩或解压缩，并指定文件名。