哈夫曼编码压缩文本c++

### C++ 实现哈夫曼编码进行文本压缩

#### 构建哈夫曼树
为了实现哈夫曼编码，首先需要构建哈夫曼树。这棵树基于输入文件中各个字符的频率而建立。每个节点代表一个字符及其出现次数，叶子节点表示实际存在的字符。

struct MinHeapNode {
    char data;
    unsigned freq;
    MinHeapNode *left, *right;

    MinHeapNode(char character, unsigned frequency) : data(character), freq(frequency),
                                                      left(nullptr), right(nullptr) {}
};

创建最小堆以便高效获取具有最低频次的两个节点并组合成新节点直至只剩下一个根节点形成完整的二叉树即为所求之哈夫曼树[^1]。

#### 编码映射表生成
一旦获得了哈夫曼树，则可以遍历此树以获得各字符对应的编码串。从根到叶路径上的每一步左转记作'0', 右转则记录为 '1'. 这样就得到了唯一确定的一组前缀码.

void buildHuffmanCodes(MinHeapNode* root, const string& str,
                       unordered_map<char, string>& huffmanCode)
{
    if (!root)
        return;

    if (root->data != '$')
        huffmanCode[root->data] = str;

    buildHuffmanCodes(root->left, str + "0", huffmanCode);
    buildHuffmanCodes(root->right, str + "1", huffmanCode);
}

#### 文件读取与写入操作
对于待压缩的目标文件而言，先统计其中所有不同字节值各自的出现次数；接着依据上述步骤构造相应的哈夫曼编码方案；最后按照该方案重新解释原始比特流内容完成最终的数据压缩工作。

ifstream fin("input.txt");
ofstream fout("output.bin");

// ... 统计频率 ...

unordered_map<char, string> codes;
buildHuffmanCodes(treeRoot, "", codes);

for (char ch; fin.get(ch); )
    compressedData += codes[ch];

fout.write(compressedData.c_str(), compressedData.size());
fin.close();
fout.close();

以上展示了如何使用C++编程语言来具体实践哈夫曼编码算法对给定文本实施有效的无损压缩处理方式[^2].