C++ LZ77 compression algorithm

Question

I had a hard time with int / size_t as we can't really substract a size_t. So I don't know if I used size_t well but I wanted to handle input strings as big as possible.

lz77 encodes and ilz77 decodes.

As external functions that I didn't copy here, there are:

int bin_to_dec(std::string bin) which converts a binary number into its decimal representation

std::string dec_to_bin(int dec, int nb_bits=-1) which does the reverse operation: takes a decimal number and outputs its binary representation of size nb_bits by adding additional 0 at the left if it is necessary.

Here is my algorithm:

#include "BinaryTools.h"

#include <string>
#include <cmath>
#include <algorithm>
#include <tuple>


/**
returns a pair (p, n) where p is the position of the first character of the match relatively to the end of dictionary (p = 0 means no match)
    and n is the length of the match
the match is the longest substring of dictionary + lookahead_buffer which is a prefix of lookahead_buffer (where + represents string concatenation)
*/
std::pair<int, int> get_longest_match(const std::string& dictionary, const std::string& lookahead_buffer)
{
    int p = 0; // q = dictionary.size() - p
    int n = 0;

    int dict_size = dictionary.size();
    int buffer_size = lookahead_buffer.size();

    for(int q = 0; q < dictionary.size(); q++)
    {
        int local_n = 0;
        while(local_n < std::min(buffer_size, dict_size - q) && dictionary[q + local_n] == lookahead_buffer[local_n])
            local_n++;
        if(local_n == dict_size - q) // the match may continue in the buffer
        {
            int buffer_index = 0;
            while(local_n < buffer_size && lookahead_buffer[buffer_index] == lookahead_buffer[local_n])
            {
                buffer_index++;
                local_n++;
            }
        }
        if(local_n > n)
        {
            n = local_n;
            p = dict_size - q;
        }
    }

    std::cout << n << " ";
    return std::make_pair(p, n);
}

/**
0: char on 8 bits
1: tuple (p, n) on 15 + 8 bits (only if n >= 3, otherwise send chars)
    note: p is shifted 1 down and n is shifted 3 down
*/
std::string lz77(const std::string& input)
{
    size_t cursor = 0;
    size_t input_size = input.size();

    int dictionary_size = pow(2, 15); // (2^15 - 1) + 1 because p >= 1 if there is a match
    int buffer_size = pow(2, 8) + 2; // (2^8 - 1) + 3 because n >= 3

    std::string output, output_bin;
    size_t output_bin_cursor = 0;

    while(cursor < input_size)
    {
        // if cursor < dictionary_size then substr(0, cursor) else substr(cursor - dictionary_size, dictionary_size)
        std::string dictionary = input.substr(std::max(0, (int)cursor - dictionary_size), std::min(cursor, (size_t)dictionary_size)); // PB
        std::string buffer = input.substr(cursor, buffer_size);

        std::pair<int, int> x = get_longest_match(dictionary, buffer);

        int p = x.first; // in {1, ..., 2^15}, will be shifted to {0, ..., 2^15 - 1} ; 2^15 = 32768
        int n = x.second; // in {3, ..., 2^8 + 2}, will be shited to {0, ..., 2^8 - 1} ; 2^8 = 256
        if(n < 3)
        {
            output_bin += "0";
            output_bin += dec_to_bin((int)(unsigned char)input[cursor], 8);
            cursor++;
        }
        else
        {
            output_bin += "1";
            output_bin += dec_to_bin(p - 1, 15);
            output_bin += dec_to_bin(n - 3, 8);
            cursor += n;
        }

        int output_bin_size = output_bin.size();
        while(output_bin_size - output_bin_cursor >= 8)
        {
            std::string c = output_bin.substr(output_bin_cursor, 8);
            output += (char)bin_to_dec(c);
            output_bin_cursor += 8;
        }

        if(output_bin_size > output_bin.max_size() - 100)
        {
            output_bin.erase(0, cursor);
            output_bin_cursor = 0;
        }
    }

    // fill last byte with 0 (minimal size to encode a something is 9 anyway)
    output_bin.erase(0, output_bin_cursor);
    if(!output_bin.empty())
    {
        std::string fill_byte(8 - output_bin.size(), '0');
        output_bin += fill_byte;
        std::string c = output_bin.substr(0, 8);
        output += (char)bin_to_dec(c);
    }

    return output;
}

std::string ilz77(const std::string& input)
{
    size_t input_size = input.size();
    size_t input_cursor = 0;

    std::string input_bin;
    size_t input_bin_cursor = 0;

    // initial input_bin fill
    while(input_cursor < input_size && input_bin.size() < input_bin.max_size() - 100)
    {
        input_bin += dec_to_bin((int)(unsigned char)input[input_cursor], 8);
        input_cursor++;
    }

    std::string output;

    while(!input_bin.empty())
    {
        char type = input_bin[input_bin_cursor];
        input_bin_cursor++;

        if(input_bin_cursor > input_bin.size() || input_bin.size() - (int)input_bin_cursor < 8) // only last byte filling bits remain
            return output;

        if(type == '0')
        {
            std::string c = input_bin.substr(input_bin_cursor, 8);
            output += (char)bin_to_dec(c);
            input_bin_cursor += 8;
        }
        else
        {
            int p = bin_to_dec(input_bin.substr(input_bin_cursor, 15)) + 1;
            input_bin_cursor += 15;
            int n = bin_to_dec(input_bin.substr(input_bin_cursor, 8)) + 3;
            input_bin_cursor += 8;

            size_t match_begin = output.size() - p; // not just substr because of the eventual overlap
            for(int k = 0; k < n; k++)
                output += output[match_begin + k];
        }

        // refill input_bin
        if(input_bin.size() - (int)input_bin_cursor < 100 && input_cursor < input_size)
        {
            input_bin.erase(0, input_bin_cursor);
            input_bin_cursor = 0;

            while(input_cursor < input_size && input_bin.size() < input_bin.max_size() - 100)
            {
                input_bin += dec_to_bin((int)(unsigned char)input[input_cursor], 8);
                input_cursor++;
            }
        }
    }

    return output;
}

My get_longest_match function is quite slow but I had seen and idea using hash tables, which I will try to implement later on.

UPDATE: as requested, here is my BinaryTools.h file:

#ifndef BINARYTOOLS_H
#define BINARYTOOLS_H

#include <string>

std::string next_bin(std::string bin)
{
    int k = bin.size() - 1;
    while(bin[k] == '1')
    {
        bin[k] = '0';
        k--;
    }
    if(k == -1)
        bin = "1" + bin;
    else
        bin[k] = '1';
    return bin;
}

int bin_to_dec(std::string bin)
{
    int dec = 0;
    int n = bin.size();
    int k = 1;
    for(int i = 0; i < n; i++)
    {
        if(bin[n-1-i] == '1')
            dec += k;
        k *= 2;
    }
    return dec;
}

// if nb_bits > 1, add 0s at the beginning of the output string so that its size is nb_bits
std::string dec_to_bin(int dec, int nb_bits=-1)
{
    std::string bin;
    while(dec != 0)
    {
        if(dec % 2 == 0)
        {
            bin = "0" + bin;
            dec /= 2;
        }
        else
        {
            bin = "1" + bin;
            dec = (dec - 1) / 2;
        }
    }

    if(nb_bits > 0 && bin.size() < nb_bits)
    {
        std::string fill(nb_bits - bin.size(), '0');
        return fill + bin;
    }
    return bin;
}


#endif // BINARYTOOLS_H

Answer 1

Welcome to code review, a nice first question. The code is well written and readable. Just a few observations that may help improve the code:

As @TobySpeight mentioned, you should change the variables to size_t so that the warning messages go away.

Missing Header File

The code is missing

#include <iostream>

which is causing the bug @TobySpeight mentioned.

