NSWI072 Algoritmy komprese dat - Zk. 15.1.2014 Dvořák

[Pecivaal]

Systém zkoušení: 4 příklady, 30 minut na přípravu/vypracování, potom společná kontrola a doplňující otázky, na závěr předvedení praktické úlohy (typicky implementace nějaké kompresní metody, kterou mu pošlete aspoň den předem) na jeho notebooku (netřeba nosit vlastní).

Otázky:
1) Huffmanův strom, délka kódového slova max. 16b. Jaká je maximální možná velikost vstupu, při níž zaručeně nedojde k přetečení?
2) Příklad na aritmetické kódování - dána abeceda {a,b,c} s pravděpodobnostmi {p(a) = 0.2, p(b) = 0.3, p(c) = 0.5} a kód 0.62359... Dešifrujte (stačí první dva znaky).
3) Burrows-Wheelerova transformace textu sssssssssh s následným použitím Move To Front.
4) Popište princip predikce u DPCM, role Wiener-Hopfových rovnic.

Odpovědi, komentář:
1) Přetečení nastane v okamžiku, kdy výška stromu překročí 17. Nejhorší případ je degenerovaný strom s téměř "lineární" strukturou - na každém patře kromě posledního a prvního vždy jen jeden list (na posledním dva, na prvním žádný). Je třeba si rozmyslet, jaké musí být nejmenší možné četnosti, aby k tomu došlo. Nejníže jsou samozřejmě četnosti 1 a 1, což dá v předposledním patře vnitřní uzel se součtem četností rovným 2. Jeho sourozenci stačí mít četnost opět jedna, tedy vnitřní uzel o patro výš bude mít četnost 2 + 1 = 3. Jeho sourozenec nemůže mít 1, protože pak by musel vytvořit dvojici o dvě patra níž s tou předchozí jedničkou. Dvojka to být může. Tedy o patro výše opět 3 + 2 = 5. Jeho sourozenec bude mít ze stejného důvodu četnost 3, o patro výš 5 + 3 = 8. Všimneme si, že posloupnost součtů četností ve vnitřních vrcholech je 2,3,5,8,..., vždy součet předchozích dvou. Což jsou Fibonacciho čísla (první dva prvky jen nejsou vnitřní uzly, ale listy v nejnižším patře). Tedy strom výšky 17 bude mít v kořeni součet četností roven sedmnáctému Fibonaccimu číslu, což je součet četností celého stromu, což je délka vstupu. Stačí tedy vzít vstup o jedna menší, aby tato situace ještě těsně nenastala.

2) Easy. Nicméně pak chtěl ještě srovnat Huffmanovo a aritmetické kódování. Úplně jsem nevěděl, co má na mysli, pak ale ještě doplnil, že to chce z hlediska teorie informace. Vzpomněl jsem si na vzorec entropie Huffmanova kódu, což je H <= L(C) < H + 1, kde L(C) je průměrná délka kódového slova. Pak jsem ještě po haluzi trefil vzorec pro aritmetické kódování, což je H <= L(C) < H + 2. Na první pohled je Huffman lepší, nicméně háček je v tom, že ve vzorci Huffmana se jedná o entropii jednoho znaku, kdežto u AC je to entropie celého textu. Takže AC je z tohoto pohledu mnohem, mnohem lepší.

3) Jednoduché, vyšlo mi něco jako sss..ss@h, kde @ je symbol konce slova. Po MTF je to (19,1,1,...1,27,10). Nebo tak nějak. To mi uznal, pak chtěl ještě vysvětlit, jak by se to dekódovalo zpátky. A k čemu je to vlastně celé dobré.

4) Napsal jsem, co jsem si pamatoval ze slajdů, vzpomněl jsem si, že jde o to, aby derivace odchylky podle parametrů byly nulové a věděl jsem, že pak se z toho nějak vymlátí ty rovnice. Co už jsem však nevěděl, bylo jak. A zajímalo ho, kde se tam vlastně vezme ta střední hodnota. To jsem netušil a i když mi to pak vysvětloval, byla to taková magic, že už si to nepamatuju.

Teorii ohodnotil pan Dvořák mezi dvojkou a trojkou (v prvním příkladu jsem měl špatnou úvahu, na Fibonacciho mě musel přivést on, v druhém jsem nevěděl ty entropie - z toho byl hodně mrzutý, trojka ok, čtvrtý skoro vůbec). Následovalo předvedení praktické úlohy. Implementoval jsem IMA ADPCM pro wav soubory. Algoritmus je jednoduchý, ale je potřeba si pohrát s formátem - správné hlavičky, blokování dat apod. Tady zkoušející ocenil moji práci a to, že jsem si to sám dohledal a že jsem se s tím tak piplal. Kód samotný ohodnotil jako solidní a díky tomu jsem si výslednou známku spravil na dvojku.

Otázky samotné nebyly až tak těžké, ale hrozně se v tom rýpal. Je potřeba vědět skutečně téměř všechno a skutečně tomu rozumět.