ONA – Zadanie 3

Naszym zadaniem będzie napisanie programu, który będzie wykonywał kompresję i testował jej zachowanie dla różnych dugości pliku i parametrów kompresji. Kolejne elementy podzadania to:

1) Zaimplementuj prosty algorytm kompresji oparty o metodę Lempela i Ziva (LZ77) omawianą na wykładzie. Powinna to być funkcja w pythonie lz77_compress(napis, rozmiar_słownika ), która pobiera napis w argumencie, a następnie zwraca jego wersję skompresowaną w postaci napisu. Zaimplementuj także funkcję odwrotną lz77_decompress(napis)>  (5 punktów)

2) Napisz dwie funkcje generujące napisy o zadanej długości. gen_losowy(dlugosc, zestaw_znakow), ktora generuje losowy ciąg znaków pochodzących z zadanego zestawu znaków. Zarówno zestaw dozwolonych znaków, jak i wynik jest w formie napisu. Drugi z generatorów powinien być mniej losowy. Najlepiej, gdyby losował kolejne znaki, ale za każdym razem wstawiał ciąg po 100 identycznych znaków. (5 punktów)

3) Napisz funkcję testuj(kompresor,generator, lista_długości), która używa podanego generatora do wygenerowania zestawu napisów o długościach zadanych w parametrze lista_dlugosci. Następnie używa podanego w pierwszym argumencie kompresora, aby dokonać kompresji wszystkich tych napisów. Ostatecznie, funkcja zwracałaby listę długości wszystkich skopmpresowanych napisów. (5 punktów)

4) Użyj napisanych funkcji, oraz swojej wiedzy o aproksymacji funkcji do tego aby napisać program pozwalający  znaleźć funkcje opisujące:

  • zależność rozmiaru skompresowanego od wejściowego jako funkcji liniowej lub kwadratowej dla obu generatorów
  • zależność współczynnika kompresji (wyestymowanego w poprzednim punkcie) od rozmiaru słownika

Obraną metodę i wyniki opisz nie tylko w komentarzach w pliku źródłowym, ale także w postaci krótkiego raportu (maksymalnie 2 strony), ilustrowanego sensowymi wykresami (10 pktów)

Rozwiązania ( w postaci 1 pliku .py i 1 pliku .pdf) przesyłamy do 3. czerwca, e-mailem do wykładowcy, proszę pamiętać o dopisku [ONA-2018-3] i o umieszczeniu plików jako standardowych załączników.

One thought on “ONA – Zadanie 3

  1. Bartek

    Po rozmowie dziś na zajęciach zdecydowałem się przedłużyć termin oddania zadań o tydzień, do niedzieli 10. VI

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>