Answer:

Algorithm for Huffman:

Input:

Characters : [C 1 ,C 2 ,…………C n ]

Weight : [W 1 ,W 2 ,………W n ]

where W i is the weight of C i

Step 1 :

One-node binary tree list is initiated.

Step 2 :

Repeat the process for n-1 times:

• search for the lowest weight in the list W' and W''and draw two trees T' and T''

• the trees are replaced with binary tree which contains the root value as W' + W''

• the subtree pointers are labeled as 0 and 1 respectively

Step 3 :

The character's code can be obtained by label in the path from root to the current node

Given:

Huffman code developed in "Exercise-7":

Consider the Message: "feed a deaf aged hag":

The Huffman code for the value "f" is as follows:

The Huffman code for the value "e" is as follows:

The Huffman code for the value "e" is as follows:

The Huffman code for the value "d" is as follows:

The Huffman code for the value "a" is as follows:

The Huffman code for the value "d" is as follows:

The Huffman code for the value "e" is as follows:

The Huffman code for the value "a" is as follows:

The Huffman code for the value "f" is as follows:

The Huffman code for the value "a" is as follows:

The Huffman code for the value "g" is as follows:

The Huffman code for the value "e" is as follows:

The Huffman code for the value "d" is as follows:

The Huffman code for the value "h" is as follows:

The Huffman code for the value "a" is as follows:

The Huffman code for the value "g" is as follows:

Thus the encoded message is as follows:

Answer:

Algorithm for Huffman:

Input:

Characters : [C 1 ,C 2 ,…………C n ]

Weight : [W 1 ,W 2 ,………W n ]

where W i is the weight of C i

Step 1 :

One-node binary tree list is initiated.

Step 2 :

Repeat the process for n-1 times:

• Search for the lowest weight in the list W' and W'' and draw two trees T' and T''

• The trees are replaced with binary tree which contains the root value as W' + W''

• The subtree pointers are labeled as 0 and 1 respectively

Step 3 :

The character's code can be obtained by label in the path from root to the current node

Given:

Use the given table to construct the Huffman code:

As per the Huffman's algorithm, a list of one-node binary tree is constructed in order of increasing order of their weight.

The two trees are selected that has the smallest weights; thus it results

.

From the list, select two of minimal weights "

".

From the list of 3 binary trees, select two of minimal weights "

".

From the list, select two of minimal weights "

":

From the list, select two of minimal weights "

".

Combine the two binary trees to get single resulting Huffman tree:

Complete Huffman tree.

Thus the Huffman code obtained from the tree:

Answer:

Problem plan:

• Include the required header files into the program.

• Use "struct" for tree node

• Allocate new tree to a node

• Define a function "encoding ()" to encode the string.

o check if the root node is null

o check if the leaf node is found

o call the function "encoding ()" to append 0

o call the function "encoding ()" to append 1

• Define a function "huff_tree ()" to generate huffman code

o Use map tp count the frequency

o store live nodes

o create leaf node and push the elements

o perform until more than 1 node in the tree

o pointer is stored to the root of the Huffman

o traverse and store the huffman codes

o print the huffman codes

• Define "main()" to demonstrate huffman technique

o Declare variables

o get input from user

o call the function "huff_tree()" to generate huffman code

Program:

/ ***********************************************************Run the code in c++ 11 compiler *

*Program to construct Huffman code and the encode a *

*message entered by the user *

********************************************************** /

/ / include header files

#include

#include

#include

#include

using namespace std;

/ / struct for tree node

struct Node

{

int f;

char ch;

Node *l, *r;

};

/ / allocation of new tree to a node

Node* g_N(char ch, int f, Node* l, Node* r)

{

Node* node = new Node();

/ / assign the node elements

node- ch = ch;

node- f = f;

node- l = l;

node- r = r;

/ / return after all the process has been done

return node;

}

/ / object for comparison

struct comp

{

bool operator()(Node* l, Node* r)

{

/ / the item with highest priority has lowest / / frequency

return l- f r- f;

}

};

/ / traverse and store in an huffman map

void encoding(Node* root, string tx, map huffmanCode)

{

/ / check if the root node is null

if (root == NULL)

return;

/ / if the leaf node is found

if (!root- l !root- r)

huffmanCode[root- ch] = tx;

/ / cal the function to append 0

encoding(root- l, tx + "0", huffmanCode);

/ / call the function to append 1

encoding(root- r, tx + "1", huffmanCode);

}

/ / / build tree and decode

void huff_tree(string inp)

{

/ / to count the frequency

map f;

for (char ch : inp)

f[ch]++;

/ / store live nodes

priority_queue , comp pq;

/ / create leaf node and push the elements

for (auto it : f)

pq.push(g_N(it.first, it.second, NULL, NULL));

/ / perform until more than 1 node in the tree

while (pq.size() != 1)

{

/ / remove nodes with highest priotity

Node *l = pq.top(); pq.pop();

Node *r = pq.top(); pq.pop();

/ / internal node is created and then a new node / / is added

int sum = l- f + r- f;

pq.push(g_N('\0', sum, l, r));

}

/ / pointer is stored to the root of the huffman tree

Node* root = pq.top();

/ / traverse and store the huffman codes

map huffmanCode;

encoding(root, "", huffmanCode);

/ / print the huffman codes

cout "Huffman Code :\n" endl;

for (auto it : huffmanCode)

cout it.first " " it.second endl;

/ / actual string

cout "\n actual string was :\n";

cout inp endl;

/ / print encoded string

string tx = "";

for (char ch : inp)

tx += huffmanCode[ch];

cout "\n encoded string is :\n" tx endl;

}

/ / main function to perform huffman encoding

int main()

{

/ / variable declaration

string inp;

cout "enter the string you want to decode:";

/ / get input from user

cin inp;

/ / call the fuction to generate huffman code

huff_tree(inp);

return 0;

}

Sample Output:

enter the string you want to decode:goodmorning

Huffman Code :

d 1100

g 00

i 1101

m 011

n 111

o 10

r 010

actual string was :

goodmorning

encoded string is :

001010110001110010111110111100