Tiedonpakkaus

Wikipedia

Tietojenkäsittelytieteessä tiedon pakkaamisella tai tiivistämisellä tarkoitetaan jotakin menetelmää, jonka avulla tietoaineksen kuvaus korvataan lyhyemmällä kuvauksella. Esimerkiksi suomen kielen lause "Ulla leipoi pullan" voidaan kuvata tiiviimmässä muodossa "G leipoi pGn", jos sovitaan, että merkkijono ulla korvataan merkillä G, joka ei ennalta esiinny tekstissä.

Tietoaineksen tiivistäminen on mahdollista, koska lähes kaikki tallennettava informaatio on tilastollisesti redudanttia 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ä.

Sisällysluettelo

1 Häviötön ja häviöllinen pakkaus
2 Sovellukset
3 Teoria
4 Katso myös
- 4.1 Tiedon pakkaaminen
- 4.2 Pakkausmenetelmiä
  - 4.2.1 Häviöttömät pakkausmenetelmät
  - 4.2.2 Häviölliset pakkausmenetelmät
5 Lähteet
6 Aiheesta muualla

[muokkaa] Häviötön ja häviöllinen pakkaus

Häviötön pakkausmenetelmä tarkoittaa, että todellista tietoainesta ei häviä vaan se kuvataan toisella tavalla. Kun pakkaus puretaan, saadaan alkuperäinen tietoaines. Häviöllisessä pakkausmenetelmässä sen sijaan tietoa tarkoituksellisesti hävitetään pyrkien mahdollisimman pieneen muutokseen ihmisen saaman kokemuksen kannalta. Esimerkiksi television katselija ei todennäköisesti havaitse, jos taustalta poistetaan joitakin yksityiskohtia samalla kun hänen katseensa kohdistuu etualalla keskusteleviin pää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 alkuperäisen tallenteen laatua. Pakattaessa siten, että suurin osa ihmisistä ei vielä eroa havaitse, häviölliset menetelmät kuitenkin kykenevät yleisesti huomattavasti parempiin pakkaussuhteisiin kuin häviöttömät menetelmät. Häviöllistä pakkausta ei kuitenkaan voida soveltaa symbolisen tiedon, eli esimerkiksi tekstin, taulukoiden tai ohjelmakoodin tapauksessa, koska se ei joitakin poikkeustapauksia lukuun ottamatta kestä yhdenkään bitin muuttamista.

[muokkaa] Sovellukset

Eräs yksinkertaisimmista pakkausmenetelmistä on juovakoodaus (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.

Ihmisen havaintoon perustuvan tiedon, kuten kuvan ja äänen, säilyttämisessä ja välittämisessä voidaan sallia tietosisällön karsintaa, kunhan muutokset eivät häiritse ymmärtämistä tai niitä ei koeta epämiellyttäviksi. 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 matalammat lähetystehot 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.

Häviöllisiä kuvanpakkausformaatteja käytetään mm. digitaalikameroissa, joissa se mahdollistaa huomattavasti pienempikokoiset kuvatiedostot hyvin vähäisellä laadun putoamisella. DVD-levyissä käytetään häviöllistä MPEG-2-pakkausmenetelmää videon ja äänen pakkaamiseen.

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ö kiintolevylle Ogg Vorbis-muodossa. Useita eri äänenpakkausmenetelmiä on lueteltu alla.

[muokkaa] 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.

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ä, gzipissä ja PNG-kuvaformaatissa. Lempel-Ziv-Welch-menetelmä (LZW) on ollut [Unisys]in 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.

Eräs tietokoneenkäyttäjille tuttu pakkausmenetelmä on ZIP. Se toteuttaa pakkaamisen lisäksi myös useiden tiedostojen arkistoinnin yhteen tiedostoon.

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

[muokkaa] Katso myös

[muokkaa] Tiedon pakkaaminen

[muokkaa] Pakkausmenetelmiä

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

Juovakoodaus (RLE) – käytössä mm. PCX-kuvissa
Sanakirjamenetelmät
- Deflate – yhdistelmä Huffmanin koodausta ja LZ77:tä) – Käytössä ZIP:ssä, gzipissä and 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

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