Huffmanov strom a BWT rovnaké ako v http://forum.matfyz.info/viewtopic.php?f=422&t=9851
Inak:
1. Elias codes + vysvetliť univerzálnosť
2. Jayant quantizer – podobný príklad ako v prezentácii
NSWI072 Algoritmy komprese dat
-
- Matfyz(ák|ačka) level I
- Příspěvky: 17
- Registrován: 4. 6. 2014 12:36
- Typ studia: Informatika Mgr.
Re: NSWI072 Algoritmy komprese dat
Zkouška z 2.2.19:
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) U LZW někdy nastane případ, že dekompresor dostane odkaz do slovníku na pozici,která tam není. Kdy to nastane a jak se to řeší?
3) Libovolný ztrátový algoritmus pro kompresi zvuku.
4) K čemu je DCT u JPG?
Doplňující otázky jsem měla: vztah DFT a DCT, Nevýhody JPG a kde se využívá LZW.
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) U LZW někdy nastane případ, že dekompresor dostane odkaz do slovníku na pozici,která tam není. Kdy to nastane a jak se to řeší?
3) Libovolný ztrátový algoritmus pro kompresi zvuku.
4) K čemu je DCT u JPG?
Doplňující otázky jsem měla: vztah DFT a DCT, Nevýhody JPG a kde se využívá LZW.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 3
- Registrován: 13. 6. 2017 00:16
- Typ studia: Informatika Mgr.
Re: NSWI072 Algoritmy komprese dat
Zkouška z 14.2.2020
1. Huffmanův strom, stejně jako u předchozího příspěvku, délka slova max 32b
2. Jak funguje inverzní BWT, pokud byla transformace použita na slovo banana
3. LZW dekódování - už tady někde bylo
4. Jaké typy obrázků jsou využívány ve video formátu MPEG, doplňující k této otázke pak bylo, na jakém principu funguje predikce dalších obrázků ve videu
Doplňující otázky - využití LZW, na jakém principu pracuje DCT v JPEG a proč jsou koeficienty v kvantizační matici vlevo nahoře tak malé
1. Huffmanův strom, stejně jako u předchozího příspěvku, délka slova max 32b
2. Jak funguje inverzní BWT, pokud byla transformace použita na slovo banana
3. LZW dekódování - už tady někde bylo
4. Jaké typy obrázků jsou využívány ve video formátu MPEG, doplňující k této otázke pak bylo, na jakém principu funguje predikce dalších obrázků ve videu
Doplňující otázky - využití LZW, na jakém principu pracuje DCT v JPEG a proč jsou koeficienty v kvantizační matici vlevo nahoře tak malé
-
- Matfyz(ák|ačka) level I
- Příspěvky: 3
- Registrován: 21. 1. 2023 12:38
- Typ studia: Informatika Mgr.
Re: NSWI072 Algoritmy komprese dat
Toto je skúška z 19.1.2023. Dostali sme nasledujúce otázky:
1. Huffmanové kódovanie
a) Ktorý z nasledujúcich kódov nemôže byť Huffmanov?
- {0, 10, 01}
- {01, 10}
- {00, 01, 10, 110}
b) Vysvetlite otpimálnosť Huffmanovho kódovania
c) Je najeké lepšie kódovanie pre lossless compression?
2. BWT transformation of banana
a) napísať výsledok tejto transformácie
b) napísať a vysvetliť dekódovanie
c) prečo je to dobré pre lossless compression?
3. Hlavné myšlienky video kompresie
Čiastočné riešenie/hinty:
1. a) ano, nie, nie - vysvetliť na tom, že v prvom vieme napisat input taký, že toto bude kód. V ostatných stačí argument, že ak postavíme stromy týchto kódov, bude tam vrchol, ktorý má iba jedného syna a tým pádom to nie je HC.
b) napísať lemmy s tým spojené, spomenúť Kraft-McMillan inequality a že HC je uniquely decodable.
c) artimetické kódovanie + argument s entropiou - toto je v nejakom predošlom príspevku.
2) a) napísať cykliské transformácie, ich abecedné zoradenie a výsledný vektor aj s číslom riadku, v ktorom je pôvodné slovo
b) popísať ten algoritmus, že máme pole F, T, L a ako sa používajú + že dekódovanie ide od konca
c) povedať, že chceme aby rovnaké písmená boli pri sebe a taktiež spomenút Move To Front a prečo je to dobré
3) toto som moc nevedela ale napísala som tam niečo o motion vectore. Potom sa ma pýtal na DCT a druhy rôznych framov (P, I, B) a trošku to spájal aj s JPEG ako sa tam využíva DCT.
Doplňujúca otázka: povedať niečo o lossless compression obrázkov (GIF, PNG), hlavne PNG a aký algoritmus sa tam používa (predikcia a LZ77)
Taktiež viem o zadaní z iného termínu:
1. Udělat huffmanuv kód z danejch pravděpodobností znaků. To mělo asi 5 poduloh, spocitat entropii, průměrnou délku slova, jakej je vztah mezi průměrnou délkou a tou entropii a pak ten priklad na maximální hloubku než dojde k přetečení u huffmanova stromu z predchádzajúcich príspevkov.
2. Elias codes a universality
3. Porovnejte z hlediska komprese png a jpeg
1. Huffmanové kódovanie
a) Ktorý z nasledujúcich kódov nemôže byť Huffmanov?
- {0, 10, 01}
- {01, 10}
- {00, 01, 10, 110}
b) Vysvetlite otpimálnosť Huffmanovho kódovania
c) Je najeké lepšie kódovanie pre lossless compression?
2. BWT transformation of banana
a) napísať výsledok tejto transformácie
b) napísať a vysvetliť dekódovanie
c) prečo je to dobré pre lossless compression?
3. Hlavné myšlienky video kompresie
Čiastočné riešenie/hinty:
1. a) ano, nie, nie - vysvetliť na tom, že v prvom vieme napisat input taký, že toto bude kód. V ostatných stačí argument, že ak postavíme stromy týchto kódov, bude tam vrchol, ktorý má iba jedného syna a tým pádom to nie je HC.
b) napísať lemmy s tým spojené, spomenúť Kraft-McMillan inequality a že HC je uniquely decodable.
c) artimetické kódovanie + argument s entropiou - toto je v nejakom predošlom príspevku.
2) a) napísať cykliské transformácie, ich abecedné zoradenie a výsledný vektor aj s číslom riadku, v ktorom je pôvodné slovo
b) popísať ten algoritmus, že máme pole F, T, L a ako sa používajú + že dekódovanie ide od konca
c) povedať, že chceme aby rovnaké písmená boli pri sebe a taktiež spomenút Move To Front a prečo je to dobré
3) toto som moc nevedela ale napísala som tam niečo o motion vectore. Potom sa ma pýtal na DCT a druhy rôznych framov (P, I, B) a trošku to spájal aj s JPEG ako sa tam využíva DCT.
Doplňujúca otázka: povedať niečo o lossless compression obrázkov (GIF, PNG), hlavne PNG a aký algoritmus sa tam používa (predikcia a LZ77)
Taktiež viem o zadaní z iného termínu:
1. Udělat huffmanuv kód z danejch pravděpodobností znaků. To mělo asi 5 poduloh, spocitat entropii, průměrnou délku slova, jakej je vztah mezi průměrnou délkou a tou entropii a pak ten priklad na maximální hloubku než dojde k přetečení u huffmanova stromu z predchádzajúcich príspevkov.
2. Elias codes a universality
3. Porovnejte z hlediska komprese png a jpeg
-
- Matfyz(ák|ačka) level I
- Příspěvky: 5
- Registrován: 11. 6. 2019 01:48
- Typ studia: Informatika Bc.
Re: NSWI072 Algoritmy komprese dat
60 minut na pisemnou cast, pak pockate na svuj blok a pak mate 30 minut na ustni.
Velmi mily zkousejici. (Jiri Dvorak)
Doporucuji neucit se z prezentaci, vetsina veci je vysvetlitelna na 2m video na youtube, ale jeho prezentace to maji napsane tak odborne, ze casto to z nich vubec nejde pochopit.
1) Arithmetic coding.
Input string of length 10 over the source alphabet a={a,b,c} with symbol probabilities P(a)=0.2, P(b)=0.3, P(c)=0.5 was encoded using arithmetic coding ("theoretical" real values)
a) decode the resulting output 0.63215699 (first symbols suffice)
b) Explain the main idea of the "theoretical" arithmetic coding algorithm.
c) How is possible to implement the algorithm in integer arithmetic?
2) Integer coding.
Describe Elias codes that are useful to encode integers and explain why they are called universal codes.
3) Video compression
Explain the main principles of lossy video compression.
Velmi mily zkousejici. (Jiri Dvorak)
Doporucuji neucit se z prezentaci, vetsina veci je vysvetlitelna na 2m video na youtube, ale jeho prezentace to maji napsane tak odborne, ze casto to z nich vubec nejde pochopit.
1) Arithmetic coding.
Input string of length 10 over the source alphabet a={a,b,c} with symbol probabilities P(a)=0.2, P(b)=0.3, P(c)=0.5 was encoded using arithmetic coding ("theoretical" real values)
a) decode the resulting output 0.63215699 (first symbols suffice)
b) Explain the main idea of the "theoretical" arithmetic coding algorithm.
c) How is possible to implement the algorithm in integer arithmetic?
2) Integer coding.
Describe Elias codes that are useful to encode integers and explain why they are called universal codes.
3) Video compression
Explain the main principles of lossy video compression.