Kodowanie słownikowe LZ77 metoda przesuwającego okna

Question

Cześć mam na zadanie na studia napisać program kodowania słownikowego LZ77, podszedłem do tematu prostszym (w teorii) algorytmem przesuwającego się okna, ale program zwraca mi jedynie wynik Pozycja: 0 Dlugosc: 0 Znak: ¨, nie mam pojęcie z czego wynika błąd
 

#include <stdio.h>
#include <string.h>
#define MaxBuforSize 4
#define MaxDictionarySize 8

struct trojkaLZ77
{
int pozycja;
int dlugosc;
char znak;
};

struct okno
{
char slownik[MaxBuforSize];
char bufor[MaxDictionarySize];
char niewykorzystane [60];
struct trojkaLZ77 *wskaznikNaTrojke;
};

char przesunNiewykorzystane(struct okno *okno);

void wczytajDane(struct okno *okno, const char *nazwaPliku)
{
FILE *plik = fopen(nazwaPliku, "r");
if (!plik)
{
perror("Błąd wczytania pliku");

    return;
}
int index = 0;
char znak;
while ((znak = fgetc(plik)) != EOF && index < sizeof(okno->niewykorzystane)-1)
{
    okno->niewykorzystane[index++] = znak;
}
okno->niewykorzystane[index] = '\0';

fclose(plik);
}

void przesuniecieOkna(struct okno *okno)
{
int przesuniecie = okno->wskaznikNaTrojke->dlugosc + 1;

for (int i = 0; i < MaxBuforSize - przesuniecie; i++)
{
    okno->slownik[i] = okno->slownik[i + przesuniecie];
}
for (int i = MaxBuforSize - przesuniecie; i < MaxBuforSize; i++)
{
    // okno->slownik[i] = okno->bufor[0];
    // for (int j = 0; j < MaxDictionarySize; j++)
    // {
    //     okno->bufor[j] = okno->bufor[j + 1];
    // }
    // okno->bufor[MaxDictionarySize - 1] = przesunNiewykorzystane(okno);
    if (i < 0) continue;
    okno->slownik[i] = okno->bufor[0];

    //Przesuniecie calego bufora
    memmove(okno->bufor, okno->bufor + 1, MaxDictionarySize - 1);
    okno->bufor[MaxDictionarySize - 1] = przesunNiewykorzystane(okno);
}
}

char przesunNiewykorzystane(struct okno *okno)
{
int niewykorzystaneDL = strlen(okno->niewykorzystane);
int buforDL = strlen(okno->bufor);
int i;

for ( i = 0; i < MaxDictionarySize - buforDL && i < niewykorzystaneDL; i++)
{
    okno->bufor[buforDL + i] = okno->niewykorzystane[i];
}

// memmove(okno->niewykorzystane, okno->niewykorzystane + i, niewykorzystaneDL - i + 1);

if (niewykorzystaneDL > 0)
{
    char znakDoBufora = okno->niewykorzystane[0];
    memmove(okno->niewykorzystane, okno->niewykorzystane + i, niewykorzystaneDL - i + 1);
    return znakDoBufora;
}
else
{
    return '\0';
}  
}

struct okno kodujLZ77()
{
struct okno noweOkno;
struct trojkaLZ77 trojka = {0,0,noweOkno.bufor[1]};

noweOkno.wskaznikNaTrojke = &trojka;
int MaxDl = 0;
int Poz = 0;

for (int i = 0; i < strlen(noweOkno.slownik); i++)
{
    for (int j = 0; j < strlen(noweOkno.bufor); j++)
    {
        int k = 0;
        while (i + k < MaxBuforSize && j + k < MaxDictionarySize && noweOkno.slownik[i + k] == noweOkno.bufor[j + k]) {
            k++;
        }   
        if (k > MaxDl)
        {
            MaxDl = k;
            Poz = i;
        } 
    }
}
trojka.pozycja = Poz;
trojka.dlugosc = MaxDl;

if (MaxDl < MaxDictionarySize)
{
    trojka.znak = noweOkno.bufor[MaxDl];
}
else
{
    trojka.znak = '\0';
}
//Przesunięcie okna w lewo o długość + 1
przesuniecieOkna(&noweOkno);

return noweOkno;
}

int main()
{
struct okno oknoKompresji;
memset(&oknoKompresji, 0, sizeof(oknoKompresji));

const char *nazwaPliku = "plik.txt";
wczytajDane(&oknoKompresji, nazwaPliku);

//Sprawdzenie czy niewykorzystane dane zostały wczytane
if (strlen(oknoKompresji.niewykorzystane) == 0)
{
    printf("Brak danych do kompresji");
    return 1;
}

//Przetwarzanie danych
struct okno skompresowaneOkno = kodujLZ77(&oknoKompresji);

printf("Pozycja: %d Dlugosc: %d Znak: %c", skompresowaneOkno.wskaznikNaTrojke->pozycja, skompresowaneOkno.wskaznikNaTrojke->dlugosc, skompresowaneOkno.wskaznikNaTrojke->znak);

return 0;
}

 

Answer 1

Zacznijmy od tego, że w ogóle nie bierzesz argumentu wejściowego.

