LZ77 compression algorithm (general code efficiency)

Question

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)
    Triplet n(0, 0, lookheadBuffer[0]);

    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
        std::string s = lookheadBuffer.substr(0, i);

        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();
            window.lookheadBuffer.append(byteDataString, 0, len);
            byteDataString.erase(0, len);
        }

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

        // Move the used part of lookheadBuffer to historyBuffer
        window.historyBuffer.append(window.lookheadBuffer, 0, tiplet.length + 1);
        window.lookheadBuffer.erase(0, tiplet.length + 1);

        // 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);

    } while (window.lookheadBuffer.length());
} 

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);
    }
}


void LZ77::readFileUncompressed(std::filesystem::path& path)
{
    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");
}


void LZ77::readFileCompressed(std::filesystem::path& path)
{
    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();
}

---

Header file:

#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
    {
        // History and lookhead buffer
        std::string lookheadBuffer;
        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 readFileUncompressed(std::filesystem::path& pathToFile);

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

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

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

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

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

Answer 1

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.readFileUncompressed("somepath");
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.