Question

Write a C++ program using produces Huffman code for a string of text entered by the user.

Must accept all ASCII characters.

Answer 1

C++ program using produces Huffman code for all ASCII characters.

Huffman code is a data compression technique that converts data. Huffman tree creates an algorithm or tree from the input characters and encodes them to equivalent codes.

Steps

• Create a leaf node
• Extract nodes and create internal nodes
• Assign frequency and add to minimum heap
• Create a root of huffman tree
• Repeat the process

Process

• Enter the text size
• Enter the string text
• Enter frequencies for each letter
• Equal Huffman code will be produced

Source Code

     
#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

class Hman_Code
{
 struct New_Node
 {
  char data;
  size_t freq;
  New_Node* left;
  New_Node* right;
  New_Node(char data, size_t freq) : data(data),
                                 freq(freq),
left(NULL),
right(NULL)
                                 {}
 ~New_Node()
 {
   delete left;
   delete right;
 }
 };

 struct compare
 {
  bool operator()(New_Node* l, New_Node* r)
  {
    return (l->freq > r->freq);
  }
};

New_Node* top;

void print_Code(New_Node* root, string str)
{
if(root == NULL)
   return;

 if(root->data == '$')
 {
  print_Code(root->left, str + "0");
  print_Code(root->right, str + "1");
 }

 if(root->data != '$')
 {
   cout << root->data <<" : " << str << "\n";
   print_Code(root->left, str + "0");
   print_Code(root->right, str + "1");
 }
}

public:
  Hman_Code() {};
  ~Hman_Code()
  {
    delete top;
  }
  void Generate_Huffman_tree(vector<char>& data, vector<size_t>& freq, size_t size)
  {
   New_Node* left;
   New_Node* right;
   priority_queue<New_Node*, vector<New_Node*>, compare > minHeap;

for(size_t i = 0; i < size; ++i)
   {
      minHeap.push(new New_Node(data[i], freq[i]));
   }

while(minHeap.size() != 1)
    {
      left = minHeap.top();
minHeap.pop();

      right = minHeap.top();
minHeap.pop();

      top = new New_Node('$', left->freq + right->freq);
      top->left  = left;
      top->right = right;
      minHeap.push(top);
     }
    print_Code(minHeap.top(), "");
 }
};

 int main()
 {
  int n, f;
  char ch;
  Hman_Code set1;
  vector<char> data;
  vector<size_t> freq;
  cout<<"Enter the size of string text: ";
  cin>>n;
  cout<<"Enter the string :";
  for (int i=0;i<n;i++)
  {
      cin>>ch;
data.insert(data.end(), ch);
  }
  cout<<"Enter the equal frequencies \n";
  for (int i=0;i<n;i++)
  {
      cin>>f;
freq.insert(freq.end(), f);
  }

  size_t size = data.size();
  set1.Generate_Huffman_tree(data, freq, size);

  return 0;
}

The Output