|
|
| Linia 1: |
Linia 1: |
| == Zadanie 1 ==
| |
|
| |
|
| ==== Polecenie ====
| |
|
| |
| # Przygotuj trzy pliki, zawierające tekst w trzech różnych językach: polskim, angielskim i trzecim dowolnie wybranym. Każdy plik powinien zawierać przynajmniej 50000 znaków. Duży wybór tekstów w różnych językach można znaleźć na przykład na stronie [http://gutenberg.org Projektu Gutenberg].
| |
| # Napisz program <tt>litery</tt>, który czyta plik tekstowy o podanej nazwie (przekazanej jako parametr wywołania programu) i wypisuje wszystkie symbole występujące w pliku wraz z ich częstością, w formie: '''A 0.134 <nowa_linia> b 0.126 ...''' Nie musi poprawnie wypisywać znaków narodowych. Program powinien wypisać też entropię binarną <!--link--> obliczonego rozkładu prawdopodobieństwa. Uruchom program dla trzech przygotowanych wcześniej plików, porównaj otrzymane wyniki.
| |
| # Napisz program <tt>huffman</tt>, który czyta plik tekstowy o podanej nazwie i oblicza kod Huffmana <!--link--> dla rozkładu symboli występujących w tym pliku. Program powinien wypisać otrzymany kod w formie: '''A 001 <nowa_linia> b 0001010 ...''' <br/> Napisz program <tt>shannon</tt>, który oblicza kod Shannona-Fano. <!--link--> Uwaga: aby otrzymać poprawny kod Shannona-Fano, nie można korzystać w obliczeniach z liczb zmiennoprzecinkowych (dlaczego?), jedynie z liczb całkowitych. Prawdopodobieństwo danego symbolu można pomnożyć przez ustaloną liczbę całkowitą (najlepiej potęgę 2, np. 65536) i zaokrąglić, otrzymując w ten sposób reprezentację całkowitoliczbową.
| |
| <!-- Uwaga: czy na wykladzie jest konstruktywna metoda obliczania kodu S-F? -->
| |
| # Napisz program <tt>kompresuj</tt>, który koduje podany plik tekstowy '''plik.txt''' za pomocą kodu Huffmana i Shannona-Fano. Wynik kodowania powinien zostać zapisany do plików '''plik.huf''' i '''plik.sf'''. Dla ułatwienia można każdy bit wynikowego kodu zapisywać na oddzielnym bajcie, jako znak "0" lub "1".
| |
| # Uruchom program <tt>kompresuj</tt> dla trzech przygotowanych plików tekstowych. Dla każdego z nich porównaj następujące wielkości:
| |
| #* liczbę bitów oryginalnego pliku,
| |
| #* liczbę znaków "0" i "1" w plikach '''.huf''' i '''.sf''',
| |
| #* entropię rozkładu prawdopodobieństwa symboli w oryginalnym pliku. <br/> Czy te wielkości zależą od języka kompresowanego tekstu?
| |
| # Napisz program <tt>kompresujbloki</tt>, który kompresuje podany plik metodą Huffmana i Shannona-Fano, zastosowanymi do bloków długości 2, 3, 4 lub więcej (tzn. kod jest generowany nie dla pojedynczych symboli, lecz dla par, trójek, czwórek ... sąsiednich symboli). Porównaj efektywność kompresji pojedynczych symboli i bloków, pod względem:
| |
| #* rozmiaru zakodowanego pliku,
| |
| #* rozmiaru kodu (aby móc wykonać dekompresję, kod musi być zapisany razem z zakodowaną informacją),
| |
| #* złożoności czasowej i pamięciowej algorytmu.
| |
|
| |
| Prowadzący laboratorium może zrezygnować z części zadania, np. z implementacji kodowania Shannona-Fano.
| |
|
| |
| ==== Rozwiązanie ====
| |
|
| |
| Rozwiązanie zadania powinno zawierać:
| |
| * wykonywalne programy,
| |
| * kody źródłowe programów,
| |
| * pliki tekstowe wykorzystane do eksperymentów,
| |
| * raport z analizą otrzymanych wyników i odpowiedziami na postawione wyżej pytania.
| |
| Pliki źródłowe i raport należy ''podpisać'' imieniem i nazwiskiem autora.
| |
|
| |
| Ocenie podlegać będzie poprawność implementacji oraz umiejętność analizy i interpretacji wyników eksperymentalnych. Dodatkowe programy, eksperymenty, komentarze będą mile widziane. Nie będzie natomiast brana pod uwagę efektywność czasowa i pamięciowa programów.
| |
|
| |
| [Uwagi: jest to przetłumaczone zadanie Hugo, trochę skrócone i z niewielkimi modyfikacjami. Zadanie jest elementarne - implementacja podstawowego algorytmu kompresji - bez niego nie da się robić kolejnych zadań (ew. można pominąć kodowanie bloków albo wydzielić jako osobne zadanie).]
| |
|
| |
| == Zadanie 2 ==
| |
|
| |
| ==== 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, <math>a_{n+1}</math>, za pomocą kodu Huffmana, który zależy od symbolu poprzedniego, <math>a_n</math>. <br/> W algorytmie tym, dla każdego symbolu <math>a</math> występującego w pliku, obliczany jest warunkowy rozkład prawdopodobieństwa następnego symbolu, <math>b</math>, pod warunkiem <math>a</math>: <math>p(b|a)</math>. Dla takiego rozkładu symboli <math>b</math> (przy ustalonym <math>a</math>) obliczany jest kod Huffmana <math>\varphi_a</math>. Kody są generowane dla wszystkich symboli <math>a</math>. <br/> Symbole pliku są kodowane kolejno, od pierwszego do ostatniego, przy czym symbol <math>a_{n+1}</math> kodowany jest za pomocą kodu <math>\varphi_{a_n}</math>. Tak zakodowana wiadomość jest możliwa do odkodowania, ponieważ w chwili dekodowania <math>a_{n+1}</math> symbol <math>a_n</math> jest już znany.
| |
| # Kodowanie analogiczne do (2), jednak przebiegające od końca pliku do początku, zatem korzystające z kodu <math>\varphi_{a_{n+1}}</math> do zakodowania <math>a_n</math>. W tym przypadku <math>\varphi_b</math> jest kodem wygenerowanym dla rozkładu <math>p(a|b)</math> symboli <math>a</math> poprzedzających ustalony symbol <math>b</math>.
| |
|
| |
| ==== 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. [http://en.wikipedia.org/wiki/Arithmetic_coding arithmetic coding]).
| |
| # Jaka jest złożoność pamięciowa i czasowa metod (1)-(3)?
| |
| # Napisz programy <tt>kompresuj1</tt>, <tt>kompresuj2</tt> i <tt>kompresuj3</tt>, implementujące algorytmy (1)-(3). Wykonaj eksperymenty, które potwierdzą poprawność Twoich odpowiedzi na powyższe pytania.
| |
|
| |
| ==== Wskazówki ====
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed">Wskazówka I:
| |
| <div class="mw-collapsible-content" style="display:none">Aby odpowiedzieć na pytania z pkt. 1 skorzystaj z własności entropii łącznej i warunkowej.
| |
| </div></div>
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed">Wskazówka II:
| |
| <div class="mw-collapsible-content" style="display:none">W eksperymentach możesz wykorzystać dwa pliki tekstowe:
| |
| * <tt>naturalny.txt</tt> - zawierający fragment tekstu w języku polskim lub angielskim,
| |
| * <tt>cyfry.txt</tt> - zawierający ciąg cyfr z przedziału '1' - '3', generowanych niezależnie z rozkładu jednostajnego.
| |
| Pamiętaj, aby pliki były dostatecznie długie - tylko wtedy uzyskane wyniki będą wiarygodne.
| |
| </div></div>
| |
|
| |
| ==== 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.
| |
|
| |
| [Uwagi: zadanie wymaga znajomości pojęcia entropii łącznej i warunkowej.]
| |
