huffman Algorithm
The Huffman Algorithm is a widely-used, lossless data compression technique that was developed by David A. Huffman in 1952. It is a variable-length, prefix coding algorithm that works by constructing an optimal binary tree using the frequency of each character in the input data. The basic idea behind Huffman coding is to assign shorter codes to more frequently occurring characters and longer codes to less frequent characters, thereby reducing the overall size of the data being encoded. This algorithm is particularly effective when applied to text, image, and audio files, where certain patterns or symbols occur more frequently than others.
To create the optimal binary tree, the Huffman Algorithm begins by assigning each character or symbol in the input a leaf node with a weight equal to its frequency. It then constructs the tree from the bottom up by repeatedly selecting the two nodes with the lowest weights, combining them into a new node, and assigning the combined weight to this new node. This process continues until all nodes are part of a single tree. Once the tree is constructed, the unique binary code for each character can be determined by traversing the tree from the root to the leaf node, assigning a "0" for each left branch and a "1" for each right branch along the way. The resulting set of binary codes can be used to efficiently compress the original data without any loss of information, allowing for effective storage and transmission.
// C++ program for Huffman Coding
#include <iostream>
#include <queue>
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 << "\n";
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;
}
