哈夫曼编码与解码（贪心算法） C++实现

哈夫曼编码与解码（贪心算法） C++实现

原理

将原有的定长编码改为变长编码，字母次数出现多的使用小位数编码，字母次数出现少的使用多位数编码，总编码长度为：
B(T)=∑c∈Cc.freq×dT(c)
个二进制位。

其中 c.freq 表示 c 在文本中出现的频率， dT(c) 表示字符 c 的码字的长度，也可表示为 c 的叶结点在树中的深度。

哈夫曼编码通常可以节省 20%∼90% 的空间。

源代码

Huffman_Code.h

#ifndef _HUFFMAN_CODE_H_
#define _HUFFMAN_CODE_H_

#include <map>
#include <string>
#include <memory>
#include <vector>
#include <fstream>
#include <utility>
#include <iostream>
#include <algorithm>
#include <stdexcept>

using std::make_shared;
using std::shared_ptr;
using std::string;
using std::vector;
using std::pair;
using std::map;
using std::cout;
using std::endl;

class H_BST {
struct Node {
        pair<string, size_t> data;
shared_ptr<Node> left = nullptr;
shared_ptr<Node> right = nullptr;
shared_ptr<Node> parent = nullptr;
    };

shared_ptr<Node> Root = nullptr;
//Binary_Search_Tree with Huffman-Code.
vector<shared_ptr<Node>> Vec_Node;
//Letters and bijection codes.
map<string, string> Map_Code;
//All of Letters's code.
string Binary_Code;

public:
    H_BST() = default;
    ~H_BST() = default;

//Reading the data.
void Huffman_Code(string const &temp_str) {
string temp_i;
map<string, size_t> temp_Map;

for(auto &i : temp_str) {
            temp_i = i;
            ++temp_Map[temp_i];
        }

        Huffman_Encoder(temp_Map);

for (auto &i : temp_str) {
            temp_i = i;
            Binary_Code += Map_Code[temp_i];
        }

        Huffman_Decoder(Vec_Node);
    }

//Reading the data from file.
void Huffman_Code_File(string const &filename) {
string temp_i, temp_str;
std::ifstream file(filename);
map<string, size_t> temp_Map;

try {
if (file) {
while (!file.eof()) {
string temp_s;
                    getline(file, temp_s);
                    temp_str += temp_s;
                }
            }
else {
throw std::runtime_error("Not find the file.");
            }
        }
catch (std::runtime_error e) {
cout << e.what() << endl;
        }

for (auto &i : temp_str) {
            temp_i = i;
            ++temp_Map[temp_i];
        }

        Huffman_Encoder(temp_Map);

for (auto &i : temp_str) {
            temp_i = i;
            Binary_Code += Map_Code[temp_i];
        }

        Huffman_Decoder_File(Vec_Node);
    }

//Encodering and saving the result.
void Huffman_Encoder(map<string, size_t> &temp_Map) {
auto temp_n = temp_Map.size();
vector<shared_ptr<Node>> temp_VecNode;

for(auto &i : temp_Map) {
auto temp_ptr = make_shared<Node>();
            temp_ptr->data.first = i.first;
            temp_ptr->data.second = i.second;

            temp_VecNode.push_back(temp_ptr);
        }

for(auto i = 1; i != temp_n; ++i) {
std::sort(temp_VecNode.begin(), temp_VecNode.end(), [](shared_ptr<Node> N1, shared_ptr<Node> N2) {return N1->data.second < N2->data.second; });
auto new_Node = make_shared<Node>();

            new_Node->left = temp_VecNode[0];
            new_Node->right = temp_VecNode[1];
            new_Node->data.second = temp_VecNode[0]->data.second + temp_VecNode[1]->data.second;

            temp_VecNode.erase(temp_VecNode.begin(), temp_VecNode.begin() + 2);
            temp_VecNode.push_back(new_Node);
        }

        Vec_Node = temp_VecNode;

        Save_Coder(Vec_Node[0], "");
    }

//Saving the unique code of letters.
void Save_Coder(shared_ptr<Node> Root, string const &code) {
if (Root) {
if (!Root->left && !Root->right) {
                Map_Code.insert(std::make_pair(Root->data.first, code));
std::cout << Root->data.first << " -> " << code << std::endl;
            }
else {
                Save_Coder(Root->left, code + "0");
                Save_Coder(Root->right, code + "1");
            }
        }
    }

//Decodering and outputting the result.
void Huffman_Decoder(vector<shared_ptr<Node>> const &Vec_Node) {
auto Ptr = Vec_Node[0];
string temp_i;

for(auto &i : Binary_Code) {
            temp_i = i;
if(temp_i == "0") {
                Ptr = Ptr->left;
if(Ptr->left == nullptr && Ptr->right == nullptr) {
cout << Ptr->data.first;
                    Ptr = Vec_Node[0];
                }
            }
if(temp_i == "1") {
                Ptr = Ptr->right;
if (Ptr->left == nullptr && Ptr->right == nullptr) {
cout << Ptr->data.first;
                    Ptr = Vec_Node[0];
                }
            }
        }

cout << endl;
    }

//Decodering and outputting the result in the file.
void Huffman_Decoder_File(vector<shared_ptr<Node>> const &Vec_Node) {
auto Ptr = Vec_Node[0];
std::ofstream out("file_encoder_to_decoder.txt");
string temp_i;

for (auto &i : Binary_Code) {
            temp_i = i;
if (temp_i == "0") {
                Ptr = Ptr->left;
if (Ptr->left == nullptr && Ptr->right == nullptr) {
                    out << Ptr->data.first;
                    Ptr = Vec_Node[0];
                }
            }
if (temp_i == "1") {
                Ptr = Ptr->right;
if (Ptr->left == nullptr && Ptr->right == nullptr) {
                    out << Ptr->data.first;
                    Ptr = Vec_Node[0];
                }
            }
        }
    }
};

#endif // !_HUFFMAN_CODE_H_

测试代码：

#include "Huffman_Code.h"

using namespace std;

int main() {
    H_BST A;
    A.Huffman_Code("aaaaaaaaaaaaaaaaaaaaaaaaassssssssssssssddddddddddddddddddeeeeeeeeeeeeefgssssssssssssssqqqqqq -???>>> <<<!@$%&(%^$#@#@");
//A.Huffman_Code_File("file_name.data");//读取文件。

return 0;
}