numerosarjojen

On olemassa monia häviöttömiä pakkausalgoritmeja, joihin en tosin ole perehtynyt. Parhaimman algoritmin valitseminen on varmasti tapauskohtaista.

Niin kuin tuossa jo kommentoitiinkin, on olemassa paljon erilaisia häviöttömiä pakkausalgoritmeja. Toki algoritmia voi kutsua kaavaksi, sitähän se oikeastaan on, mutta pakkauksessa idea on pikemminkin fiksata kaava ja tuoda kaavan parametrit (syöte) ulkopuolelta. Tämä parametrijoukko on se pakattu tiedosto.

Tässä jotain esimerkkejä ideoista millä voi pelata:

- Run-length-encoding: Korvataan pitkät sarjat kuten 4,4,4,4,4 sarjoilla kuten 4,6. Toki jokin erikoisjärjestely tarvitaan jotta lukumäärä 4 erotetaan data 4:sta.

- LZW ja muut sanakirjamenetemät: Ideana on koodata toistuvat sarjat 1,2,3,1,2,3,1,2,3 jollain sanakirja-avaimella. Eli vaikka jos 10=1,2,3, niin tuo pakkautuu muotoon 10,10,10.

- Huffman-koodaus ja muut entropiamenetelmät: Jos numeroiden jakauma ei ole tasainen, numeroiden koodausta (bittimäärää) voidaan muuttaa sillä tavalla, että data mahtuu pienempään tilaan.

- Numerot voidaan myös ensin järjestää sopivasti (BWT) tai niille voidaan ensin tehdä jokin häviöllinen sovellusriippuva muunnos kuten differentiaalikoodaus, LPC, Kosinimuunnos jne. Mutta näissä jälkimmäisissä häviää hieman tarkkuutta.

Tuolta voi opiskella lisää:

http://en.wikipedia.org/wiki/Data_compression

"Pystyykö muodostamaan mitään kaavaa, jonka kuvaaminen vie vähemmän tilaa kun tuollaisen numerosarjan"

Edellä mainittiin jo pakkauksesta, mutta tarkasti lukien kysymystäsi vastaus on ei. Ei ole mitään yleispätevää keinoa pakata *kaikkia* numerosarjoja, tai ylipäätään mitään dataa, pienempään tilaan. Jokaisella pakkauskeinolla on jokin merkkijono, jonka esittäminen vie alkuperäistä suuremman tilan vaikka enin osa voitaisiinkin pakata pienempään tilaan.

Tämän todistaminen on suht helppoa kun ajattelet pakkauksen kuvauksena merkkijonoilta merkkijonoille ja mietit lähtö- ja tulojoukkojen kokoja.