LZ-77 text compression algorithm
Bug

The bug you mentioned about not handled files larger than 4K is here:


        s += s.substr(max(0, i - window_size) + pos.to_ulong(), length);



Here, i is the amount of compressed file you have read so far.  But you want to use the size of the decompressed file instead.  So that line should be changed to:

        s += s.substr(max(0, (int) s.size() - window_size) +
                pos.to_ulong(), length);


I tested this change against a large file and it fixed the problem.

Substrings are costly

In the main loop of lz_compress(), you set call s.substr() for every byte of the input file, and the substring can be as large as your window size (4KB).  Each time you do that, you are making a copy of a portion of the original string.  So for a 1 MB file, you end up copying 4 GB of data during the course of your compression loop.  You could do a lot better if you just passed the original string into your longest_prefix() function along with the start index and length of the substring you would have created.  That way you wouldn't need to make unneeded copies of your input string.

Simplification of bit packing/unpacking

It looks like you did something really complicated here with bitsets in the compress function:


        bitset&lt;4&gt; length(match.second);
        bitset&lt;12&gt; pos(match.first);
        bitset&lt;16&gt; concat(length.to_string() + pos.to_string()); // change a 4-bit and a 12-bit number into two 8-bits numbers
        bitset&lt;8&gt; bit1(concat.to_string().substr(0,8));
        bitset&lt;8&gt; bit2(concat.to_string().substr(8,8));

        i += match.second;



This could be simplified to:

        int pos    = match.first;
        int length = match.second;
        compressed += (char) ((length &lt;&lt; 4) | (pos &gt;&gt; 8));
        compressed += (char) (pos &amp; 0xff);

        i += length;


Similarly, the decompress function:


for(int i = 0; i &lt; compressed.size(); i += 2)
{
    bitset&lt;8&gt; bit1(compressed[i]);
    bitset&lt;8&gt; bit2(compressed[i+1]);
    bitset&lt;16&gt; concat(bit1.to_string() + bit2.to_string());
    bitset&lt;4&gt; length_b(concat.to_string().substr(0,4));
    int length = length_b.to_ulong();

    if(length == 0)
    {
        bitset&lt;8&gt; c(concat.to_string().substr(8, 8));
        s += (char)c.to_ulong();
    }
    else
    {
        bitset&lt;12&gt; pos(concat.to_string().substr(4, 12));

        s += s.substr(max(0, (int) s.size() - window_size) +
                pos.to_ulong(), length);
    }
 }



could be simplified to:

for(int i = 0; i &lt; compressed.size(); i += 2)
{
    unsigned char byte1 = compressed[i];
    unsigned char byte2 = compressed[i+1];
    int length = (byte1 &gt;&gt; 4);

    if(length == 0)
    {
        s += byte2;
    }
    else
    {
        int pos = ((byte1 &amp; 0xf) &lt;&lt; 8) | byte2;

        s += s.substr(max(0, (int) s.size() - window_size) + pos, length);
    }


}

Speed of compression

One of the slowest parts of your program is the longest_prefix() function.  This function searches a 4KB window for the longest match to a 16 byte pattern.  Your brute force search takes \$O(n*m)\$ time, where \$n\$ = 4KB and \$m\$ = 16.  To achieve faster compression speeds, you will need to use a faster search algorithm.  Some alternatives are: Knuth-Morris-Pratt searching or hash tables.  I found this webpage that discusses some of the various alternatives with sample implementations, if you are interested in improving your search algorithm.