# How can I make my LZ77 algorithm to compress faster or to compress more?

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{

public:

RawData encode(RawData const& data);

private:
// 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
// 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;

};


Source

/*
The lookahead buffer is implicit within the data and
its size is limited by the max match length
SEARCH BUFFER
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
*/

/************************
PUBLIC
*************************/

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

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

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

return output;
}

/************************
PRIVATE
*************************/

// 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){
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
// CONDITIONS
// 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)){
++i;
length++;
}
// 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){
auto currentLength = length;
while(i < data.size() && length < MAX_LENGTH && data.get(i) == data.get(i + currentLength)){
++i;
++length;
}
}
return length;
}


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

Other


typedef unsigned char ByteType;

class RawData{

public:

...

private:

std::vector<ByteType> bytes;

};


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

Best regards, thanks!

• Is this an exercise, or is there some functionality the half a dozen or so LZ77 implementations are missing?
– user33306
Commented May 14, 2020 at 4:34
• Its not an exercice, its it is a personal project I wanted to code. But the project is not LZ77 is involves PNG Commented May 14, 2020 at 6:05
• 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 Commented May 20, 2020 at 21:02
• @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! Commented May 20, 2020 at 21:11
• 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 ...] Commented May 20, 2020 at 22:41