# LZ77 compression algorithm (general code efficiency)

I'm implementing LZ77 compression algorithm. To compress any file type, I use its binary representation and then read it as chars (because 1 char is equal to 1 byte, afaik) to a std::string. Current program version compresses and decompresses files (.txt, .bmp, etc) just fine – size of raw file in bytes matches the size of uncompressed file.

And now for the actual code part. Here's the short info on how LZ77 handles compression:

Below are 2 main functions: compress and findLongestMatch:

• compress moves char data between 2 buffers and saves encoded tuple ⟨offset, length, nextchar⟩
• findLongestMatch finds the longest match of lookheadBuffer in historyBuffer

So, any way to improve efficiency (time / memory) in general? Search, comparisons? Also, I don't like my loops so much, any thoughts on how to make things more elegant?

UPD: To clarify things, I hope to get code review all in all.

Thank you!

Code:

LZ77::Triplet LZ77::slidingWindow::findLongestPrefix()
{
// Minimal tuple (if no match >1 is found)

size_t lookCurrLen = lookheadBuffer.length() - 1;
size_t histCurrLen = historyBuffer.length();

// Increasing the substring (match) length on every iteration
for (size_t i = 1; i <= std::min(lookCurrLen, histCurrLen); i++)
{
// Getting the substring

size_t pos = historyBuffer.find(s);
if (pos == std::string::npos)
break;

if ((historyBuffer.compare(histCurrLen - i, i, s) == 0) && (lookheadBuffer[0] == lookheadBuffer[i]))
pos = histCurrLen - i;

// check if there are any repeats
// following the of current longest substring in lookheadBuffer
int extra = 0;
if (histCurrLen == pos + i)
{
// Check for full following repeats
while ((lookCurrLen >= i + extra + i) && (lookheadBuffer.compare(i + extra, i, s) == 0))
extra += i;

// Check for partial following repeats
int extraextra = i - 1;
while (extraextra > 0)
{
if ((lookCurrLen >= i + extra + extraextra) && (lookheadBuffer.compare(i + extra, extraextra, s, 0, extraextra) == 0))
break;
extraextra--;
}

extra += extraextra;
}

// Compare the lengths of matches
if (n.length <= i + extra)
n = Triplet(histCurrLen - pos, i + extra, lookheadBuffer[i + extra]);
}

return n;
}

