f



Huffman coding

respected sir,
Please send me full coding of this program.
thank you.
Phase 1 Tasks
Read the message to be encoded and compute character frequencies for
each character in the message (include the EOF character). Store these
frequencies in an array indexed by each character's ASCII code. Print
out each character with its frequency. 
Create a priority queue prioritized by the smallest frequency for the
characters in the message. The priority queue is to be implemented
using the heap ADT. The code has been covered in the lectures. Using
the priority queue, create a Huffman tree for the message. Your
program should print the tree out. Printing a binary horizontally was
done in the last practice assignement. 
Using the generated Huffman tree, traverse it and create and print out
a code table for the given input message below:  
Manny's mom and dad are Huffman encoding experts.

You must include the end of line character. Your table would be
different; the output format should be similar to the table below.



                   CODE TABLECHARACTER ASCII FREQUENCY BIT PATTERN
CODELENGTH (# of
bits)------------------------------------------------------------   NL
10	  1	   110011      6         32	  7	   100         3   '     39	  1
101111      6   .     46	  1	   111000      6   H     72	  1	   00101 
5   M     77	  1	   110110      6   a     97	  5	   010         3   c 
99	  1	   101100      6   d    100	  4	   1010        4   e    101	  4
1111        4   f    102	  2	   11101       5   g    103	  1	   00010 
5   i    105	  1	   110111      6   m    109	  3	   0011        4   n 
110	  6	   011         3   o    111	  2	   11000       5   p    112	 
1	   101101      6   r    114	  2	   11010       5   s    115	  2	  
0000        4   t    116	  1	   111001      6   u    117	  1	   00100 
5   x    120	  1	   101110      6   y    121	  1	   00011       5
Phase 2 Tasks
Using the code table, write an encode function which encodes the
message in a bitset (a class in the STL which provides for bit
processing) and print the encoded message out as a bit pattern.

50 characters encoded in 216 bits, 4.320000 bits per char. (your's may
be different)


Write a decode function that decodes the bit patterns back into the
original characters using the Huffman tree: 
DECODED MESSAGE: Manny's mom and dad are Huffman encoding experts.
Huffman Binary Tree
The Huffman tree is a binary tree (not a binary search tree). The leaf
nodes contain the characters that make up the message; each leaf node
contains one character. The node also contains the frequency of the
character. The internal nodes contain only frequencies. The frequency
in an internal node is equal to the sum of the frequencies of its left
and right children nodes. The class TreeNode provided with this
assignment has all the necessary mechanism to generate tree nodes,
both leaf and internal, for the Huffman binary tree. 
The tree nodes, leaf and internal, will be placed in a priority queue
as the tree building algorithm proceeds. The priority queue will be
implemented using the heap ADT. Code for heap ADT has been provided.
The heap ADT in the files provided can contain pointer to tree nodes,
i.e., 

  // create a tree node with the ith character of the message and its
frequency
  TreeNode* node = new TreeNode(msg[i], freq[i]);
  heap.insert( freq[i], node );
   ....
   ....
  // insert a new internal node
  TreeNode* n1 = heap.removeMin();
  TreeNode* n2 = heap.removeMin();
  int sumOfFrequencies = n1->getFrequency()+n2->getFrequency();
  TreeNode* internalNode = new TreeNode(n1->getCharacter(),
sumOfFrequencies);
  internalNode->setLeft( n1);
  internalNode->setRight( n2);
  heap.insert( sumOfFrequencies, internalNode );

Eventually, there will be only one tree node in the priority queue
(heap). This will be the root of the Huffman tree. Standard tree
traversal methods can be used to visit the tree. 

0
1/28/2004 1:22:48 PM
comp.soft-sys.matlab 211266 articles. 22 followers. lunamoonmoon (257) is leader. Post Follow

0 Replies
426 Views

Similar Articles

[PageSpeed] 24

Reply: