Как реализовать сжатие LZ77 на примере одной строки?

Question

[David Gegiya]

Есть задание, закодировать строку по методу LZ77. Нигде в интернете не нашёл как нормального объяснения алгоритма "по полочкам", так и адекватного кода на c++. То, как я понимаю текущий алгоритм громоздко и неправильно. Долго создавал код, который не работает, и который трудно дебажить опять же потому, что сам не до конца понимаю тот самый алгоритм...

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

Во первых понятия не имею, как сделать адекватную проверку на содержание какой-либо части буфера в "окне". Поэтому буфер всего на 3 символа и даже там пришлось простите, говнокодить (функция contains). Эта самая contains должна возвращать найденный индекс какой-либо части строки в окне, а затем отнимая от длинны окна индекс по идее должны получать число сдвигов для ссылки. Число numGL - глобальная переменная, которая должна в себе хранить количество символов, которые совпадают в ссылке. Сама структура сделана в виде однонаправленного списка, пал выбор в пользу неё из-за того, что не нужно хранить как в строке бесполезные символы ("." - для отделения сдвига, количества и символа).

Comments

[Александр Ананьев]

Тут смотрели? https://neerc.ifmo.ru/wiki/index.php?title=Алгорит...

Answer 1

[User700]

Что-то страное конечно. Какая-то глобальная переменная, потоки от строк... есть new, но нет delete ("утечка" памяти). Почему не ипользовать библиотечный лист? Также, c++ отличается от Java/Python -- при передаче по значению контейнера (в частности строки) он копируется (или перемещается, но при использовании доп. функций); так стоит делать если функции нужно собственное владение объектом, а не только считывание его данных. В обычном случае передают константную ссылку, пару итераторов, или легковесный объект-просмотрщик, в который может привестись контейнер. Кроме того, наверно нужно rfind вместо find чтобы искать с конца.
Можно двумя способами. Ниже алгоритм по принципу автомата. А можно было бы с вложенным циклом.

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

Comments

[David Gegiya]

такое условие задания - нельзя использовать усложнённые структуры, всё нужно делать только ручками.
Удаление прописать не проблема, забываю иногда про него. Интересно Вы код пишите, так, что непонятно ничего :)

[User700]

Davidaa_WoW, эм... там конечно не только с удалением, выше только часть описана.
Усложнённые структуры -- это что, forward_list что-ли усложнённая??? :) это однонаправленный список (в каждом элементе указатель на следующий), одна из простейших структур данных. При этом добавление у меня происходит в конец без посмотра всего списка от начала, а одним действием в конец.
А почему тогда используете структуру данных, контейнер, std::string? (Это такой же библиотечный класс, как и list).
Конечно, forward_list самим реализовать никто не запрещает. Или найти. Только нужно чтобы там были итераторы, begin(), end(), и было insert_after(...).
Интересно Вы код пишите, так, что непонятно ничего -- тут претензии могут быть только к себе :) Пробовал запустить?