Tiedon puristaminen pienemmäksi

(Funky Tee / Flickr. CC-BY-SA 2.0.)

Mitä on tieto? Kun puhumme, välitämme tietoa. Osa siitä on täysin turhaa — "niinku"-sanojen poistaminen harvemmin vaikuttaa viestin ymmärtämiseen, ja jopa phaat kirojtuvisrhet ovrt yltätävän hulptsti korajttvikasa. Mutta jos kaikki konsonantit poistetaan... iiä ei aa eää ii ao eää. Saako tätä tutkittua matemaattisemmin?

Jos tieteellisen artikkelin vaikuttavuutta mitataan siihen tehtyjen viittausten määrällä, Claude Shannon (1916-2001) on korkealla. Vuonna 1948 hän julkaisi artikkelin A Mathematical Theory of Communication (Viestinnän matemaattinen teoria), joka aloitti koko informaatioteorian alan.

Ydinajatuksena informaatioteoriassa on viestin siirtäminen mahdollisesti häiriöistä väylää pitkin. Kuten viime kerralla nähtiin, häiriöitä voivat olla niin ihmisen tekemät virheet, kohisevat puhelin- ja radiolinjat tai vaikkapa hälyinen ympäristö. Shannonin teoria määritteli rajat sille, kuinka paljon tietoa pystyy luotettavasti siirtämään häiriöisen linjan yli. Luotettavuutta voidaan lisätä sekoittamalla tietoon toistoa pitkien ilmausten tai viimekertaisten tarkistusbittien tapaan, ja tätä kutsutaan entropian vähentämiseksi.

Shannon määritteli entropian viestin satunnaisuutena. Esimerkiksi AAAAAAAAAAAAAAA ei ole kovin satunnainen viesti, joten sen entropia on matala. Puolestaan lyhyemmän viestin ADNTAGUNRL entropia on paljon suurempi.^[1] Jos sinun pitäisi arvata kummankin viestin seuraava kirjain, kummassa osuisit todennäköisemmin oikeaan?

Tästä päästään myös sujuvasti tiedon pakkaamiseen. Helpoin tapa välittää ensimmäinen viesti toiselle olisi sanoa "viisitoista isoa aata", kirjoitettuna vaikkapa 15A. Tätä kutsutaan jaksonpituuskoodaukseksi (run-length encoding, RLE), ja kuten huomata saattaa, se on kohtalaisen tehokas tietyille viesteille.^[2] Jälkimmäinen viesti ei pakkaudu pienemmäksi jaksonpituuskoodauksella eikä millään muullakaan menetelmällä. Pakkaus hyödyntää tiedossa olevaa toistoa ja kuvioita, joita satunnaisessa tekstissä ei ole.

Myös luonnollisessa kielessä on paljon ylimääräistä informaatiota. Shannon tutki pari vuotta myöhemmin englannin kieltä näyttämällä koehenkilöille lauseita, joissa osa kirjaimista puuttui.

RY--Ä KAL--UNOI-A PELA-- P--IÄ -A H-VIS-

Hän päätyi tulokseen, että yksi kirjain sisältää noin yhden bitin verran informaatiota. Tämä tarkoittaa, että tekstitiedostona olevan kirjan voi pakata parhaimmillaan osapuilleen kymmeneen prosenttiin alkuperäisestä koostaan. Randall Munroen What If? -blogi vastaa tätä soveltaen kysymykseen mahdollisten twiittien määrästä (englanniksi) loistavalla tavalla.

Näin tietoa pakataan

Yleisimmät tiedonpakkausmenetelmät perustuvat juurikin siihen, että aivomme osaavat paikata puutteita. Näihin häviöllisiin menetelmiin kuuluvat valokuvien JPEG ja musiikin MP3, kuten myös erilaiset videoformaatit. Pakatusta tuotteesta on poistettu yksityiskohtia, joihin aivot eivät kiinnitä huomiota tai osaavat arvioida uudelleen.

Kuvatiedostojen pakkaaminen JPEG-menetelmällä menee erittäin yksinkertaistetusti seuraavasti: Ensin kuva jaetaan sävyiksi ja kirkkaudeksi ja väritieto tallennetaan pienempänä kuvana, koska aivot ovat paljon herkempiä kirkkauden kuin sävyjen yksityiskohdille. Sitten kuva jaetaan ruudukoksi. Jokainen ruutu muutetaan sarjaksi lukuja, joiden avulla voidaan osapuilleen toistaa ruudussa esiintyvä muoto. Tämä kuitenkin aiheuttaa häiriöitä suurikontrastisiin ruutuihin, kuten kuvasta näkyy.

(Suurennos rajusti JPEG-pakatusta kuvasta.)

Kun tietoa halutaan pakata ilman menetyksiä, käytetään hieman toisenlaisia menetelmiä — tämä on usein myös viimeinen vaihe edellisissä tavoissa. Otetaan esimerkiksi suomenkielinen teksti.

Osa kirjaimista on reippaasti yleisempiä kuin toiset: A ja I löytyvät käytännössä joka lauseesta, mutta B:tä saa etsimällä etsiä. Kuitenkin tietokone tallentaa kaikki yhtä pitkinä ykkösten ja nollien ketjuina.^[3] Eikö olisi kätevämpää, jos yleisemmät merkit kirjoitettaisiin lyhyempinä lukuina ja harvinaisemmat pidempinä? Tähän ajatukseen perustuu David Huffmanin (1925-1999) kehittämä Huffman-koodaus.

(Huffman-puu muutaman kirjaimen kielelle. Jo lyhyessä tekstissä saavutetaan noin 15 % säästö.)

Asetellaan kirjaimet ylösalaisin olevan puun "lehdiksi". Nollia ja ykkösiä luettaessa aloitetaan huipulta ja edetään vasemmalle tai oikealle numeroiden mukaan, kunnes saavutaan kirjaimeen. Yleisemmät kirjaimet ovat lähempänä huippua, joten niihin päästään lyhyempää polkua pitkin. Vastaavasti harvinaisemmat kirjaimet vaativat pidemmän numerosarjan kuin ennen, mutta niiden harvuuden ansiosta se ei ole ongelma. Menetelmää voi edelleen jatkaa tunnistamaan useamman kirjaimen yhdistelmiä.

Informaatioteorian tekniikat mahdollistavat luotettavat ja nopeat tietokoneet ja -verkot, täysin näkymättömästi tavalliselle käyttäjälle. HD-tasoisen sarjan katsominen Netflixistä vaatisi ilman pakkausta reippaasti yli gigabitin nettiyhteyden — pakkauksen ansiosta sadasosa riittää.

Ensi viikolla: Piipahdamme salakirjoituksen ihmeelliseen maailmaan.

---

^[1] Satunnaista tekstiä ja muuta kivaa saa helposta osoitteesta random.org.
^[2] Kolakoskin sarja on oma jaksonpituuskoodauksensa.
^[3] Ääkkösiä lukuunottamatta juurikin siitä syystä, että ääkköset ovat harvinaisempia kansainvälisellä tasolla. Yleisin tapa tallentaa merkkejä tarvitsee ääkkösiin tuplasti tilaa aakkosiin verrattuna.