TrickmanOff

Huffman

Oct 18th, 2020
545
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <cstddef>
  3. #include <istream>
  4. #include <memory>
  5. #include <ostream>
  6. #include <string>
  7. #include <unordered_map>
  8. #include <vector>
  9. #include <queue>
  10.  
  11. using namespace std;
  12.  
  13. enum Error {
  14.     OK = 0,
  15.     WRONG_ARGUMENTS,
  16.     OUTPUT_ERROR
  17.     // You can add here yours errors.
  18. };
  19.  
  20. struct Node {
  21.     unique_ptr<Node> l_son;
  22.     unique_ptr<Node> r_son;
  23.     uint64_t freq;
  24.     char ch;
  25.  
  26.     Node(char ch, uint64_t freq) : l_son(nullptr), r_son(nullptr), freq(freq), ch(ch) {}
  27.     Node(Node* l, Node* r) : l_son(l), r_son(r), freq(l->freq + r->freq) {}
  28.  
  29.     bool operator<(const Node& rhs) const {
  30.         return freq < rhs.freq;
  31.     }
  32.  
  33.     bool is_leaf() const {
  34.         return !l_son && !r_son;
  35.     }
  36. };
  37.  
  38. class CmpNodes {
  39. public:
  40.     bool operator()(const Node* lhs, const Node* rhs) {
  41.         return lhs->freq > rhs->freq;
  42.     }
  43. };
  44.  
  45. class Bohr {
  46. public:
  47.     unique_ptr<Node> root;
  48.  
  49.     Bohr(const unordered_map<char, uint64_t>& freqs) {
  50.         priority_queue<Node*, vector<Node*>, CmpNodes> pq;
  51.         // inserting one-char trees
  52.         for (const auto& [ch, freq] : freqs) {
  53.             pq.push(new Node(ch, freq));
  54.         }
  55.  
  56.         while (pq.size() > 1) {
  57.             Node* l_node = pq.top();
  58.             pq.pop();
  59.  
  60.             Node* r_node = pq.top();
  61.             pq.pop();
  62.  
  63.             pq.push(new Node(l_node, r_node));
  64.         }
  65.  
  66.         root.reset(pq.top());
  67.     }
  68.  
  69.     unordered_map<char, string> get_codes() {
  70.         unordered_map<char, string> codes;
  71.         vector<char> cur_code;
  72.         traversal(root.get(), cur_code, &codes);
  73.         return codes;
  74.     }
  75.  
  76.     void traversal(Node* cur_node, vector<char>& cur_code, unordered_map<char, string>* codes) {
  77.         if (cur_node->is_leaf()) {  // set code for char
  78.             (*codes)[cur_node->ch] = string(cur_code.begin(), cur_code.end());
  79.         }
  80.  
  81.         if (cur_node->l_son) {
  82.             cur_code.push_back('0');
  83.             traversal(cur_node->l_son.get(), cur_code, codes);
  84.             cur_code.pop_back();
  85.         }
  86.         if (cur_node->r_son) {
  87.             cur_code.push_back('1');
  88.             traversal(cur_node->r_son.get(), cur_code, codes);
  89.             cur_code.pop_back();
  90.         }
  91.     }
  92. };
  93.  
  94. class Reader {
  95. private:
  96.     static const size_t BUF_SIZE = 4096;
  97.     char buf[BUF_SIZE];
  98.     size_t buf_pos = 0;
  99.     size_t chars_in_buf = 0;
  100.  
  101.     istream* in;
  102.     size_t start_pos;
  103.  
  104.     void read_block() {
  105.         in->read(buf, BUF_SIZE);
  106.  
  107.         chars_in_buf = in->gcount();
  108.         buf_pos = 0;
  109.     }
  110.  
  111. public:
  112.     Reader(istream* in) : in(in), start_pos(in->tellg()) {}
  113.  
  114.     // returns true if successfully read
  115.     bool read(char* ch) {
  116.         if (buf_pos == chars_in_buf) {
  117.             read_block();
  118.         }
  119.         if (buf_pos == chars_in_buf) {
  120.             return false;
  121.         }
  122.         *ch = buf[buf_pos++];
  123.         return true;
  124.     }
  125.  
  126.     void reset() {
  127.         in->clear();
  128.         in->seekg(start_pos);
  129.     }
  130. };
  131.  
  132. class Writer {
  133. private:
  134.     static const size_t BUF_SIZE = 4096;
  135.     char buf[BUF_SIZE];
  136.     size_t buf_pos = 0;
  137.     ostream* out;
  138.  
  139. public:
  140.     Writer(ostream* out) : out(out) {}
  141.  
  142.     void write_buf() {
  143.         out->write(buf, buf_pos);
  144.         buf_pos = 0;
  145.     }
  146.  
  147.     void write_char(char ch) {
  148.         buf[buf_pos++] = ch;
  149.         if (buf_pos == BUF_SIZE) {
  150.             write_buf();
  151.         }
  152.     }
  153.  
  154.     void write_bit(bool bit) {
  155.         static char bits_written = 0;
  156.  
  157.         buf[buf_pos] <<= 1;
  158.         buf[buf_pos] += bit;
  159.         ++bits_written;
  160.  
  161.         if (bits_written == 8) {
  162.             ++buf_pos;
  163.             bits_written = 0;
  164.         }
  165.     }
  166.  
  167.     void flush() {
  168.         if (buf_pos != 0) {
  169.             write_buf();
  170.         }
  171.     }
  172. };
  173.  
  174. // encodes and prints
  175. class Encoder {
  176. private:
  177.     Reader* reader;
  178.     Writer writer;
  179.  
  180.     uint8_t byte_num = 0;  // номер текущего байта в выводе (используется только для первых <= 8)
  181.  
  182.     unordered_map<char, string> codes;
  183.  
  184.     // Порядок кодирования
  185.     // В первых 8 байтах младший бит совпадает
  186.     // В первом байте записана мощность алфавита
  187.     // а, в остальных 7 закодирована длина последовательности в битах (хватит на ОООчень большой файл)
  188.     // Остальные байты - закодированный файл, последний байт дополнен нулями, если нужно
  189.  
  190. public:
  191.     Encoder(Reader* reader, ostream* out, unordered_map<char, string>&& codes) : reader(reader), writer(out), codes(move(codes)) {}
  192.  
  193.     void encode_table() {
  194.         vector<pair<char, string>> codes_sorted(codes.begin(), codes.end());
  195.         sort(codes_sorted.begin(), codes_sorted.end());
  196.        
  197.         for (const auto& [ch, code] : codes) {
  198.             for (char bit : code) {
  199.                 writer.write_bit(bit);
  200.             }
  201.             for (int _ = 0; _ < codes.size() - code.length(); ++_) {
  202.                 writer.write_bit(0);
  203.             }
  204.         }
  205.     }
  206.  
  207.     void encode_len() {
  208.         unsigned char n = codes.size();
  209.         bool same_bit = n % 2;
  210.  
  211.         writer.write_char(n);
  212.  
  213.         // считаем сумму длин кодов в битах
  214.         uint64_t sum = 0;
  215.         char ch;
  216.         while (reader->read(&ch)) {
  217.             sum += codes[ch].length();
  218.         }
  219.         reader->reset();
  220.  
  221.         vector<char> code;
  222.         for (int _ = 0; _ < 8; ++_) {
  223.             unsigned char byte = sum % (1 << 7);
  224.             byte <<= 1;
  225.             byte += same_bit;
  226.             code.push_back(byte);
  227.             sum >>= 7;
  228.         }
  229.  
  230.         reverse(code.begin(), code.end());
  231.         for (char byte : code) {
  232.             writer.write_char(byte);
  233.         }
  234.     }
  235.  
  236.     void encode() {
  237.         encode_len();
  238.         encode_table();
  239.  
  240.         char ch;
  241.         while (reader->read(&ch)) {
  242.             for (char bit : codes[ch]) {
  243.                 writer.write_bit(bit);
  244.             }
  245.         }
  246.     }
  247. };
  248.  
  249. // count frequency of each character
  250. unordered_map<char, uint64_t> cnt_freqs(Reader* reader) {
  251.     unordered_map<char, uint64_t> freqs;
  252.  
  253.     char ch;
  254.     while (reader->read(&ch)) {
  255.         ++freqs[ch];
  256.     }
  257.     return freqs;
  258. }
  259.  
  260. int compress(std::istream* in, std::ostream* out) {
  261.     if (in == nullptr || out == nullptr) {
  262.         return Error::WRONG_ARGUMENTS;
  263.     }
  264.  
  265.     Reader reader(in);
  266.     Bohr bohr(cnt_freqs(&reader));
  267.     reader.reset();
  268.  
  269.     try {
  270.         Encoder encoder(&reader, out, bohr.get_codes());
  271.         encoder.encode();
  272.         reader.reset();
  273.     }
  274.     catch (...) {
  275.         return Error::OUTPUT_ERROR;
  276.     }
  277.  
  278.     return Error::OK;
  279. }
  280.  
  281. // decodes
  282. class Decoder {
  283. private:
  284.     Reader reader;
  285.     bool same_bit;
  286.  
  287. public:
  288.     Decoder(istream* in, ostream* out) : reader(in) {}
  289.  
  290.     char get_n() {
  291.         char n = 0;
  292.  
  293.         if (!reader.read(&n)) {
  294.             throw std::invalid_argument("bad file");
  295.         }
  296.         same_bit = n % 2;
  297.        
  298.         return n >> 1;
  299.     }
  300.  
  301.     uint64_t get_len() {
  302.         uint64_t len = 0;
  303.         for (int _ = 0; _ < 7; ++_) {
  304.             char byte;
  305.  
  306.             if (!reader.read(&byte)) {
  307.                 throw std::invalid_argument("bad file");
  308.             }
  309.             if ((byte % 2) != same_bit) {
  310.                 throw std::invalid_argument("bad file");
  311.             }
  312.  
  313.             len <<= 7;
  314.             len += (byte >> 1);
  315.         }
  316.         return len;
  317.     }
  318. };
  319.  
  320. int decompress(std::istream* in, std::ostream* out) {
  321.     if (in == nullptr || out == nullptr) {
  322.         return Error::WRONG_ARGUMENTS;
  323.     }
  324.  
  325.     return Error::OK;
  326. }
  327.  
  328. #include <sstream>
  329. #include <fstream>
  330.  
  331. ofstream out("output.txt");
  332.  
  333. int main() {
  334.     stringstream ss;
  335.     ss << "abracadabra";
  336.     stringstream ssout;
  337.     int x = compress(&ss, &out);
  338. }
RAW Paste Data