Write a program that takes any input text and produces both a frequency table an
ID: 3927469 • Letter: W
Question
Write a program that takes any input text and produces both a frequency table and the corresponding Huffman code. Take approximately 360 words from any English document as your input text. Ignore all blanks, all punctuation marks, al special symbols. Create an input file with this input text. Construct the frequency table according to the input text read from the file, in the form: The Frequency's MUST be listed, in order, from largest (at the top) to smallest (at the bottom). Only the BELOW Tablet Format will be accepted: Letter Comma Space Percentage Example: A, 2.5% Then, using the Huffman algorithm, construct the optimal prefix binary code for the table. Design your program to read the input from the input file "infile.dat" Your program must produce the output, in the file "outfile.dat". consisting of the frequency table for the source text. the Huffman code for each letter and digit in the source code, and the length of the coded message in terms of number of bits. MUST use exact file names providedExplanation / Answer
#include "FileLoader.h"
#include "CharFreqInVector.h"
#include "LeafNode.h"
#include "TreeFromListConstruction.h"
#include "GenerateHuffFile.h"
#include "Decompressor.h"
#include <crtdbg.h>
#include <list>
#include <fstream>
int main()
{
{
vector<char> vFile;
vector<char> cvFile;
vector<char> charByte;
vector<int> frequency;
FileLoader File("shakespeare.txt");
vFile = File.loadFileIntoVector();
CharFreqInVector Frequency(vFile);
Frequency.calculateFrequency();
charByte = Frequency.getEachChar();//Frequency.getEachChar(); // need copies of the char and its frequency to put to a LeafNode
frequency = Frequency.getEachFrequency();//Frequency.getEachFrequency();
TreeFromListConstruction tree(charByte, frequency);
//passing into a class that can modify the list into a binary tree
tree.formTree(); //modify the list into a binary tree
GenerateHuffFile Huff(tree.getTree(), vFile, "compressed.txt",charByte, frequency);
Huff.writeHuffFile();
///////////////////////////////////////////////////////////////////////////////////////decompression time
FileLoader cFile("compressed.txt");
cvFile = cFile.loadFileIntoVector();
CharFreqInVector Formated(cvFile);
Formated.calcFreqInCompressed();
charByte = Formated.getEachChar();//Frequency.getEachChar(); // need copies of the char and its frequency to put to a LeafNode
frequency = Formated.getEachFrequency();//Frequency.getEachFrequency();
TreeFromListConstruction recontructedTree(charByte, frequency);
recontructedTree.formTree();
Decompressor uncompress(recontructedTree.getTree(), cvFile, "compressed.txt", "decompressed.txt", vFile.size());
uncompress.remakeFile();
}
cout << _CrtDumpMemoryLeaks(); //no memory leaks yay!
system("pause");
return 0;
}
CharFreqInVector.h
#ifndef CHARFREQINVECTOR_H
#define CHARFREQINVECTOR_H
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
class CharFreqInVector
{
public:
CharFreqInVector(vector<char>& charVec);
~CharFreqInVector();
void clearVectors();
void calculateFrequency();
void calcFreqInCompressed();
void displayFrequency();
int convertStringToInt(string aString);
vector<char> getEachChar(){return eachChar;}
vector<int> getEachFrequency(){return eachFrequency;}
private:
vector<char> charVector;
vector<char> eachChar;
vector<int> eachFrequency;
static const int streamSize = 255;
};
#endif
/CharFreqInVector.cpp
#include "CharFreqInVector.h"
CharFreqInVector::CharFreqInVector(vector<char>& charVec)
{
charVector = charVec;
}
void CharFreqInVector::displayFrequency()
{
for(unsigned int i = 0; i < eachChar.size(); i++)
{
cout <<"char:" << eachChar[i] << " freq:" << eachFrequency[i] << endl;
}
}
void CharFreqInVector::calcFreqInCompressed()
{
string intString;
int j = 0;
int i = 0;
while(1)
{
eachChar.push_back(' ');
eachFrequency.push_back(0);
eachChar[j] = charVector[i];
i++;
while(charVector[i] != ',')
{
intString.push_back(charVector[i]);
i++;
}
i++;
eachFrequency[j] = convertStringToInt(intString);
intString.clear();
if(eachChar[j] == '0' || eachFrequency[j] == 0)
{
eachChar.pop_back();
eachFrequency.pop_back();
break;
}
j++;
}
}
int CharFreqInVector::convertStringToInt(string aString)
{
int anInt;
stringstream myStream;
myStream.str(aString);
myStream >> anInt;
return anInt;
}
void CharFreqInVector::calculateFrequency()
{
bool isAlreadyIn = false;
unsigned int i = 0;
unsigned int j = 0;
for(i = 0; i < charVector.size(); i++)
{
for(j = 0; j < eachChar.size(); j++)
{
if(charVector[i] == eachChar[j])
{
eachFrequency[j]++;
isAlreadyIn = true;
break;
}
}
if(!isAlreadyIn)
{
eachChar.push_back(charVector[i]);
eachFrequency.push_back(1);
}
else
isAlreadyIn = false;
}
}
void CharFreqInVector::clearVectors()
{
charVector.clear();
eachChar.clear();
eachFrequency.clear();
}
CharFreqInVector::~CharFreqInVector()
{
clearVectors();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//Decompressor.h
#ifndef DECOMPRESSOR_H
#define DECOMPRESSOR_H
#include "LeafNode.h"
class Decompressor
{
public:
Decompressor(vector<Node*> *aList, vector<char> vFile, string inFile, string outFile, unsigned int origFile);
void remakeFile();
void uncompressChars(unsigned int i);
private:
vector<char> vectorFile;
unsigned int originalFileSize;
string outputFileName;
string inputFileName;
vector<Node*> *myList;
ofstream fout;
ifstream infile;
};
#endif
//FileLoader.h
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
#ifndef FileLoader_H
#define FileLoader_H
class FileLoader
{
public:
FileLoader(string fName);
~FileLoader(){;}
vector<char> loadFileIntoVector();
vector<char> fileVector;
private:
string fileName;
};
#endif
#include "FileLoader.h"
FileLoader::FileLoader(string fName)
{
fileName = fName;
}
vector<char> FileLoader::loadFileIntoVector()
{
ifstream fin;
fin.open(fileName.c_str(), ios::binary);
if(!fin)
{
cout << "unable to open file ";
exit(1);
}
char ch;
while(fin.get(ch))
fileVector.push_back(ch);
fin.close();
return fileVector;
}
//GenerateHuffFile.h
#ifndef GENERATEHUFFFILE_H
#define GENERATEHUFFFILE_H
#include "LeafNode.h"
#include "string"
class GenerateHuffFile
{
public:
GenerateHuffFile(vector<Node*> *aList, vector<char> vFile, string outPutFile,vector<char> charBytes, vector<int> frequencies);
void writeHuffFile();//writes the true and bits to file
void writeTreePortionToFile();//writes the tree into a file
void writeBitPortionToFile();//writes the bits to a file
void writeBits(vector<bool> bitVector,int i);
void convertBoolVecToBits();//turns the boolean vector representing bits to real bits to write to file
string getBitsInChar(char dummyByte);
private:
vector<Node*> *myList;
vector<char> vectorFile;
vector<char> charBytes ;
vector<int> frequencies ;
string outputFile;
ofstream fout;
char dummyByte;
int bitCounter;
int bitPosition;
int totalBitsInFile;
static const int bitsInAByte = 8;
};
#endif
//GenerateHuffFile.cpp
#include "GenerateHuffFile.h"
GenerateHuffFile::GenerateHuffFile(vector<Node*> *aList, vector<char> vFile, string outFile, vector<char> cBytes, vector<int> freqs)
{
vectorFile = vFile;
outputFile = outFile;
myList = aList;
bitCounter = 0;
bitPosition = 128;
totalBitsInFile = 0;
charBytes = cBytes;
frequencies = freqs;
}
void GenerateHuffFile::writeHuffFile()
{
fout.open(outputFile.c_str(), ios::binary);
//diplay tree in file
for(unsigned int i = 0; i < charBytes.size(); i++)
{
fout << charBytes[i];
fout << frequencies[i];
fout << ',';
}
fout << "00" << ','; //marker to mark the end of the tree in the file
writeBitPortionToFile();
fout.close();
}
void GenerateHuffFile::writeBits(vector<bool> bitVector,int index)
{
// for(unsigned int i = 1; i < bitVector.size();i++)
//{
//cout << bitVector[i];
// }
//cout << endl;
for(unsigned int i = 1; i < bitVector.size(); i++)
{
if(bitVector[i])
{
for(int j = 0; j < bitCounter; j++)
{
bitPosition = bitPosition/2;
}
dummyByte = dummyByte | bitPosition;
bitPosition = 128;
bitCounter++;
totalBitsInFile++;
}
else
{
bitCounter++;
totalBitsInFile++;
}
if(bitCounter == 8 || (index == vectorFile.size() - 1) && (i == bitVector.size() - 1))
{
fout << dummyByte;//cout dummy byte to a file
///cout << getBitsInChar(dummyByte);
bitCounter = 0;
dummyByte = dummyByte & 0;
}
}
}
string GenerateHuffFile::getBitsInChar(char dummyByte)
{
int bitPosition = 128;
string bits;
for(int i = 0; i < 8; i++)
{
for(int j = 0; j < i; j++)
{
bitPosition = bitPosition/2;
}
if((dummyByte & bitPosition) == bitPosition)
{
bits.push_back('1');
}
else
bits.push_back('0');
bitPosition = 128;
}
bits.push_back(' ');
return bits;
}
void GenerateHuffFile::writeBitPortionToFile()
{
bool inChild = false;
Node *aNode;
dummyByte = dummyByte & 0; //clear bit inside to zero
for(unsigned int i = 0; i < vectorFile.size(); i++)
{
for(unsigned int j = 0; j < myList->size(); j++)
{
if(myList[0][j]->getMyChildrenSize() > 0)
{
aNode = myList[0][j]->searchCharByte(vectorFile[i]) ;
writeBits(aNode->getBitVector(),i);
}
}
}
//cout << endl << totalBitsInFile << endl;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.