Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
6.3 kB
2
Indexable
Never
#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;
}