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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Nie podano opisu zmian
Nie podano opisu zmian
Linia 35: Linia 35:
== Zadanie 2 ==
== Zadanie 2 ==


Wykonaj następujący eksperyment:
Wykonaj następujący eksperyment aby sprawdzić, czy ponowna kompresja pliku już skompresowanego może pozwolić na dalsze zmniejszenie rozmiaru pliku:
# Przygotuj plik <tt>dane.txt</tt> zawierający tekst w języku naturalnym (polskim lub angielskim) o długości przynajmniej 50000 znaków.
# Przygotuj plik <tt>dane.txt</tt> zawierający tekst w języku naturalnym (polskim lub angielskim) o długości przynajmniej 50000 znaków.
# Skompresuj <tt>dane.txt</tt> [[Teoria informacji/TI Wykład 3#huffman|algorytmem Huffmana]], zapisując zakodowaną informację do pliku <tt>wynik.huf</tt> (możesz wykorzystać program <tt>kompresuj</tt> z zadania 1). Dla ułatwienia możesz każdy wynikowy bit zapisywać na oddzielnym bajcie, jako znak "0" lub "1".
# Skompresuj <tt>dane.txt</tt> [[Teoria informacji/TI Wykład 3#huffman|algorytmem Huffmana]], zapisując zakodowaną informację do pliku <tt>wynik.huf</tt> (możesz wykorzystać program <tt>kompresuj</tt> z zadania 1). Dla ułatwienia możesz każdy wynikowy bit zapisywać na oddzielnym bajcie, jako znak "0" lub "1".
# Wynikowy ciąg bitów skompresuj [[Teoria informacji/TI Wykład 3#huffman|algorytmem Huffmana]], zastosowanym [[Teoria informacji/TI Wykład 3#kodowanie par|do grup]] 1, 2, 4, 8 i 16 bitów, otrzymując pięć kolejnych plików: <tt>wynik01.huf</tt>, <tt>wynik02.huf</tt>, <tt>wynik04.huf</tt>, <tt>wynik08.huf</tt>, <tt>wynik16.huf</tt> (możesz wykorzystać program <tt>kompresujbloki</tt> z zadania 1).
# Wynikowy ciąg bitów skompresuj [[Teoria informacji/TI Wykład 3#huffman|algorytmem Huffmana]], zastosowanym [[Teoria informacji/TI Wykład 3#kodowanie par|do bloków]] 1, 2, 4, 8 i 16 bitów, otrzymując pięć kolejnych plików: <tt>wynik01.huf</tt>, <tt>wynik02.huf</tt>, <tt>wynik04.huf</tt>, <tt>wynik08.huf</tt>, <tt>wynik16.huf</tt> (możesz wykorzystać program <tt>kompresujbloki</tt> z zadania 1).
# Porównaj liczbę bitów w plikach <tt>wynik.huf</tt> oraz <tt>wynik??.huf</tt>.
<!--# Porównaj liczbę bitów w plikach <tt>wynik.huf</tt> oraz <tt>wynik??.huf</tt>.-->
 
Odpowiedz na pytania:
# Czy poprzez powtórne zastosowanie tego samego algorytmu kodowania (tzn. algorytmu Huffmana dla bloków 1-elementowych) można osiągnąć mniejszy rozmiar pliku? Wyjaśnij dlaczego.
# Czy poprzez powtórne zastosowanie innego algorytmu kodowania można osiągnąć mniejszy rozmiar pliku? Wyjaśnij dlaczego.
# W praktyce, aby móc wykonać dekompresję, w nagłówku wynikowego pliku musiałby być też zapisany kod, użyty do zakodowania wiadomości. Oszacuj ile bajtów byłoby potrzebnych w takiej sytuacji na zapisanie każdego z pięciu kodów, użytych w pkt. 3 do powtórnej kompresji.
# Czy powtórne zastosowanie algorytmu Huffmana, być może z innym rozmiarem bloku, może spowodować zwiększenie rozmiaru pliku z nagłówkiem, czyli łącznego rozmiaru zakodowanej wiadomości i kodu, użytego do zakodowania?


Co możesz powiedzieć o możliwości kompresji pliku już skompresowanego? Czy poprzez kilkakrotne zastosowanie kompresji można osiągnąć mniejszy rozmiar pliku? Jeśli tak, to w jakiej sytuacji? Uwzględnij fakt, że aby móc wykonać dekompresję, w wynikowym pliku musi być też zapisany kod, użyty do zakodowania wiadomości.


