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 <bits/stdc++.h> 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<int, set<char>> 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<Node*, vector<Node*>, mycomp>que; for(int i = 0;i < n;++i){ Node* newnode = new Node(); newnode->c = arr_char[i]; newnode->data =https://www.cnblogs.com/xuan01/archive/2023/04/14/ 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 = https://www.cnblogs.com/xuan01/archive/2023/04/14/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<int, set<char>>::iterator it = data.begin(); it != data.end(); ++it){ set<char> 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 : 0 a : 10 b : 110 d : 111 */
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/550145.html
標籤：其他