Huffman编码与解码

Huffman编码在数据结构里是必学的部分。要实现霍夫曼编码首先要实现霍夫曼树（一个简单的教程，它是一个带权最优编码树，主要特性有两点：

• 所有数据都在叶节点
• 出现概率越高的字符(权重越高)离根节点越近

这就为编码和解码提供了思路。编码时，先新建森林，每一个树上只有单独的权重和节点，然后两两合并为新的树，最后合并为一颗整数。从根节点往下递归，左分支为0，右分支为1，得到编码。 如图所示：

解码时思路也相同，从形如0010101的bitset中解码时，需要预先知道霍夫曼树的全体信息。从根节点开始遍历，每一次遍历检查是否为叶节点，为叶节点时提取数据并回到根节点，解码一个字符。

从森林中合并为树

    while(forest.size() > 1)
    {
        std::sort(forest.begin(),forest.end(),[&](node* a,node* b){return a->weight < b->weight;});
        ptr = new node;
        ptr->weight = forest.at(0)->weight + forest.at(1)->weight;
        ptr->lChild = forest.at(0);
        ptr->rChild = forest.at(1);
        forest.pop_front();
        forest.pop_front();
        forest.push_back(ptr);
    }

将森林里的树排序，将权重最小的两棵树合并为一个新树并重新插入森林。循环下去直到森林里只剩下一棵树，这棵树的入口就是根节点。

递归法生成编码表

void generateCode(std::deque<bool>* code,int length,std::map<char,std::deque<bool>>* table,node* pptr)
{
    if(IsLeaf(pptr))
    {
        table->insert(std::make_pair(pptr->data,std::deque<bool>{code->begin(),code->begin() + length}));
    }
    if(HasLChild(pptr))
    {
        (*code)[length] = 0;
        generateCode(code,length + 1,table,pptr->lChild);
    }

    if(HasRChild(pptr))
    {
        (*code)[length] = 1;
        generateCode(code,length + 1,table,pptr->rChild);
    }
}

auto  generateTable(node* treeroot)
{
    auto code = new std::deque<bool>{{0,0,0,0}};
    auto Hufftable = new std::map<char,std::deque<bool>>;
    generateCode(code,0,Hufftable,treeroot);
    return Hufftable;
}

从treeroot根节点进入，编码长度为0，每走一步查看是否为叶节点，若不是叶节点则将本位设置为0或1，编码长度 + 1，并走下一步，直到遍历的到叶节点。遍历到叶节点后，将char和bitset插入一个key-value pair，即代表一个编码对。