Vaihdanta.

Olen jo aikaisemmin kirjoitellut häviöttömästä pakkaamisesta. Tämä juttu ei tuo hirveästi uusia tietoja. Mutta ymmärtämistä se voi helpottaa; Tämä tarina on tavallaan analogian, vertauksen kautta tehty juttu, joka tekee siitä ymmärrettävän.

Ongelmana on sana "pakkaaminen". Se kun tuo mieleen suoraan pienentämisen. Mutta entä jos sana vaidetaankin muotoon "vaihtaminen"? No compression - Switch!

Häviöttömässä pakkaamisessahan on kyse vaihdannasta. Karkeasti sanoen luku vaihdetaan toiseen lukuun. Ennen tietokoneaikaa tätä olisi voinut olla vaikeaa selittää, mutta bittejähän tämäkin blogiviesti on. Numeroita. Periaatteessa sitä voisi kertoa vaikkapa tämän blogiartikkelin jollain toisella blogiartikkelilla ja saada vastauksen. Tosin mitään järkeähän tässä ei olisi, mutta voisi.

Pakkausalgoritmi vaihtaa numeroita keskenään ja purkaminen vaihtaa ne takaisin. Siinä on oltava muutamia ehtoja:
1: Kun pakataan, samaa lopputulosta ei tule kahdesta eri lähtökohdasta. Muuten tästä tulee häviöllinen pakkaus: Häviää tietoa juuri sen verran, että ei purkuvaiheessa tiedetä mikä näistä vaihtoehdoista on se alkuperäinen.
2: Jokainen syöte on voitava lähettää sen läpi. Tämä ei tarkoita että kaikkia olisi käsiteltävä: Esimerkiksi pakkausalgoritmi, jossa sotasuunnitelma vaihtuu "H" -kirjaimeksi ja takaisin, ja toisin päin, muuta ei käsitellä. Mutta se pakkaa sen yhden viestin. Muiden kohdalla B=B, C=C. Kaikki merkkijonot voidaan saada pakattua ja purettua, eli merkkijonona vaihdetaan siten että purkamisella saadaan takaisin juuri se, mitä ollaan ensin pakattu. Tämä on tärkeää. Ilman purkamismahdollisuutta ei oikeastaan ole järkevää puhua pakkaamisestakaan. Ilman yksiselitteisyyttä ei voida puhua häviöttömästä pakkaamisesta. (Ja muustahan en tässä höpise.)

Toisin sanoen pakatessa sanotaan että "vaihda tuo numero A tuohon numeroon B". Ongelmana on tietysti se, että jos pakkausalgoritmin on tuotettava kaikki, sen on tuotettava myös se numero B. Sitä ei voi merkitä itsellään, koska muutenhan purku ei osaisi erottaa olisiko se A vai B. Ja kun kaikkia on käsiteltävä, on oltava niin että B:kin saataisiin jotenkin pakattua.

Tässä käy niin, että lyhyempiin vaihtaminen ei onnistunut aina. Kolmella merkillä kun voidaan ilmoittaa monta enemmän kuin 2 merkillä. Tästä seuraa se, että on pakko joskus ottaa sellainen paikka, joka on pidempi kuin se joka vaihdetaan. Kaikkea ei voi pakata. Itse asiassa esimerkiksi jos pakkaus vaihtaa "päikseen" vaihtoehtoja, se että A vaihtuu lyhyemmäksi B:ksi tarkoittaa sitä että jos kyseessä on A:n pakkaus, se pienenee, mutta jos B:n pakkaaminen, se kasvaa A:ksi. Tällöin puolet kasvattavat ja puolet kutistavat. Samoin käy keskimäärin, vaikka ottaisimme A:n, jonka vaihtaisimme lyhyempään B:hen, jonka vaihtaisimme lyhyempään C:hen... kunnes vaihtaisimme Z:tan A:han. Tällöin juuri niin paljon kuin onnistumme tässä A...Y -ketjussa nappaamaan talteen, rymähtää niskaan aina Z:tan kohdalla. Ja kun Z on pakko ottaa huomioon, eikä sitä saa jättää pois, on selvää että näin tapahtuu usein.

Mutta tietysti pystytään parempaan kuin tuo karkea esitys. Pakkaamisesta saadaan pienellä tempulla paljon järkevämpää. Toki se ei muuta vääräksi mitään, mitä esitin.

Esimerkiksi nerokkaassa (ei ehkä kaikista nerokkaimmassa, mutta kuitenkin nerokkaassa) Huffmanin koodauksessa vaihdantaideaa on kehitetty aika pitkälle. Karkeasti sanoen se perustuu siihen, että se käy läpi tekstin. Jos siinä on joitain merkkejä paljon, se ottaa ne talteen "hyviksi vaihdettaviksi" ja antaa niille lyhyemmän symbolin, johon tämä toiste vaihdetaan. Eli kun analyysi aloitetaan, jokainen merkki ja yhdistelmä on samanarvoinen, mutta sen arvo muuttuu esiintymistiheyden mukana. Kaksi harvinaisinta yhdistetään puuksi ja yhdistetään kunnes näistä muodostetaan puu. Eli jos aineistossa on toistetta, tästä merkistä tulee "painava". Tässä sen polusta puuhun tulee lyhyt verrattuna muihin. tämä taas tarkoittaa sitä että sen bittiesityksestä tulee lyhyempi. Kun tieto tästä ympätään aineistoon, se pakkaa aineiston jos siinä on toistuvia jaksoja - eli jos sillä on vähän rakennetta. Tämä tarkoittaa tietysti sitä että harvinaisista sarjoista tulee "kevyitä" ja niiden bittiesitykset kasvavat. Mutta kun "kutistumisia" on enemmän kuin "levenemisiä", pakkaus onnistuu yleensä.

Tämä tarkoittaa sitä että pakkausalgoritmit harjoittavat eri tavalla fiksuja vaihtoja. On vain päätettävä mitkä ovat sellaisia joista me pidämme ja joista emme. Jos ne joita haluamme pakata, ovat rakenteeltaan tietynlaisia, voimme käyttää tätä hyväksemme. Ne muunlaiset tietysti kasvaisivat ikään kuin "kostoksi"; Joudumme antamaan niille isomman numeron, mutta käytännössä tämä ei haittaa koska niitä ei olla pakkaamassa.

---

Vaihtaminen on toisaalta hyvä, koska voin käyttää tätä aasinsilta -artikkelina, kun jossain vaiheessa kirjoittelen joitain asioita salaamisesta. Siinäkin on kyse vaihtamisesta. Merkki vaihdetaan toiseen. Siinä on hieman samantapaisia asioita.