Huffman coding || Huffman coding with example || Huffman coding method || Huffman coding in c/c++ ||Huffman coding programe in c/c++/data structure /java || what is Huffman coding || Huffman complete,
Huffman coding
Huffman Algorithm was developed by David Huffman in 1951.
This is a technique which is used in a data compression or it can be said that it is a coding technique which is used for encoding data.
This technique is a mother of all data compression scheme.
This idea is basically dependent upon the frequency, i.e. the frequency of the corresponding character which needs to be compressed, and by that frequency, only Huffman code will be generated.
In case of Huffman coding, the most generated character will get the small code and least generated character will get the large code.
Huffman tree is a specific method of representing each symbol.
This technique produces a code in such a manner that no codeword is a prefix of some other code word. These codes are called as prefix code.
Algorithm for Huffman code
1. Input:-Number of message with frequency count.
2. Output: - Huffman merge tree.
3. Begin
4. Let Q be the priority queue,
5. Q= {initialize priority queue with frequencies of
all symbol or message}
6. Repeat n-1 times
7. Create a new node Z
8. X=extract_min(Q)
9. Y=extract_min(Q)
10. Frequency(Z) =Frequency(X) +Frequency(y);
11. Insert (Z, Q)
12. End repeat
13. Return (extract_min(Q))
14. End.
Method
The following general procedure is applied for construction a Huffman tree:
Search for the two nodes having the lowest frequency, which are not yet assigned to a parent node.
Couple these nodes together to a new interior node.
Add both the frequencies and assign this value to the new interior node.
The procedure has to be repeated until all nodes are combined together in a root node.
Example:
Let obtain a set of Huffman code for the message (m1.....m7) with relative frequencies (q1.....q7) = (12,5,20,8,10,4,7). Let us draw the Huffman tree for the given set of codes.
Step 1) Arrange the data in ascending order in a table.
4,5,7,8,10,12,20
Step 2) Combine first two entries of a table and by this create a parent node.
Step 3)
A) Remove the entries 4 and 5 from the table and inert 9 at its appropriate position. 7,8,9,10,12,20
Combine minimum value of table and create a parent node.
B) Now remove the entries 7 and 8 from the table and insert 15 at its appropriate position. 9,10,12,15,20
Combine minimum value of two blocks and create a parent node.
C) Remove the entries 9 and 10 from the table and insert 19 at its proper position. 12,15,19,20.
Combine minimum value of two blocks and create parent node.
D) Remove the entries 15 and 12 from the table and insert 27 at its appropriate position. 19,20,27
Combine minimum value of two blocks and create parent node.
E) Remove the entries 19 and 20 from the table and insert 39 in the table. 27,39
Combine minimum value of two blocks and create parent node.
Step 4) Now assign left child as 0 and right child as 1 to encode the frequencies.
Huffman Coding Algorithm Example
Construct a Huffman tree by using these nodes.
Solution:
Step 1: According to the Huffman coding we arrange all the elements (values) in ascending order of the frequencies.
Step 2: Insert first two elements which have smaller frequency.
Step 3: Taking next smaller number and insert it at correct place.
Step 4: Next elements are F and D so we construct another subtree for F and D.
Step 5: Taking next value having smaller frequency then add it with CEA and insert it at correct place.
Step 6: We have only two values hence we can combined by adding them.
Huffman Tree
Now the list contains only one element i.e. FDCEAB having frequency 68 and this element (value) becomes the root of the Huffman tree.
Program in C++
#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;
// A Tree node
struct Node
{
char ch;
int freq;
Node *left, *right;
};
// Function to allocate a new tree node
Node* getNode(char ch, int freq, Node* left, Node* right)
{
Node* node = new Node();
node->ch = ch;
node->freq = freq;
node->left = left;
node->right = right;
return node;
}
// Comparison object to be used to order the heap
struct comp
{
bool operator()(Node* l, Node* r)
{
// highest priority item has lowest frequency
return l->freq > r->freq;
}
};
// traverse the Huffman Tree and store Huffman Codes
// in a map.
void encode(Node* root, string str,
unordered_map<char, string> &huffmanCode)
{
if (root == nullptr)
return;
// found a leaf node
if (!root->left && !root->right) {
huffmanCode[root->ch] = str;
}
encode(root->left, str + "0", huffmanCode);
encode(root->right, str + "1", huffmanCode);
}
// traverse the Huffman Tree and decode the encoded string
void decode(Node* root, int &index, string str)
{
if (root == nullptr) {
return;
}
// found a leaf node
if (!root->left && !root->right)
{
cout << root->ch;
return;
}
index++;
if (str[index] =='0')
decode(root->left, index, str);
else
decode(root->right, index, str);
}
// Builds Huffman Tree and decode given input text
void buildHuffmanTree(string text)
{
// count frequency of appearance of each character
// and store it in a map
unordered_map<char, int> freq;
for (char ch: text) {
freq[ch]++;
}
// Create a priority queue to store live nodes of
// Huffman tree;
priority_queue<Node*, vector<Node*>, comp> pq;
// Create a leaf node for each character and add it
// to the priority queue.
for (auto pair: freq) {
pq.push(getNode(pair.first, pair.second, nullptr, nullptr));
}
// do till there is more than one node in the queue
while (pq.size() != 1)
{
// Remove the two nodes of highest priority
// (lowest frequency) from the queue
Node *left = pq.top(); pq.pop();
Node *right = pq.top(); pq.pop();
// Create a new internal node with these two nodes
// as children and with frequency equal to the sum
// of the two nodes' frequencies. Add the new node
// to the priority queue.
int sum = left->freq + right->freq;
pq.push(getNode('\0', sum, left, right));
}
// root stores pointer to root of Huffman Tree
Node* root = pq.top();
// traverse the Huffman Tree and store Huffman Codes
// in a map. Also prints them
unordered_map<char, string> huffmanCode;
encode(root, "", huffmanCode);
cout << "Huffman Codes are :\n" << '\n';
for (auto pair: huffmanCode) {
cout << pair.first << " " << pair.second << '\n';
}
cout << "\nOriginal string was :\n" << text << '\n';
// print encoded string
string str = "";
for (char ch: text) {
str += huffmanCode[ch];
}
cout << "\nEncoded string is :\n" << str << '\n';
// traverse the Huffman Tree again and this time
// decode the encoded string
int index = -1;
cout << "\nDecoded string is: \n";
while (index < (int)str.size() - 2) {
decode(root, index, str);
}
}
// Huffman coding algorithm
int main()
{
string text = "Huffman coding is a data compression algorithm.";
buildHuffmanTree(text);
return 0;
}
Comments
Post a Comment