Sort kompresija podataka
Davno sam dosao na ovu ideju, ali do sada nisam stigao da se pozabavim tematikom.
Planiram da napravim jedno istrazivanje na tu temu, pa sam hteo da vidim
kako ocenjujete samu ideju i da li ce neko imati neke smernice za samo istrazivanje.
Evo o cemu se radi.
Pod pretpostavkom da imamo niz bajtova proizvoljne duzine bez obzira na samu strukturu
(entropiju, kao i sekvence koje se ponavljaju)
entropija informacije koliko kojih bajtova ima unutar datog niza je dosta mala (tabela frekvencija).
Za recimo 64K nam treba 512 bajtova u opstem slucaju da se zapishe tabela frekvencija.
Po word za svaki bajt ulaznog niza a posto ima 256 razlicitih vrednosti, i imamo bafer od 64K
matematika je jasna - 512 bajtova (index u word array-u oznacava za koji bajt se gleda, a sama
vrednost word-a je broj ponavljanja datog bajta)
Ova informacija se moze iskoristiti da bi se rekonstruisao niz od 64K bajtova koji imaju sledecu
karakteristiku:
Svi bajtovi koji su prisutni u rekonstruisanom nizu, prisutni su i u ulaznom nizu. Tacno onoliko
razlicitih vrednosti koliko ima u ulazu ima i u izlaznom nizu. Izlazni niz je zapravo ulazni
niz, soritiran tako da vrednosti budu po rastucem ili opadajucem redosledu.
Pored ove table frekvencija, bilo bi bitno zapisati i redosled operacija kojim se od ulaznog niza
doslo do izlaznog niza kako bi se moglo backtrackingom rekonstruisati ulazni niz.
U opstem slucaju, operacije koje se koriste prilikom sortiranja mogu se vrlo lako kodirati u samo
par bita.
Obicno su to operacije tipa :
- poredjenje 2 vrednosti i ishod poredjenja
- zamena mesta vrednostima
- prelazak na sledece poredjenje (pomeranje indexa, u jednu ili drugu stranu)
Znaci za svaki sort algoritam se moze konstruisati varijanta algoritma koja ce prilikom sortiranja
generisati niz brojeva (i to iz dosta malog skupa, od par cifara) takav da opisuje trenutnu operaciju
u datom algoritmu, a iz kojeg se moze rekonstruisati pocetno stanje u odnosu na zavrsni sortirani niz
Odokativnom metodom sam dosao do zakljucka da je vrlo moguc sledeci scenario:
u zavisnosti od algoritma, odredjene sekvence bajtova unutar ulaznog niza
(vishebajtne reci koje se ponavljaju) ce proizvesti iste sekvence operacija u izlazu, znaci ovom
transformacijom bi se u odredjenim slucajevima zadrzala redudancija ulaznog niza, pa je moguce
na izlaznom nizu transformacije (kodovi operacija) primeniti neki od vec postojecih algoritama
za kompresiju koji se oslanjaju na redudanciju informacija ovog tipa.
Takodje mi se cini da ce odredjeni algoritmi za sortiranje proizvesti distinktno razlicite frekvencije
operacija (mnogo vishe poredjenja nego recimo zamena ili dosta pomeranja indexa u odnosu na ostale
operacije), samim tim i neka vrsta entropijskog kodiranja izlaza dolazi u obzir.
Da li znate za istrazivanja koja su se bavila ovom idejom, i ako da, do kakvih rezultata se doslo?
Sta generalno mislite o samoj ideji?
Vredi li se upustati u istrazivanje i implementaciju ovakvog pristupa kompresiji?
Voleo bih kada bi zainteresovani prodiskutovali ovaj pristup pre nego sto se upustim u bilo
kakav istrazivacki rad na datu temu.
 |  |
 |
