Pura ja kokoa

Tätä ei voi juurikaan ymmärtää ilman että osaa hyvin tämän aikaisemman jutun. Sen kanssa toivon että se on lasten leikkiä. Jos ei, sori.

Tässä puhutaan häviöttömästä pakkaamisesta, eli pakkaamisesta jossa ei tuhota tietoa, vaan jossa purettu on täsmälleen sama kuin alkuperäinen viesti. Tämänkaltaisen pakkaamisen ideana on yksinkertaisesti se, että tuhotaan niin paljon redundanssia alkuperäisestä viestistä kuin mahdollista. Tällöin viestin rakenteen ohjeet tiivistyvät ja niistä tulee kompleksisia. Ideana on se, että kun meillä on pakkausalgoritmi C, ja y on pakattu viesti ja x on alkuperäinen viesti, niin y on merkkeinä esitettynä lyhyempi kuin x. Pakkausalgoritmilla C on lisäksi oltava jokin käänteistoiminto, joka muuttaa y:n takaisin x:äksi niin että x on täsmälleen sama kuin mikä se oli ennen pakkaamista C:llä.

Kuitenkin sellaista funktiota, joka tekisi toimen niin että olipa x mikä tahansa y on mikä tahansa. Syynä on se, että pakattavan ja purettavan systeemin on oltava käänteisiä: Jotta pakkaaminen ei tuhoaisi tietoa, olisi oltava keino joka muuttaa tilanteen niin että y:stä saadaan takaisin se alkuperäinen viesti x. Tämä on mahdotonta aivan helppotajuisesta syystä. Jos meillä on suurempi setti, josta kasataan lyhyempiä, ollaan vaikeuksissa koska jos kaikille pitkille voitaisiin tehdä näin, lyhyempiä pätkiä pitäisi olla vähintään sama määrä, mielellään useampia kuin niitä pidempiä pätkiä on. Syynä on se, että ollakseen kunnon takaisinpurkuohjelma, sen olisi tuotettava yhdestä lähtötilasta vain yksi lopputulos. Se alkuperäinen x. Jos meillä on esimerkiksi käytettävissä numeroita, se tarkoittaisi että jokainen 3 mittainen olisi esitettävissä joko 1 tai 2 merkillä. erilaisia 3 merkin mittaisia on 1000kpl. 2 merkin mittaisia on 100 ja 1 mittaisia 10. Yhteensä 2 ja 1 mittaisia on 110. Kun 3 merkillä voidaan kuvata 1000 erilaista juttua ja 110 niistä on 2 tai 3 merkkiä pitkiä, 3 merkin mittaisia on tasan 890 kpl. 110 yksiköllä ei voida kuvata yksiselitteisesti kaikkia näitä vaihtoehtoja, koska sen sisällä on pienempi määrä numeroita ("yksiselitteisyysehto" ei toteutuisi)

