Implement by C++ code. Huffman Codes Description Suppose that we have to store a
ID: 3705529 • Letter: I
Question
Implement by C++ code.
Huffman Codes Description Suppose that we have to store a sequence of symbols (a file) efficiently, namely we want to minimize the amount of memory needed. For the sake of simplicity we assume that the symbols are restricted to the first 6 letters of the alphabet. For example, let us assume that the frequency of different symbols that you have to store are the following: symbol frequency 1000 150 200 800 300 Total 2500 As we have to store 6 different symbols, the obvious way is to encode each of them in 3 bits, as with 3 bits it is possible to encode 23 different symbols. With this encoding, we need 2500 x 3 7500 bits to store the above symbols. A different way to address the problem is the following. Instead of assigning to each symbol a code with the same length (i.e., number of bits), we assign shorter codes to symbols that are more frequent, and longer codes to symbols that are less frequent. One possible encoding according to this sequence is the following symbol encoding 10101 1011 100 10100 According to this encoding the number of required bits is 1000 x 1 + 150 x 5 + 200 x 4 + 800 x 2 +300 x 3 + 50 x 5-5300 This idea is at the basis of the programs used to compress files. First they analyze the input, then they choose the codes, and then they recode the input according to the determined codes. While this idea brings benefits in terms of the space requirements, using variable length codes presents some problems. Once we have coded a file according to a variable length code, we must also be able to decode it in the original format (i.e., once we have compressed the file, we want to able to decompress it). The encoding works only if the codes assigned to different characters are such that no code is a prefix of any other code. If this property does not hold, there isa problem of ambiguity when trying to decompress the sequence. You can prove that in the depicted example no code is a prefix of any other code. For example no code starts with 0 except from the code of A. So while decompressing the file, if we findia symbol whose code starts with 0, we know it's A. If we find a character whose code starts with 11, we know it's D. It can't be any other symbol, as no code starts with 11 other than D's code. And so on. How do we assign codes? This is done through a greedy algorithm. We assign the shortest code to the most frequent character, the second longest one to the second most frequent character, and so on. The figure below illustrates the first few stages of the algorithm.Explanation / Answer
#include <bits/stdc++.h>
using namespace std;
// A Huffman tree node struct
struct Min_Heap_Node {
char data;
unsigned freq;
// Left and right child
Min_Heap_Node *left, *right;
Min_Heap_Node(char data, unsigned freq)
{
left = right = NULL;
this->data = data;
this->freq = freq;
}
};
// For comparison of two heap nodes
struct compare {
bool operator()(Min_Heap_Node* l, Min_Heap_Node* r)
{
return (l->freq > r->freq);
}
};
// Prints huffman codes from root
void printCodes(struct Min_Heap_Node* root, string str)
{
if (!root)
return;
if (root->data != '$')
cout << root->data << ": " << str << " ";
printCodes(root->left, str + "0");
printCodes(root->right, str + "1");
}
// The main function that builds a Huffman Tree and
// print codes by traversing the built Huffman Tree
void HuffmanCodes(char data[], int freq[], int size)
{
struct Min_Heap_Node *left, *right, *top;
// Create a min heap & inserts all characters of data[]
priority_queue<Min_Heap_Node*, vector<Min_Heap_Node*>, compare> minHeap;
for (int i = 0; i < size; ++i)
minHeap.push(new Min_Heap_Node(data[i], freq[i]));
// Iterate while size of heap doesn't become 1
while (minHeap.size() != 1) {
// Extract the two minimum freq items from min heap
left = minHeap.top();
minHeap.pop();
right = minHeap.top();
minHeap.pop();
// Create a new internal node with
// frequency equal to the sum of the
// two nodes frequencies. Make the
// two extracted node as left and right children
// of this new node. Add this node
// to the min heap '$' is a special value
// for internal nodes, not used
top = new Min_Heap_Node('$', left->freq + right->freq);
top->left = left;
top->right = right;
minHeap.push(top);
}
// Print Huffman codes using
// the Huffman tree built above
printCodes(minHeap.top(), "");
}
// Test Function
int main()
{
char arr[] = { 'A', 'B', 'C', 'D', 'E', 'F' };
int freq[6] ;
int size = sizeof(arr) / sizeof(arr[0]);
std::cout << "Enter frequencies" << std::endl;
for(int i=0;i<size;i++)
cin>>freq[i];
HuffmanCodes(arr, freq, size);
return 0;
}
Input:
15
11
5
1
2
4
Output:-
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.