So, I am trying to create a PNG compression library, and to do that I need to use the DEFLATE algorithm; DEFLATE consists of two parts, the LZ77 compression, and the Huffman Compression. Currently, my LZ77 algorithm has a pretty good compression rate, although I think it could be better, the problem is that is really slow. I have tried some optimizations but its compression speed isn't acceptable. I have seen that libraries such as ZLIb implement something called a "Lazy matching" but I have just found vague explanations. To summarize I was wondering if someone could help me improve the algorithm. My main focus is to make it faster but if there is something I can do to increase the compression rate it'll also be really helpful.


class LZ77{


    RawData encode(RawData const& data);

    // searches for matches in the current
    // index of the look ahead buffer
    bool search(RawData const& data);
    // moves data from the lookahead buffer into the search buffer
    // by quantity positions
    void shift(RawData const& data, unsigned int quantity);
    // given an index in the search buffer , it returns the length
    // the longest match from that position
    unsigned int searchFromIndex(RawData const& data, int i) const;
    // the buffer size fixes the physical size of the search buffer
    // determined by the DEFLATE specifications
    static const unsigned int BUFFER_SIZE = 32 * 1024;
    // to limit the max length of an encountered string match
    static const unsigned int MAX_LENGTH = 258;
    // stop searching if length is long enough
    static const unsigned int MARGIN_LENGTH = 200;
    // to limit the minimum length a match must have to
    // be considered a match
    static const unsigned int MIN_LENGTH = 5; // Min length for a match
    // aheadSize is a pointer to the first element in the
    // look ahead buffer, hence the name
    unsigned int aheadPointer;
    // when a match is encounter the distance from the 0 position
    // and the match begining is saved as the offset
    unsigned int offset;
    // contains the largest match at a given time
    unsigned int matchLength;
    // represents the search buffer of the algorithm
    // where characters that have already been seen
    // are saved and discarted on buffer fill
    std::array<ByteType, BUFFER_SIZE> searchBuffer;



    The lookahead buffer is implicit within the data and
    its size is limited by the max match length
    The search buffer is implemented as a fixed array
    of size 32KB (32 * 1024), specified in the PNG standard
    The first position of the buffer is indexed by a 0


RawData LZ77::encode(RawData const& data){
    RawData output;
    aheadPointer = 0;
    // setup

    // main algorithm
    while(aheadPointer < data.size()){
        bool match = search(data);// 1. search
            shift(data, matchLength); // shift
            output.push("["+ std::to_string(offset) +"," + std::to_string(matchLength) + "]");
            aheadPointer += matchLength;
            shift(data, 1); // no match => add a single character

    std::cout << "LZ77 compression ratio: " << (float(data.size()) / output.size()) * 100 << std::endl;

    return output;


// pre: quantity <= BUFFER_SIZE
void LZ77::shift(RawData const& data, unsigned int quantity){

    // min is needed when search buffer is not full
    unsigned int size = std::min(BUFFER_SIZE, aheadPointer);
    // shift search buffer elements
    for(int i = quantity; i < size; ++i)
        searchBuffer[i - quantity] = searchBuffer[i];

    // move elements betweeen buffers
    for(int i = size - quantity; i < size; ++i)
        searchBuffer[i] = data.get(aheadPointer + i);


bool LZ77::search(RawData const& data){
    bool found = false;
    // min is needed when search buffer is not full
    unsigned int size = std::min(BUFFER_SIZE, aheadPointer);
    // set the matchLength to the minimum, this way
    // I only accept matches with at least that length
    matchLength = MIN_LENGTH;
    offset = 1;
    // 0 is the last element of the search buffer
    bool stopSearching = false;
    for(unsigned int i = 0; i < size && !stopSearching; ++i){
        if(searchBuffer[i] == data.get(aheadPointer)){
            auto length = searchFromIndex(data, i + 1);
            // find sequence with max length
            if(length > matchLength){
                found = true;
                offset = size - i;
                matchLength = length;
            auto separation = size - i + MAX_LENGTH;
            // if length is long enough or given the current
            // position we cannot get a better one, stop searching
            if(length >= separation || length >= MARGIN_LENGTH){
                stopSearching = true;
    return found;

unsigned int LZ77::searchFromIndex(RawData const& data, int i) const{
    unsigned int length = 1;
    unsigned int size = std::min(BUFFER_SIZE, aheadPointer);
    // continue comparing characters and incrementing the length
    // of the matching string
    // 1. check length is less than maximum lenght
    // 2. check iterator lesser than size of the buffer
    // 3. while there is a character match
    // RESULT
    // 1. increment the iterator -> decrements buffer position
    // 2. increment length
    while(length < MAX_LENGTH && i < size && searchBuffer[i] == data.get(length + aheadPointer)){
    // when we have compared all the search buffer
    // we can continue to compare data from within the lookup
    // buffer, this way we can compress the data even further
    if(i >= size){
        i = aheadPointer;
        auto currentLength = length;
        while(i < data.size() && length < MAX_LENGTH && data.get(i) == data.get(i + currentLength)){
    return length;

The RawData class is just a container for a byte vector.


   typedef unsigned char ByteType;

    class RawData{




        std::vector<ByteType> bytes;


You can test the entire program in https://github.com/polmonroig/sfic

Best regards, thanks!

  • \$\begingroup\$ Is this an exercise, or is there some functionality the half a dozen or so LZ77 implementations are missing? \$\endgroup\$
    – user33306
    May 14, 2020 at 4:34
  • 1
    \$\begingroup\$ Its not an exercice, its it is a personal project I wanted to code. But the project is not LZ77 is involves PNG \$\endgroup\$
    – polmonroig
    May 14, 2020 at 6:05
  • \$\begingroup\$ shift looks suspiciously slow. You may want a ring queue for searchBuffer. Also, you have to allocate/initialize output [RawData] on each call to encode. Might be faster to pre-allocate it and pass as a 2nd arg (ensuring there is sufficient space so that push does not grow/reallocate from the heap. To do a ring queue, you might consider: en.cppreference.com/w/cpp/container/deque \$\endgroup\$ May 20, 2020 at 21:02
  • \$\begingroup\$ @CraigEstey I'll modify the things that you mentioned. Yes, shifts looks very slow, but I didn't know how to optimize it. Thanks for your help! \$\endgroup\$
    – polmonroig
    May 20, 2020 at 21:11
  • \$\begingroup\$ Also, to_string seems to be implemented with vsnprintf and there are two calls, so you might be better off with doing your own single sprintf call [a bit "dirty", but ...] \$\endgroup\$ May 20, 2020 at 22:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.