== Zadanie 3 ==
== Zadanie 3 ==
Linia 47: Linia 52:
Wykonaj następujący eksperyment:
Wykonaj następujący eksperyment:
# Przygotuj plik <tt>dane.txt</tt> zawierający tekst w języku naturalnym (polskim lub angielskim) o długości przynajmniej 50000 znaków.
# Przygotuj plik <tt>dane.txt</tt> zawierający tekst w języku naturalnym (polskim lub angielskim) o długości przynajmniej 50000 znaków.
# Wygeneruj [[Teoria informacji/TI Wykład 3#huffman|kody Huffmana]] <math>\varphi_1</math>, <math>\varphi_2</math> i <math>\varphi_3</math> [[Teoria informacji/TI Wykład 3#kodowanie par|dla grup]] 1, 2 i 3 symboli pliku <tt>dane.txt</tt>.
# Wygeneruj [[Teoria informacji/TI Wykład 3#huffman|kody Huffmana]] <math>\varphi_1</math>, <math>\varphi_2</math> i <math>\varphi_3</math> [[Teoria informacji/TI Wykład 3#kodowanie par|dla bloków]] 1, 2 i 3 symboli pliku <tt>dane.txt</tt>.
# Wygeneruj losowy ciąg 10000 bitów i zapisz do pliku <tt>kod.huf</tt>.
# Wygeneruj losowy ciąg 10000 bitów i zapisz do pliku <tt>kod.huf</tt>.
# Odczytaj 1000 symboli poprzez "zdekodowanie" pliku <tt>kod.huf</tt> (tak jakby był to plik skompresowany), używając każdego z kodów <math>\varphi_1</math>, <math>\varphi_2</math> i <math>\varphi_3</math>. Wynik dekodowania zapisz do plików <tt>dekod1.txt</tt>, <tt>dekod2.txt</tt> i <tt>dekod3.txt</tt>.
# Odczytaj 1000 symboli poprzez "zdekodowanie" pliku <tt>kod.huf</tt> (tak jakby był to plik skompresowany), używając każdego z kodów <math>\varphi_1</math>, <math>\varphi_2</math> i <math>\varphi_3</math>. Wynik dekodowania zapisz do plików <tt>dekod1.txt</tt>, <tt>dekod2.txt</tt> i <tt>dekod3.txt</tt>.
Linia 54: Linia 59:
# Czy każdy ciąg bitów można zdekodować za pomocą [[Teoria informacji/TI Wykład 3#huffman|kodów Huffmana]] <math>\varphi_i</math>? A za pomocą dowolnego kodu, niekoniecznie będącego kodem Huffmana?
# Czy każdy ciąg bitów można zdekodować za pomocą [[Teoria informacji/TI Wykład 3#huffman|kodów Huffmana]] <math>\varphi_i</math>? A za pomocą dowolnego kodu, niekoniecznie będącego kodem Huffmana?
# Ile bitów pliku <tt>kod.huf</tt> musiałeś zdekodować w każdym z 3 przypadków, aby uzyskać 1000 symboli? W którym przypadku liczba bitów była największa, a w którym najmniejsza? Dlaczego są one różne dla każdego przypadku?
# Ile bitów pliku <tt>kod.huf</tt> musiałeś zdekodować w każdym z 3 przypadków, aby uzyskać 1000 symboli? W którym przypadku liczba bitów była największa, a w którym najmniejsza? Dlaczego są one różne dla każdego przypadku?
# Jak można przewidzieć te wartości bez wykonywania eksperymentu, znając jedynie kod <math>\varphi_i</math>?
# Jak można przewidzieć te wartości bez wykonywania eksperymentu, znając jedynie kod <math>\varphi_i</math>? Podaj odpowiedni wzór.
# Który z plików <tt>dekod*.txt</tt> jest najbardziej podobny do pliku <tt>dane.txt</tt>?
# Który z plików <tt>dekod*.txt</tt> jest najbardziej podobny do pliku <tt>dane.txt</tt>?

Wersja z 19:08, 1 wrz 2006

Laboratorium

Zadanie 1

