Wersja z 07:56, 1 sie 2006

Laboratorium

Zadanie 1

Treść

Rozważmy trzy warianty kompresji pliku tekstowego, które wykorzystują korelację między sąsiednimi symbolami do osiągnięcia większego stopnia kompresji:

Kodowanie Huffmana zastosowane do bloków 2 symboli.
Kodowanie kolejnego symbolu pliku, $a_{n + 1}$ , za pomocą kodu Huffmana, który zależy od symbolu poprzedniego, $a_{n}$ .
W algorytmie tym, dla każdego symbolu $a$ występującego w pliku, obliczany jest warunkowy rozkład prawdopodobieństwa następnego symbolu, $b$ , pod warunkiem $a$ : $p (b | a)$ . Dla takiego rozkładu symboli $b$ (przy ustalonym $a$ ) obliczany jest kod Huffmana $φ_{a}$ . Kody są generowane dla wszystkich symboli $a$ .
Symbole pliku są kodowane kolejno, od pierwszego do ostatniego, przy czym symbol $a_{n + 1}$ kodowany jest za pomocą kodu $φ_{a_{n}}$ . Tak zakodowana wiadomość jest możliwa do odkodowania, ponieważ w chwili dekodowania $a_{n + 1}$ symbol $a_{n}$ jest już znany.
Kodowanie analogiczne do (2), jednak przebiegające od końca pliku do początku, zatem korzystające z kodu $φ_{a_{n + 1}}$ do zakodowania $a_{n}$ . W tym przypadku $φ_{b}$ jest kodem wygenerowanym dla rozkładu $p (a | b)$ symboli $a$ poprzedzających ustalony symbol $b$ .

Polecenie

Porównaj warianty (1) i (2) oraz (2) i (3) pod względem osiąganego stopnia kompresji:
- Który z wariantów pozwoli uzyskać większy stopień kompresji? Czy zależy to od charakterystyki danych wejściowych? Jeśli to możliwe, podaj ścisły dowód.
- Czy fakt, że znaki w pliku tekstowym są zapisane w "naturalnej" kolejności, czyli w takiej, w jakiej są odczytywane przez człowieka, pozwala na uzyskanie większego stopnia kompresji za pomocą metody (2) niż (3)?
- Oprócz wariantów (1)-(3) rozważ też sytuację, gdy zamiast kodu Huffmana stosowany jest kod, którego średnia długość jest dokładnie równa entropii odpowiedniego rozkładu (dla zainteresowanych: kodowanie arytmetyczne jest metodą, która w pewnym sensie pozwala osiągnąć średnią długość kodu równą entropii; zob. arithmetic coding).
Jaka jest złożoność pamięciowa i czasowa metod (1)-(3)?
Napisz programy kompresuj1, kompresuj2 i kompresuj3, implementujące algorytmy (1)-(3). Wykonaj eksperymenty, które potwierdzą poprawność Twoich odpowiedzi na powyższe pytania.

Wskazówki

Wskazówka I:

Wskazówka II:

Rozwiązanie

Rozwiązanie zadania powinno zawierać:

wykonywalne programy,
kody źródłowe programów,
dane wejściowe wykorzystane do eksperymentów,
raport zawierający:
- odpowiedzi na pytania, być może z dowodami,
- opis wykonanych eksperymentów i wykorzystanych danych wejściowych,
- interpretację wyników eksperymentów.

Pliki źródłowe i raport należy podpisać imieniem i nazwiskiem autora.

Ocenie podlegać będzie: poprawność i ścisłość rozumowania, poprawność implementacji, umiejętność zaplanowania eksperymentów i interpretacji ich wyników. Nie będzie brana pod uwagę efektywność czasowa i pamięciowa programów.

Zadanie 2

Treść

Dane wejściowe mają postać ciągu ${a_{i}}_{1}^{n}$ symboli nad alfabetem $A = A_{0} \cup A_{1} \cup A_{2}$ , gdzie $A_{0} = {s p a c j a}$ , $A_{1} = {^{'} a^{'}, . . .,^{'} z^{'}}$ , $A_{2} = {^{'} 0^{'}, . . .,^{'} 9^{'}}$ . Kolejne znaki tego ciągu są generowane losowo z następującego rozkładu prawdopodobieństwa:

symbol $a_{1}$ jest generowany z rozkładu $(μ_{1} + μ_{2}) / 2$ ,
jeśli $a_{n} \in A_{0}$ , to $a_{n + 1}$ jest generowany z rozkładu $(μ_{1} + μ_{2}) / 2$ ,
jeśli $a_{n} \in A_{1}$ , to $a_{n + 1}$ jest generowany z rozkładu $(μ_{0} + μ_{1}) / 2$ ,
jeśli $a_{n} \in A_{2}$ , to $a_{n + 1}$ jest generowany z rozkładu $(μ_{0} + μ_{2}) / 2$ ,

