Question

Read through "The Huffman Code" on page 415 of the book. Write a program to implement Huffman coding and decoding. It should do the following: Accept a text message, possibly of more than one line. Create a Huffman tree for this message. Create a code table. Encode the message into binary. Decode the message from binary back to text.

Answer 1

CONSIDERING THE CONDITIONS AND PARAMETERS FROM QUESTION:

C++ Code:

// C++ program to encode and decode a string using Huffman Coding.
#include <bits/stdc++.h>
#define MAX_TREE_HT 256
using namespace std;
  
// to map each character its huffman value
map<char, string> codes;
  
// to store the frequency of character of the input data
map<char, int> freq;
  
// A Huffman tree node
struct MinHeapNode
{
char data; // One of the input characters
int freq; // Frequency of the character
MinHeapNode *left, *right; // Left and right child
  
MinHeapNode(char data, int freq)
{
left = right = NULL;
this->data = data;
this->freq = freq;
}
};
  
// utility function for the priority queue
struct compare
{
bool operator()(MinHeapNode* l, MinHeapNode* r)
{
return (l->freq > r->freq);
}
};
  
// utility function to print characters along with
// there huffman value
void printCodes(struct MinHeapNode* root, string str)
{
if (!root)
return;
if (root->data != '$')
cout << root->data << ": " << str << "\n";
printCodes(root->left, str + "0");
printCodes(root->right, str + "1");
}
  
// utility function to store characters along with
// there huffman value in a hash table, here we
// have C++ STL map
void storeCodes(struct MinHeapNode* root, string str)
{
if (root==NULL)
return;
if (root->data != '$')
codes[root->data]=str;
storeCodes(root->left, str + "0");
storeCodes(root->right, str + "1");
}
  
// STL priority queue to store heap tree, with respect
// to their heap root node value
priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minHeap;
  
// function to build the Huffman tree and store it
// in minHeap
void HuffmanCodes(int size)
{
struct MinHeapNode *left, *right, *top;
for (map<char, int>::iterator v=freq.begin(); v!=freq.end(); v++)
minHeap.push(new MinHeapNode(v->first, v->second));
while (minHeap.size() != 1)
{
left = minHeap.top();
minHeap.pop();
right = minHeap.top();
minHeap.pop();
top = new MinHeapNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
minHeap.push(top);
}
storeCodes(minHeap.top(), "");
}
  
// utility function to store map each character with its
// frequency in input string
void calcFreq(string str, int n)
{
for (int i=0; i<str.size(); i++)
freq[str[i]]++;
}
  
// function iterates through the encoded string s
// if s[i]=='1' then move to node->right
// if s[i]=='0' then move to node->left
// if leaf node append the node->data to our output string
string decode_file(struct MinHeapNode* root, string s)
{
string ans = "";
struct MinHeapNode* curr = root;
for (int i=0;i<s.size();i++)
{
if (s[i] == '0')
curr = curr->left;
else
curr = curr->right;
  
// reached leaf node
if (curr->left==NULL and curr->right==NULL)
{
ans += curr->data;
curr = root;
}
}
// cout<<ans<<endl;
return ans+'\0';
}
  
// Driver program to test above functions
int main()
{
string str = "Welcome All";
string encodedString, decodedString;
calcFreq(str, str.length());
HuffmanCodes(str.length());
cout << "Code Table:\n";
for (auto v=codes.begin(); v!=codes.end(); v++)
cout << v->first <<' ' << v->second << endl;
  
for (auto i: str)
encodedString+=codes[i];
  
cout << "\nEncoded Huffman data:\n" << encodedString << endl;
  
decodedString = decode_file(minHeap.top(), encodedString);
cout << "\nDecoded Huffman Data:\n" << decodedString << endl;
return 0;
}

You Have not given in which language to implement but i ahve used C++ for the implementation

PLEASE UPVOTE ITS VERY NECESSARY FOR ME...............