Huffman编码与解码 | Blurred code

Huffman编码与解码

panda

2019/05/20

LastMod:2021/02/23

Categories: cpp

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

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

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

从森林中合并为树

    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,并走下一步,直到遍历的到叶节点。遍历到叶节点后,将charbitset插入一个key-value pair,即代表一个编码对。