Tiedonpakkaus

Tiedon pakkaamisella tarkoitetaan tietojenkäsittelytieteessä jotakin menetelmää, jonka avulla tietoaineksen kuvaus korvataan lyhyemmällä kuvauksella. Kuvaus voi olla häviöllinen tai häviötön riippuen siitä, muuttuuko tietoaineksen sisältö käsittelyn yhteydessä vai ei.
Tietoaineksen tiivistäminen on mahdollista, koska lähes kaikki tallennettava informaatio on tilastollisesti redundanttia eli se sisältää vähemmän todellista informaatiota kuin sen kuvaamiseen on käytetty. Useimmissa merkistöissä, kuten ASCIIssa, jokainen kirjain kuvataan samalla bittimäärällä. Toisaalta kirjainten esiintymistiheydet eroavat suurestikin, esimerkiksi suomen kielessä kirjain 'k' on huomattavasti yleisempi kuin kirjain 'g'. Voidaan myös huomata, että on todennäköisempää, että vokaalia seuraa konsonantti kuin toinen vokaali. Kun nämä havainnot tehdään tilastollisin menetelmin tiivistettäväksi tarkoitetusta datasta, saadaan täsmällistä tietoa, jota varsinainen pakkausalgoritmi hyödyntää.
Tiedon tiivistäminen on tärkeää, koska se vähentää kalliin tallennus- ja tiedonsiirtokapasiteetin käyttöä. Kuitenkin tiedon tiivistys vaatii laskentatehoa. Tehokkaat laitteet voivat olla kalliita. Siksi pakkausmenetelmien soveltaminen käytäntöön vaatii monien asioiden huomioimista, etenkin jos kyseessä on häviöllinen menetelmä.

Häviötön ja häviöllinen pakkaus

Häviötön pakkausmenetelmä tarkoittaa, että tietoaines ei muutu lopullisesti vaan se kuvataan toisella tavalla pakkaamisen yhteydessä. Kun pakkaus puretaan, saadaan alkuperäinen tietoaines. Häviötön pakkaus tuottaa alkuperäistä pienemmän tietoaineksen silloin, kun pakattava data sisältää riittävästi redundanssia. Merkkejä suuresta redundanssista ovat esimerkiksi toistuvat merkkijonot tai ennustettavuus. Yksinkertaisin tilastollinen pakkaus, Huffmanin koodaus, perustuu siihen että useammin esiintyviä symboleja merkitään lyhyemmällä symbolilla.
Häviöllisessä pakkausmenetelmässä sen sijaan tiedon muuttuminen sallitaan, pyrkien kuitenkin mahdollisimman pieneen muutokseen ihmisen saaman kokemuksen kannalta. Esimerkiksi television katselija ei todennäköisesti havaitse, jos taustalta poistetaan joitakin yksityiskohtia tilanteessa, jossa hänen katseensa kohdistuu etualalla keskusteleviin henkilöihin. Myöskään ihmisen kuulo ei ole täydellinen; monet erilaiset ääninäytteet voivat kuulostaa samalta, vaikka ovatkin hyvin erilaisia tietokoneanalyysin mukaan. Kun löydetään sellaiset korvaavat palaset, jotka voidaan kuvata vähemmällä tietomäärällä kuin toiset, ja ne kuitenkin havainnoitsijasta tuntuvat samalta kuin alkuperäiset, voidaan saavuttaa pienempiä tiedostokokoja.
Periaatteessa häviöllinen pakkaus heikentää aina tallenteen laatua verrattuna alkuperäiseen. Pakattaessa siten, että laatuero ei suurinta osaa ihmisistä vielä häiritse, häviölliset menetelmät kuitenkin kykenevät yleisesti huomattavasti parempiin pakkaussuhteisiin kuin häviöttömät menetelmät.
Usein ihmiset kokevat häviöllisen pakkauksen miellyttävämmäksi vaihtoehdoksi kuin suuremman levytilan tai kaistanleveyden käytön. Tietyissä tapauksissa, kuten GSM-puhelimessa, äänen pakkaus mahdollistaa pienempien tiedonsiirtomäärien ansiosta matalamman lähetystehon ja useampien puhelimien yhtäaikaisen käytön samalla taajuuskaistalla.
Häviöllistä pakkausmenetelmää ja sen asetuksia valittaessa on otettava huomioon ainakin suorituskyvyn tarve, tiivistyneen tiedon määrä ja häviöllisyyden tuntuma.

Sovelluksia

