Toistettu pakkaaminen.

Tämä juttu käsittelee taas häviötöntä pakkaamista. Tässä on tärkeää muistaa se, miten pakkaaminen keskittyy vaihtamiseen, kaikkea ei voida tietenkään vaihtaa toiseksi : Pakatun kun täytyy voida palauttaa takaisin lähtötilaansa purkamalla se. Eli pitää saada purkamalla juuri sama tulos kuin ennen pakkaamista on ollut. Kun lyhyt ohjelma sisältää vähemmän bittejä, se voi kattaa vain pienen osan. Jos meillä on vain 1 "normaalin numerojärjestelmän lukua" voimme ilmaista niillä 10 (0....9) vaihtoehtoa. Mutta kahdella voimme ilmaista sata erilaista vaihtoehtoa (00...99). On suorastaan ilmiselvää että kaikkea ei voida pakata. Häviöttömässä pakkauksessa tietysti voidaan toimia likiarvoilla, jolloin kaikki numerot 80...89 saavat arvon 8, mutta tässä purkaessa tuhoutuu tietoa: Jos meillä on se kasi, emme voi tietää onko se ollut 81, 84 tai jokin muu tässä välissä. Tällöin pakkaaminen ja purkaminen tuhoaisi informaatiota, eli se ei olisi häviötöntä.

Kuitenkin meillä on erilaisia pakkausohjelmia. Esimerkiksi ZIPpaaminen toimii meilläkin ihan mukavasti. Hyvä pakkausohjelma toimiikin siksi siten, että se yrittää etsiä redundanssia, toistuvuutta. On hyvä muistaa miten tämä liittyy "rakenteeseen": Merkkijonolla 111111111111111 on vähän rakennetta ja paljon redundanssia: Se voidaan tiivistää vaikka sanomalla että "15X1". Yksi tapa tehostaa pakkaamista on tietenkin se, että jos lopputulos onkin pidempi kuin ennen pakkaamista, ei kannata pakkata sitä. Eli esimerkiksi jos meillä on yllä oleva tilanne ja meillä pitääkin käsitellä teksti "15X1" emme voisi laittaa sitä sellaisenaan, koska ohjelma purkaisi sen väärin, jos kyse olisi yksinkertaisesta "päikseen vaihdosta" pakkaus merkitsisi että "111111111111111". (Kaikkeen toimivalla hyvällä häviöttömällä pakkauksen nyrkkisääntö on : Kaikki syötteet pitää voida käsitellä algoritmilla, eikä samaa lopputulosta saa tulla kahdesta eri syötteestä.) Tällöin tulos olisi pidempi kuin alkuperäinen. Pakkausohjelmaan voidaan tietysti laittaa vaikka apumerkki, eli se laittaa ensin merkin siitä onko käytetty algoritmia vai ei. Tällöin merkkijoni "111111111111111" tiivistyy vaikka muotoon "015X1" ja "15X1" olisi muotoa "115X1". Tällä tavalla voidaan ajatella että pakkaamiseen tulee monimuotoisuutta.

Moni ajattelee että pakkaamisohjelman uudelleenpyörittämisellä voidaan pakata jo pakattuja merkkijonoja ja saada tätä kautta vielä tuotakin lyhyempi pätkä. Näin ei ole.

Kun pakkaus palautuu siihen että se tunnistaa toisteisuutta pakattavasta aineistosta, määrää "rakenteen" määrä minimikoon. Redundanssia on rajallinen määrä. Kun on poistettu kaikki laskettavissa oleva redundanss, on saatu maksimitasoisesti pakattu tulos. Tässä on tietysti otettava huomioon se, että joskus toiseen kertaan pakkaaminen tosiaan pienentää aineistoa lisää ja kahden purkamisen jälkeen saadaan alkuperäinen aines palautettua. Tämä johtuu siitä että pakkaussysteemit eivät ole täydellisiä. Ne eivät tunnista ensimmäisellä kierroksella kaikkea redundanssia aineistosta. Parhaat pakkausohjelmat tunnistavat redundanssin hyvin ja silloin ne identifioivat ja käyttävät hyväkseen kaikkea aineistossa olevaa redundanssia.

Toistetusta pakkaamsiesta on siis hyötyä jos ja vain jos ensimmäinen pakkaaminen ei eliminoinutkaan kaikkea redundanssia. Eli jos pakkausohjelma säännönmukaisesti pienentää aineistoa, se johtuu siitä että sen suorittama pakkaaminen on alun perinkin puutteellista. Eli huonoissa pakkausohjelmissa toisto voi pienentää tulosta.

Esimerkiksi Huffmanin koodauksessa etsitään yleisin kirjainyhdistelmä ja korvataan niitä harvinaisimmilla lyhyemmillä. Näin ne joita aineistossa on vähän saavat pitkän koodauksen ja muut lyhyemmän. Voidaan kuvitella että Huffmanin koodaus tuottaa hahmopareja ensimmäisellä kerralla ja tätä kautta sitä voidaan jonkin verran pakata toisellakin kierroksella. Kuitenkin kun tässä pelataan todennäköisyyksillä, edustaa tämä tilanne vain pientä osaa "kaikista mahdollisista tilanteista". Eli vaikka pakkaamista voidaan tehdä kierros kierroksella, jokaisen kierroksen odotettavissa oleva pakkausteho kutistuu valtavan paljon. Eli aluksi se pakkaa (prosentuaalisesti verrattuna pakattavan merkkijonon pituuteen) paljon ja sen jälkeen aina vain (prosentuaalisesti) vähemmän ja vähemmän.

Tämä tarkoittaa sitä että ennen pitkää vastaan tulee raja, jonka jälkeen odotettavissa ei enää ole kutistumista. Jos käytössä on LZW -pakkaus, on se edellä mainuttua tehokkaampi. Tällöin pakkausta ei kannata yleensä uusia. Tosin tässä on mukana sellainen jännittävä ilmiö, että emme voi useinkaan tietää onko jokin merkkijono maksimaalisesti pakattu vai ei. Pakkaustehoa ei siksi saada millään algoritmilla ihan täydelliseksi. Mikä on eri asia kuin sanoa että ne eivät toimisi erinomaisen hyvin.

Itse asiassa pakattavuus on eräällä tavalla jännittävä ilmiö: Kun muistetaan että korkea algoritminen kompleksisuus on tilastollisesti yleinen merkkijonojen ominaisuus: Jos sattumalta arvotaan merkkijono, se osuu usein algoritmisesti kompleksiselle alueelle ja vain harvoin tulee tuloksia jossa olisi pitkä sarja toistuvaa. Pakattavuuden määrä kertoo eräänlaisesta "poikkeuksellisuudesta".