#include <iostream>
#include <queue>
#include <fstream>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
// Function to write the name to a text file
void writeNameToFile(const string& filename, const string& name) {
ofstream file(filename);
if (file.is_open()) {
file << name;
file.close();
cout << "Name written to file successfully." << endl;
}
else {
cerr << "Unable to open the file." << endl;
}
}
// Function to read the content of a file
string readFileContent(const string& filename) {
ifstream file(filename);
string content;
if (file.is_open()) {
string line;
while (getline(file, line)) {
content += line;
}
file.close();
}
else {
cerr << "Unable to open the file." << endl;
}
return content;
}
// Function to display the dictionary
void displayDictionary(const unordered_map<string, int>& dictionary) {
cout << "Dictionary:" << endl;
for (const auto& entry : dictionary) {
cout << entry.first << " : " << entry.second << endl;
}
cout << endl;
}
// LZW Encoding function
vector<int> lzwEncode(const string& content, unordered_map<string, int>& dictionary) {
int dictSize = 256;
for (int i = 0; i < 256; i++) {
dictionary[string(1, i)] = i;
}
string current;
vector<int> encodedData;
for (char c : content) {
string next = current + c;
if (dictionary.find(next) != dictionary.end()) {
current = next;
}
else {
encodedData.push_back(dictionary[current]);
dictionary[next] = dictSize++;
current = string(1, c);
}
}
if (!current.empty()) {
encodedData.push_back(dictionary[current]);
}
return encodedData;
}
// Function to calculate the compression ratio
double calculateCompressionRatio(const string& content, unordered_map<char, pair<int, unsigned char>> dictionary) {
int originalSize = content.size() * 8; // Bits
int encodedSize = dictionary.size() * 8; // Bits
return static_cast<double>(originalSize) / encodedSize;
}
// Function to calculate the compression ratio
double calculateCompressionRatioNonConst(const string& content, const vector<int>& encodedData) {
int originalSize = content.size() * 8; // Bits
int encodedSize = encodedData.size() * 8; // Bits
return static_cast<double>(originalSize) / encodedSize;
}
// Node structure for Huffman tree
struct node {
int freq; // Frequency of the character
char data; // Character data
const node* child0; // Pointer to left child
const node* child1; // Pointer to right child
// Constructor for a leaf node
node(char d, int f = -1) {
data = d;
freq = f;
child0 = nullptr;
child1 = nullptr;
}
// Constructor for an internal node
node(const node* c0, const node* c1) {
data = 0;
freq = c0->freq + c1->freq;
child0 = c0;
child1 = c1;
}
// Operator overloading for priority queue comparison
bool operator<(const node& a) const {
return freq > a.freq;
}
// Traverses the Huffman tree and builds the dictionary
void traverse(string code, unordered_map<char, pair<int, unsigned char>>& dictionary) const {
if (child0 != nullptr) {
child0->traverse(code + '0', dictionary);
child1->traverse(code + '1', dictionary);
}
else {
// Leaf node, add data, frequency, and code to the dictionary
dictionary[data] = make_pair(freq, static_cast<unsigned char>(stoi(code, nullptr, 2)));
}
}
};
// Function to perform Huffman coding
void huffmanCoding(string content) {
priority_queue<node> qu;
int frequency[256];
for (int i = 0; i < 256; i++)
frequency[i] = 0;
// Calculate the frequency of each character in the input string
for (int i = 0; i < content.size(); i++) {
frequency[int(content[i])]++;
}
// Build the Huffman tree
for (int i = 0; i < 256; i++) {
if (frequency[i]) {
qu.push(node(i, frequency[i]));
}
}
while (qu.size() > 1) {
node* c0 = new node(qu.top());
qu.pop();
node* c1 = new node(qu.top());
qu.pop();
qu.push(node(c0, c1));
}
// Print the Huffman Code
cout << "The Huffman Code: " << endl;
unordered_map<char, pair<int, unsigned char>> dictionary;
qu.top().traverse("", dictionary);
// Print the data, frequency, and code for each character in the dictionary
for (const auto& entry : dictionary) {
cout << "Data: " << entry.first << ", Frequency: " << entry.second.first << ", Code: " << static_cast<int>(entry.second.second) << endl;
}
double huffmanCompressionRatio = calculateCompressionRatio(content, dictionary);
cout << "Compression Ratio (Huffman Encoding): " << huffmanCompressionRatio << endl;
}
int main() {
string filename = "name.txt";
string name = "";
cout << "Enter text for encoding: ";
cin >> name;
// Step 1: Write the name to a text file
writeNameToFile(filename, name);
// Step 2: Read the content of the file
string content = readFileContent(filename);
// Step 3: LZW Encoding and Display code
unordered_map<string, int> dictionary;
vector<int> encodedData = lzwEncode(content, dictionary);
cout << "LZW Encoded Code:" << endl;
for (int code : encodedData) {
cout << code << " ";
}
cout << endl;
// Step 4: Calculate the compression ratio for LZW Encoding
double lzwCompressionRatio = calculateCompressionRatioNonConst(content, encodedData);
cout << "Compression Ratio (LZW Encoding): " << lzwCompressionRatio << endl;
// Step 5: Huffman Encoding
huffmanCoding(content);
// Step 6: Calculate the compression ratio for Huffman Encoding
return 0;
}