fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <string>
  5. #include <bitset>
  6. #include <sstream>
  7.  
  8. using namespace std;
  9.  
  10. // LZW Compression Algorithm
  11. vector<int> lzwCompress(const string& input) {
  12.     unordered_map<string, int> dictionary;
  13.     vector<int> output;
  14.  
  15.     // Initialize the dictionary with single characters (ASCII)
  16.     for (int i = 0; i < 256; ++i) {
  17.         dictionary[string(1, char(i))] = i;
  18.     }
  19.  
  20.     string current = "";
  21.     int code = 256;  // Next available code
  22.  
  23.     for (char c : input) {
  24.         current += c;
  25.  
  26.         // If the current substring exists in the dictionary, extend it
  27.         if (dictionary.find(current) != dictionary.end()) {
  28.             continue;
  29.         } else {
  30.             // Output the code for the current substring (longest match)
  31.             output.push_back(dictionary[current.substr(0, current.length() - 1)]);
  32.  
  33.             // Add the current substring to the dictionary
  34.             dictionary[current] = code++;
  35.  
  36.             // Start a new current substring
  37.             current = string(1, c);
  38.         }
  39.     }
  40.  
  41.     // Output the code for the last substring
  42.     if (!current.empty()) {
  43.         output.push_back(dictionary[current]);
  44.     }
  45.  
  46.     return output;
  47. }
  48.  
  49. // LZW Decompression Algorithm
  50. string lzwDecompress(const vector<int>& input) {
  51.     unordered_map<int, string> dictionary;
  52.     string output = "";
  53.  
  54.     int code = 256;  // Next available code
  55.     string prev = string(1, char(input[0]));
  56.     output += prev;
  57.  
  58.     dictionary[256] = prev;
  59.  
  60.     for (size_t i = 1; i < input.size(); ++i) {
  61.         int currentCode = input[i];
  62.         string current;
  63.  
  64.         // If the current code is already in the dictionary, just fetch it
  65.         if (dictionary.find(currentCode) != dictionary.end()) {
  66.             current = dictionary[currentCode];
  67.         } else {
  68.             // Handle the special case where the current code is the next code
  69.             current = prev + prev[0];
  70.         }
  71.  
  72.         output += current;
  73.  
  74.         // Add the new string to the dictionary
  75.         dictionary[code++] = prev + current[0];
  76.  
  77.         // Set the previous string for the next iteration
  78.         prev = current;
  79.     }
  80.  
  81.     return output;
  82. }
  83.  
  84. // Function to display a hexdump of the encoded data (like bvi style)
  85. void hexdump(const vector<int>& data) {
  86.     size_t offset = 0;
  87.     const size_t bytesPerLine = 16;
  88.  
  89.     while (offset < data.size()) {
  90.         printf("%08X  ", offset);
  91.  
  92.         // Print hexadecimal representation
  93.         for (size_t i = 0; i < bytesPerLine; ++i) {
  94.             if (offset + i < data.size()) {
  95.                 printf("%02X ", data[offset + i]);
  96.             } else {
  97.                 printf("   ");
  98.             }
  99.         }
  100.  
  101.         printf(" |");
  102.  
  103.         // Print ASCII representation
  104.         for (size_t i = 0; i < bytesPerLine; ++i) {
  105.             if (offset + i < data.size()) {
  106.                 char c = char(data[offset + i]);
  107.                 printf("%c", isprint(c) ? c : '.');
  108.             } else {
  109.                 printf(" ");
  110.             }
  111.         }
  112.  
  113.         printf("|\n");
  114.         offset += bytesPerLine;
  115.     }
  116. }
  117.  
  118. int main() {
  119.     // Example input data
  120.     string inputData = "this is an example of lzw compression in c++";
  121.  
  122.     // LZW Compression
  123.     vector<int> compressedData = lzwCompress(inputData);
  124.  
  125.     // LZW Decompression
  126.     string decompressedData = lzwDecompress(compressedData);
  127.  
  128.     // Output the results
  129.     cout << "Original Data: " << inputData << endl;
  130.     cout << "Decompressed Data: " << decompressedData << endl;
  131.  
  132.     // Hexdump the compressed data (encoded as integer codes)
  133.     cout << "Hexdump of the compressed data:" << endl;
  134.     hexdump(compressedData);
  135.  
  136.     return 0;
  137. }
  138.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Original Data: this is an example of lzw compression in c++
Decompressed Data: ttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt
Hexdump of the compressed data:
00000000  74 68 69 73 20 102 20 61 6E 20 65 78 61 6D 70 6C  |this . an exampl|
00000010  65 20 6F 66 20 6C 7A 77 20 63 6F 10D 72 65 73 73  |e of lzw co.ress|
00000020  69 6F 108 69 108 63 2B 2B                          |io.i.c++        |
https://ideone.com/unIR5a
lzw compression
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!