{ "cells": [ { "cell_type": "markdown", "id": "parliamentary-mobile", "metadata": {}, "source": [ "# DS and Algo in C++" ] }, { "cell_type": "markdown", "id": "close-prison", "metadata": {}, "source": [ "## FFT\n", "\n", "Simple c++ implementation of the [Cooley–Tukey algorithm](https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm#The_radix-2_DIT_case) for arrays whose size is a power of 2. " ] }, { "cell_type": "code", "execution_count": 1, "id": "gross-violence", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(6,0), (-2,2), (-2,0), (-2,-2), " ] } ], "source": [ "#include \n", "#include \n", "#include // M_PI\n", "#include \n", "\n", "void _fft(std::vector >& out, const std::vector& x, const int& n)\n", "{\n", " // assuming n is a power of 2\n", " if (n==1)\n", " {\n", " out.resize(1);\n", " out[0] = x[0];\n", " }\n", " else{\n", " std::vector > o(n/2), e(n/2);\n", " std::vector x_odd, x_even;\n", " size_t i=0;\n", " while (i < n){\n", " x_even.push_back(x[i++]);\n", " x_odd.push_back(x[i++]);\n", " }\n", " _fft(e, x_even, n/2);\n", " _fft(o, x_odd, n/2);\n", " \n", " std::vector > w;\n", " for (size_t k=0 ; k(0., 1.)/((double)n)));\n", " \n", " out.resize(n);\n", " for (size_t k=0 ; k x = {0, 1, 2, 3};\n", "std::vector > out;\n", "\n", "_fft(out, x, 4);\n", "\n", "for (auto c : out)\n", " std::cout << c << \", \";" ] }, { "cell_type": "code", "execution_count": 1, "id": "alpha-entity", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(6,0), (-2,2), (-2,0), (-2,-2), " ] } ], "source": [ "// by Eigen\n", "\n", "#pragma cling add_include_path(\"/srv/conda/envs/notebook/include/eigen3/\")\n", "\n", "#include \n", "#include \n", "#include \n", "#include \n", "\n", "Eigen::FFT fft;\n", "std::vector a = {0, 1, 2, 3};\n", "std::vector > out;\n", "\n", "fft.fwd(out, a);\n", "\n", "for (auto c : out)\n", " std::cout << c << \", \";" ] }, { "cell_type": "markdown", "id": "crude-tablet", "metadata": {}, "source": [ "## Huffman Coding in C++\n", "\n", "* 結果是對的但有 memory leaking，只有 `new` 沒有 `delete`，下面的 dtor 寫的不對\n", "* coding 結果和 python 不一樣，可能是因為 priority queue 處理同 freq 的 node 方法不同\n", "* `original_message` 是用來計算 frequency table 和建立 Huffman Tree 的，可以和要壓縮的字串不同" ] }, { "cell_type": "code", "execution_count": 1, "id": "pharmaceutical-eating", "metadata": {}, "outputs": [], "source": [ "#include \n", "#include \n", "#include // std::priority_queue\n", "#include \n", "#include // std::pair, std::swap\n", "#include // std::greater\n", "#include \n", "\n", "class HeapNode\n", "{\n", "public: \n", " HeapNode* left = nullptr;\n", " HeapNode* right = nullptr;\n", " int freq;\n", " char ch;\n", " \n", " HeapNode(int freq, char ch, HeapNode* left, HeapNode* right) \n", " : freq(freq), ch(ch), left(left), right(right) {}\n", " \n", " HeapNode(const HeapNode& other) { // copy ctor\n", " HeapNode* p = clone(&other); \n", " \n", " this->freq = p->freq;\n", " this->ch = p->ch;\n", " this->left = p->left;\n", " this->right = p->right;\n", " }\n", " \n", "// ~HeapNode() { \n", "// deleteNode(this->left);\n", "// deleteNode(this->right);\n", "// }\n", " \n", "// void deleteNode(const HeapNode* p) {\n", "// if (p){\n", "// deleteNode(p->left);\n", "// deleteNode(p->right);\n", "// delete p;\n", "// }\n", "// }\n", " \n", " HeapNode* clone(const HeapNode* other) {\n", " HeapNode* p = new HeapNode(other->freq, other->ch, nullptr, nullptr);\n", " \n", " if (other->left)\n", " p->left = clone(other->left);\n", " if (other->right)\n", " p->right = clone(other->right);\n", " \n", " return p;\n", " }\n", " \n", " friend bool operator>(const HeapNode& a, const HeapNode& b) { \n", " return a.freq > b.freq; \n", " }\n", "};" ] }, { "cell_type": "code", "execution_count": 2, "id": "elementary-custody", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code proceeds by means of Huffman coding, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper \"A Method for the Construction of Minimum-Redundancy Codes\".\"" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class HuffmanCoding{\n", "\n", " std::string original_message;\n", " std::vector> codeCharPairs;\n", " const HeapNode* huffmanTree;\n", " std::priority_queue, std::greater>* q;\n", " \n", " void buildHuffmanTree()\n", " {\n", " std::unordered_map freq;\n", " for (const char& c : original_message)\n", " freq[c]++;\n", "\n", " std::vector nodes;\n", " for (const auto& pair : freq){\n", " char letter = pair.first;\n", " int frequency = pair.second;\n", " nodes.push_back(HeapNode(frequency, letter, nullptr, nullptr));\n", " }\n", "\n", " q = new std::priority_queue, std::greater>(std::greater(), nodes);\n", "\n", " while(q->size() > 1) \n", " {\n", " HeapNode* left = new HeapNode(q->top());\n", " q->pop();\n", " \n", " HeapNode* right = new HeapNode(q->top());\n", " q->pop();\n", " \n", " HeapNode* root = new HeapNode(left->freq + right->freq, '\\0', left, right);\n", " q->push(*root);\n", " }\n", " huffmanTree = &(q->top());\n", " }\n", " \n", " std::vector> getCodeCharPairs(const HeapNode* p)\n", " { \n", " // if this weren't a member function it would have to be defined as an auto as the original signature wouldn't work in cling\n", " // this is a known issue; see https://github.com/jupyter-xeus/xeus-cling/issues/40\n", "\n", " if (p->ch)\n", " {\n", " std::string ch(1, p->ch);\n", " return std::vector> {{ch, \"\"}};\n", " }\n", " else \n", " {\n", " std::vector> from_left = getCodeCharPairs(p->left);\n", " std::vector> from_right = getCodeCharPairs(p->right);\n", "\n", " for (auto& pair : from_left)\n", " pair.second = '0' + pair.second;\n", "\n", " for (auto& pair : from_right)\n", " pair.second = '1' + pair.second;\n", "\n", " from_left.insert(from_left.end(), from_right.begin(), from_right.end());\n", " return from_left;\n", " }\n", " }\n", "\n", "public:\n", " HuffmanCoding(const std::string& original_message) : original_message(original_message) {}\n", " \n", " std::string compress(const std::string& message){\n", " if (!huffmanTree)\n", " buildHuffmanTree();\n", " if (codeCharPairs.size()==0)\n", " codeCharPairs = getCodeCharPairs(huffmanTree);\n", " \n", " std::unordered_map codeTable(codeCharPairs.begin(), codeCharPairs.end());\n", " \n", " std::string compressed;\n", " for (const char& c : message)\n", " {\n", " std::string ch(1, c);\n", " compressed += codeTable[ch];\n", " }\n", " return compressed;\n", " }\n", " std::string decompress(const std::string& compressed){\n", " if (!huffmanTree)\n", " buildHuffmanTree();\n", " if (codeCharPairs.size()==0)\n", " codeCharPairs = getCodeCharPairs(huffmanTree);\n", "\n", " for (auto& pair : codeCharPairs)\n", " std::swap(pair.first, pair.second);\n", "\n", " std::unordered_map charTable(codeCharPairs.begin(), codeCharPairs.end());\n", "\n", " std::string::const_iterator it = compressed.begin();\n", " std::string code, message;\n", "\n", " while (it!=compressed.end())\n", " {\n", " code += *it;\n", " if (charTable.find(code) != charTable.end()){\n", " message += charTable[code];\n", " code = \"\";\n", " }\n", " it++;\n", " }\n", " return message;\n", " }\n", "};\n", "\n", "std::string original_message(R\"(In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code proceeds by means of Huffman coding, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper \"A Method for the Construction of Minimum-Redundancy Codes\".)\");\n", "\n", "original_message" ] }, { "cell_type": "code", "execution_count": 3, "id": "helpful-aquarium", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"110110000110111110101010100011000010010000111001011011100111101001001100011011010110011101110110001011101000110101111010101101000101110001010010100110111000101010110010101011001011010011001110111111010111010010101111011110001011101101111101010100010110011101000011111011111110000011110110000101001101010010000010111101101110001010110100001100111101010111111101010000000101001000101110000111110000101101100101110100100111001111110101010001011001110001010100111000111101000011111110101010100011000110100110000010101101111001000111100001011110111101010110111000011010001100110000111000011001111100100111000101111111101010101000110000101101100001100110100101001100000011110000000010101100111100001011010101101011000011001111110101011111110111010001100010010001101101110111101010110111100100011010001101101110111001110010110100101011101111111101010100010110011110000101101010110101100110000100011111100110101011011110001110001110110001111110101011111101011101001010111101111000101110110111110101010001001000110110111010011001110111011011101110000111011101010101100100000101010100011110010110011011110110000001101010000110000101111001101010110111110110100111110111100100001011110011110000001111010111010010101111011110001011101101110000001010100100000011100111010101100111000000101110011111011111110011101011010000001110110100000011110011000110010001011000110000111101110001111010111111011000000000010011001110111011000101111000010010100110100001010000110101011000010111010001101110001010101100111110110010100111011100111000100111111111100000111100001100101101111101111110011110111010111111000001010101010001011110111101010110111000101010110011111011011101001100011000110110100101101000010100101001101111010101111110101111010001100100100011001010001110110011100111110110000101001001100010011101101101001011011111011011101000101100001111011111000001\"" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "HuffmanCoding hc(original_message);\n", "\n", "std::string message = original_message;\n", "std::string compressed = hc.compress(message);\n", "compressed" ] }, { "cell_type": "code", "execution_count": 4, "id": "mediterranean-radical", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code proceeds by means of Huffman coding, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper \"A Method for the Construction of Minimum-Redundancy Codes\".\"" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "std::string recovered = hc.decompress(compressed);\n", "recovered" ] }, { "cell_type": "code", "execution_count": 5, "id": "relevant-despite", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(recovered == message)" ] }, { "cell_type": "markdown", "id": "coordinate-antibody", "metadata": {}, "source": [ "## Huffman Coding in C++, Smart Pointer Version\n", "\n", "* 還沒改好的 shared_ptr 版本" ] }, { "cell_type": "code", "execution_count": 1, "id": "wicked-acrobat", "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "In file included from input_line_5:1:\n", "In file included from /srv/conda/envs/notebook/include/xeus/xinterpreter.hpp:13:\n", "In file included from /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/functional:54:\n", "In file included from /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/tuple:39:\n", "In file included from /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/array:39:\n", "In file included from /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/stdexcept:39:\n", "In file included from /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/string:41:\n", "In file included from /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/allocator.h:46:\n", "In file included from /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/x86_64-linux-gnu/c++/7.5.0/bits/c++allocator.h:33:\n", "/usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/ext/new_allocator.h:136:23: error: no matching constructor for initialization of '__cling_N52::HeapNode'\n", " { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }\n", " ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~\n", "/usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/alloc_traits.h:475:8: note: in instantiation of function template specialization '__gnu_cxx::new_allocator<__cling_N52::HeapNode>::construct<__cling_N52::HeapNode, const __cling_N52::HeapNode *>' requested here\n", " { __a.construct(__p, std::forward<_Args>(__args)...); }\n", " ^\n", "/usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/shared_ptr_base.h:526:30: note: in instantiation of function template specialization 'std::allocator_traits >::construct<__cling_N52::HeapNode, const __cling_N52::HeapNode *>' requested here\n", " allocator_traits<_Alloc>::construct(__a, _M_ptr(),\n", " ^\n", "/usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/shared_ptr_base.h:637:18: note: in instantiation of function template specialization 'std::_Sp_counted_ptr_inplace<__cling_N52::HeapNode, std::allocator<__cling_N52::HeapNode>, __gnu_cxx::_Lock_policy::_S_atomic>::_Sp_counted_ptr_inplace' requested here\n", " ::new (__mem) _Sp_cp_type(std::move(__a),\n", " ^\n", "/usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/shared_ptr_base.h:1294:14: note: in instantiation of function template specialization 'std::__shared_count<__gnu_cxx::_Lock_policy::_S_atomic>::__shared_count<__cling_N52::HeapNode, std::allocator<__cling_N52::HeapNode>, const __cling_N52::HeapNode *>' requested here\n", " : _M_ptr(), _M_refcount(__tag, (_Tp*)0, __a,\n", " ^\n", "/usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/shared_ptr.h:344:4: note: in instantiation of function template specialization 'std::__shared_ptr<__cling_N52::HeapNode, __gnu_cxx::_Lock_policy::_S_atomic>::__shared_ptr, const __cling_N52::HeapNode *>' requested here\n", " : __shared_ptr<_Tp>(__tag, __a, std::forward<_Args>(__args)...)\n", " ^\n", "/usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/shared_ptr.h:690:14: note: in instantiation of function template specialization 'std::shared_ptr<__cling_N52::HeapNode>::shared_ptr, const __cling_N52::HeapNode *>' requested here\n", " return shared_ptr<_Tp>(_Sp_make_shared_tag(), __a,\n", " ^\n", "/usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/shared_ptr.h:706:19: note: in instantiation of function template specialization 'std::allocate_shared<__cling_N52::HeapNode, std::allocator<__cling_N52::HeapNode>, const __cling_N52::HeapNode *>' requested here\n", " return std::allocate_shared<_Tp>(std::allocator<_Tp_nc>(),\n", " ^\n", "input_line_8:13:50: note: in instantiation of function template specialization 'std::make_shared<__cling_N52::HeapNode, const __cling_N52::HeapNode *>' requested here\n", " std::shared_ptr p = clone(std::make_shared(&other));\n", " ^\n", "input_line_8:12:5: note: candidate constructor not viable: no known conversion from 'const __cling_N52::HeapNode *' to 'const __cling_N52::HeapNode' for 1st argument; dereference the argument with *\n", " HeapNode(const HeapNode& other) { // copy ctor\n", " ^\n", "input_line_8:9:5: note: candidate constructor not viable: requires 4 arguments, but 1 was provided\n", " HeapNode(int freq, char ch, std::shared_ptr left, std::shared_ptr right) \n", " ^\n" ] }, { "ename": "Interpreter Error", "evalue": "", "output_type": "error", "traceback": [ "Interpreter Error: " ] } ], "source": [ "#include \n", "#include \n", "#include // std::shared_ptr, std::make_shared\n", "#include // std::priority_queue\n", "#include \n", "#include // std::pair, std::swap\n", "#include // std::greater\n", "#include \n", "\n", "class HeapNode\n", "{\n", "public: \n", " std::shared_ptr left = nullptr;\n", " std::shared_ptr right = nullptr;\n", " int freq;\n", " char ch;\n", " \n", " HeapNode(int freq, char ch, std::shared_ptr left, std::shared_ptr right) \n", " : freq(freq), ch(ch), left(left), right(right) {}\n", " \n", " HeapNode(const HeapNode& other) { // copy ctor\n", " std::shared_ptr p = clone(std::make_shared(&other));\n", " \n", " this->freq = p->freq;\n", " this->ch = p->ch;\n", " this->left = p->left;\n", " this->right = p->right;\n", " }\n", " \n", "// ~HeapNode() { \n", "// deleteNode(this->left);\n", "// deleteNode(this->right);\n", "// }\n", " \n", "// void deleteNode(const HeapNode* p) {\n", "// if (p){\n", "// deleteNode(p->left);\n", "// deleteNode(p->right);\n", "// delete p;\n", "// }\n", "// }\n", " \n", " std::shared_ptr clone(std::shared_ptr other) {\n", " std::shared_ptr p = std::make_shared(other->freq, other->ch, nullptr, nullptr);\n", " \n", " if (other->left)\n", " p->left = clone(other->left);\n", " if (other->right)\n", " p->right = clone(other->right);\n", " \n", " return p;\n", " }\n", " \n", " friend bool operator>(const HeapNode& a, const HeapNode& b) { \n", " return a.freq > b.freq; \n", " }\n", "};" ] }, { "cell_type": "code", "execution_count": 8, "id": "sealed-proportion", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code proceeds by means of Huffman coding, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper \"A Method for the Construction of Minimum-Redundancy Codes\".\"" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class HuffmanCoding{\n", "\n", " std::string original_message;\n", " std::vector> codeCharPairs;\n", " const std::shared_ptr huffmanTree;\n", " std::shared_ptr, std::greater>> q;\n", " \n", " void buildHuffmanTree()\n", " {\n", " std::unordered_map freq;\n", " for (const char& c : original_message)\n", " freq[c]++;\n", "\n", " std::vector nodes;\n", " for (const auto& pair : freq){\n", " char letter = pair.first;\n", " int frequency = pair.second;\n", " nodes.push_back(HeapNode(frequency, letter, nullptr, nullptr));\n", " }\n", "\n", " q = std::make_shared, std::greater>>(std::greater(), nodes);\n", "\n", " while(q->size() > 1) \n", " {\n", " std::shared_ptr left = std::make_shared(q->top());\n", " q->pop();\n", " \n", " std::shared_ptr right = std::make_shared(q->top());\n", " q->pop();\n", " \n", " std::shared_ptr root = std::make_shared(left->freq + right->freq, '\\0', left, right);\n", " q->push(*root);\n", " }\n", " huffmanTree = &(q->top());\n", " }\n", " \n", " std::vector> getCodeCharPairs(const std::shared_ptr p)\n", " { \n", " // if this weren't a member function it would have to be defined as an auto as the original signature wouldn't work in cling\n", " // this is a known issue; see https://github.com/jupyter-xeus/xeus-cling/issues/40\n", "\n", " if (p->ch)\n", " {\n", " std::string ch(1, p->ch);\n", " return std::vector> {{ch, \"\"}};\n", " }\n", " else \n", " {\n", " std::vector> from_left = getCodeCharPairs(p->left);\n", " std::vector> from_right = getCodeCharPairs(p->right);\n", "\n", " for (auto& pair : from_left)\n", " pair.second = '0' + pair.second;\n", "\n", " for (auto& pair : from_right)\n", " pair.second = '1' + pair.second;\n", "\n", " from_left.insert(from_left.end(), from_right.begin(), from_right.end());\n", " return from_left;\n", " }\n", " }\n", "\n", "public:\n", " HuffmanCoding(const std::string& original_message) : original_message(original_message) {}\n", " \n", " std::string compress(const std::string& message){\n", " if (!huffmanTree)\n", " buildHuffmanTree();\n", " if (codeCharPairs.size()==0)\n", " codeCharPairs = getCodeCharPairs(huffmanTree);\n", " \n", " std::unordered_map codeTable(codeCharPairs.begin(), codeCharPairs.end());\n", " \n", " std::string compressed;\n", " for (const char& c : message)\n", " {\n", " std::string ch(1, c);\n", " compressed += codeTable[ch];\n", " }\n", " return compressed;\n", " }\n", " std::string decompress(const std::string& compressed){\n", " if (!huffmanTree)\n", " buildHuffmanTree();\n", " if (codeCharPairs.size()==0)\n", " codeCharPairs = getCodeCharPairs(huffmanTree);\n", "\n", " for (auto& pair : codeCharPairs)\n", " std::swap(pair.first, pair.second);\n", "\n", " std::unordered_map charTable(codeCharPairs.begin(), codeCharPairs.end());\n", "\n", " std::string::const_iterator it = compressed.begin();\n", " std::string code, decompressed;\n", "\n", " while (it!=compressed.end())\n", " {\n", " code += *it;\n", " if (charTable.find(code) != charTable.end()){\n", " decompressed += charTable[code];\n", " code = \"\";\n", " }\n", " it++;\n", " }\n", " return decompressed;\n", " }\n", "};\n", "\n", "std::string original_message(R\"(In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code proceeds by means of Huffman coding, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper \"A Method for the Construction of Minimum-Redundancy Codes\".)\");\n", "\n", "original_message" ] }, { "cell_type": "code", "execution_count": 9, "id": "spoken-floor", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"110110000110111110101010100011000010010000111001011011100111101001001100011011010110011101110110001011101000110101111010101101000101110001010010100110111000101010110010101011001011010011001110111111010111010010101111011110001011101101111101010100010110011101000011111011111110000011110110000101001101010010000010111101101110001010110100001100111101010111111101010000000101001000101110000111110000101101100101110100100111001111110101010001011001110001010100111000111101000011111110101010100011000110100110000010101101111001000111100001011110111101010110111000011010001100110000111000011001111100100111000101111111101010101000110000101101100001100110100101001100000011110000000010101100111100001011010101101011000011001111110101011111110111010001100010010001101101110111101010110111100100011010001101101110111001110010110100101011101111111101010100010110011110000101101010110101100110000100011111100110101011011110001110001110110001111110101011111101011101001010111101111000101110110111110101010001001000110110111010011001110111011011101110000111011101010101100100000101010100011110010110011011110110000001101010000110000101111001101010110111110110100111110111100100001011110011110000001111010111010010101111011110001011101101110000001010100100000011100111010101100111000000101110011111011111110011101011010000001110110100000011110011000110010001011000110000111101110001111010111111011000000000010011001110111011000101111000010010100110100001010000110101011000010111010001101110001010101100111110110010100111011100111000100111111111100000111100001100101101111101111110011110111010111111000001010101010001011110111101010110111000101010110011111011011101001100011000110110100101101000010100101001101111010101111110101111010001100100100011001010001110110011100111110110000101001001100010011101101101001011011111011011101000101100001111011111000001\"" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "HuffmanCoding hc(original_message);\n", "\n", "std::string message = original_message;\n", "std::string compressed = hc.compress(message);\n", "compressed" ] }, { "cell_type": "code", "execution_count": 10, "id": "awful-scout", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code proceeds by means of Huffman coding, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper \"A Method for the Construction of Minimum-Redundancy Codes\".\"" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "std::string recovered = hc.decompress(compressed);\n", "recovered" ] }, { "cell_type": "code", "execution_count": 11, "id": "single-shame", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(recovered == message)" ] } ], "metadata": { "kernelspec": { "display_name": "C++17", "language": "C++17", "name": "xcpp17" }, "language_info": { "codemirror_mode": "text/x-c++src", "file_extension": ".cpp", "mimetype": "text/x-c++src", "name": "c++", "version": "17" } }, "nbformat": 4, "nbformat_minor": 5 }