We run the Huffman algorithm on a set of symbols paired with their relative freq

Question

We run the Huffman algorithm on a set of symbols paired with their relative
frequencies, to produce a trie that creates a correspondence between the
symbols and variable-length binary strings. Consider now what would be
required to actually implement the Huffman algorithm: identity (in the
language of your choice or pseudocode c++) what class(es) or struct(s) you would
need to create to represent the tree and support the algorithm (including
their elds); and what library ADTs would you make use of, and how.
(Note: this is essentially the early design phase of a Huffman implementa-
tion, but that's all|no code is expected here!)

Explanation / Answer

a) The algorithm for Huffman Coding is given below.

Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree.

1. Create a leaf node for each unique character and build a min heap of all leaf nodes (Min Heap is used as a priority queue. The value of frequency field is used to compare two nodes in min heap. Initially, the least frequent character is at root)

2. Extract two nodes with the minimum frequency from the min heap.

3. Create a new internal node with frequency equal to the sum of the two nodes frequencies. Make the first extracted node as its left child and the other extracted node as its right child. Add this node to the min heap.

4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete.

b) The struct used in the implmentation is:

c) List of ADTs used:

Here is the code:

CODE

=====================

// C++ program for Huffman Coding

#include <bits/stdc++.h>

using namespace std;

// A Huffman tree node

struct MinHeapNode {

// One of the input characters

char data;

// Frequency of the character

unsigned freq;

// Left and right child

MinHeapNode *left, *right;

MinHeapNode(char data, unsigned freq)

{

left = right = NULL;

this->data = data;

this->freq = freq;

}

};

// For comparison of

// two heap nodes (needed in min heap)

struct compare {

bool operator()(MinHeapNode* l, MinHeapNode* r)

{

return (l->freq > r->freq);

}

};

// Prints huffman codes from

// the root of Huffman Tree.

void printCodes(struct MinHeapNode* 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 MinHeapNode *left, *right, *top;

// Create a min heap & inserts all characters of data[]

priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minHeap;

for (int i = 0; i < size; ++i)

minHeap.push(new MinHeapNode(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 MinHeapNode('$', 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(), "");

}

// Driver program to test above functions

int main()

{

char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };

int freq[] = { 5, 9, 12, 13, 16, 45 };

int size = sizeof(arr) / sizeof(arr[0]);

HuffmanCodes(arr, freq, size);

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.