C++项目基于HuffmanTree实现文件的压缩与解压缩功能

标题：C++项目基于HuffmanTree实现文件的压缩与解压缩功能

一、HuffmanTree基本概念

Huffman编码是一种无损压缩算法，主要思想是利用频率较高的字符使用较短的二进制编码，频率较低的字符使用较长的二进制编码，从而实现压缩目的。

Huffman树是一种高效的实现Huffman编码的数据结构，它是一棵带权树，其中每个叶子结点代表一个字符，其权值为该字符在文本中出现的频率。利用HuffmanTree的思想，我们可以在不降低原始数据质量的情况下实现对文本的压缩。

二、项目实现过程

下面介绍C++项目基于HuffmanTree实现文件的压缩与解压缩功能的详细实现步骤。

1. 遍历文件并生成字符频率map

首先，我们需要遍历所要压缩的文件，并统计文件中每个字符出现的频率。这里使用std::map<char, int>来记录字符与出现频率的对应关系。

示例代码：

#include <fstream>
#include <map>

// 遍历文件并生成字符频率map
std::map<char, int> getCharFrequency(std::string filePath) {
    std::map<char, int> frequencyMap;
    std::ifstream file(filePath, std::ios::binary);
    char c;
    while (file.get(c)) {
        ++frequencyMap[c];
    }
    return frequencyMap;
}

2. 根据字符频率map构建Huffman树

获取到字符频率map后，我们需要构建Huffman树。具体实现方法为：

1. 将频率map中的字符和权重都存入一个vector中；
2. 构建小根堆，按照每个字符出现频率的大小进行排序；
3. 从小根堆获取最小的两个节点，创建一个新的父节点，权重为两个节点的权重之和，并将父节点插入回小根堆；
4. 重复第三步，直到小根堆只剩下一个节点，即Huffman树的根节点。

示例代码：

#include <queue>
#include <vector>

// Huffman树节点结构体
struct Node {
    char character;
    int weight;
    Node *leftChild;
    Node *rightChild;
    Node(char c, int w, Node *l = nullptr, Node *r = nullptr) : character(c), weight(w), leftChild(l), rightChild(r) {}
};

// 小根堆比较器
struct compareNode {
    bool operator()(const Node *a, const Node *b) { return a->weight > b->weight; }
};

// 根据字符频率map构建Huffman树
Node *buildHuffmanTree(std::map<char, int> frequencyMap) {
    std::priority_queue<Node *, std::vector<Node *>, compareNode> minHeap;
    for (const auto &frequency : frequencyMap) {
        minHeap.push(new Node(frequency.first, frequency.second));
    }
    while (minHeap.size() > 1) {
        Node *leftChild = minHeap.top();
        minHeap.pop();
        Node *rightChild = minHeap.top();
        minHeap.pop();
        minHeap.push(new Node('\0', leftChild->weight + rightChild->weight, leftChild, rightChild));
    }
    return minHeap.top();
}

3. 生成Huffman编码表

生成Huffman编码表的过程是将Huffman树进行遍历，并在遍历过程中记录下每个字符的Huffman编码。在这里我们使用递归的方式来进行Huffman树的遍历。

示例代码：

#include <unordered_map>

// 生成Huffman编码表的递归函数
void buildHuffmanCode(Node *node, std::string code, std::unordered_map<char, std::string> &codeTable) {
    if (node->leftChild == nullptr && node->rightChild == nullptr) {
        codeTable[node->character] = code;
        return;
    }
    buildHuffmanCode(node->leftChild, code + "0", codeTable);
    buildHuffmanCode(node->rightChild, code + "1", codeTable);
}

// 生成Huffman编码表
std::unordered_map<char, std::string> buildHuffmanCodeTable(Node *huffmanTree) {
    std::unordered_map<char, std::string> codeTable;
    buildHuffmanCode(huffmanTree, "", codeTable);
    return codeTable;
}

4. 将文件按照Huffman编码进行压缩

获取到Huffman编码表后，我们就可以将所要压缩的文件按照这个编码表进行压缩。具体实现方法是：

1. 遍历文件，获取到每个字符对应的Huffman编码；
2. 将Huffman编码依次存入一个字符串中，每8个二进制位组成一个字节，并将其写入到文件中；
3. 在文件的开头写入字符频率map，以便解压缩时可以重新生成Huffman树。