Functions in Header Files

Obviously putting function bodies into header files works, however, it is more common to put function prototypes into headers and function bodies into cpp source files. The reason for this is that if the header file that includes function bodies is included by multiple files, the functions are now multiply defined and the user runs into multiple definition errors at link time. One way around this is to make the functions in the header file static, but it is much better to just have the prototypes in the header file and link multiple object files together.

Reduce Complexity, Follow SRP

The Single Responsibility Principle states that every module or class should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by the class. All its services should be narrowly aligned with that responsibility.

Robert C. Martin expresses the principle as follows:
    `A class should have only one reason to change.`

While this is primarily targeted at classes in object oriented languages it applies to functions and subroutines well.

The lz77(const std::string& input) function could be broken up into at multiple functions, especially the outer while loop. The inner while loop seems to be a good candidate for a function, the two clauses of the first if statement also seem to be good candidates for functions.

The more separate functions there are the easier it is to understand or read the code. This also makes it easier for any programmer to maintain or debug the code.

The function ilz77(const std::string& input) also seems overly complex and could be broken up as well.

Numeric Constants versus Symbolic Constants

There are several numeric constants (8, 15, 3, 100) used that really aren't explained. It might be better to use symbolic constants which give names and meanings to these values. This does a number of things in C++

1. It clearly defines what the number means, which makes the code more readable.
2. It provides a type for the type checking that makes C++ a strongly typed language.
3. It makes it easier to change the algorithm by allowing the values to change in one place rather than going through all the code to make the changes necessary.

Class Versus Procedure

If the target of this code is a set of library routines, it might make more sense to encapsulate it in a class. This would provide the functionality already here with a single or fewer interfaces to call to implement the compression.

Inconsistent Variable Naming Conventions

The code contains well named variables such as dict_size and buffer_size but then it contains variables with names such as p, n and q are harder to understand. Keep in mind that code needs to be maintained and features may need to be added in 3 to 5 years. Even the original author of the code may have a hard time maintaining code with single character variable names after such a length of time.

Answer 2

You should fix these compiler warnings:

g++ -std=c++17 -fPIC -g -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Weffc++      164064.cpp    -o 164064
164064.cpp: In function ‘std::__cxx11::string dec_to_bin(int, int)’:
164064.cpp:53:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(nb_bits > 0 && bin.size() < nb_bits)
                       ~~~~~~~~~~~^~~~~~~~~

164064.cpp: In function ‘std::pair<int, int> get_longest_match(const string&, const string&)’:
164064.cpp:84:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int q = 0; q < dictionary.size(); q++)
                    ~~^~~~~~~~~~~~~~~~~~~

164064.cpp: In function ‘std::__cxx11::string lz77(const string&)’:
164064.cpp:157:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(output_bin_size > output_bin.max_size() - 100)
            ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

To fix the middle one of these, I think that get_longest_match() should be operating exclusively on unsigned types:

std::pair<int, int> get_longest_match(const std::string& dictionary,
                                      const std::string& lookahead_buffer)
{
    auto n = 0u;

    auto const dict_size = dictionary.size();
    auto const buffer_size = lookahead_buffer.size();

    for (size_t q = 0; q < dictionary.size(); q++) {
        auto local_n = 0u;
        while (local_n < std::min(buffer_size, dict_size - q) && dictionary[q + local_n] == lookahead_buffer[local_n])
            ++local_n;

        if (local_n == dict_size - q) {
            // the match may continue in the buffer
            for (int buffer_index = 0;
                 local_n < buffer_size && lookahead_buffer[buffer_index] == lookahead_buffer[local_n];
                 ++buffer_index)
                ++local_n;
        }
        if (local_n > n)
            n = local_n;
    }

    return std::make_pair(dict_size - q, n);
}

Also,

164064.cpp:105:5: error: ‘cout’ is not a member of ‘std’
     std::cout << n << " ";
     ^~~

I'm guessing that's just some stray debug you didn't mean to leave in.