gdzie $μ_{0}$ , $μ_{1}$ i $μ_{2}$ to rozkłady prawdopodobieństwa na zbiorze $A$ takie, że:

$μ_{0} (A_{0}) = 1$ (czyli rozkład $μ_{0}$ jest skupiony na zbiorze $A_{0}$ ),
$μ_{1} (A_{1}) = 1$ ,
$μ_{2} (A_{2}) = 1$ .

Polecenie

Opracuj możliwie najskuteczniejszą metodę kompresji danych o powyższej charakterystyce, opartą na kodowaniu Huffmana. Zaimplementuj ją.
Oszacuj teoretycznie ile średnio bitów $L$ pliku skompresowanego będzie przypadało na jeden symbol pliku wejściowego. Przyjmij, że znana jest entropia rozkładów $μ_{1}$ i $μ_{2}$ .
Wykonaj eksperymenty, aby sprawdzić swoje przewidywania. Wygeneruj kilka ciągów o podanej wyżej charakterystyce, dla różnych wyborów rozkładów $μ_{1}$ i $μ_{2}$ , skompresuj je Twoją metodą i porównaj rozmiary plików wejściowych i wynikowych.
Oszacuj teoretycznie wartość $L$ dla zwykłej kompresji Huffmana zastosowanej do danych o podanej charakterystyce. Czy Twój algorytm osiąga lepszą kompresję?
Jaka dodatkowa informacja musiałaby być zapisana w skompresowanym pliku, aby umożliwić jego dekompresję? Oszacuj jej rozmiar.

Wskazówka:

@@ Linia 50: / Linia 50: @@
 ==== Treść ====
-Dane wejściowe mają postać ciągu <math>\{a_i\}_1^n</math> symboli nad alfabetem <math>A = A_0 \cup A_1 \cup A_2 = \{spacja\} \cup \{'a',...,'z'\} \cup \{'0',...,'9'\}</math>. Kolejne znaki tego ciągu są generowane losowo z następującego rozkładu prawdopodobieństwa:
+Dane wejściowe mają postać ciągu <math>\{a_i\}_1^n</math> symboli nad alfabetem <math>A = A_0 \cup A_1 \cup A_2</math>, gdzie <math>A_0=\{spacja\}</math>, <math>A_1=\{'a',...,'z'\}</math>, <math>A_2=\{'0',...,'9'\}</math>. Kolejne znaki tego ciągu są generowane losowo z następującego rozkładu prawdopodobieństwa:
 * symbol <math>a_1</math> jest generowany z rozkładu <math>(\mu_1+\mu_2)/2</math>,
 * jeśli <math>a_n \in A_0</math> , to <math>a_{n+1}</math> jest generowany z rozkładu <math>(\mu_1+\mu_2)/2</math>,
 * jeśli <math>a_n \in A_1</math> , to <math>a_{n+1}</math> jest generowany z rozkładu <math>(\mu_0+\mu_1)/2</math>,
 * jeśli <math>a_n \in A_2</math> , to <math>a_{n+1}</math> jest generowany z rozkładu <math>(\mu_0+\mu_2)/2</math>,
-gdzie:
+gdzie <math>\mu_0</math>, <math>\mu_1</math> i <math>\mu_2</math> to rozkłady prawdopodobieństwa na zbiorze <math>A</math> takie, że:
-* <math>\mu_0</math> to rozkład jednopunktowy na zbiorze <math>A_0</math> ,
+* <math>\mu_0(A_0)=1</math> (czyli rozkład <math>\mu_0</math> jest skupiony na zbiorze <math>A_0</math> ),
-* <math>\mu_1</math> to pewien ustalony rozkład prawdopodobieństwa na zbiorze <math>A_1</math> ,
+* <math>\mu_1(A_1)=1</math>,
-* <math>\mu_2</math> to pewien ustalony rozkład prawdopodobieństwa na zbiorze <math>A_2</math> .
+* <math>\mu_2(A_2)=1</math>.
 ==== Polecenie ====

Teoria informacji/TI Ćwiczenia 5: Różnice pomiędzy wersjami

Wersja z 07:56, 1 sie 2006

Spis treści

Laboratorium

Zadanie 1

Treść

Polecenie

Wskazówki

Rozwiązanie

Zadanie 2

Treść

Polecenie

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia