最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

天天新动态：Huffman实现

来源：博客园

Huffman编码树

秒懂：【算法】Huffman编码_哔哩哔哩_bilibili


(资料图片)

约定：字符x的编码长度 就是其对应叶节点的深度；

在一个字符集中，每个字符出现的次数有多有少，那么若都采用固定长度编码的话，那么编码长度会非常大，并且搜索时间复杂度都非常高；若采用非固定编码，出现次数多的字符编码长度小一些，并且放在树深度小的地方，提高搜索时间效率；这样带权平均编码长度（weight average leaf depth）就会达到最优；同时为了避免歧义，任何字符不能是其他字符的编码前缀；还有一点就是没有度为1的节点，也就是说是一颗满二叉树；

个人理解：

没有前缀：在具体实现时，由 priority_queue 排序完成后的 节点权值树 再转存在map中时，不会存储根节点，只会存叶子节点，就能避免前缀相同的情况；还有一点就是第一个设置为0，而不是1，1的话就会成为其他字符的前缀；

没有度为1 的节点 和 无前缀相同编码 的不一定是Huffman，还需满足 ald 最短；

时间复杂度：对于出现次数多的字符，让它在靠近根节点位置，这样就能接近O（1）时间复杂度；而对于出现次数少的字符，就靠近树的最底部位置；

具体实现：

代码参考：Canonical Huffman Coding - GeeksforGeeks

1、实现一个struct，保存字符出现的次数，以及字符本身，还有左右子节点；

2、写一个路径长度模块函数，create_code();

3、写一个Huffman编码函数，create_huffman(); 其中， 先按频率从小到大排列，然后取最小的两个合并为一大的，在继续合并直至成为一个根节点，再将字符树存进map中；接着实现Huffman编码；

①在编码时，利用路径长度信息，和bitset<32>类，实现位操作，并且利用成员函数to_string()转化为字符串，左边为高位，右边为低位；substr函数第二个参数长度设置为32，默认到头；

②怎么利用路径长度信息的？ 比如说代码中 给出的例子c，编码为0，假设还有叶子节点，那么当前编码值加上1，然后再左移(下一层的深度 - 当前层的深度)位，即 0 +1 = 12，再左移（2-1）位，变成102；在内层循环中，当是同一层的最后两个叶子节点时，即110 和 111 ， 不做左移，只做值加一操作，代码这儿用了一个next_len 和 cur_len 相减实现左移的次数值；(非常巧妙)；

③学到了一个next 函数，和 bitset 位操作；

#include using namespace std;/*Huffman codes : a lossless data compression algorithm; weighted average leaf depth（带权平均深度最小）*/struct Node{    int data;    char c;    Node* left, *right;};struct mycomp{    bool operator()(Node* a, Node* b){        return a->data > b->data;    }};class huffman{private:    map> data;public:    huffman(){}    void create_code(Node* root, int code_len){        if(root == nullptr){            return;        }        /*only store leaf node*/        if(root->left == nullptr && root->right == nullptr){            data[code_len].insert(root->c);        }        create_code(root->left, code_len + 1);        create_code(root->right, code_len + 1);    }    void create_huffman(int n, char arr_char[], int freq[]){        /* 小顶堆  取堆顶 freq 小的两个合并*/        priority_queue, mycomp>que;        for(int i = 0;i < n;++i){            Node* newnode = new Node();            newnode->c = arr_char[i];            newnode->data = freq[i];            newnode->left = nullptr;            newnode->right = nullptr;            que.push(newnode);        }        /*Node Tree*/        Node* root = nullptr;        while(que.size() > 1){            Node* tmp1 = que.top();            que.pop();            Node* tmp2 = que.top();            que.pop();            Node* mergeNode = new Node();            mergeNode->data = tmp1->data + tmp2->data;            mergeNode->c = "-";            mergeNode->left = tmp1;            mergeNode->right = tmp2;            root = mergeNode;            que.push(mergeNode);        }        huffman obj = huffman();        create_code(root, 0);        int cur_code = 0, cur_len = 0, next_len = 0;        for(map>::iterator it = data.begin(); it != data.end(); ++it){            set s = it->second;            cur_len = it->first;            for(auto i = s.begin(); i != s.end(); ++i){                cout << *i << " : ";                /* coding */                cout << bitset<32>(cur_code).to_string().substr(32 - cur_len, 32) << endl;                                /* 相同长度 有一个以上叶子节点时 : 这种情况只出现在 尾部的那俩个元素*/                if(next(i) != s.end() || next(it) == data.end()) next_len = cur_len;                else next_len = next(it)->first;                                cur_code = (cur_code + 1) << (next_len - cur_len);            }        }    }};int main(){    int n = 4;    char arr[] = {"a", "b", "c", "d"};    int fre[] = {10, 1, 15, 7};    huffman obj;    obj.create_huffman(n,arr,fre);     system("pause");    return 0;}/*c : 0a : 10b : 110d : 111*/

关键词：