How to implement LZ77 compression using a single line as an example?

Question

C++ / C#

There is a task to encode a string using the LZ77 method. Nowhere on the Internet did I find either a normal explanation of the algorithm "on the shelves" or an adequate code in c ++. The way I understand the current algorithm is cumbersome and wrong. For a long time I created code that does not work, and which is difficult to debug, again because I myself do not fully understand the very algorithm ...

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

int numGL;

struct LZ77 {
    char distance;
    char count;
    char nextSym;
    LZ77* next = 0;
    LZ77(char a, char b, char c) {
        this->distance = a;
        this->count = b;
        this->nextSym = c;
    }
};

void addToStruct(LZ77 *& code, char distance, char count, char nextSym) {
    if (code->next == 0) {
        LZ77* New = new LZ77(distance, count, nextSym);
        code->next = New;
    }
    else
    {
        addToStruct(code->next, distance, count, nextSym);
    }

}

void LZ77Out(LZ77* code) {
    if (code->next == 0)
        return;
    cout << (int)code->distance << "." << (int)code->count << "." << code->nextSym << endl;
    LZ77Out(code->next);
}

int contains(string window, string key) {
    stringstream ss;
    string buf;
    int index = -1;
    if (key.size() == 2)
    {
        if (window.find(key) != string::npos) {
            numGL = 2;
            return window.find(key);
        }
        else {
            return -1;
        }
    }
    if (key.size() == 3) {
        ss << key[0] << key[1];
        ss >> buf;
        ss = {};
        if (window.find(buf) != string::npos) {
            index = window.find(buf);
        }
        else {
            index = -1;
        }
        if (index!=-1) {
            buf += key[2];
            if (window.find(buf) != string::npos) {
                numGL = 3;
                return window.find(buf);
            }
            else {
                numGL = 2;
                return index;
            }
        }
        else {
            buf = "";
            ss << key[1] << key[2];
            ss >> buf;
            ss = {};
            if (window.find(buf) != string::npos) {
                numGL = 2;
                return window.find(buf);
            }
            else {
                index = -1;
            }
        }
    }
    return index;
}

LZ77 *encodeLZ77(string input) {
    string window = to_string(input[0]-48);
    string buf = "";
    stringstream ss;
    int index, temp = 0;
    for (int a = 0; a < 3; a++) {
        buf += input[a];
    }
    LZ77* code = new LZ77(0,0,input[0]);
    for (int a = 1; true; a++) {
        numGL = 0;
        if (a == input.size())
            break;
        window += input[a];
        if (buf.size() == 1) {
            addToStruct(code,0, 0, input[a]);
        }
        if (contains(window, buf) != -1) {
            index = window.size() - contains(window, buf);
            addToStruct(code,index, numGL, input[a]);
        }
        else {
            addToStruct(code,0,0,input[a+1]);
        }
        if (numGL == 3) {
            for (int b = a; b < input.size(); b++) {
                if (temp == 3)
                    break;
                ss << input[b];
                temp++;
            }
            buf = "";
            ss >> buf;
            buf = {};
        }
        if (numGL == 2) {
            for (int b = a; b < input.size(); b++) {
                if (temp == 2)
                    break;
                ss << input[b];
                temp++;
            }
            buf = "";
            ss >> buf;
            buf = {};
        }
    }
    return code;
}

int main()
{
    LZ77Out(encodeLZ77("0100001000000100001"));
}

First of all, I have no idea how to make an adequate check for the content of any part of the buffer in the "window". Therefore, the buffer is only 3 characters long, and even there I had to pardon, shit-code (the contains function). This contains should return the found index of some part of the string in the window, and then subtracting the index from the length of the window, in theory, should receive the number of shifts for the link. Number numGL is a global variable that should store the number of characters that match in the link. The structure itself is made in the form of a singly-directed list, the choice fell in favor of it due to the fact that it is not necessary to store useless characters as in a string ("." - to separate the shift, quantity and character).

Answer 1

Something weird for sure. Some kind of global variable, streams from strings... there is new, but no delete ("memory leak"). Why not use the library sheet? Also, c++ differs from Java/Python -- when passed by value of a container (in particular a string), it is copied (or moved, but when using additional functions); this is worth doing if the function needs its own ownership of the object, and not just reading its data. In the usual case, a constant reference is passed, a pair of iterators, or a lightweight viewer object into which the container can be cast. Also, you probably need rfind instead of find to search from the end.
It is possible in two ways. Below is an algorithm based on the principle of an automaton. And it would be possible with a nested loop.

#include <iostream>
#include <string>
#include <string_view>
#include <forward_list>
#include <algorithm>

using namespace std;

struct CodeNode
{
    unsigned char beg;
    unsigned char len;
    char ch;
};

bool push_shift (string& s, char c, size_t len)  // return true if first symbol were erased
{
    if (s.size() < len) {s.push_back(c); return false;}
    move (next(s.begin()), s.end(), s.begin());
    s.back() = c; return true;
}

forward_list<CodeNode> LZ77 (string_view s, size_t win_len = 255)
{
    forward_list<CodeNode> res; auto it = res.before_begin();
    string win, buf; win.reserve(win_len); buf.reserve(win_len);
    CodeNode next; size_t saved_win_len = 0;
    for (char c : s) {
        buf.push_back(c);
        size_t pos;
        next.ch = c;
//cout<<win<<' '<<buf<<' '<<saved_win_len<<'\n';
        if ((pos = win.rfind(buf)) != string::npos) {
            next.beg = saved_win_len-pos; next.len = buf.size();
            if (  push_shift (win, c, win_len)  ) saved_win_len--;  //shift
        } else {
            it = res.insert_after(it, next); buf.resize(0);
            next.beg = 0; next.len = 0;
            push_shift (win, c, win_len);
            saved_win_len = win.size();
        }
    }
    if (next.len != 0) {next.len--; res.insert_after(it, next);}
    return res;
}

size_t LZ77length (const forward_list<CodeNode>& code) { // get length of original string
    size_t len = 0;
    for (const CodeNode& cn : code) len += cn.len+1;
    return len;
}

size_t LZ77size (const forward_list<CodeNode>& code) {  // get size of coded data
    return sizeof(CodeNode) * distance(code.begin(), code.end());
}

string LZ77decode (const forward_list<CodeNode>& code)
{
    string res;
    res.reserve(LZ77length(code)); // can not be
    for (CodeNode cn : code) {
        for (size_t i = res.size()-cn.beg, e = i+cn.len; i != e; ++i)
            res += res[i];
        res += cn.ch;
    }
    return res;
}

ostream& operator<< (ostream& os, CodeNode cn) {
    return os << '<' << int(cn.beg) << ',' << int(cn.len) << ',' << cn.ch << '>';
}

int main()
{
    string s;
    getline (cin, s);
    //s = "helolohelololololololololololololo"; // для тестирования
    auto code = LZ77(s,10);
    for (CodeNode cn : code) cout << cn << ' ';
    cout << endl;
    cout << LZ77decode(code) << '\n' << s << endl;
    //cout << s.size() << ' ' << LZ77size(code) << endl;
    return 0;
}