4261638921

Zadania przykładowe do kolokwium z AA2

Zadanie 1

Dla tekstu ALA_MA_KOTA_ALE_ON_MA_ALERGIĘ zilustruj działanie algorytmów:

a)    LZ77,

b)    LZ78,

c)    LZSS.

Załóż, że maksymalna długość dopasowania to 4, rozmiar okna to 8.

Zadanie 2

Odczytaj tekst 010100111100011010000 zakodowany kodem Huffmana wiedząc, że częstość występowania symboli w tekście jest następująca: A (3), B (1), K (1), R (4), M (1). Gdyby w trakcie budowy drzewa Huffmana miała miejsce sytuacja, że do wyboru są więcej niż dwa węzły, wybierz węzły opisane literami najwcześniejszymi w porządku alfabetycznym.

Zadanie 3

Wygeneruj wszystkie możliwe kody Huffmana dla tekstu ABRACADABRA.

Zadanie 4

Poznany kod Huffmana jest kodem binarnym. Możliwe, i czasami stosowane w praktyce, są jednak także niebinarne kody Huffmana. Kod taki tworzy się w analogiczny sposób jak binarny kod Huffmana. Zamiast łączenia węzłów w pary łączy się je w grupy po k węzłów oraz opisuje krawędzie symbolami od 0 do k — 1 otrzymując drzewa fc-arne. Utwórz w ten sposób:

•    trójkowy kod Huffmana dla tekstu ABRACADABRA,

•    czwórkowy kod Huffmana dla tekstu KALORYFEROWNIA.

Zadanie 5

Przy założeniu, że maksymalna długość dopasowania wynosi 256, rozmiar okna to 65536, a rozmiar alfabetu to 4 oszacuj dla algorytmu LZSS minimalny współczynnik kompresji (wyrażony w bps). Dla uproszczenia załóż, że kodowany tekst jest bardzo długi i nie bierz jego rozmiaru pod uwagę. Przez minimalny rozumiemy taki współczynnik kompresji, który ma miejsce w sytuacji, kiedy tekst kompresuje się najgorzej jak to jest możliwe.

Zadanie 6

Podaj przykład tekstu długości 6 (wliczając wartownika), dla którego łączna liczba symboli opisujących krawędzie w drzewie sufiksów jest maksymalna. Podaj regułę tworzenia takich „najgorszych” tekstów.