Untitled
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; }