Tähän kohtaan minulla on jopa pieni tarina omista harharetkistäni. Ajattelin, että kun π (pii) on siitä jännittävä luku, että se 1) tiedetään hyvin ja voidaan laskea suurilla desimaaleilla 2) on sellainen että sitä ei voi pakata, vaan se sisältää kaikki merkkiyhdistelmät. Tästä perusteelta sitten ajattelin että tätä voitaisiin käyttää pakkaamisessa. Tarvitaan vain jokin, jolla sovitaan että on jokin luku. (kun tieto on bitteinä, se on itse asiassa jo numeerisessa muodossa.) Sitten tarvitaan vain vastaavuus π desimaalien arvon ja viestin arvojen väliltä. (joka löytyy taatusti koska sen desimaaleissa on löydettävissä mikä tahansa numerosarja.) Karkeimmillaan se olisi esimerkiksi sitä, että se katsoisi "monesko numero on ensimmäinen vastaava ja montako lukua otetaan", tätä voidaan tehdä pätkissä tai kokonaan. Ja koska piin desimaalit eivät muutu, niin viestin purkaminen ei ole vaikeaa, jos lukuja on vain laskettu varastotietoon riittävästi. Ongelmana tässä oli tietenkin se, että kaikki merkkivaihtoehdot eivät ole riittävän lähellä π:n alkua. Osassa jo se, mistä aloitetaan onkin siksi pidempi kuin se itse viesti, jota lähetään pakkaamaan. Osan vaihtoehdoista tämä tietysti pakkaa, mutta suurta osaa ei. Tämä hairahdukseni on siis osa suurempaa asiaa. (Pii on toki ihmeellinen numero, mutta se ei silti voi toteuttaa taikaehtoa, joka rinnastuu tilanteeseen jossa vaadittiin että 110 >= 889, jota sen toiminta wörkkisi toivomallani tavalla.) Samaa virhettä voi sitten toteuttaa sitten vaikka erilaisilla pseudorandomnumerogeneraattoreilla. Niilläkin voi jokin syöte tuottaa tietyn lukusarjan, ja osa niistä pitkistä saadaan lyhyellä numeron heitolla ja nämä ovat aina käänteisiä eli pakatusta saadaan aivan sama viesti kuin aluksi. Mutta eksponentiaalinen kasvu, joka olennaisesti liittyy siihen että merkkijonon pituutta kasvatetaan, on tässä kohden julmia ja lahjomaton.

Tietenkin asiaa voi siirtää. Jos esimerkiksi teet monimutkaisen sotilassuunnitelman joka vie vaikka 1000 sivua tekstiä, voit käynnistää sen lähettämällä kenraalille tekstiviestin "H", josta hän tietää että nyt alkaa "H -hetki". (Amerikkalaisille "D-Day". Englantilaisille "T- Time" [T lausutaan "tii" ~ "tea" tee]?) Samoin jos sinulla on valmistunut kirja ja olet lähettänyt sen painoon, ja huomaat kirjoitusvirheen, voit lähettää viestin "sivu 114, rivi 17, huoria->nuoria" ja virheesi osataan korjata, eikä sinun tarvitse kertoa koko kirjan sisältöä koska se on siellä jo valmiina. Voit siis poistaa tietoa, kunhan se on toisessa päässä palautettavan joukossa. Siksi jos ilman alkubriifingiä vain lähettelet "H" -kirjaimia vaikka kaikille sotilashenkilöille, ei siitä mikään Normandian maihinnousu ala. Koska tietoa mitä kaikkea siihen on liitettävä, puuttuu. Sama kirjaesimerkin kohdalla : Kilpaileva kustantaja, jolla ei ole kirjaasi ei voi konstruoida kirjaasi tuon viestin pohjalta, eikä siksi ole väliä lähteekö viesti salattuna vai ei ja onnistuuko hän kaappaamaan tämän viestin vai ei.

Tosin tässäkin on se, että jos yrität poistaa uudestaan tätä samaa tietoa, minkä olet jo poistanut ja joka lisätään purkamisen yhteydessä, ei itse asiassa enää tapahdu mitään. Sehän on jo poistettu.

Toisin sanoen, vaikka miten hankalaksi tekee asian, ollaan samassa tilanteessa. On tietty määrä informaatiota, jota ei voi poistaa ilman että sitä ei enää saa takaisin. Ja "redundanssiton osuus informaatiosta" on vain siirrettävä jotenkin jossakin vaiheessa (joko mukana tai se on valmiina määränpäässä.) Tiedonsiirto ei siis pienene kokonaisuutena tietyn rajan alle. Yleensä musiikin, kuvien ja tekstin pakkaaminen onnistuu koska niissä on paljon redundanssia. Tämä osuus voidaan pienentää. Ja redundanssin idea on se, miksi asiat ylipäätään ovat häviöttömästi pakattavissa. Eikä hyvilläkään pakkausalgoritmeilla voi silti pakata ihan kaikkea. Ne ovat silti monessa yhteydessä käteviä.