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 (engl. rate distortion theory) 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 ajatukseen, 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

Pääartikkeli: 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

Pääartikkeli: 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 (Arkistoitu – Internet Archive)

Aiheesta muualla

• How File Compression Works, lyhyt johdatus pakkausmenetelmien toimintaan (englanniksi)
• Pakkausformaattien tiedostopäätteitä (englanniksi)

Pakkausmenetelmien vertailuja

• CompressionRatings.Com (englanniksi)
• Large Text Compression Benchmark sekä Generic Compression Benchmark (englanniksi)