LZ78 Encoding issue in C++
<p>I'm trying to implement the LZ78 compression algorithm in C++, and I want my program to work like this:</p>

<ol>
<li>Open file and read contents into string</li>
<li><p>Compress string, outputting a string containing the binary representation     of each (key, char) present in the dictionary.</p></li>
<li><p>Convert each 8-character chunk of the string to its binary number</p></li>
<li>Write these numbers to a file.</li>
</ol>

<p>For an example:</p>

<ol>
<li>string = "Kakashi."</li>
<li><p>Running the algorithm produces 
(0, K)
(0, a)
(0, k)
(2, s)
(0, h)
(0, i)
(0, .)
(0, )</p>

<p>The binary representation of all pairs:
00000000010010110000000001100001000000000110101100000010011100110000000001101000000000000110100100000000001011100000000000001010</p></li>
<li><p>In my code I read the string above 8 chars at a time, convert it to a number, writing it to the file, in binary mode.</p></li>
</ol>

<p>But, if the string I want to compress is a bit longer, when I decompress it, not every word is right, some letters are missing and others are out of order. I believe I'm doing something very wrong when I write the compressed text to the file.  </p>

<p>Here is my full code:</p>

<pre><code>#include &lt;bits/stdc++.h&gt;
#include &lt;list&gt;
#include &lt;bitset&gt;
#include &lt;iostream&gt;
#include &lt;fstream&gt;
#include &lt;string&gt;
#include &lt;algorithm&gt;
#include &lt;queue&gt;

using namespace std;

string encode_int(int in)
{
  return bitset&lt;8&gt;(in).to_string();
}

int decode_int(char out)
{
  return bitset&lt;8&gt;(out).to_ulong();
}

string encode_char(string in)
{
  return bitset&lt;8&gt;(in[0]).to_string();
}

char decode_char(string out)
{
  return (char)bitset&lt;8&gt;(out).to_ulong();
}

struct Dict
{
  string label; // dictionary entry string
  char output;  // first non-matching symbol
  int entry;    // longest matching dictionary entry

  Dict(string label, int entry, char output) // constructor
  {
    this-&gt;label = label;
    this-&gt;entry = entry;
    this-&gt;output = output;
  }
};

int find(string l, list&lt;Dict&gt; enc_list)
{ // change list to map

  list&lt;Dict&gt; temp = enc_list;
  int i = 1;

  while(!temp.empty())
  {
      if(!(l.compare(temp.front().label)))
      {
          return i;
      }
      temp.pop_front();
      i++;
  }
  return -1;
}

void write_file(string input, string output_filename)
{
  string one_byte;
  unsigned long bin_number;
  unsigned char chr;
  int i, len = input.length();

  FILE *fp;
  fp = fopen(output_filename.c_str(), "wb");

  if(fp == NULL)
  {
    printf("Unable to open output file!\n");
    return;
  }

  for (i=0; i&lt;len; i+= 8)
  {
    one_byte = input.substr(i, 8);
    bin_number = strtol(one_byte.c_str(), NULL, 2);

    chr = bin_number;
    fprintf(fp, "%c", bin_number);
  }

  fclose(fp);
}

void LZ78_Compress(string txt, string output_filename)
{
  list &lt;Dict&gt; Dictionary;
  string Prefix = "", Char, compressed;

  int CodeWord, IndexForPrefix = 1, len, i;

  len = txt.length();


  for(i=0; i&lt;len; i++){

     Char = string(1, txt[i]);

     IndexForPrefix = find((Prefix + Char), Dictionary);  // if it equals to -1, it means (Prefix + Char) is not in the dictionary
     if(IndexForPrefix != -1)
     {    
         Prefix = Prefix + Char; // if  Prefix + Char already exists, append Char
     }

     else
     {
        if(Prefix.empty())
        {
          CodeWord = 0;           // if Prefix is empty, a new letter was processed
          compressed += "00000000";
        }
        else
        {
          CodeWord = find(Prefix, Dictionary);     // search Prefix index
          compressed += encode_int(CodeWord);       // encode index
        }

        compressed += encode_char(Char);                                // encode char
        Dictionary.push_back(Dict((Prefix + Char), CodeWord, txt[i])); // add new entry to the dictionary
        Prefix.clear();      
     }
  } 

  write_file(compressed, output_filename);
}

void LZ78_Decompress(string input_filename, string output_filename)
{
  // Decompression Variables
  string dict = "";
  string decompressed_text;      // the the decomressed string
  string compressed_text;        // the compressed input
  string character;              // the character immediately after the current codeword
  string temp;                   

  unsigned char ch;
  unsigned int codeword, l = 0, i, len;           // the current dictionary entry being processed

  FILE *fp;
  fp = fopen(input_filename.c_str(), "rb");

  if(fp == NULL)
  {
    printf("Unable to open compressed file!\n");
    return;
  }


  while(fscanf(fp, "%c", &amp;ch) == 1)
  {
    compressed_text += ch;
  }
  len = compressed_text.length();

  fclose(fp);

  ofstream outfile(output_filename.c_str(), ios::binary);

  int *idx = new int[len]; // used for storing the index of the i-th dictionary entry

  for (i=0;i&lt;len;i+=2)
  {
    codeword = compressed_text[i];                      // longest matching dictionary entry
    character = compressed_text.substr(i + 1, 1);       // first non-matching symbol
    dict += character;                           
    idx[l] = codeword;
    l++; // idx size

    // let's say l = 0
    // then (idx[0], dict[0]) represents the first dictionary entry

    if(codeword == 0)
    {
        decompressed_text += character; // new letter, just append
    }

    else
    {      
       while(codeword &gt; 0)  // go back in the dictionary string, adding each letter until you get one with codeword = 0
       {
        temp += dict[codeword-1];
        codeword = idx[codeword-1];
       }
       reverse(temp.begin(), temp.end()); // restore correct order
       decompressed_text += temp;         // append string and char
       decompressed_text += character;
       temp.clear();
    }
  }
  outfile &lt;&lt; decompressed_text;
  outfile.close();
}


void Compress(string input_filename, string output_filename)
{
  ifstream in(input_filename.c_str());
  string line, txt;

  while(getline(in, line))
  {
    txt += line;
    txt += "\n";
  }
  in.close();

  LZ78_Compress(txt, output_filename);
}

int main()
{
  Compress("FullText.txt", "Compressed.out");
  LZ78_Decompress("Compressed.out", "Decompressed.out");
}
</code></pre>

<p>If I run it with "Kakashi" as input, it works fine. But if I run with </p>

<p>"Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aenean commodo ligula eget dolor. Aenean massa. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Donec quam felis, ultricies nec, pellentesque eu, pretium quis, sem. Nulla consequat massa quis enim. Donec pede justo, fringilla vel, aliquet nec, <em>vulputate eget, arcu.</em>"</p>

<p>the program outputs almost the whole string, but instead of this </p>

<p>[vulputate eget, arcu.] </p>

<p>it shows this [vulputatricéeget, arcu.]</p>