Elikkä Run Length Encoding. Teoria on helppo: Sen sijaan että kirjoitetaan nnnnnnnnnn, kirjoitetaan vaan "n10". Paitsi että, jos seuraa tätä teoriaa sokeasti, niin abcde:stä tulee a1b1c1d1e1, mikä ei todellakaan ole optimaalista.
Eräs ratkaisu tähän on että aina jos merkki toistuu, se on signaali että kyseessä on RLE-jakso. Elikkä siis abcdddddddddefg olisikin abcdd8efg, tai abcdd9efg, riippuen miten haluaa asian ilmaista. Tietty, tässä tapauksessa emme enää tiedä missä kohdassa enkoodaus on --- mikä ei ole ongelma jos käsittelemme koko RLE-pakatun pätkän kerralla, mutta entä jos kyseessä on massivinen tiedosto, josta luetaan vaikka 10 kiloa kerrallaan puskuriin?
Siinä tilanteessa meillä tulee rajatapaus jossa puskurin sisältö saattaa päättyä vaikkapa abcd, ja sitten seuraavana meillä onkin puskurissa def, mistä seuraa että jos se päätyy sellaisenaan abcddef, RLE-pakattuun tiedostoon, niin dekoodausvaiheessa e tulkitaan toistonumeroksi. Tämä on helppo ratkaista siten, että tarkastellaan puskurin kahta viimeistä merkkiä, ja jos ne ovat eriävät, enkoodaamme yhtä merkkiä lyhemmästi, ja kopioimme viimeisen merkin puskurin alkuun. Seuraava paketti luetaan sitten merkkiä myöhempään osoitteeseen.
Eli:
buffer abcd -> encode abc, copy d
buffer dbcd -> read data, store to buffer+1
buffer ddef -> return to beginning.
Jos kaksi viimeistä merkkiä ovatkin samat, voimme enkoodata huoletta.
Dekoodaus on hieman kimurantimpi, muttei paljoa.
No comments:
Post a Comment