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
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; }
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
