The first step is to generate the Huffman tree. As discussed in the textbook and
ID: 3806197 • Letter: T
Question
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 character’s 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
Here's the starting project only having to adjust the huffman.h
huffman.h:
#ifndef HUFFMAN_H_INCLUDED
#define HUFFMAN_H_INCLUDED
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include "huffnode.h"
using namespace std;
class huffman
{
public:
huffman();
void buildTree(const string& characters, const vector<int>& charFreq);
void generateCodes();
void listCodes();
void writeTree();
string Compress(string str);
string Decompress(string bits);
private:
int numChars;
int numLeaves;
int treeSize;
//Huffman tree is stored in a vector of huffNode's
vector<huffNode> tree;
//Vector holding the locations of the characters (leaf nodes) in the Huffman tree
vector<int> charLoc;
//String of characters used to generate the Huffman tree
string characters;
//Corresponding frequencies for the characters
vector<int> charFreq;
};
huffman::huffman()
{
numChars = 0;
numLeaves = 0;
treeSize = 0;
charLoc.resize(256);
}
void huffman::buildTree(const string& chars, const vector<int>& freqs)
{
//priority queue used to build Huffman tree
priority_queue<huffNode, vector<huffNode>, greater<huffNode> > huffPQ;
}
void huffman::generateCodes()
{
}
void huffman::listCodes()
{
}
void huffman::writeTree()
{
}
string huffman::Compress(string str)
{
}
string huffman::Decompress(string bits)
{
}
#endif // HUFFMAN_H_INCLUDED
huffnode.h:
#ifndef HUFFNODE_H_INCLUDED
#define HUFFNODE_H_INCLUDED
#include <string>
using namespace std;
//NIL represents empty subtree
const short NIL = -1;
class huffNode
{
public:
unsigned char ch;
short left, right;
int freq;
int index;
int parent;
int numBits;
string bitCode;
huffNode();
friend bool operator> (huffNode lhs, huffNode rhs);
};
huffNode::huffNode()
{
ch = 0;
left = NIL;
right = NIL;
freq = 0;
index = 0;
parent = 0;
numBits = 0;
bitCode = "";
}
bool operator>(huffNode lhs, huffNode rhs)
{
return lhs.freq > rhs.freq;
}
#endif // HUFFNODE_H_INCLUDED
main:
#include "huffnode.h"
#include "huffman.h"
using namespace std;
int main()
{
string characters;
vector<int> charFreq;
characters = "etaoinsrhldcu";
charFreq = {125,93,80,76,73,71,65,61,55,41,40,31,27};
huffman huff1;
huff1.buildTree(characters, charFreq);
huff1.generateCodes();
huff1.listCodes();
huff1.writeTree();
string charStr, bitCode;
charStr = "end";
//bitCode = huff1.Compress(charStr);
cout << "Compress" << endl;
cout << charStr << " = " << bitCode << endl << endl;
bitCode = "100010101010101000";
//charStr = huff1.Decompress(bitCode);
cout << "Decompress" << endl;
cout << bitCode << " = " << charStr << endl << endl;
//Keep Console window open until keyboard input
int hold;
cin >> hold;
}
Explanation / Answer
#ifndef HUFFMAN_H_INCLUDED
#define HUFFMAN_H_INCLUDED
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include "huffnode.h"
using namespace std;
class huffman
{
public:
huffman();
void buildTree(const string& characters, const vector<int>& charFreq);
void generateCodes();
void listCodes();
void writeTree();
string Compress(string str);
string Decompress(string bits);
private:
int numChars;
int numLeaves;
int treeSize;
//Huffman tree is stored in a vector of huffNode's
vector<huffNode> tree;
//Vector holding the locations of the characters (leaf nodes) in the Huffman tree
vector<int> charLoc;
//String of characters used to generate the Huffman tree
string characters;
//Corresponding frequencies for the characters
vector<int> charFreq;
};
huffman::huffman()
{
numChars = 0;
numLeaves = 0;
treeSize = 0;
charLoc.resize(256);
}
void huffman::buildTree(const string& chars, const vector<int>& freqs)
{
//priority queue used to build Huffman tree
priority_queue<huffNode, vector<huffNode>, greater<huffNode> > huffPQ;
}
void huffman::generateCodes()
{
}
void huffman::listCodes()
{
}
void huffman::writeTree()
{
}
string huffman::Compress(string str)
{
}
string huffman::Decompress(string bits)
{
}
#endif // HUFFMAN_H_INCLUDED
huffnode.h:
#ifndef HUFFNODE_H_INCLUDED
#define HUFFNODE_H_INCLUDED
#include <string>
using namespace std;
//NIL represents empty subtree
const short NIL = -1;
class huffNode
{
public:
unsigned char ch;
short left, right;
int freq;
int index;
int parent;
int numBits;
string bitCode;
huffNode();
friend bool operator> (huffNode lhs, huffNode rhs);
};
huffNode::huffNode()
{
ch = 0;
left = NIL;
right = NIL;
freq = 0;
index = 0;
parent = 0;
numBits = 0;
bitCode = "";
}
bool operator>(huffNode lhs, huffNode rhs)
{
return lhs.freq > rhs.freq;
}
#endif // HUFFNODE_H_INCLUDED
main:
#include "huffnode.h"
#include "huffman.h"
using namespace std;
int main()
{
string characters;
vector<int> charFreq;
characters = "etaoinsrhldcu";
charFreq = {125,93,80,76,73,71,65,61,55,41,40,31,27};
huffman huff1;
huff1.buildTree(characters, charFreq);
huff1.generateCodes();
huff1.listCodes();
huff1.writeTree();
string charStr, bitCode;
charStr = "end";
//bitCode = huff1.Compress(charStr);
cout << "Compress" << endl;
cout << charStr << " = " << bitCode << endl << endl;
bitCode = "100010101010101000";
//charStr = huff1.Decompress(bitCode);
cout << "Decompress" << endl;
cout << bitCode << " = " << charStr << endl << endl;
//Keep Console window open until keyboard input
int hold;
cin >> hold;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.