|
|
| (Nie pokazano 10 wersji utworzonych przez 3 użytkowników) |
| Linia 1: |
Linia 1: |
| == Zadanie 1: kompresja danych == | | == Ćwiczenia == |
|
| |
|
| ==== Polecenie ====
| | {{cwiczenie|1 [Sfałszowana moneta]|mdt| |
| | Monetę nazywamy ''sfałszowaną'', jeśli prawdopodobieństwo wypadnięcia orła jest inne niż reszki. |
| | Jak przy pomocy sfałszowanej monety dokonać sprawiedliwego losowania między dwiema osobami?}} |
|
| |
|
| # 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.
| | {{cwiczenie|2 [Moneta dla trzech]|mdt| |
| | W jaki sposób można przy pomocy monety przeprowadzić losowanie wśród trzech osób?}} |
|
| |
|
| ==== Rozwiązanie ====
| |
|
| |
|
| Rozwiązanie zadania powinno zawierać:
| | {{cwiczenie|3 [Magiczna sztuczka]|ms| |
| * wykonywalne programy,
| | W pewnej magicznej sztuczce bierze udział magik, jego asystent i ochotnik z widowni. Asystent, którego nadnaturalne zdolności mają być pokazane, jest zamykany w dźwiękoszczelnym pomieszczeniu. Magik daje ochotnikowi 6 pustych kart: 5 białych i jedną zieloną. Ochotnik ma na każdej z kart napisać inną liczbę naturalną pomiędzy 1 a 100. Ochotnik zatrzymuje zieloną kartę, i oddaje pozostałe karty magikowi. Magik, który widział wszystkie pisane liczby, ustawia białe karty w jakiejś kolejności i przekazuje je asystentowi. Asystent po obejrzeniu kart ogłasza jaki numer został napisany na zielonej karcie. |
| * 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.
| | Wyjaśnij jak ta sztuczka działa.}} |
|
| |
|
| [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 == | | {{cwiczenie|4 [Entropia jako metryka]|ejm| |
| | Dla rozkładów X i Y definiujemy funkcję <math>d(X,Y)=H(X|Y)+H(Y|X)</math>. Pokaż, że funkcja ta spełnia warunki metryki: |
| | :a) <math>d(X,Y)\ge 0</math> |
| | :b) <math>d(X,Y)=d(Y,X)</math> |
| | :c) <math>d(X,Y)=0 \Leftrightarrow</math> istnieje bijekcja między X a Y |
| | :d) <math>d(X,Y)+d(Y,Z) \ge d(X,Z)</math>}} |
|
| |
|
| Rozważmy trzy warianty kompresji pliku tekstowego, które wykorzystują korelację między sąsiednimi symbolami do osiągnięcia większego stopnia kompresji:
| | == Zadania domowe == |
| # 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 ==== | | === Zadanie 1 - Efektywne testy przesiewowe === |
|
| |
|
| # Porównaj warianty (1) i (2) oraz (2) i (3) pod względem osiąganego stopnia kompresji:
| | Załóżmy, że mamy do przebadania pod kątem obecności jakiegoś wirusa <math>N</math> próbek krwi. Prawdopodobieństwo pozytywnego wyniku <math>p</math> dla każdej próbki jest niewielkie (np. <math>p=0,01</math>), a każdy test jest kosztowny. |
| #* 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. <div class="mw-collapsible mw-made=collapsible mw-collapsed"> Wskazówka: <div class="mw-collapsible-content" style="display:none">skorzystaj z własności entropii łącznej i warunkowej. </div></div>
| | Zamiast badać każdą próbkę osobno, możemy badać zmieszane fragmenty próbek. Zakładamy wtedy, że wynik jest pozytywny jeśli choć jedna z wymieszanych próbek zawierała wirusa. Zakładamy też, że każdą próbkę możemy podzielić na wystarczająco wiele fragmentów. Ostatecznie musimy jednak dla każdej próbki wiedzieć bez wątpliwości czy zawiera wirusa, czy nie. |
| #* 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).
| | O ile możemy zmniejszyć oczekiwaną liczbę testów do wykonania? |
| #* 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 przez metodę (2) niż (3)?
| | Zaprojektuj efektywne badanie dla <math>p=0,01</math> i <math>N=300</math> i policz oczekiwaną liczbę testów. |
| # Jaka jest złożoność pamięciowa i czasowa metod (1)-(3)?
| |
| # Zaimplementuj każdy z wariantów (1)-(3). Wykonaj eksperymenty, które potwierdzą poprawność Twoich odpowiedzi na powyższe pytania. W eksperymentach wykorzystaj przynajmniej dwa pliki tekstowe, każdy o długości co najmniej 50000 znaków:
| |
| #* <tt>naturalny.txt</tt> - tekst w języku polskim lub angielskim,
| |
| #* <tt>cyfry.txt</tt> - ciąg cyfr '0'-'9' wygenerowanych niezależnie z rozkładu jednostajnego.
| |
|
| |
|
| [Uwagi: zadanie wymaga znajomości entropii produktowej i zależnej.]
| |
|
| |
|
| <!--
| | === Zadanie 2 - Optymalność kodu Huffmana === |
| Różne warianty kompresji:
| | |
| * blokami o długości 2
| | Udowodnij, że kod Huffmana dla źródeł binarnych ma optymalną długość. Zacznij od udowodnienia, że każde źródło ma kod optymalny, w którym dwa najdłuższe słowa kodowe są rodzeństwem (różnią się tylko ostatnim bitem). |
| * przewidywanie kolejnego symbolu na podstawie poprzedniego
| | Uogólnij to rozumowanie na źródła o dowolnej ilości symboli i udowodnij optymalność kodu Huffmana w ogólnym przypadku. |
| * od końca: przewidywanie poprzedniego na podstawie następnego
| | |
| Który wariant powinien być najlepszy? Porównaj (stopień kompresji, złożoność pamięciowa), udowodnij, skomentuj, zaimplementuj.
| | Jeśli kod Huffmana jest optymalny, dlaczego używa się wielu różnych metod kompresji? |
| Przeprowadź rozumowanie dla dwóch sytuacji: słowa kodowe muszą mieć długość całkowitą lub nie muszą. (dla zainteresowanych: zob. kodowanie arytmetyczne)
| |
| -->
| |
Ćwiczenia
Ćwiczenie 1 [Sfałszowana moneta]
Monetę nazywamy sfałszowaną, jeśli prawdopodobieństwo wypadnięcia orła jest inne niż reszki.
Jak przy pomocy sfałszowanej monety dokonać sprawiedliwego losowania między dwiema osobami?
Ćwiczenie 2 [Moneta dla trzech]
W jaki sposób można przy pomocy monety przeprowadzić losowanie wśród trzech osób?
Ćwiczenie 3 [Magiczna sztuczka]
W pewnej magicznej sztuczce bierze udział magik, jego asystent i ochotnik z widowni. Asystent, którego nadnaturalne zdolności mają być pokazane, jest zamykany w dźwiękoszczelnym pomieszczeniu. Magik daje ochotnikowi 6 pustych kart: 5 białych i jedną zieloną. Ochotnik ma na każdej z kart napisać inną liczbę naturalną pomiędzy 1 a 100. Ochotnik zatrzymuje zieloną kartę, i oddaje pozostałe karty magikowi. Magik, który widział wszystkie pisane liczby, ustawia białe karty w jakiejś kolejności i przekazuje je asystentowi. Asystent po obejrzeniu kart ogłasza jaki numer został napisany na zielonej karcie.
Wyjaśnij jak ta sztuczka działa.
Ćwiczenie 4 [Entropia jako metryka]
Dla rozkładów X i Y definiujemy funkcję . Pokaż, że funkcja ta spełnia warunki metryki:
- a)
- b)
- c) istnieje bijekcja między X a Y
- d)
Zadania domowe
Zadanie 1 - Efektywne testy przesiewowe
Załóżmy, że mamy do przebadania pod kątem obecności jakiegoś wirusa próbek krwi. Prawdopodobieństwo pozytywnego wyniku dla każdej próbki jest niewielkie (np. ), a każdy test jest kosztowny.
Zamiast badać każdą próbkę osobno, możemy badać zmieszane fragmenty próbek. Zakładamy wtedy, że wynik jest pozytywny jeśli choć jedna z wymieszanych próbek zawierała wirusa. Zakładamy też, że każdą próbkę możemy podzielić na wystarczająco wiele fragmentów. Ostatecznie musimy jednak dla każdej próbki wiedzieć bez wątpliwości czy zawiera wirusa, czy nie.
O ile możemy zmniejszyć oczekiwaną liczbę testów do wykonania?
Zaprojektuj efektywne badanie dla i i policz oczekiwaną liczbę testów.
Zadanie 2 - Optymalność kodu Huffmana
Udowodnij, że kod Huffmana dla źródeł binarnych ma optymalną długość. Zacznij od udowodnienia, że każde źródło ma kod optymalny, w którym dwa najdłuższe słowa kodowe są rodzeństwem (różnią się tylko ostatnim bitem).
Uogólnij to rozumowanie na źródła o dowolnej ilości symboli i udowodnij optymalność kodu Huffmana w ogólnym przypadku.
Jeśli kod Huffmana jest optymalny, dlaczego używa się wielu różnych metod kompresji?
