Huffman Coding:
Programming assignment 4 is about Huffman coding. There is Code Blocks project for starting the assignment (assig4_start). This programming assignment is based on material from the textbook chapter 14 and the textbook website www.fordtopp.com. Your assignment is to generate the code required for the member functions in the huffman class. The characters and character frequencies for the assignment are stored in characters and charFreq respectively in the Code Blocks project.
The first step is to generate the Huffman tree. As discussed in the textbook and in lecture the Huffman tree is stored in a vector of huffNodes called tree. The huffNode is already setup in the Code blocks Project. The buildTree function fills in this vector. Recall from lecture the Huffman algorithm uses a priority queue to generate the tree. You are required to use the priority queue from the standard template library for this function. The priority queue is already set up to use in the starting Code blocks project. Also, there is a Code Blocks project example using the priority queue. Material from the textbook and d_hcomp.h (from the website) may be useful for the buildTree function. Finding a characters location in the tree uses a form of hashing and the vector charLoc that will be discussed in lecture. The characters location is used when compressing text to find the bit codes corresponding to the text characters.
The second step is to generate codes for the characters. This is done in generateCodes. Again material from Chapter 14 and the website may be useful.
The functions listCodes and writeTree are used to output information about the Huffman tree. The required output is shown below.
The function Compress is used to generate binary code for the given string in the Code Blocks project. Similarly the function Decompress is used to generate text from a given binary code. To make the project easier to implement the binary codes are stored in strings.
Your program should generate the following output in the following order. Your table and numbers will different.
Huffman Codes
a 000010
b 0010
c 00000
d 00110
e 00111
f 0001
g 000011
m 01
y 1
Huffman Tree
Index ch freq left right parent numBits bitCode
0 a 26 -1 -1 9 6 000010
1 b 139 -1 -1 13 4 0010
2 c 42 -1 -1 10 5 00000
3 d 88 -1 -1 11 5 00110
4 e 98 -1 -1 11 5 00111
5 f 121 -1 -1 12 4 0001
6 g 35 -1 -1 9 6 000011
7 m 999 -1 -1 15 2 01
8 y 1999 -1 -1 16 1 1
9 61 0 6 10 0
10 103 2 9 12 0
11 186 3 4 13 0
12 224 10 5 14 0
13 325 1 11 14 0
14 549 12 13 15 0
15 1548 4 7 16 0
16 3547 15 8 0 0
Compress
bad = 001000001000110
Decompress
011 = my