LZ-77 text compression algorithm

Question

This is my version of a LZ-77 lossless compression algorithm for text. It maintains a sliding window of 4095 characters and can pick up patterns up to 15 characters long. Basically, the compressed file is made of tuples (length, pos), with length on 4 bits and pos on 12 bits which makes 2 bytes each time. Besides, if I have to write a character that is not in the window, I set length=0, then I have 4 empty bits and the 8 bits left are used to encode the character.

I've spent a few hours on it correcting little bugs and it seems functional, although it appears not to work entirely for big files (size > window) but I'll correct this later. Anyway I'm not here for algorithm but for code design so tell me what's good or bad about this code, don't hesitate.

Also, I haven't implemented any file-manager system but the functions' names are quite explicit on how to use them.

#include <iostream>
#include <string>
#include <tuple>
#include <bitset>
#include <sstream>
#include <fstream>

using namespace std;

/**
Given two strings s1 and s2, find the longest prefix of s2 that is in s1
and returns the position of the prefix' first character in s1 and its length in a pair

If s1 = "lossless compression in opposition to " and s2 = "lossy compression", the longest prefix is "loss"
and the function returns (0, 4).
*/
pair<int, int> longest_prefix(string s1, string s2)
{
    int pos {0};
    int length {0};

    for(int i = 0; i < s1.size(); i++)
    {
        int l {0};
        while(i+l < s1.size() && l < s2.size() && s1[i+l] == s2[l])
            l++;

        if(l > length)
        {
            pos = i;
            length = l;
        }

        if(i == s1.size() - length || length == s2.size())
            return pair<int,int>(pos, length);
    }

    return pair<int,int>(pos, length);
}

/**
we have a sliding window of fixed size and instead of rewriting text that already is in the window,
we just refer to it with its position in the window and its size
*/
string lz77_compress(string s)
{
    string compressed { "" };
    int window_size { 4095 };
    int pattern_size { 15 };
    int i { 0 };

    while(i < s.size())
    {
        string s1 { i >= window_size ? s.substr(i - window_size, window_size) : s.substr(0, i) };
        string s2 { s.substr(i, min(pattern_size, (int)s.size() - i)) };
        pair<int,int> match = longest_prefix(s1, s2); // fst = pos; snd = length

        if(match.second == 0) // length = 0: no match, we just add a char (0, char)
        {
            compressed += (char)0;
            compressed += s[i];

            i++;
        }
        else // match, then we add (pos, length)
        {
            bitset<4> length(match.second);
            bitset<12> pos(match.first);
            bitset<16> concat(length.to_string() + pos.to_string()); // change a 4-bit and a 12-bit number into two 8-bits numbers
            bitset<8> bit1(concat.to_string().substr(0,8));
            bitset<8> bit2(concat.to_string().substr(8,8));
            compressed += (char)bit1.to_ulong();
            compressed += (char)bit2.to_ulong();

            i += match.second;
        }
   }

    return compressed;
}

string lz77_decompress(string compressed)
{
    string s { "" };
    int window_size { 4095 };

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

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

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

    return s;
}

Answer 1

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<4> length(match.second);
        bitset<12> pos(match.first);
        bitset<16> concat(length.to_string() + pos.to_string()); // change a 4-bit and a 12-bit number into two 8-bits numbers
        bitset<8> bit1(concat.to_string().substr(0,8));
        bitset<8> 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 << 4) | (pos >> 8));
        compressed += (char) (pos & 0xff);

        i += length;

Similarly, the decompress function:

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

    if(length == 0)
    {
        bitset<8> c(concat.to_string().substr(8, 8));
        s += (char)c.to_ulong();
    }
    else
    {
        bitset<12> 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 < compressed.size(); i += 2)
{
    unsigned char byte1 = compressed[i];
    unsigned char byte2 = compressed[i+1];
    int length = (byte1 >> 4);

    if(length == 0)
    {
        s += byte2;
    }
    else
    {
        int pos = ((byte1 & 0xf) << 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.