Wersja z 15:57, 30 lip 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}$ znaków nad alfabetem $A = A_{0} \cup A_{1} \cup A_{2} = {s p a c j a} \cup {^{'} a^{'}, . . .,^{'} z^{'}} \cup {^{'} 0^{'}, . . .,^{'} 9^{'}}$ . Kolejne znaki tego ciągu są generowane losowo z następującego rozkładu:

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:

$μ_{1}$ to rozkład jednopunktowy na zbiorze $A_{0}$ ,
$μ_{1}$ to pewien ustalony rozkład prawdopodobieństwa na zbiorze $A_{1}$ ,
$μ_{2}$ to pewien ustalony rozkład prawdopodobieństwa na zbiorze $A_{2}$ .

Polecenie

Opracuj możliwie najskuteczniejszą metodę kompresji danych o powyższej charakterystyce, opartą na kodowaniu Huffmana.

@@ Linia 51: / Linia 51: @@
 Dane wejściowe mają postać ciągu <math>\{a_i\}_1^n</math> znaków 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:
-* symbol <math>a_1</math> jest generowany z rozkładu <math>\mu_0</math>,
+* 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_0</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_1</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_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:
-* <math>\mu_1</math> to pewien ustalony rozkład prawdopodobieństwa na zbiorze <math>A_1\cup A_0</math> ,
+* <math>\mu_1</math> to rozkład jednopunktowy na zbiorze <math>A_0</math> ,
-* <math>\mu_2</math> to pewien ustalony rozkład prawdopodobieństwa na zbiorze <math>A_2\cup A_0</math> ,
+* <math>\mu_1</math> to pewien ustalony rozkład prawdopodobieństwa na zbiorze <math>A_1</math> ,
-*
+* <math>\mu_2</math> to pewien ustalony rozkład prawdopodobieństwa na zbiorze <math>A_2</math> .
+==== Polecenie ====
+# Opracuj możliwie najskuteczniejszą metodę kompresji danych o powyższej charakterystyce, opartą na kodowaniu Huffmana.

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

Wersja z 15:57, 30 lip 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