Bittejä pakettiin

[2. Hukkaamaton pakkaus]

• 2.1 Mitä se on
• 2.2 Miten se tehdään
• 2.3 Yleisimpiä menetelmiä
  • 2.3.1 RLE
  • 2.3.2 Sanasto
  • 2.3.3 LZ*
  • 2.3.4 Huffman

• 3.1 Still-kuva
• 3.2 Video
• 3.3 Tärkeimmät kuvanpakkaus menetelmät
  • 3.3.1 JFIF (JPEG)
  • 3.3.2 MPEG

• Miten?
  • Häviötön
  • Häviöllinen
• Yleisimpiä standardeja
  • MPEG - 1,2,3
  • ATRAC - MiniDisc
  • GSM

Hukkaamattomasa pakkauksessa dataa purettaessa on lopputulos täsmälleen sama kuin alkuperäinen eli tieto muutetaaan väliaikaisesti mutta palautetaan alkuperäiseen muotoonsa hävittämättä siitä mitään. Hukkaavissa menetelmissä voidaan ihmisen rajalliseen havainnointi kykyyn ja suhteelliseen tarkkuuteen perustuen muuttaa dataa ilman että lopputulos olisi välttämättä käsittämättömässä muodossa. Kun käsitellään esimerkiksi tekstiä ei yleensä ole varaa muuttaa sen sisältöä muuttamatta kokonaisuuden ymmärrettävyyttä tai esimerkiksi ohjelma koodin tapauksessa ohjelman toimivuutta. Eli kun käsitellään tekstiä tai jotain muuta muutoksille herkkää dataa on syytä käyttää hukkaamattoimia pakkausmentelmiä.

Toteutukseen käytetään muutamaa yleistä algoritmiä, eli tarkkaa ongelman ratkaisu menetelmää, ja niiden sovellutusta joilla erillaiset pakkausohjelmat tiivistävät käyttäjän haluaman tiedon. Kaikkein yksinkertaisimmilla algoritmeilla pakkaus prosentti riippuu suuresti käsiteltävästä tiedostosta ja yleensä päädytään suhteellisen heikkoon tulokseen. Monimutkaisemmilla menetelmillä päästään tasaisempiin ja parempiin tuloksiin.

Tässä algoritmissa yksinkertaisesti samat peräkkäin esiintyvät merkit ilmoitetaan jollain koodilla josta ilmenee että dataa on pakattu, mitä merkkiä on pakattu ja kuinka monta merkkiä alunperin oli peräkkäin.Esimerkiksi seuraavanlainen jono 'aaaaaaaa' voidaan muuttaa muotoon '$a8' jossa $ ilmoittaa että dataa on tiivistetty. Sitä seuraava merkki (a) kertoo mitä merkkiä on esiintynyt useasti peräkkäin ja luku kahdeksan ilmoittaa montako merkkiä on peräkkäin aluperin ollut. Tai jos on kyseessä binäärinen data eli nollista ja ykkösistä muodostuva kokonaisuus voidaan esimerkiksi jono '0000011110000000' korvata '5a4b7a' jossa numero ilmoittaa merkkien määrän ja a kirjain vastaa nollaa ja b kirjain ykköstä.

Jos käsitellään tekstiä voidaan usein esiintyvät sanat korvata tietyllä koodilla jolla viitataan johonkin valmiiksi laadittuun sanastoon josta saadaan purettaessa koodia vastaava sana. Alla olevassa esimerkissä luku '£'-merkin jälkeen ilmaisee millä rivillä kyseinen sana on sanastossa.

Lyhenne LZ tulee sukunimistä Lempel ja Ziv. Yleisesti käyettyssä LZW:ssä viimeinen W tulee Welch:stä. Herrat kehittivät mentelmän jossa käytetään datassa toistuvia elementtejä hyväkseen. Usein toistutvat sarjat korvataan lyhyemmillä koodeilla eli muodostetaan tavallaan oma kirjasto jota päivitetään jatkuvasti. LZ77 käytetään mm. V.42bis standardoiduissa modeemeissa jotta ne voisivat lähettää nopeammin enemmän dataa niiden käytössä olevalla kapealla taajuusalueellaan.

Huffmannin tekniikka perustuu tilastollisiin todennäköisyyksiin joilla tietyt merkit esiintyvät kyseisessä datassa. Näiden todennäköisyyksien perusteella muodostetaan kompressoitu versio joka on aina parasmahdollinen tulos minkä tällä tekniikkalla voi saada aikaan. Kuten LZ:sta on rönsyillyt monta erillaista muotoa on Huffmanista mm. kehitetty ns. Shannon-Fano koodi. Seuraavassa esimerkkissä verrataan Huffmanin algoritmiä seitsämän bittiseen ASCII-koodiin ja koodiin jossa on määrätty tietyt kolme bittiset yhdistelmät vastaamaan kirjaimia a,b,c,d,e ja f. Esimerkissä on käsitelty 100 000:tta merkkiä.

GIF on lyhenne Graphic Interchange Formatista ja tarkoittaa erästä yleistä kuvien tallenusmuotoa. GIF käyttää hyväkseen edellä mainittua LZW-algoritmia ja on näin ollen periaatteessa häviötön. Jos kuvassa,joka pakataan, on enemmän kuin 256 väriä tai GIF:lle määrittelemättömiä värejä hukkaa se nämä värit mutta korvaa ne jollain muulla värillä joten GIF on käytännössä mahdollisesti ensimmäisellä talletus kerralla hukkaava menetelmä, mutta seuraavilla kerroilla samaa kuvaa käsiteltäessä se ei sitä tee. GIF käyttää värien koodaamiseen 8-bittiä ja sillä voidaan päästä noin 50% pakkaus suhteeseen.

PNG eli Portable Network Graphics on myös hukkaamaton kuvien talletusmuoto kuten GIF ja on itseasiassa siitä jatkojalostettu versio. PNG käyttää värien koodaamiseen 24-bittiä joten sillä päästään suurempaan värimäärään kuin GIF:llä ja lisäksi parempaan pakkaus suhteeseen.

JPEG yhdistetään usein hukkaavaan kuvantalletusmuotoon mutta nyt on myös siitä kehitelty hukkaamaton versio joka löytyy osoitteesta http://cs.cornell.edu/Info/Projects/zeno/LosslessJPEG/

TIFF eli Tag Image File Format on erittäin monipuolinen kuvaformaatti joka itse ei pakkaa mutta käsittelee hukkaamattomasti eri talletusmuotoja. Konversio GIF-TIFF ei hukkaa tietoa mutta pitää olla varovainen päinvastaisen käännöksen kanssa sillä se hukkaa.

PKZIP on eräs suosituimmista MS-DOS pohjaisista pakkaaja ohjelmista. Se käyttää useita kirjasto pohjaisia algoritmeja ja mm. LZ77:n eri variaatioita.

Winzip kuten useat muut xxxZIP ohjelmat preustuu LZW ja Huffman koodaukseen ja ne pystyvät tulkitsemaan useita eri talletusmuotoja.

Compress ja gzip ovat normaalit UNIX-ympäristön pakkaajia jotka keskittyvät yhteen tiedostoon kerrallaan.