#include #include #include #include #include using namespace std; const string quote="It is by will alone I set my mind in motion. It is by the juice of Sapho that thoughts acquire speed, the lips acquire stains, stains become a warning. It is by will alone I set my mind in motion. - Dune 1984"; struct Node{ char value=0; Node*left=nullptr; Node*right=nullptr; int priority; Node(char c,int priority): value{c}, priority{priority} {} Node(Node*l,Node*r): left{l}, right{r}, priority{l->priority+r->priority} {} ~Node(){ delete left;left=nullptr; delete right;right=nullptr; } }; struct greaterNodePointer{ bool operator()(Node*l,Node*r){ return l->priority>r->priority;} }; Node* huffman(string s){ priority_queue, greaterNodePointer> pq; mapchar_map; for(const auto&c:s) (char_map.find(c)!=char_map.end())?++char_map[c] :char_map[c]=1; for(const auto&p:char_map){ printf("%c : %d\n",p.first,p.second); pq.emplace(new Node(p.first,p.second)); } while(pq.size()!=1){ Node*left=pq.top();pq.pop(); Node*right=pq.top();pq.pop(); pq.emplace(new Node(left,right)); } return pq.top(); } void mapping(const Node*const n, map&encode_map, map&decode_map, string s=""){ if(n->value!=0){ encode_map[n->value]=s; decode_map[s]=n->value; return; } mapping(n->left,encode_map,decode_map,s+"0"); mapping(n->right,encode_map,decode_map,s+"1"); } string encode(const string&msg, const map&encode_map){ string encoded=""; for(const auto&c:msg) encoded+=encode_map.at(c); return encoded; } string decode(const string&encoded, const map&decode_map){ string decoded=""; string key=""; unsigned cursor=0; while(cursor0;power/=2){ s+=b/power+48; b%=power; } } return s; } int main() { cout<<"Occurences\n"<encode_map; mapdecode_map; mapping(tree_root,encode_map,decode_map); string encoded=encode(quote,encode_map); string decoded=decode(encoded,decode_map); cout<<"\nEncoding Map\n"<

huffman Huffman compression