Sanakirja-enkoodaus, osa 1 /Ääneen ajattelua

Eräs ohjelmoinnillisista mielenkiinnon aiheistani on datakompressio, ja Richard Feynmania apinoiden pyrin keksimään pyörän uudestaan tyhjästä, aina kun mahdollista jotta oppisinkin oikeasti jotain. Tässä siis mietteitä sanakirjakompressiosta.

Sanakirjakompression ideahan on siinä, että jos meillä joku pätkä toistuu pakattavassa tiedostossa, niin otamme toistuvan pätkän, tallennamme sen kerran, ja laitamme pakattuun tiedostoon vain merkin siihen missä tämä sana on,

Esim:

talo talon talona taloa taloksi talossa talosta taloon

pakkautuisi seuraavasti:

1. "talo"
1 1n 1na 1a 1ksi 1ssa 1sta 1on

Tämä yksinkertaistettu esimerkki kuvaa idean. Sanakirjan muodostukseen liittyy muutama mielenkiintoinen ongelma:

• Miten sanakirja muodostetaan?
• Miten havaitaan toistuvat sanat?

Tässä vaiheessa pitää huomauttaa että kirjoitan tätä täysin lennosta, joten saa nähdä miten paikkaansapitävää asiaa tähän tulee. Eteenpäin!

Joka tapauksessa, sanakirjan muodostuksesta lähdetään. Ainoa looginen tapa lähteä lukemaan tiedostoa on alusta loppuun. Luku tapahtuu seuraavasti, eli seuraa
Algoritmi:

1. alustetaan puskuri1 P1, puskuri2 P2, Sanakirja, paikanosoitin i=0
   
2. luetaan merkki P2:een
3. kopioidaan P2:n ensimmäinen merkki jatkoksi P1:een
   
4. tallennetaan P1 sanaksi sanakirjaan
5. Luetaan suurimman sanan koko merkkiä P2:een.
6. jos P2 löytyy sanakirjasta, niin tyhjennetään P1, i=i+sanan koko, palataan kohtaan 4.
7. i=i+1
   
8. Palataan kohtaan 3

Tämä muodostaa meillä vasta sanakirjan, joka myös sisältää paljon ylimääräisiä sanoja.
Sanakirja itsessään on taulukko, jonka jokainen rivi sisältää sanan, sanan kappalemäärän
tiedostossa, sekä sanan pituuden. Sana = Sx, Kappalemäärä = Sxk, Sanan pituus = Sxp

Kohta 6 tutkitaan vertaamalla P2:n Sxp merkkiä Sx:ään, ja parhaan vastaavuuden löytyessä
kasvatetaan kyseisen sanan Sxk:ta.

Ei hätäillä... Tarkastellaan algoritmin toimintaa edellisen esimerkin datalla:

talo talon talona taloa taloksi talossa talosta taloon.

Sanakirja S = S1 ... Sn
P2: "t", p1 tyhjä
P1: "t" -> S1: "t"
P2: "a", ei löydy S:stä->P1: "ta"->S2: "ta"
P2: "lo", ei löydy S:stä->P1: "tal"->S3: "tal"
P2: "o t", ei löydy S:stä->P1: "talo"->S4:"talo"
P2: " tal", ei löydy S:stä->P1: "talo "-> S5:"talo "
P2: "talon", löytyy S4:stä->S4k=1, P1=""
P2: "n talo", ei löydy S:stä->P1: "n"->S6: "n"
P2: " talo", ei löydy S:stä->P1: "n "->S7: "n "
P2: "talon", löytyy S4:stä->S4k=2, P1=""

Jne. Tämä algoritmi ei löydä kaikkia sanoja, Esim. toistuvat sanat "talon" ja "n t" jäävät siltä
huomaamatta ylläolevasta. Parannusta vaaditaan vielä.

Sanakirjan spesifinen talletusformaatti yllä on myös lähinnä teoreettinen, sillä se kuluttaa massiivisesti muistia. Eräs ratkaisu olisi huomata merkki kerrallaan rakennetut sanat, ja
merkitä minkä pituiset alisanat niistä toistuvat, esim. yllä oltaisiin voitu rakentaa tietue jossa
Sana="talo "
Löytynyt={(4,2)} //merkkejä alusta, toistumat
Sana="n "
Löytynyt={}

Käytetty algoritmi takaa sen, että sanojen maksimipituus on korkeintaan lyhyimmän toistuneen sanan pituus, joten voimme tämän jälkeen leikata sanan, jos lyhimmän toistuneen alisanan pituus on pienempi kuin sanan maksimipituus. Loppuosasta muodostetaan oma sanansa. Vastaavasti jos sana ei toistunut kertaakaan, tiedämme että maksimipituinen versio sanasta esiintyy kerran. Täten, todellinen
sanakirja YO. algoritmilla esimerkillemme olisi:

talo talon talona taloa taloksi talossa talosta taloon.

1. "talo" {(4, 8)}
2. " " {(1, 1)}
3. "n " {(2, 1)}
4. "na " {(3, 1)}
5. "a " {(2, 1)}
6. "ksi " {(4, 1)}
7. "ssa " {(4, 1)}
8. "sta " {(4, 1)}
9. "on." {(3, 1)}

ja varsinainen tiedosto sisältäisi datana: "1213141516171819"

Tässä teräväsilmäinen huomaa että "na " sisältää itseasiassa sanan "a ". Tässä tulee huomata että koska enkoodaus suoritetaan alusta loppuun, ja sanat kirjataan pisimmästä lyhyempään, "na " on korkeammalla prioriteetilla kuin "a ", ja näin pääsee tapahtumaan. Jos sanajärjestys olisi erilainen, meillä olisi sanat "a " sekä "n".

Data itsessään kannattaa vielä pakata Huffmanin algoritmilla, jolloin se tiivistyy huomattavasti. Sanakirjassa kaava Sxk * Sxp:llä antaa suoran painoarvon jonka mukaan enkoodaus kannattaa tehdä. Sanakirja itsessään talleennetaan key-value pareina, jolloin meillä hukkuu tieto kappalemäärästä sekä sanan pituudesta, mutta tämä säästää huomattavasti tilaa.

Tässä kaikki tältäerää, nämä algoritmit ovat vielä kaukana optimaalisista, enkä ole testannut niitä vielä käytännössä. Ääneenajattelua, tajunnanvirtaa ja silleen.