ALGORITEM STISKANJA PRI PDF

Poizvedi, kako stiskamo PDF datoteke in kakšen algoritem stiskanja je pri tem uporabljen.

Datoteke PDF lahko hitro postanejo zelo velike, sploh, če vsebujejo visoko kvalitetne slike, videoposnetke, imajo veliko število strani, … Zato je algoritem stiskanja pri teh datotekah zelo pomemben (Compression in PDF files, b.d.).

Format PDF podpira več algoritmov stiskanja. Ti algoritmi so lahko izgubni (pri stiskanju se del podatkov izgubi) ali pa brez izgubni (pri stiskanju ne izgubimo nič podatkov). Uporaba več algoritmov pomeni, da je mogoče uporabiti algoritem, ki je najbolj primeren za posamezno vrsto vsebine v datoteki. Torej, nekateri algoritmi bodo opravili boljše delo z enobarvnimi slikami, nekateri s črno-belimi, drugi z besedilom, … (Compression in PDF files, b.d.).

Algoritmi, ki jih podpira PDF: 

1. CCITT

Ta algoritem je mogoče uporabiti za črno-bele slike. To je algoritem brez izgub, kar pomeni, da ne bo vplival na kakovost slik. 

2. FLATE/DEFLATE

Algoritem za stiskanje besedila in slik. Več o tem algoritmu najdeš TUKAJ.

3. JBIG2

Ta algoritem je alternativa algoritmu CCITT za enobarvne črno-bele slike. 

4. JPEG

Izgubni algoritem, ki se uporablja za stiskanje barvnih slik in sivin.  

5. JPEG2000

Alternativa algoritmu JPEG. Čeprav je učinkovitejši od algoritma JPEG, se v veliki meri še ne uporablja zaradi prevelike obremenitve CPE in težav z združljivostjo s starejšimi sistemi.

6. LZW

Algoritem za stiskanje besedila in slik, ampak ga vedno bolj zamenjuje FLATE algoritem.

7. RLE

Algoritem za enobarvne slike. Gre za algoritem brez izgub, zato se kakovost slik ne spremeni.

8. ZIP

Algoritem, ki se uporablja za stiskanje barvnih slik in sivin. Je brez izgubni algoritem in predstavlja neko pametnejšo različico LZW algoritma.

(Compression in PDF files, b.d.).

PREVERI SVOJE ZNANJE

LZW

Spodaj je malo podrobneje opisan in predstavljen LZW algoritem, saj se uporablja pri stiskanju tako besedila kot slik, ker je ta algoritem zelo hiter in ker je predhodnik DEFLATE algoritma, kateri je opisan že pri formatu PNG.

LZW je algoritem stiskanja brez izgub, kar pomeni, da pri stiskanju datoteke ne izgubimo nobenih podatkov (kakovost ostane enaka). Najbolje deluje pri stiskanju datotek, ki vsebujejo veliko ponavljajočih se podatkov. To pogosto velja za besedilo in enobarvne slike. Algoritem LZW temelji na slovarju. Pregleda datoteko in išče zaporedja podatkov, ki se pojavijo večkrat. Ta zaporedja se nato shranijo v slovar in v stisnjeno datoteko se namesto ponavljajočih zaporedij dodajo sklici do njih. Ta algoritem pa se ne uporablja samo pri formatu PDF, ampak tudi pri formatih TIFF in GIF (Compression in PDF files, b.d.).

KAKO DELUJE ALGORITEM LZW?

Algoritem nadomesti ponavljajoče nize znakov z eno kodo. Na začetku doda vsak nov niz znakov, ki jih vidi, v tabelo nizov. Stiskanje se zgodi, ko se namesto niza znakov izpiše ena koda (LZW compression, b.d.).

Algoritem LZW se začne s slovarjem 256 znakov (v primeru 8 bitov), ki predstavljajo »standardni« nabor znakov (npr. ASCII, ki zajema črke, številke, ločila, …). Nato začne z branjem zaporedja vhodnih znakov in jih enega za drugim doda trenutnemu nizu. Vsakič, ko nizu doda nov znak, preveri, če ima nastali niz kodo v slovarju. Če jo ima, prebere naslednji znak in ga doda nizu. Če pa je nima, pomeni, da je algoritem našel nov niz, zato izpiše kodo, ki ustreza nizu brez tega novega znaka, doda niz z novim znakom v slovar, kjer dobi kodo (ta koda je za 1 večja od največje kode v tem slovarju) ter ponastavi niz na ta najnovejši znak. Naslednjič, ko bo algoritem naletel na ponovljen niz znakov, bo ta niz kodiran samo z eno številko. Algoritem se izvaja, dokler ne pride do konca zaporedja, zapiše še kodo zadnjega novega niza in prikaže izhodno kodo znakov (Rugelj, b.d.; Setturu, 2016).

Pokažimo ta algoritem še na primeru:

PRIMER:

  • zaporedje vhodnih znakov: wabbawabba
  • uporabljamo začetni slovar: {(a,1), (b, 2), (w, 3)} – znak a je kodiran s številko 1, znak b s številko 2 in w s številko 3

IZHODNA KODA: 3 1 2 2 1 4 6 1

PREVERI SVOJE ZNANJE

Sedaj pa je tvoja naloga, da uporabiš algoritem LZW na spodnjem primeru:

  • zaporedje vhodnih znakov: ababbabcababba
  • začetni slovar: {(a, 1), (b, 2), (c, 3)}

Ko ugotoviš, kakšna je izhodna koda, jo poišči med spodaj podanimi odgovori.

VIRI