[ MixMaster @ 23.12.2005. 22:36 ] @
Pokusavam da napravim C/C++ algoritam za LZ kodiranje i dekodiranje binarnog alfabeta (sa razlicitim varijanama duzine rjecnika simbola, kao i sa mogucnoscu izbora pocetnog stanja u rjecniku podataka). Ajde da probamo za sada ovo sto nije u zagradama, dakle da pocnemo od LZ kodiranja. Napomena: LZ kodiranje je zasnovano na rjecniku (dictionary based) u kojem se pamte do sada vidjeni stringovi (ponavljanja kodnih simbola). Evo i PRIMJER za one koji nisu upuceni u LZ kodiranje a znaju C/C++: Polazimo od praznog rjecnika i pod pretpostavkom da nas rjecnik nema vise od 8 simbola kada je pun. Neka je dat string: 1011010100010... OBJASNJENJE: Ovaj string se dijeli dok se ne dobije najkraci string koji prethodno nije postojao u rjecniku. String se upisuje kao novi element u rjecnik, koji se sastoji od prethodnog prefiksa i novog bita. Npr. bit 1 nije bio vidjen prethodno i zato mi saljemo indeks njegovog prefixa (postavljen na 000) i zatim broj 1. Dodamo 1 u rjecnik (dakle 1 nema nista “ispred sebe”, odn. ima null ciji je LZ indeks 000). Zatim, nula nije postojala prethodno i mi postavljemo indeks njenog prefiksa i broj 0 (nulu smo dae, uzeli za novi string, ispred nule ne postoji nista, tj. postoji null ciji je LZ indeks 000). Dodamo 0 u rjecnik. Niz 11 ima prefiksni string 1 (dakle, gleda se samo zadnja cifra, sve ostalo se zove prefiks-u slucaju da niste uspjeli da to pohvatate) i zato se salje prefiks string od 1 i saljemo njegov indeks i broj 1. Tako idemo do kraja i rjecnik izgleda ovako: LZ indeks|sadrzaj rjecnika 000|null <- null postavljamo jer smo rekli “polazimo od praznog rjecnika” 001|1 010|0 011|11 100|01 101|010 110|00 111|10 I napokon, kodirana sekvenca ima oblik: (000,1),(000,0),(001,1),(000,1),(100,0),(000,0),(001,0) Huh, cini mi se da sam sve dobro odradio. Dakle, ima li ko ideju kako da odradim ovo. Vjerovatno cu LZ indekse raditi preko cijelih brojeva, a string koji zadajem za kodiranje preko stringova. Hm, mada i ne mora... Dakle?! |