Polecenie

  1. 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 Projektu Gutenberg.
  2. Napisz program litery, 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ą obliczonego rozkładu prawdopodobieństwa. Uruchom program dla trzech przygotowanych wcześniej plików, porównaj otrzymane wyniki.
  3. Napisz program huffman, który czyta plik tekstowy o podanej nazwie i oblicza kod Huffmana dla rozkładu symboli występujących w tym pliku. Program powinien wypisać otrzymany kod w formie: A 001 <nowa_linia> b 0001010 ...
    Napisz program shannon, który oblicza kod Shannona-Fano.
  4. Napisz program kompresuj, który koduje (kompresuje) 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 wynikowy bit zapisywać na oddzielnym bajcie, jako znak "0" lub "1".
  5. Uruchom program kompresuj 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"/"1" w plikach .huf i .sf,
    • entropię rozkładu prawdopodobieństwa symboli w oryginalnym pliku.
      Czy te wielkości zależą od języka kompresowanego tekstu?
  6. Napisz program kompresujbloki, 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 w praktyce wykonać dekompresję, kod musiałby 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.


Zadanie 2

Wykonaj następujący eksperyment aby sprawdzić, czy ponowna kompresja pliku już skompresowanego może pozwolić na dalsze zmniejszenie rozmiaru pliku:

  1. Przygotuj plik dane.txt zawierający tekst w języku naturalnym (polskim lub angielskim) o długości przynajmniej 50000 znaków.
  2. Skompresuj dane.txt algorytmem Huffmana, zapisując zakodowaną informację do pliku wynik.huf (możesz wykorzystać program kompresuj z zadania 1). Dla ułatwienia możesz każdy wynikowy bit zapisywać na oddzielnym bajcie, jako znak "0" lub "1".
  3. Wynikowy ciąg bitów skompresuj algorytmem Huffmana, zastosowanym do bloków 1, 2, 4, 8 i 16 bitów, otrzymując pięć kolejnych plików: wynik01.huf, wynik02.huf, wynik04.huf, wynik08.huf, wynik16.huf (możesz wykorzystać program kompresujbloki z zadania 1).

Odpowiedz na pytania:

  1. Czy poprzez powtórne zastosowanie tego samego algorytmu kodowania (tzn. algorytmu Huffmana dla bloków 1-elementowych) można osiągnąć mniejszy rozmiar pliku? Wyjaśnij dlaczego.
  2. Czy poprzez powtórne zastosowanie innego algorytmu kodowania można osiągnąć mniejszy rozmiar pliku? Wyjaśnij dlaczego.
  3. W praktyce, aby móc wykonać dekompresję, w nagłówku wynikowego pliku musiałby być też zapisany kod, użyty do zakodowania wiadomości. Oszacuj ile bajtów byłoby potrzebnych w takiej sytuacji na zapisanie każdego z pięciu kodów, użytych w pkt. 3 do powtórnej kompresji.
  4. Czy powtórne zastosowanie algorytmu Huffmana, być może z innym rozmiarem bloku, może spowodować zwiększenie rozmiaru pliku z nagłówkiem, czyli łącznego rozmiaru zakodowanej wiadomości i kodu, użytego do zakodowania?


Zadanie 3

Wykonaj następujący eksperyment:

  1. Przygotuj plik dane.txt zawierający tekst w języku naturalnym (polskim lub angielskim) o długości przynajmniej 50000 znaków.
  2. Wygeneruj kody Huffmana φ1, φ2 i φ3 dla bloków 1, 2 i 3 symboli pliku dane.txt.
  3. Wygeneruj losowy ciąg 10000 bitów i zapisz do pliku kod.huf.
  4. Odczytaj 1000 symboli poprzez "zdekodowanie" pliku kod.huf (tak jakby był to plik skompresowany), używając każdego z kodów φ1, φ2 i φ3. Wynik dekodowania zapisz do plików dekod1.txt, dekod2.txt i dekod3.txt.

Odpowiedz na pytania:

  1. Czy każdy ciąg bitów można zdekodować za pomocą kodów Huffmana φi? A za pomocą dowolnego kodu, niekoniecznie będącego kodem Huffmana?
  2. Ile bitów pliku kod.huf musiałeś zdekodować w każdym z 3 przypadków, aby uzyskać 1000 symboli? W którym przypadku liczba bitów była największa, a w którym najmniejsza? Dlaczego są one różne dla każdego przypadku?
  3. Jak można przewidzieć te wartości bez wykonywania eksperymentu, znając jedynie kod φi? Podaj odpowiedni wzór.
  4. Który z plików dekod*.txt jest najbardziej podobny do pliku dane.txt?
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Teoria_informacji/TI_Ćwiczenia_4&oldid=39470”