Häviöllisessä äänenpakkauksessa käytetään hyväksi psykoakustiikkaa, jonka avulla pystytään äänestä poistamaan osia, jotka ovat vaikeasti tai eivät lainkaan kuultavissa. Ihmisäänen pakkaamiseen sovelletaan vielä tästäkin erikoistuneempia menetelmiä ja siksi puheen pakkaamiseen käytetään erikoistuneita menetelmiä. Puheenpakkausmenetelmiä käytetään etenkin matkapuhelinverkoissa ja Internet-puheluissa kun puolestaan musiikin pakkaamiseen erikoistuneita äänenpakkausmenetelmiä käytetään esimerkiksi arkistoitaessa CD-levyn sisältö häviöttömästi kiintolevylle.
Valokuvia tallennettaessa yleinen häviöllinen pakkausmenetelmä on JPEG (.jpg).
DVD-levyissä käytetään häviöllistä MPEG-2-pakkausmenetelmää videon ja äänen pakkaamiseen.
Häviöllistä pakkausta ei voida soveltaa symbolisen tiedon, eli esimerkiksi tekstin, taulukoiden tai ohjelmakoodin tapauksessa, koska se ei joitakin poikkeustapauksia lukuun ottamatta kestä yhdenkään bitin muuttamista. Häviöllistä pakkausta ei kannata myöskään käyttää esimerkiksi lääketieteellisten tai muiden ehdotonta tarkkuutta vaativien kuvien tallentamiseen, sillä se voi tuoda kuvaan ikäviä artefakteja eli pakkaushäviöstä johtuvia virheitä. Diagrammi- ja muissa vastaavissa kuvissa häviöllinen pakkaus ei välttämättä edes anna parempaa pakkaustulosta. Yleinen häviötön kuvamuoto on PNG (.png), ja myös GIF on häviötön, mutta sen väriavaruus rajoittuu 256 väriin.

Teoria

Informaatioteoria, algoritmiikka ja hävikkiteoria (rate distortion theory) muodostavat tiedontiivistämisen teoreettisen pohjan. Tälle pohjan loi Claude Shannon julkaistessaan alan ensimmäiset teokset 1940- ja 1950-lukujen taitteessa. Doyle ja Carlson vuonna 2000 kirjoittivat tiedonpakkauksesta yhtenä yksinkertaisimmista ja hienostuneimmista tieteenaloista. Kryptografia ja Koodausteoria liittyvät myös läheisesti pakkausmenetelmiin. Tiedon tiivistämisen ajatus liittyy myös tilastolliseen päättelyyn ja Suurimman uskottavuuden estimointiin (MLE).
Monet häviöttömät pakkausmenetelmät voidaan kuvata nelivaiheisena mallina. Häviöllisissä menetelmissä on useimmiten vielä useampia vaiheita, kuten ennustaminen, taajuusmuunnos ja kvantisointi.
Eräs yksinkertaisimmista pakkausmenetelmistä on juoksupituuskoodaus (RLE). Se perustuu ajatuksen, että usein tiedostoissa esiintyy samaa arvoa peräkkäisissä kohdissa. Etenkin piirrostyylisissä kuvissa esiintyy usein samaa väriarvoa rivin peräkkäisissä kuvapisteissä. Tällöin yksi samanvärinen juova, jossa muuten kuvattaisiin jokaisen pisteen väri erikseen, korvataan tiedolla käytetystä väristä ja juovan pituudesta. Tämä on malliesimerkki kuvien häviöttömästä pakkauksesta. Häviöttömyys on tärkeää täsmällisen tiedon, kuten tekstin, tietokoneohjelmien ja mittaustuloksien säilyttämisessä, koska pienikin sisällön muutos voi aiheuttaa virheellistä tulkintaa.
Lempel-Ziv (LZ) -pakkausmenetelmä on suosituin häviötön pakkausmenetelmä. Deflate-algoritmi on LZ:n muunnos, joka on optimoitu nopeaa pakkauksen purkamista ja parempaa tiivistyssuhdetta silmällä pitäen. Tosin pakkausajat voivat olla Deflatella LZ-menetelmää pitemmät. Deflatea käytetään esimerkiksi PKZIP:ssä, PNG-kuvaformaatissa. Lempel-Ziv-Welch-menetelmä (LZW) on ollut Unisysin patentoima useissa länsimaissa kesäkuuhun 2003 saakka ja sitä on käytetty GIF-kuvien pakkaamisessa. Unisysin patentti ei ollut koskaan voimassa Suomessa. Mainitsemisen arvoinen on myös LZR-menetelmä (LZ-Renau), joka on Zip-menetelmän taustalla. Lempel-Ziv-menetelmät taulukoivat usein toistuvaa dataa, joka useimmissa menetelmissä kerätään aiemmasta datasta. Taulukko itsessään on usein Huffman-koodattu (esimerkiksi SHRI ja LZX). LZX on saanut alkunsa Amiga-tietokoneelle tehdyssä pakkausohjelmassa ja on käytössä ainakin Microsoftin Cabinet-pakkausmuodossa.
Kuten muunkin viestinnän yhteydessä, tiedon välittäminen pakattuna vaatii tuen sekä lähettäjältä että vastaanottajalta. Kirjoitetunkin tekstin osalta pitää ymmärtää tekstissä käytetty kieli, jotta tekstiä voisi lukea. Sama pätee myös tiedonpakkaukseen, eli molempien osapuolien pitää hallita käytetty pakkausmenetelmä. Vastaanottajan pitää myös tietää, millä pakkausmenetelmällä tieto on tiivistetty niiden kaikkien menetelmien joukosta, jotka on vastaanottajan hallussa. Tämän selvittämiseen tiedostonnimien perässä on usein maininta käytetystä pakkaus- tai arkistointimenetelmästä, esimerkiksi .zip.