struct okno kodujLZ77() // <--
...
kodujLZ77(&oknoKompresji);

Kompilator w trybie C na to nie krzyczy, ale w trybie C++owym już tak.

Poza tym, nawet w trybie C, krzyczy na to że w kilku miejscach używasz niezainicjalizowane dane. Zakładając GCC/Clanga, nie zapominaj o flagach -Wall -Wextra.

Answer 2

Zmieniłem kod i dodatkowo zainicjalizowałem do funkcji kodujLZ77 strukturę okna, program wykonuje się. Jednak w wyniku dalej jest Pozycja: 0 Długość: 0 Znak:. Debuger znajduje breakpoint w inicjalizacji struktury w linii 102 "memset(&oknoKompresji, 0, sizeof(oknoKompresji)); // Inicjalizacja struktury "

#include <stdio.h>
#include <string.h>
#define MaxBuforSize 4
#define MaxDictionarySize 8
#define Min(x, y) ((x) < (y) ? (x) : (y))

struct trojkaLZ77 
{
    int pozycja;
    int dlugosc;
    char znak;
};

struct okno 
{
    char slownik[MaxBuforSize];
    char bufor[MaxDictionarySize];
    char niewykorzystane[60];
    struct trojkaLZ77 trojka; // Teraz trojka jest częścią struktury okno
};

void wczytajDane(struct okno *okno, const char *nazwaPliku) 
{
    FILE *plik = fopen(nazwaPliku, "r");
    if (!plik) 
    {
        perror("Błąd wczytania pliku");
        return;
    }
    int index = 0;
    char znak;
    while ((znak = fgetc(plik)) != EOF && index < sizeof(okno->niewykorzystane) - 1) 
    {
        okno->niewykorzystane[index++] = znak;
    }
    okno->niewykorzystane[index] = '\0';
    fclose(plik);
}

void przesuniecieOkna(struct okno *okno) {
    int przesuniecie = okno->trojka.dlugosc + 1;

    // Przesunięcie słownika
    for (int i = 0; i < MaxBuforSize - przesuniecie; i++) 
    {
        okno->slownik[i] = okno->slownik[i + przesuniecie];
    }

    // Przesunięcie bufora
    memmove(okno->bufor, okno->bufor + przesuniecie, MaxDictionarySize - przesuniecie);

    // Wczytanie nowych danych do bufora z niewykorzystanych
    int iloscDoWczytania = Min(przesuniecie, strlen(okno->niewykorzystane));
    memcpy(okno->bufor + MaxDictionarySize - przesuniecie, okno->niewykorzystane, iloscDoWczytania);

    // Aktualizacja niewykorzystanych
    memmove(okno->niewykorzystane, okno->niewykorzystane + iloscDoWczytania, strlen(okno->niewykorzystane) - iloscDoWczytania + 1);
}

struct okno kodujLZ77(struct okno *wejscioweOkno) 
{
    wejscioweOkno->trojka.pozycja = 0;
    wejscioweOkno->trojka.dlugosc = 0;
    wejscioweOkno->trojka.znak = wejscioweOkno->bufor[0]; 

    int MaxDl = 0, Poz = 0;

    for (int i = 0; i < strlen(wejscioweOkno->slownik); i++) 
    {
        for (int j = 0; j < strlen(wejscioweOkno->bufor); j++) 
        {
            int k = 0;
            while (i + k < MaxBuforSize && j + k < MaxDictionarySize && wejscioweOkno->slownik[i + k] == wejscioweOkno->bufor[j + k]) 
            {
                k++;
            }   
            if (k > MaxDl) 
            {
                MaxDl = k;
                Poz = i;
            } 
        }
    }
    wejscioweOkno->trojka.pozycja = Poz;
    wejscioweOkno->trojka.dlugosc = MaxDl;

    if (MaxDl < MaxDictionarySize) 
    {
        wejscioweOkno->trojka.znak = wejscioweOkno->bufor[MaxDl];
    } else 
    {
        wejscioweOkno->trojka.znak = '\0';
    }
    przesuniecieOkna(wejscioweOkno);

    return *wejscioweOkno;
}

int main() 
{
    struct okno oknoKompresji;
    memset(&oknoKompresji, 0, sizeof(oknoKompresji)); // Inicjalizacja struktury

    const char *nazwaPliku = "plik.txt";
    wczytajDane(&oknoKompresji, nazwaPliku);

    if (strlen(oknoKompresji.niewykorzystane) == 0) 
    {
        printf("Brak danych do kompresji.\n");
        return 1;
    }

    // Przetwarzanie danych
    struct okno skompresowaneOkno = kodujLZ77(&oknoKompresji);

    printf("Pozycja: %d, Długość: %d, Znak: %c\n", skompresowaneOkno.trojka.pozycja, skompresowaneOkno.trojka.dlugosc, skompresowaneOkno.trojka.znak);

    return 0;
}

 

Comments

To wciąż wygląda mega dziwnie... robisz pętlę po strlen na wejscioweOkno->slownik, ale ten słownik jest zawsze pusty (same zera)?

---

Faktycznie, zapełniłem słownik znakiem x, niby poprawnie porównuje, ale program rozszerza wszystkie tablice i nie znajduje podobiństw