Есть задание, закодировать строку по методу 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 - глобальная переменная, которая должна в себе хранить количество символов, которые совпадают в ссылке. Сама структура сделана в виде однонаправленного списка, пал выбор в пользу неё из-за того, что не нужно хранить как в строке бесполезные символы ("." - для отделения сдвига, количества и символа).