Part II: Implement text compression. In this part, use a text file as input, read through the text file, calculate the frequencies of each character, apply your Huffman Algorithm to encode the text file into a new file. You program should have the following functions, besides the above functions. Encode: takes a text file name, calls the Huffman coding algorithm, traverse the tree to get the code word, and then encode the text file into a new file. Decode: takes a prefix tree, and an encoded file, decode the file. What to turn in: Well documented source code in C++. Run your algorithm for 20 files and show the compression ratio of the size of the original file and the size of the compressed file. Show the ratios in the table. //code // C++ program for Huffman Coding #include #include #include #include #include using namespace std; /*structure to represent node of huffman tree*/ struct node { // One of the input characters char data; // Frequency of the character int freq; // Left and right child node *left, *right; /*constructor for node creation*/ node(char data, unsigned freq) { left = right = NULL; this->data = data; this->freq = freq; } }; /* comparison function for custom comparator, required for min heap*/ struct cmp { bool operator()(node* l, node* r) { return (l->freq > r->freq); } }; /* traverse function to print huffman code for each character*/ void traverse(struct node* root, string str) { if (!root) return; if (root->data != '$') cout << root->data << ": " << str << "\n"; traverse(root->left, str + "0"); traverse(root->right, str + "1"); } //takes a set of characters and their frequencies specified, returns a prefix tree. node* Huffman(map ma) { struct node *left, *right, *top; // Create a min heap & inserts all characters of data[] priority_queue, cmp> pq; for (auto it=ma.begin();it!=ma.end();it++) { pq.push(new node((*it).first,(*it).second)); } // traverse through heap until its size is 1 while (pq.size() != 1) { // Extract the two minimum // freq items from min heap left = pq.top(); pq.pop(); right = pq.top(); pq.pop(); top = new node('$', left->freq + right->freq); top->left = left; top->right = right; pq.push(top); } //return root of the prefic tree created above. return pq.top(); } // Driver program to test above functions int main() { int freq[26] = {0}; string str; /* take string input from user*/ cout << "Enter String :: "; cin >> str; map ma; //map to store character and its frequency for (int i = 0; i < str.length(); i++) { ma[str[i]]++; } node * ptr = Huffman(ma); traverse(ptr, ""); return 0; }

Part II: Implement text compression. In this part, use a text file as input, read through the text file, calculate the frequencies of each character, apply your Huffman Algorithm to encode the text file into a new file. You program should have the following functions, besides the above functions. Encode: takes a text file name, calls the Huffman coding algorithm, traverse the tree to get the code word, and then encode the text file into a new file. Decode: takes a prefix tree, and an encoded file, decode the file. What to turn in: Well documented source code in C++. Run your algorithm for 20 files and show the compression ratio of the size of the original file and the size of the compressed file. Show the ratios in the table. //code // C++ program for Huffman Coding #include #include #include #include #include using namespace std; /structure to represent node of huffman tree/ struct node { // One of the input characters char data; // Frequency of the character int freq; // Left and right child node left, right; /constructor for node creation/ node(char data, unsigned freq) { left = right = NULL; this->data = data; this->freq = freq; } }; /* comparison function for custom comparator, required for min heap/ struct cmp { bool operator()(node l, node* r) { return (l->freq > r->freq); } }; /* traverse function to print huffman code for each character/ void traverse(struct node root, string str) { if (!root) return; if (root->data != '$') cout << root->data << ": " << str << "\n"; traverse(root->left, str + "0"); traverse(root->right, str + "1"); } //takes a set of characters and their frequencies specified, returns a prefix tree. node* Huffman(map ma) { struct node left, right, top; // Create a min heap & inserts all characters of data[] priority_queue, cmp> pq; for (auto it=ma.begin();it!=ma.end();it++) { pq.push(new node((it).first,(it).second)); } // traverse through heap until its size is 1 while (pq.size() != 1) { // Extract the two minimum // freq items from min heap left = pq.top(); pq.pop(); right = pq.top(); pq.pop(); top = new node('$', left->freq + right->freq); top->left = left; top->right = right; pq.push(top); } //return root of the prefic tree created above. return pq.top(); } // Driver program to test above functions int main() { int freq[26] = {0}; string str; / take string input from user/ cout << "Enter String :: "; cin >> str; map ma; //map to store character and its frequency for (int i = 0; i < str.length(); i++) { ma[str[i]]++; } node ptr = Huffman(ma); traverse(ptr, ""); return 0; }

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter17: Linked Lists

Section: Chapter Questions

Problem 16PE

See similar textbooks

Related questions

Concept explainers

Question

Part II: Implement text compression.

In this part, use a text file as input, read through the text file, calculate the frequencies of each character, apply your Huffman Algorithm to encode the text file into a new file.

You program should have the following functions, besides the above functions.

Encode: takes a text file name, calls the Huffman coding algorithm, traverse the tree to get the code word, and then encode the text file into a new file.

Decode: takes a prefix tree, and an encoded file, decode the file.

What to turn in:

Well documented source code in C++.
Run your algorithm for 20 files and show the compression ratio of the size of the original file and the size of the compressed file. Show the ratios in the table.

//code

// C++ program for Huffman Coding #include <iostream> #include<queue> #include<vector> #include<string> #include<map> using namespace std; /*structure to represent node of huffman tree*/ struct node { // One of the input characters char data; // Frequency of the character int freq; // Left and right child node *left, *right; /*constructor for node creation*/ node(char data, unsigned freq) { left = right = NULL; this->data = data; this->freq = freq; } }; /* comparison function for custom comparator, required for min heap*/ struct cmp { bool operator()(node* l, node* r) { return (l->freq > r->freq); } }; /* traverse function to print huffman code for each character*/ void traverse(struct node* root, string str) { if (!root) return; if (root->data != '$') cout << root->data << ": " << str << "\n"; traverse(root->left, str + "0"); traverse(root->right, str + "1"); } //takes a set of characters and their frequencies specified, returns a prefix tree. node* Huffman(map<char,int> ma) { struct node *left, *right, *top; // Create a min heap & inserts all characters of data[] priority_queue<node*, vector<node*>, cmp> pq; for (auto it=ma.begin();it!=ma.end();it++) { pq.push(new node((*it).first,(*it).second)); } // traverse through heap until its size is 1 while (pq.size() != 1) { // Extract the two minimum // freq items from min heap left = pq.top(); pq.pop(); right = pq.top(); pq.pop(); top = new node('$', left->freq + right->freq); top->left = left; top->right = right; pq.push(top); } //return root of the prefic tree created above. return pq.top(); } // Driver program to test above functions int main() { int freq[26] = {0}; string str; /* take string input from user*/ cout << "Enter String :: "; cin >> str; map<char, int> ma; //map to store character and its frequency for (int i = 0; i < str.length(); i++) { ma[str[i]]++; } node * ptr = Huffman(ma); traverse(ptr, ""); return 0; }

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.