SHARE
TWEET

Untitled

a guest Feb 20th, 2020 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <queue>
  4. #include <map>
  5. #include <fstream>
  6.  
  7. using namespace std;
  8.  
  9. struct Node {
  10.     char symbol;
  11.     int weight;
  12.     Node *left, *right;
  13.  
  14.     Node(char symbol, int weight, Node *left, Node *right) {
  15.         this->symbol = symbol;
  16.         this->weight = weight;
  17.         this->left = left;
  18.         this->right = right;
  19.     }
  20. };
  21.  
  22. struct compareByWeight {
  23.     bool operator()(Node &l, Node &r) {
  24.         // highest priority => lowest weight
  25.         return l.weight > r.weight;
  26.     }
  27. };
  28.  
  29. map<char, int> countWeights(string &rawText) {
  30.     // Count weights
  31.     map<char, int> weights;
  32.     for (auto &symbol: rawText)
  33.         weights[symbol]++;
  34.  
  35.     return weights;
  36. }
  37.  
  38. void writeCodes(Node *root, const string &str, map<char, string> &huffmanCode) {
  39.     if (root == nullptr)
  40.         return;
  41.  
  42.     // found a leaf node
  43.     if (!root->left && !root->right) {
  44.         huffmanCode[root->symbol] = str;
  45.     }
  46.  
  47.     writeCodes(root->left, str + "0", huffmanCode);
  48.     writeCodes(root->right, str + "1", huffmanCode);
  49. }
  50.  
  51. void decode(Node *root, int &index, string encodedText, string &decodedText) {
  52.     if (root == nullptr)
  53.         return;
  54.  
  55.     // found a leaf node
  56.     if (!root->left && !root->right) {
  57.         decodedText += root->symbol;
  58.         return;
  59.     }
  60.  
  61.     index++;
  62.  
  63.     if (encodedText[index] == '0')
  64.         decode(root->left, index, encodedText, decodedText);
  65.     else
  66.         decode(root->right, index, encodedText, decodedText);
  67. }
  68.  
  69. Node *buildHuffman(map<char, int> &weights) {
  70.     // Tree
  71.     priority_queue<Node, vector<Node>, compareByWeight> nodes;
  72.  
  73.     // Create a leaf node for each character¬†and add it to nodes.
  74.     for (auto weight: weights)
  75.         nodes.push(*new Node(weight.first, weight.second, nullptr, nullptr));
  76.  
  77.     while (nodes.size() > 1) {
  78.         // Remove the two nodes with lowest weights from the tree
  79.         Node *left = new Node(nodes.top());
  80.         nodes.pop();
  81.         Node *right = new Node(nodes.top());
  82.         nodes.pop();
  83.  
  84.         // Merge two deleted nodes in one
  85.         int sum = left->weight + right->weight;
  86.         nodes.push(*new Node('\0', sum, left, right));
  87.     }
  88.  
  89.     Node *root = new Node(nodes.top());
  90.  
  91.     return root;
  92. }
  93.  
  94. map<char, int> decodeWeights(string &codes) {
  95.  
  96.     int l = 0, weight, counter = 0;
  97.     char symbol;
  98.     map<char, int> weights;
  99.     for (int i = 0; i < codes.length(); i++)
  100.         if (codes[i] == ' ') {
  101.             counter++;
  102.             if (counter % 2 != 0)
  103.                 symbol = char(stoi(codes.substr(l, l - i)));
  104.             else {
  105.                 weight = stoi(codes.substr(l, l - i));
  106.                 weights[symbol] = weight;
  107.             }
  108.             l = i + 1;
  109.         }
  110.  
  111.     return weights;
  112. }
  113.  
  114. void decodeText() {
  115.     ifstream encodedFile("../result.txt");
  116.     string codes, encodedText, decodedText;
  117.     getline(encodedFile, codes);
  118.     getline(encodedFile, encodedText);
  119.  
  120.     map<char, int> weights = decodeWeights(codes);
  121.     Node *root = buildHuffman(weights);
  122.  
  123.     ofstream decodedFile("../test.txt");
  124.     int index = -1;
  125.     cout << "\nDecoded text:\n";
  126.     while (index + 2 < encodedText.size())
  127.         decode(root, index, encodedText, decodedText);
  128.  
  129.     cout << decodedText;
  130.     decodedFile << decodedText;
  131. }
  132.  
  133. void encodeText() {
  134.     // Input
  135.     char test;
  136.     ifstream decodedFile("../test.txt");
  137.     string line, decodedText;
  138.  
  139.     while (decodedFile.get(test))
  140.         decodedText += test;
  141.  
  142.     // Calculate
  143.     map<char, int> weights = countWeights(decodedText);
  144.     Node *root = buildHuffman(weights);
  145.     map<char, string> huffmanCode;
  146.     writeCodes(root, "", huffmanCode);
  147.  
  148.     // Output
  149.     ofstream encodedFile("../result.txt");
  150.  
  151.     cout << "Symbols weights and codes:\n";
  152.     for (auto &code: huffmanCode) {
  153.         cout << code.first << " " << code.second << " " << weights[code.first] << '\n';
  154.         encodedFile << (int) code.first << ' ' << weights[code.first] << ' ';
  155.     }
  156.  
  157.     cout << "\nOriginal text:\n" << decodedText << '\n';
  158.  
  159.     string encodedText;
  160.     for (auto &symbol: decodedText)
  161.         encodedText += huffmanCode[symbol];
  162.     cout << "\nEncoded text:\n" << encodedText << endl;
  163.     encodedFile << endl << encodedText;
  164. }
  165.  
  166. int main() {
  167.  
  168.     encodeText();
  169. //    decodeText();
  170.  
  171.     return 0;
  172. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top