void LZ77::compress()
{
do
{
if ((window.lookheadBuffer.length() < window.lookBufferMax) && (byteDataString.length() != 0))
{
int len = window.lookBufferMax - window.lookheadBuffer.length();
byteDataString.erase(0, len);
}

LZ77::Triplet tiplet = window.findLongestPrefix();

// Move the used part of lookheadBuffer to historyBuffer

// If historyBuffer's size exceeds max, delete oldest part
if (window.historyBuffer.length() > window.histBufferMax)
window.historyBuffer.erase(0, window.historyBuffer.length() - window.histBufferMax);

encoded.push_back(tiplet);

}

void LZ77::decompress()
{
for (auto code : encoded)
{
int length = code.length;
if (length)
{
// Getting the substring
std::string s = byteDataString.substr(byteDataString.length() - code.offset, std::min(length, code.offset));
// Considering the repeats
while (length)
{
int repeat = std::min(length, static_cast<int>(s.length()));
byteDataString.append(s, 0, repeat);
length -= repeat;
}
}
byteDataString.append(1, code.next);
}
}

{
std::ifstream file(path, std::ios::in | std::ios::binary);

if (file.is_open())
{
// Building the byte data string
byteDataString = std::string(std::istreambuf_iterator<char>(file), {});
file.close();
}
else
throw std::ios_base::failure("Failed to open the file");
}

void LZ77::createFileCompressed(std::filesystem::path& path)
{
std::ofstream out(path / "packed.lz77", std::ios::out | std::ios::binary);

if (out.is_open())
{
for (auto triplet : encoded)
{
intToBytes(out, triplet.offset);
out << triplet.next;
intToBytes(out, triplet.length);
}
out.close();
}
else
throw std::ios_base::failure("Failed to open the file");
}

{
std::ifstream file(path, std::ios::in | std::ios::binary);

if (file.is_open())
{

Triplet element;

while (file.peek() != std::ifstream::traits_type::eof())
{
element.offset = intFromBytes(file);
file.get(element.next);
element.length = intFromBytes(file);
encoded.push_back(element);
}
file.close();
}
else
throw std::ios_base::failure("Failed to open the file");
}

void LZ77::createFileUncompressed(std::filesystem::path& path)
{
std::ofstream out(path / "unpacked.unlz77", std::ios::out | std::ios::binary);
out << byteDataString;
out.close();
}


#include <iostream>
#include <fstream>
#include <iterator>
#include <vector>
#include <string>
#include <filesystem>
#include <algorithm>

class LZ77
{
struct Triplet
{
int offset;
int length;
char next;

Triplet() = default;
Triplet(int off, int len, char next) : offset(off), length(len), next(next) {};
~Triplet() = default;
};

struct slidingWindow
{
std::string historyBuffer;

// Max buffers sizes
size_t lookBufferMax;
size_t histBufferMax;

slidingWindow() = default;
slidingWindow(std::string hbf, std::string lhbf) : historyBuffer(hbf), lookheadBuffer(lhbf) {}
~slidingWindow() = default;

// Function to get longest match
Triplet getLongestPrefix();
};

// Sliding window (2 buffers)
LZ77::slidingWindow window;

// Byte data string
std::string byteDataString;

// Vector of encoded tuples <offset, length, next>
std::vector<Triplet> encoded;

public:

void compress();

void decompress();

void createFileCompressed(std::filesystem::path& pathToFile);

void createFileUncompressed(std::filesystem::path& pathToFile);

void reset()
{
encoded.clear();
window.historyBuffer.clear();
byteDataString.clear();
}

LZ77(size_t lookBufMaxSize, size_t histBufMaxSize)
{
window.lookBufferMax = lookBufMaxSize * 1024;
window.histBufferMax = histBufMaxSize * 1024;
};
};

• It seems that the compression code is the same as in your previous question codereview.stackexchange.com/q/233262/35991, and has already been reviewed. Dec 11, 2019 at 12:56
• In that question I specifically asked, if there was a more efficient way of finding longest common match, and yes, that question was answered. Now I hope to get a code review in general. Logic, ways to improve time / memory efficiency overall, not only compression specifically Dec 11, 2019 at 13:08
• Adding the header file and a small example showing expected results would greatly improve this question and make it much easier to review. Dec 11, 2019 at 13:32

# Rework the API

The main issue with your code is the way you structured your API. It is a bit weird and not generic. If I want to compress a file, I need to write four lines of code:

LZ77 lz77(5, 7);
lz77.compress();
lz77.createFileCompressed("somepath");


First of all, what numbers should I specify for lookBufMaxSize and histBufMaxSize? Unless I know the algorithm intimately, I don't have any clue what numbers are good. It would be better to have defaults, and a simple way to set these parameters, similar to how gzip has compression levels from 1 to 9.

Second, why do you have to specify a directory, but not the actual filename that is to be read or written? It would be better if the application can choose the complete filename.

Third, I need to read the file, compress it, and write it back in separate steps. But it is very unlikely that I would ever want to run these steps in a different order. So it would make much more sense to have a single function that does everything in one go, so I could write something like:

LZ77 lz77(...);
lz77.compress("somepath/uncompressed.txt", "somepath/compressed.lz77");


But then it would even be better to avoid instantiating a class. What if we could just write:

LZ77::compress("somepath/uncompressed.txt", "somepath/compressed.lz77");


Perhaps with an optional third parameter to set the compression level. This will make the API much simpler, and prevent mistakes from happening. For example, with your API it is probably not safe to reuse an instance of class LZ77 without calling reset() between operations.

By limiting the input and output methods of the class to reading and writing files, you have made your code less general than possible. What if an application already has some data in memory, and wants to send a compressed version of it over the network? Having to write it out to file, then compressing it, writing it to another file, and reading back is hugely inefficient. Also, if the application does want to read and write to files, but already has an open input or output stream, it would be much nicer if you could pass in those.

Having a class keeping state would make more sense if you would support some kind of streaming interface, where an application could feed small amounts of data into the state at a time.

# Avoid large temporary buffers

One way to improve memory usage is to get rid of the temporary buffers, which you can do if you make the API changes I mentioned above. If you are (de)compressing a file of N bytes, this will save you something in the order of 2*N bytes worth of memory.