In my Huffman Algorithm project, so far I have generated the codes for each character of the input file. I have also stored the characters and their corresponding codes in an unordered map. Now, I want to read our input string, and print the corresponding codes of each character in the output file. However, printing the codes in string format will not compress the file. I want to convert my string code to bits format. I know that we need to use a byte buffer, but I do not know how I will apply this concept to my code. Any help will be very much appreciated.
#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include<bitset>
#include<fstream>
#include<unordered_map>
#include<map>
using namespace std;
struct node
{
char c; //character in the string
int f; //Frequency of character in the string
node* next;
node* left, * right; //left and right child of binary tree respectively
node()
{
f = 0;
left = NULL;
right = NULL;
c = NULL;
next = NULL;
}
};
struct compare {
public:
bool operator()(node* a, node* b) // overloading both operators
{
return a->f > b->f; //To maintain the order of min heap priority queue
}
};
class Huffman
{
string filename; //The name of the file we want to encode
string text; //The text that will be encoded
priority_queue<node*, vector<node*>, compare> pq; //Priority queue that will contian characters of our string and their frequency
string encoded;
unordered_map <char, string> um;
public:
Huffman()
{
text = "";
encoded = "";
}
void FileRead()
{
cout << "Enter the name of the file you want to encode:";
cin >> filename;
fstream readfile(filename, fstream::in);
getline(readfile, text, '\0');
cout << text << endl;
readfile.close();
}
//Function which will calculate the frequency of characters in the string entered by the user
void CharacterFrequency()
{
for (int i = 0; i < text.length(); i++)
{
int sum = 0;
for (int j = 0; j < text.length(); j++)
{
if (j < i and text[i] == text[j])
{
break;
}
if (text[i] == text[j])
{
sum++;
}
}
if (sum != 0)
{
PriorityQueue(text[i], sum);
}
}
}
// This will push our characters and their frequencies into our STL min heap priority queue
void PriorityQueue(char ch, int freq)
{
node* n=new node; //pointer of type node is created
n->c = ch; //Pointer stores character
n->f = freq; //Pointer stores frequency of the character
pq.push(n); //The node is pushed into the priority queue
}
//Will display the whole priority queue. All of the elements will be popped from it as a result.
void PriorityQueueDisplay()
{
while (!pq.empty())
{
cout << (pq.top())->c<<" "<<(pq.top())->f << endl;
pq.pop();
}
}
//This function will create our Huffman Tree from a priority queue
void HuffmanTree()
{
node* n1, * n2; //The nodes that will be popped each time from the priority queue
//This loop will continue to pop out two nodes from the priority queue until only one nodes is left
//in the priority queue
while (pq.size()!=1)
{
n1 = pq.top();
pq.pop();
n2 = pq.top();
pq.pop();
node* z = new node; //Creation of new node of Huffman tree
z->left = n1;
z->right = n2;
z->f = (n1->f) + (n2->f); //Storing sum of the two popped nodes in Huffman tree node
z->c = '&'; //Assigning the new node a character that is not used in formal speech
pq.push(z); //Pushing the node into the priority queue again
}
node* root = pq.top(); //Making the last node the root node
EncodeAndPrintCodes(root,encoded); //Passing the root node and a string that will encode each character of our inputted string
}
//This function will recursively search for a character in the string, and will print it's corresponding code.
//It will do this for all our characters
void EncodeAndPrintCodes(node* root,string en)
{
if (root == NULL)
{
return ;
}
if (root->c != '&')
{
//cout << root->c << ":" << en;
StoreinMap(root->c, en);
}
EncodeAndPrintCodes(root->left, en + "0");
EncodeAndPrintCodes(root->right, en + "1");
}
//Will convert our code in string to bitstream and then store it in a text file
void CompressedFile(char ch, string code)
{
ofstream compressed;
compressed.open("CompressedFile.txt", ios::app | ios::out);
}
void StoreinMap(char ch, string code)
{
um.emplace(pair<char, string>(ch,code));
}
/*void DisplayEncoded()
{
cout << encoded;
}*/
//Displays the size of the priority queue
void DisplaySize()
{
cout<<pq.size();
}
};
int main()
{
Huffman obj;
obj.FileRead();
obj.CharacterFrequency();
//obj.PriorityQueueDisplay();
obj.HuffmanTree();
//obj.DisplaySize();
//obj.DisplayEncoded();
//obj.CompressedFile();
return 0;
}
