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 pakkaaminen 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 pakattavaksi tarkoitetusta datasta, saadaan täsmällistä tietoa, jota varsinainen pakkausalgoritmi hyödyntää.

Tiedon pakkaaminen on tärkeää, koska se vähentää kalliin tallennus- ja tiedonsiirtokapasiteetin käyttöä. Kuitenkin tiedon pakkaaminen 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, pakatun 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ö kiintolevylle.
Yleisiä häviöllisiä menetelmiä ovat MP3 ja Ogg. 

Häviöttömässä äänenpakkauksessa sama äänisignaali voidaan palauttaa äänen laadun kärsimättä. Yleinen häviöttömään pakkaukseen käytetty menetelmä on FLAC.

Kuvanpakkauksessa käytetty yleinen häviöllinen pakkausmenetelmä on JPEG. Yleisiä häviöttömiä menetelmiä ovat PNG ja TIFF. Myös GIF on häviötön, mutta sen väriavaruus rajoittuu 256 väriin.

DVD-levyissä käytetään häviöllistä MPEG-2-pakkausmenetelmää videon ja äänen pakkaamiseen.

Yleisessä tiedoston pakkauksessa ei voida soveltaa häviöllistä pakkausta. Tämä sisältää symbolisen tiedon, eli esimerkiksi tekstin, taulukoiden tai ohjelmakoodin pakkauksen, koska nämä eivät 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.

Teoria 
Informaatioteoria, algoritmiikka ja hävikkiteoria () muodostavat tiedon pakkaamisen 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 pakkaamisen 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 pakkaussuhdetta 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 pakattu niiden kaikkien menetelmien joukosta, jotka on vastaanottajan hallussa. Käytetyn pakkausmenetelmän ja parametrien vuoksi tiedostomuoto sisältää tarvittavan tiedon pakatun purkamiseen: pakkaukseen käytettävät algoritmit voivat käyttää sanastoa tai parametreja, jotka on tunnettava kun tieto puretaan.

Tiedon pakkaamisen tyypit
 kuvanpakkaus
 puheen pakkaaminen
 videonpakkaus
 äänenpakkaus
 tekstuurien pakkaus tietokonegrafiikassa

Pakkausmenetelmiä

Häviöttömät pakkausmenetelmät 

 Juoksupituuskoodaus (RLE) – käytössä mm. PCX-kuvissa
 Sanakirjamenetelmät
 Lempel-Ziv (LZ)
 Deflate – (yhdistelmä Huffmanin koodausta ja LZ77:tä) – Käytössä ZIP:ssä, PNG-kuvissa
 Lempel-Ziv-Welch (LZW) – käytössä Unixin vanhassa compress-työkalussa (tiedostopääte .Z ) sekä GIF-kuvissa
 Lempel-Ziv-Oberhumer (LZO) – Pakkausmenetelmä, joka on nopea ja tarvitsee hyvin vähän muistia
 Lempel-Ziv-Ross-Williams (LZRW)
 Lempel-Ziv-Stac (LZS)
 Lempel-Ziv-Storer-Szymanski (LZSS)
 Lempel-Ziv-Markov chain algorithm (LZMA)
 Statistical Lempel-Ziv
 Lohkopakkausmenetelmät
Burrows-Wheeler-muunnos
 bzip2 – yhdistelmä Burrows-Wheeleriä ja Huffman-koodausta
 Ennustava pakkaus
 Entropiakoodaus
 Huffmanin koodaus – yksinkertainen, käytetään usein pakkauksen viimeisenä vaiheena
 Aritmeettinen koodaus – monimutkaisempi
 Lineaarinen ennustava koodaus
 TTA – käytetään häviöttömässä äänenpakkauksessa
 FLAC – käytetään häviöttömässä äänenpakkauksessa
 Dynamic Markov Compression (DMC)
 Shannonin koodaus

Häviölliset pakkausmenetelmät 

 diskreetti kosinimuunnos (DCT)
 JPEG – kuvanpakkausmuoto, joka käyttää diskreetin kosinimuunnoksen lisäksi kvantisointia ja lopuksi Huffmanin koodausta
 MPEG – äänen ja videon pakkausmuoto, joka on hyvin laajassa käytössä. Soveltaa diskreetin kosinimuunnoksen lisäksi liikkeen ennustusta videonpakkauksen yhteydessä
 MP3 – osana MPEG-1-standardia äänen ja musiikin pakkaamista varten. Käyttää kaistaerottelua ja MDCT:tä, havaintomallinnusta, kvantisointia ja Huffmanin koodausta
 AAC – osana MPEG-2:n ja MPEG-4:n äänenpakkauksen määritystä, käyttää MDCT:tä, havaintomallinnusta, kvantisointia ja Huffmanin koodausta
 Ogg Vorbis – AAC:n kaltainen pakkausmuoto, ei käytä patentoituja menetelmiä
 Wavelet-pakkaus
 JPEG 2000 – waveletteihin, kvantisointiin, ja entropiakoodaukseen perustuva menetelmä
 tekstuurien pakkaukseen (tietokonegrafiikassa) on kehitetty useita häviöllisiä menetelmiä
 3Dc
 ASTC
 ETC
 FXT1
 PVRTC
 S2TC
 S3TC
 Puheen pakkaamiseen tarkoitettuja menetelmiä
 Lyra
 Speex

Lähteet 
 Tilastotieteen ja todennäköisyyslaskennan sanasto

Aiheesta muualla 

 How File Compression Works, lyhyt johdatus pakkausmenetelmien toimintaan 
 Pakkausformaattien tiedostopäätteitä

Pakkausmenetelmien vertailuja 
 CompressionRatings.Com 
 Large Text Compression Benchmark sekä Generic Compression Benchmark 

Koodausmenetelmät
 
Seulonnan keskeiset artikkelit