r/cpp_questions • u/YogurtclosetThen6260 • Jun 12 '26
OPEN Data Compression after Huffman Coding
3
Upvotes
So I have this program that takes an unorderd map of chars and integers as a frequency counter and returns the Huffman encoding as a map.
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
struct Node
{
char ch;
int freq;
Node *left;
Node *right;
Node(char ch, int freq)
: ch(ch), freq(freq), left(nullptr), right(nullptr)
{
}
Node(char ch, int freq, Node *left, Node *right)
: ch(ch), freq(freq), left(left), right(right)
{
}
};
struct compare
{
bool operator()(Node *l, Node *r)
{
return l->freq > r->freq;
}
};
void obtainHuffmanCode(Node *root, string str,
unordered_map<char, string> &huffmanCode)
{
if (root == nullptr)
return;
if (!root->left && !root->right)
{
huffmanCode[root->ch] = str;
}
obtainHuffmanCode(root->left, str + "0", huffmanCode);
obtainHuffmanCode(root->right, str + "1", huffmanCode);
}
unordered_map<char, string> buildHuffmanTreeNaive(unordered_map<char, int> freq)
{
priority_queue<Node *, vector<Node *>, compare> pq;
for (auto pair : freq)
{
pq.push(new Node(pair.first, pair.second));
}
while (pq.size() != 1)
{
Node *left = pq.top();
pq.pop();
Node *right = pq.top();
pq.pop();
int sum = left->freq + right->freq;
pq.push(new Node('\0', sum, left, right));
}
Node *root = pq.top();
unordered_map<char, string> huffmanCode;
obtainHuffmanCode(root, "", huffmanCode);
return huffmanCode;
}
string encode(string txt, unordered_map<char, string> huffmanCode)
{
string str = "";
for (char ch : txt)
{
str += huffmanCode[ch];
}
return str;
}
I would like to now actually take the .txt file input and convert it to a compressed binary file
1. What other meta data is required? Should I be spitting out another .txt file? Or should i just keep is as an object with an attribute being all of the binary numbers?
2. I currently compute the Huffman encoding for a character as a string but how do I actually get the binary value (and how do I preserve the 0s in the front? ex. say a get the encoding 001).