示例代码：

#include <bitset>
#include <fstream>

// 将文件按照Huffman编码进行压缩
void compressFile(std::string sourcePath, std::string targetPath) {
    auto frequencyMap = getCharFrequency(sourcePath);
    auto huffmanTree = buildHuffmanTree(frequencyMap);
    auto codeTable = buildHuffmanCodeTable(huffmanTree);
    std::ifstream inputFile(sourcePath, std::ios::binary);
    std::ofstream outputFile(targetPath, std::ios::binary);
    // 写入字符频率map
    size_t frequencyMapSize = frequencyMap.size();
    outputFile.write((char *)&frequencyMapSize, sizeof(size_t));
    for (const auto &frequency : frequencyMap) {
        outputFile.write(&frequency.first, sizeof(char));
        outputFile.write((char *)&frequency.second, sizeof(int));
    }
    // 将文件按照Huffman编码进行压缩
    std::string bitString;
    char c;
    while (inputFile.get(c)) {
        bitString += codeTable[c];
        while (bitString.length() >= 8) {
            std::bitset<8> byte(bitString.substr(0, 8));
            outputFile.write((char *)&byte, sizeof(char));
            bitString.erase(0, 8);
        }
    }
    if (!bitString.empty()) {
        bitString += std::string(8 - bitString.length() % 8, '0');
        std::bitset<8> byte(bitString.substr(0, 8));
        outputFile.write((char *)&byte, sizeof(char));
    }
}

5. 解压缩文件

将文件按照Huffman编码进行压缩后，我们需要实现对其进行解压缩。具体实现方法是：

1. 读取文件开头的字符频率map，重新生成Huffman树；
2. 加载文件中的Huffman编码，并根据Huffman编码还原出文件中的原始字符。

示例代码：

#include <fstream>

// 解压缩文件
void decompressFile(std::string sourcePath, std::string targetPath) {
    std::ifstream inputFile(sourcePath, std::ios::binary);
    size_t frequencyMapSize;
    // 读取字符频率map
    inputFile.read((char *)&frequencyMapSize, sizeof(size_t));
    std::map<char, int> frequencyMap;
    for (size_t i = 0; i < frequencyMapSize; ++i) {
        char c;
        int frequency;
        inputFile.read(&c, sizeof(char));
        inputFile.read((char *)&frequency, sizeof(int));
        frequencyMap[c] = frequency;
    }
    // 构建Huffman树并重新生成Huffman编码表
    auto huffmanTree = buildHuffmanTree(frequencyMap);
    auto codeTable = buildHuffmanCodeTable(huffmanTree);
    std::ofstream outputFile(targetPath, std::ios::binary);
    // 解压缩文件
    std::string bitString;
    char c;
    while (inputFile.get(c)) {
        std::bitset<8> byte(c);
        bitString += byte.to_string();
    }
    if (bitString.length() % 8 != 0) {
        bitString.erase(bitString.length() - (bitString.length() % 8));
    }
    Node *currentNode = huffmanTree;
    for (size_t i = 0; i < bitString.length(); ++i) {
        if (bitString[i] == '0') {
            currentNode = currentNode->leftChild;
        } else {
            currentNode = currentNode->rightChild;
        }
        if (currentNode->leftChild == nullptr && currentNode->rightChild == nullptr) {
            outputFile.write(&currentNode->character, sizeof(char));
            currentNode = huffmanTree;
        }
    }
}

三、示例说明

下面给出两个压缩和解压缩文件的示例：

示例一

压缩文件test.txt并将其解压到output.txt中。

std::string sourcePath = "test.txt";
std::string compressedPath = "compressed.bin";
std::string decompressedPath = "output.txt";
compressFile(sourcePath, compressedPath);
decompressFile(compressedPath, decompressedPath);

示例二

压缩文件test.mov并将其解压到output.mov中。

std::string sourcePath = "test.mov";
std::string compressedPath = "compressed.bin";
std::string decompressedPath = "output.mov";
compressFile(sourcePath, compressedPath);
decompressFile(compressedPath, decompressedPath);

以上就是C++项目基于HuffmanTree实现文件的压缩与解压缩功能的完整攻略。