Vyuka

Klasifikovaný zápočet:
5 bodovaných úloh, každá za 20 bodů.

28.2. Výpočet entropie

Dataset: Pizza and Chili Corpus
Spočtěte velikost abecedy a četnosti symbolů pro vybrané soubory z datasetu.
Spočítejte empirickou entropii souborů.
Spočítejte podmíněnou entropii.
Spočítejte přibližnou velikost souborů po kompresi, jako počet symbolů krát entropie.
Předpokládejte následující situaci: naučili jste libovolnou neuronovou síť pravděpodobnostní rozdělení symbolů p(y|x) v jednom ze souborů z datasetu. Nyní byste chtěli takto naučenou síť použít pro predikci p'(y|x) nad jiným souborem z datasetu, spočítejte o kolik se v nejlepším případě zhorší kódování jednoho znaku.
Solution

7.3. Výpočet entropie k-tého řádu (20 bodů)

Dataset stejně jako minule: Pizza and Chili Corpus
Spočítejte entropii k-tého řádu pro vybraný soubor z datasetu pro k=0,1,2,3,4,5,... . (8 bodů)
Spočítejte přibližnou velikost zkomprimovaného souboru jako Hk*n, kde n je počet symbolů na vstupu. (2 body)
Předpokládejte, že ukládáte podmíněné četnosti modelu k-tého řádu ve stromové nebo jiné struktuře, spočítejte počedt bitů, které budete potřebovat pro uložení této struktury. Velikost této struktury společně s velikostí zkomprimovaného výstupu(vypočteno pomocí entropie k-tého řádu). Nalezněte k takové, že teoretická výsledná velikost souboru bude minimální.(10 bodů)

21.3. Kódy proměnné délky (20 bodů)

Implementujte Golombův algoritmus kódování/dekódování. Pro testovací data nalezněte optimální M(5 bodů)
Imlementujte jeden z algoritmů Elias gamma, delta nebo Fibonacci.(5 bodů)
Měli byste symboly setřídit podle četnosti a symbolům s větší četností přiřadit kratší kód a naopak.
Data nemusíte ukládat binárně stačí v textové podobě skevence nul a jedniček.
Porovnejte své výsledky s entropií a spočítejte redudanci kódu jako R = C - H, kde C je průměrný počet bitů na jeden bajt původního souboru: 8*|c(m)|/|m|(1 bod)
Připravte si odpovědi na bonusové otázky a úkoly z přednášek (9 bodů)

28.3. Statistické kódování - 20 bodů

(4 body) Odpovězte na následující otázky:
- 1) Které z následujících kódů nemůžou být Huffmanovými kódy a proč? (2 body)
  a) {0, 10, 11}
  b) {00, 01, 10, 110}
  c) {01, 10}
- 2) Třídy kódů. Uvažujte kód {0, 01}. (1 bod)
  a) Je to prefixový kód?
  b) Je unikátně dekódovatelný?
  c) Je nesingulární?
- 3) Optimální délky slov. (1 bod)
  a) Může l=(1, 2, 2) být délkami slov Huffmanova kódu?
  a) Může l=(2, 2, 3, 3) být délkami kódu Huffmanova kódu?
(6 bodů) Odpovězte na bodované příklady z přednášky.
(10 bodů) Programovací úloha
- Implementujte Huffmanovo kódování - sestavte Huffmanův strom a zakódujte vstupní soubor.
- Stejný strom použijte pro dekódování.
- Porovnejte dosažené kódování s entropií.
- Výsledná data nemusíte ukládat binárně, stačí v textové podobě jako sekvence 0 a 1.

4.4. Statistické a slovníkové kódování I - 20 bodů

11.4. Transformace pro kompresi dat (20 bodů)

Implementujte BZIP2 proces pro zakódování/dekódování s BWT, MTF a RLE transformacemi nakonec zakódujte pomocí Huffmanova kódování.(12 bodů)
Rozdělte vstupní soubor na menší bloky, vyzkoušejte kompresi po menších blocích(32, 64, 128, 256 kB) (4 body).
Porovnejte a vyhodnoťte dosažené výsledky na menších blocích s případem, kdy zakódujeme celý vstup najednou (4 body).