Tiedon pakkaus

Wikipedia
Loikkaa: valikkoon, hakuun

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[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

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 pakkaamista ei yleensä pidetä äänenpakkausmenetelmänä. Puheenpakkausmenetelmiä käytetään etenkin Internet-puheluissa kun puolestaan äänenpakkausmenetelmiä käytetään esimerkiksi arkistoitaessa CD-levyn sisältö häviöttömästi kiintolevylle FLAC-muodossa. Useita eri äänenpakkausmenetelmiä on lueteltu alla.

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[muokkaa | muokkaa wikitekstiä]

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 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.

Katso myös[muokkaa | muokkaa wikitekstiä]

Tiedon pakkaaminen[muokkaa | muokkaa wikitekstiä]

Pakkausmenetelmiä[muokkaa | muokkaa wikitekstiä]

Häviöttömät pakkausmenetelmät[muokkaa | muokkaa wikitekstiä]

  • Juoksupituuskoodaus (RLE) – käytössä mm. PCX-kuvissa
  • Sanakirjamenetelmät
    • Deflate – (yhdistelmä Huffmanin koodausta ja LZ77:tä) – Käytössä ZIP:ssä, PNG-kuvissa
    • LZW – käytössä Unixin vanhassa compress-työkalussa (tiedostopääte .Z ) sekä GIF-kuvissa
    • LZO – Pakkausmenetelmä, joka on nopea ja tarvitsee hyvin vähän muistia
  • 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

Häviölliset pakkausmenetelmät[muokkaa | muokkaa wikitekstiä]

  • 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ä

Lähteet[muokkaa | muokkaa wikitekstiä]

Aiheesta muualla[muokkaa | muokkaa wikitekstiä]

Pakkausmenetelmien vertailuja[muokkaa | muokkaa wikitekstiä]