Scribd Logo
Upload

Welcome to Scribd!

  • 20 views

    Huffmann Algo

    Uploaded by

    s.r.
    huffman code in c++11

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Huffmann Algo

    Uploaded by

    s.r.
    20 views3 pages
    huffman code in c++11

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    huffman code in c++11

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    20 views3 pages

    Huffmann Algo

    Uploaded by

    s.r.
    huffman code in c++11

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 3

    #include <iostream>

    #include <string>
    #include <queue>
    #include <unordered_map>
    using namespace std;
    int total = 0;

    // A Tree node
    struct Node
    {
    char ch;
    int freq;
    Node *left, *right;
    };

    // Function to allocate a new tree node


    Node* getNode(char ch, int freq, Node* left, Node* right)
    {
    Node* node = new Node();

    node->ch = ch;
    node->freq = freq;
    node->left = left;
    node->right = right;

    return node;
    }

    struct comp
    {
    bool operator()(Node* l, Node* r)
    {
    // highest priority item has lowest frequency
    return l->freq > r->freq;
    }
    };

    void encode(Node* root, string str,


    unordered_map<char, string> &huffmanCode)
    {
    if (root == nullptr)
    return;

    // found a leaf node


    if (!root->left && !root->right) {
    huffmanCode[root->ch] = str;
    }

    encode(root->left, str + "0", huffmanCode);


    encode(root->right, str + "1", huffmanCode);
    }

    // traverse the Huffman Tree and decode the encoded string


    void decode(Node* root, int &index, string str)
    {
    if (root == nullptr) {
    return;
    }

    // found a leaf node


    if (!root->left && !root->right)
    {
    cout << root->ch;
    return;
    }

    index++;

    if (str[index] =='0')
    decode(root->left, index, str);
    else
    decode(root->right, index, str);
    }

    // Builds Huffman Tree and decode given input text


    void buildHuffmanTree(string text)
    {
    // count frequency of appearance of each character
    // and store it in a map
    unordered_map<char, int> freq;

    for (char ch: text) {


    freq[ch]++;
    }

    // for (auto pair: freq) {


    // cout << pair.first<<" "<<pair.second<<endl;
    // }

    priority_queue<Node*, vector<Node*>, comp> pq;

    // Create a leaf node for each character and add it


    // to the priority queue.
    for (auto pair: freq) {
    pq.push(getNode(pair.first, pair.second, nullptr, nullptr));
    }

    // do till there is more than one node in the queue


    while (pq.size() != 1)
    {
    // Remove the two nodes of highest priority
    // (lowest frequency) from the queue
    Node *left = pq.top(); pq.pop();
    Node *right = pq.top(); pq.pop();

    int sum = left->freq + right->freq;


    pq.push(getNode('\0', sum, left, right));
    }

    Node* root = pq.top();

    unordered_map<char, string> huffmanCode;


    encode(root, "", huffmanCode);

    cout << "Huffman Codes are :\n" << '\n';


    for (auto pair: huffmanCode) {
    cout << pair.first << " " << pair.second <<" "<< "Length in bits: " <<pair.second.length()<< '\n';

    }
    for (auto pair: huffmanCode ) {
    total = total+pair.second.length() * freq.at(pair.first);

    cout << "\nOriginal string was :\n" << text << '\n';

    // print encoded string


    string str = "";
    for (char ch: text) {
    str += huffmanCode[ch];
    }

    cout << "\nEncoded string is :\n" << str << '\n';

    int index = -1;


    cout << "\nDecoded string is: \n";
    while (index < (int)str.size() - 2) {
    decode(root, index, str);
    }
    }

    int main()
    {

    string text = "Huffman coding is a data compr This is a big one. Depending upon where you place your comma, your sentence could
    convey an entirely different meaning. Like in this sentenceession algorithm.";
    cout<<"\n";

    buildHuffmanTree(text);
    cout<<"\n";
    cout<<"Length of UnCompressed text:"<<text.length()*8<<endl;
    cout<<"Length of Compressed text:"<<total<<endl;

    double ratio = (float)(text.length()*8)/(float)total;


    cout<<"Compression ratio :"<< " " <<ratio<<endl;
    return 0;
    }

    You might also like