KOMPRESIJA FORMATA
Pomembni sta 2 stvari pri stiskanju GIF . Prvič, gre za stiskanje brez izgub, kar pomeni, da se v postopku stiskanja ne izgubijo podatki o sliki, dekompresirana slika pa je enaka originalu. Drugič, GIF uporablja LZW kompresijsko tehniko (leta 1984 je Terry Welch izboljšal različico Abrahama Lempela in Jacoba Ziva, ki se je imenovala LZ78, zaradi letnice 1987), ki pri kompresiji uporabi ponovitve nizov v podatkovnih tokovih. ([5], [7], [8])
To delo je objavljeno pod licenco Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna.
To delo je objavljeno pod licenco Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna.
Čeprav se s posnetka ne opazi, da prihranimo na prostoru, saj se zmanjšana različica iz 10 bitov informacij na 7 bitov informacij ne opazi tako dobro. Če želite izračunati kompresijsko razmerje, število prvotnih informacij delite s končno količino informacij, torej 10/7 = 1.43.
Ne pozabite, da so datoteke kot so slike, ki jih stiskamo z različnimi formati, napram temu primeru zgoraj nepredstavljivo večje oz. vsebujejo nekaj milijon informacij, kjer pa se stiskanje res občuti.
Pred nadaljnjo predstavitvijo formata GIF se preverite, ali ste res razumeli algoritem LZW in ali obvladate ta kompresijski postopek.
Na desni strani sta še enkrat prikazana predzadnji 9. korak in zadnji 10. korak. Kaj če 10. korak nebi bil zadnji in bi originalnemu nizu na koncu dodali še AB torej bi bil celotni niz: ABABBABCABAB. Premislite kako spremeniti 10. korak in koliko korakov morate dodati, da dokončate kompresijo tega niza, če jih je sploh potrebno dodati.
To delo je objavljeno pod licenco Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna.
To delo je objavljeno pod licenco Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna.
To delo je objavljeno pod licenco Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna.
DVE RAZLIČICI FORMATA
Obstajata dve različici formata in sicer GIF87a, ki je nastal leta 1987, in GIF89a, ki je izboljšana verzija GIF87a, ki je nastal leta 1989 (ta omogoča možnost animiranega GIF-a).
GIF87a
Leta 1987 je CompuServe (ameriški ponudnik speltnih storitev) javnosti predstavil barvni slikovni format za svoja območja za nalaganje datotek. Ta je nadomestil njihovo prejšnjo obliko kodiranja, ki je uporabljala le dve barvi in sicer belo in črno. ([3])
GIF89a
Leta 1989 pa je CompuServe prvotni različici dodal podporo za zamude pri animaciji, prosojne barve ozadja in shranjevanje metapodatkov, specifičnih za aplikacije. Obe različici lahko med seboj ločimo tako, da pogledamo prvih šest bajtov dototeke, ki se v interpretaciji ASCII glasi “GIF87a” oziroma “GIF89a”.
Leta 1995 je Netscape Navigator 2.0 dodal možnost animiranih GIF-ov. To je funkcija shranjevanja več slik v eni datoteki, skupaj s kontrolnimi podatki, ki se v spletu pogosto uporablja za izdelavo preprostih animacij. ([1], [3])
ANIMIRANI GIF89a
Čeprav format GIF ni bil zasnovan kot animacijski medij, je njegova sposobnost shranjevanja več slik v eno datoteko pripeljala do tega, da se je razvil format za shranjevanje okvirjev zaporedja animacije. Različici GIF89a je bila dodana razširitev grafičnega nadzora, ki omogoča slikanje slik (okvirjev) v datoteki s časovnimi zamiki in tako tvori posnetek. Znotraj vsakega okvirja so slikovni podatki kodirani z LZW in razporejeni v podbloke do 255 bajtov.
Ampak tako je šele nastal posnetek, ki se je po koncu vseh slik, ki so bile dodane, ustavil. Želeli so še omogočiti zanko, da bi se posnetek ponavljal neprestano in tako so ustvarili poseben blok, ki določa, kolikokrat naj se zaporedje sličic predvaja (od 1 do 65535-krat) ali naj se neprekinjeno ponavlja (za to uporabimo število 0, ki pomeni za vedno). ([3])
PREVERITE SE
Poskusite sami narediti animirani GIF. Spodaj so naložene slike, s katerimi poskusite poustvariti GIF, ki se prikazuje čisto zgoraj pod logotipom in prikazuje grafiko. Hkrati imate dostop do spletne strani, ki vam omogoča zastonj izdelavo animiranega GIF-a. Svetujem vam, da si najprej ustvarite profil (vse je zastonj, brez skrbi), in nato poustvarite zgornji GIF. Ko vam uspe ste pripravljeni narediti kateri koli GIF, le da si morate pridobiti/narediti slike, ki se bodo ponavljale v neskončnost.
Format PDF
KAJ JE PDF?
Prenosna oblika dokumenta (PDF) je vrsta dokumenta, ki ga je podjetje Adobe ustvaril v devetdesetih letih prejšnjega stoletja. Namen te datoteke je bil uvesti standard za predstavitev dokumentov in drugega referenčnega gradiva v obliki, ki je neodvisna od aplikativne programske opreme, strojne opreme in operacijskega sistema. Hkrati je oblika datoteke, ki je vse elemente natisnjenega dokumenta zajela kot elektronsko sliko, ki si jo lahko ogledate, jo premikate, natisnete ali posredujete nekomu drugemu.
Datoteke PDF so še posebej uporabne za dokumente, kot so članki iz revij, brošure izdelkov ali letaki, v katerih želite ohraniti prvotni grafični videz v spletu.
V jedru PDF je slikovni model, ki izhaja iz jezika opisa strani PostScript. Ta model omogoča popolno, natančno in strokovno opisovanje besedil in grafik na način, ki je neodvisen od naprave in ločljivosti. Za razliko od Postcripta, ki je programski jezik, PDF temelji na strukturirani binarni obliki zapisa datoteke, ki je optimizirana za visoko zmogljivost v interaktivnem ogledu.
Kot zanimivost naj omenim, da arhitekturno obstaja le ena omejitev v standardu PDF: celotna velikost datoteke mora biti pod ~ 10 GB, saj tabele navzkrižnih referenc, ki opredeljujejo strukturo PDF, uporabljajo 10 bitov.
Datoteke PDF je seveda možno odpreti s pomočjo programov Adobe Acrobat (Reader/Writer). Dodatna prednost pa je tudi ta, da v primeru, da nimamo programa Adobe Acrobat lahko dokument odpremo tudi v večini brskalnikov (Chrome, Safari, Firefox,…). Večina komercialno dostopnih programskih paketov ponuja tudi pretvorbo svojih dokumentov v format datoteke PDF brez potrebe po dodatnih komponentah programske opreme. Tako da lahko datoteka PDF vsebuje informacije, kot so besedilo, slike, hiperpovezave, polja obrazcev, obogateni mediji, digitalni podpisi, priloge, metapodatki,… ([14], [16], [15])
ČASOVNICA RAZVOJA
Spodaj je predstavljena kratka zgodovina razvoja formata PDF. Dobro si jo preberite in si skušajte čimbolj zapomniti, kaj je katero leto format PDF pridobil pri razvoju. ([11])
To delo je objavljeno pod licenco Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna.
KOMPRESIJA FORMATA
Stiskanje PDF datoteke je zmanjšanje velikosti slike PDF, da postane združljiva s postopki, kot so nalaganje v spletu, tiskanje in pripenjanje na e-poštna sporočila. Stiskanje PDF je pomembno, ker so datoteke PDF lahko zelo obsežne glede na količino informacij, ki jih vsebujejo. Ker mnogi uporabniki želijo ohraniti izvirno datoteko PDF, vendar jo zmanjšajo na manjšo velikost, je priljubljena rešitev stiskanje PDF brez izgub.
PDF uporablja zelo veliko vrst kompresij. Zakaj? Ker vsebuje tako slike, kot besedilo, kot večpredstavnostne elemente (kot sta zvok in video), možen je digitalni podpis, … Kot lahko opazite, lahko skoraj vse pretvorimo v PDF format in ravno zato je pomembno, da je PDF zmožen uporabljati tako velik nabor algoritmov za stiskanje.
Katere vse uporablja in čemu točno so namenjeni pa lahko preverite tu –>
Ko je PDF ustvarjen, lahko še vedno spremenite razmerje stiskanja. To je lahko priročno, če je datoteka prevelika za pošiljanje po e-pošti ali za nalaganje. Ne pozabite na pomanjkljivost: pri ponovnem stiskanju podatkov pride do dodatne izgube podrobnosti! ([9], [12], [13])
Seznam algoritmov stiskanja, ki jih je mogoče uporabiti, je obsežen:
- CCITT G3 / G4 – uporablja se za enobarvne slike
- JPEG – algoritem z izgubami, ki se uporablja za slike
- JPEG2000 – sodobnejša alternativa JPEG, ki se uporablja tudi za stiskanje slik
- Deflate – uporablja se za stiskanje besedila in slik
- JBIG2 – alternativa CCITT stiskanju za enobarvne slike
- LZW – uporablja se za stiskanje besedila in slik, vendar ga zamenja Deflate
- RLE – uporablja se za enobarvne slike
- ZIP – uporablja se za sivine ali barvne slike
([9])
Algoritem deflate:
Bolj podrobno pa predstavimo algoritem Deflate. Ta algoritem je snoval Phil Katz. Sicer pa gre za kombinacijo dveh algoritmov stiskanja in sicer LZ77 in Huffmanova drevesa.
Sam algoritem je zelo zapleten, predvsem če se spustimo v programsko kodo. Ravno zaradi tega, bomo spoznali algoritem le površinsko, saj je pomembno, da razumemo delovanje algoritma!
Spodnja slika predstavlja kako poteka sam algoritem, in sicer vhodne podatke najprej zakodiramo z algoritmom LZ77, nato zakodirane podatke zakodiramo še v Huffmanovo drevo. Dobljeni podatki iz Huffmanovega drevesa predstavljajo podatke zakodirane na način Deflate. ([17])
To delo je objavljeno pod licenco Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna.
Kako deluje algoritem LZ77?
Osnovna ideja algoritma, ki temelji na slovarju, je nadomestiti pojav določenega zaporedja niza bitov podatkov s sklicevanjem na prejšnji pojav tega niza. Če povemo z drugimi besedami: če smo ravnokar prebrali nek niz in vemo, da smo tak niz že srečali, ga nadomestimo z v naprej določeno sintakso, ki jo bomo spoznali nekoliko nižje. S tem smo stisnili podatke, saj smo nek niz recimo dolžine 8 nadomestili le z znakom * (gre za izmišljeno sintakso, za lažje razumevanje). ([17])
Natančneje algoritem stiskanja LZ77 deluje tako, da z drsnim oknom poišče zaporedja podatkov, ki se ponavljajo, in vsako ponovljeno zaporedje kodira s parom števil (D, R), kjer D predstavlja dolžino, R pa razdaljo.
Drsno okno je sestavljeno iz dveh delov: iskalnega vmesnika in bralnega umesnika. Iskalni vmesnik vsebuje slovar – nedavno kodirane podatke, bralni vmesnik pa vsebuje naslednji del zaporedja vhodnih podatkov, ki ga je treba kodirati. Na spodnji sliki je prikazan primer drsnega okna. ([17])
To delo je objavljeno pod licenco Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna.
V praksi je običajno velikost drsnega okna od nekaj KB do MB, na primer 4 KB, 32 KB, 1 MB ali 4 MB.
- R = razdalja od iskalnega kurzorja do ujemajočega niza v iskalnem vmesniku
- D = dolžina najdaljšega ujemajočega niza
- Z = naslednji znak v bralnem vmesniku, ki ni več del ujemanja
V primeru, da se kateri koli znak prvič pojavi, kar pomeni, da ni bilo ujemanja zapišemo s trojko (0, 0, znak). ([17])
Spodnja slika prikazuje primer, kako algoritem LZ77 poišče najdaljše ujemanje in kodira ponavljajoše se znake za dani niz “azttoaztnazsst”.
To delo je objavljeno pod licenco Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna.
Če na kratko razložim na primer zadnjo trojko, tj. (4, 2, s). 4 predstavlja število pomikov v levo, torej pridemo na temno roza a, 2 predstavlja koliko elementov vzamemo za zakodiranje, torej elementa az, s pa je najslednji znak.
S tem smo uspeli zakodirat niz “azttoaztnazsst”.
Kako deluje Huffmanovo drevo?
Predno razložimo kako deluje naj povem, da bomo uporabljali dimanično Huffmanovo drevo, obstaja pa tudi statično.
Je eden najbolj priljubljenih algoritmov, saj ga je enostavno implementirati in poleg tega tvori tudi optimalne kode. Kaj so optimalne kode? Torej simbolom, ki se največkrat pojavijo dodeli najkrajše kode. ([10])
1. korak, ki ga je potrebno narediti, je narisati tabelo frekvenc, tj. kolikokrat se pojavi simbol v vhodnih podatkih. Naredimo primer na vhodnem nizu “azttoaztnazsst”.
| a | n | o | s | t | z |
| 3 | 1 | 1 | 2 | 4 | 3 |
Torej vidimo, da se simbol a pojavi 3-krat, n 1-krat, o 1-krat, s 2-krat, t 4-krat in z 3-krat.
Potrebno je tabelo tudi urediti po padajočem vrstem redu (kanonični Huffman):
| t | a | z | s | n | o |
| 4 | 3 | 3 | 2 | 1 | 1 |
Sedaj pa napoči konstrukcija Huffmanovega drevesa. Posebnost konstrukcije je ta, da se drevo konstruira od spodaj navzgor in ne obratno kot večina stvari!
Postopek: na vsakem koraku izberemo 2 vozlišči, ki imata najnižji frekvenci ponavljanja. Ker pa smo si delo olajšali in tabelo uredili po padajočih frekvencah vedno vzamemo zadnje dva niza/podatka. Nato pa te dva niza družimo tako, da gre nižja frekvenca na desno stran, višja pa na levo (v primeru, da najmanjši frekvenci nista enaki). V korenu pa zlepimo niza skupaj in novemu dodamo frekvenco, ki je vsota obeh najnižjih. Ta koren umestimo ustrezno glede na padajoče frekvence v vrsto. Ta postopek ponavljamo dokler drevo ni konstuirano tako, da ima samo celoten koren, ostali nizi pa so del drevesa. ([10])
Za lažje razumevanje svetujem ogled konstrukcije, ki je spodaj narejena točno za ta primer.
Torej če izpišemo kakšne kode Huffmanovo drevo priredi simbolom:
t – 01, a – 10, z – 11, s – 001, n – 0000, s – 0001
S tem je postopek kodiranja s Huffmanovim drevesom končan.
Torej če bi želeli neke podatke kodirati z algoritmom DEFLATE, bi najprej podatke zakodirali z algoritmom LZ77 po postopku, ki je predstavljen zgoraj in zakodirane podatke prenesli še v Huffmanovo drevo in na koncu zapisali končno verzijo zakodiranih podatkov.
Postopek dekodiranja pa je ravno obraten postopku kodiranje, torej najprej dekodiramo podatke s pomočjo Huffmanovega drevesa, nato pa odkodirane podatke odkodiramo še z algoritmom LZ77.
PREVERITE SE
Predno pa zaključite s formatom PDF se preverite, ali ste res razumeli kako se generira Huffmanovo drevo. Imamo niz: “PROCESOR PROCESIRA”. Če ste že pozabili, kako deluje si ga že enkrat na hitro preberite zgoraj in potem sami, glede na tabelo frekvenc in opisanega postopka, poskusite zgenerirati spodnje drevo. Pozor! Tudi presledek, ki je označen z _ se šteje kot znak in pa dobro poglejte kako so zapisani sestavljeni nizi. SREČNO!!
VIRI
Format GIF
[1] All About GIF89a. (1997). Prodobljeno s http://www6.uniovi.es/gifanim/gifabout.htm
[2] GIF. (b.d.). Pridobljeno s https://www.ntchosting.com/encyclopedia/multimedia/gif-graphics-interchange-format/
[3] GIF. (b.d.). Pridobljeno s https://en.wikipedia.org/wiki/GIF
[4] GIF. (2016). Pridobljeno s https://techterms.com/definition/gif
[5] GIF Compression. (2001). Pridobljeno s https://docstore.mik.ua/orelly/web2/wdesign/ch19_03.htm
[6] GIF (Graphics Interchange Format). (2006). Pridobljeno s https://searchwindevelopment.techtarget.com/definition/GIF
[7] What is a GIF file? (b.d.). Pridobljeno s https://docs.fileformat.com/image/gif/
[8] What is LZW and what are the issues surrounding it? (2018). Pridobljeno s https://kb.iu.edu/d/aghf
Format PDF
[9] Compression in PDF files. (b.d.). Pridobljeno s https://www.prepressure.com/pdf/basics/compression
[10] Herlah, J. (2009). Praktična uporaba algoritmov stiskanja podatkov (Diplomsko delo). Univerza v Mariboru, Fakulteta za elektrotehniko, računalništvo in informatiko, Maribor.
[11] History of PDF. (2020). Pridobljeno s https://en.wikipedia.org/wiki/History_of_the_Portable_Document_Format_(PDF)
[12] Lossless Pdf Compression. (b.d.). Pridobljeno s http://www.cvisiontech.com/reference/pdf-compression/lossless-pdf-compression.html in http://www.cvisiontech.com/resources/jbig2-compression-primer/overview-benefits-pdf-compression-conversion.html
[13] Overview Benefits Pdf Compression Conversion. (b.d.). Pridobljeno s http://www.cvisiontech.com/resources/jbig2-compression-primer/overview-benefits-pdf-compression-conversion.html
[14] PDF File Format. (b.d.). Pridobljeno s https://docs.fileformat.com/pdf/
[15] Portable Document Format (PDF). (2010). Pridobljeno s https://whatis.techtarget.com/definition/Portable-Document-Format-PDF
[16] Sustainability of Digital Formats: Planning for Library of Congress Collections. (2020). Pridobljeno s https://www.loc.gov/preservation/digital/formats/fdd/browse_list.shtml
[17] Understanding ZLIB. (2019). Pridobljeno s https://www.euccas.me/zlib/#deflate