Interesuje me samo na kom principu rade algoritmi za kompresiju. Recimo obicni ZIP ili RAR? Mozda se traze djelovi koji se ponavljaju ili tako nekako,ne znam stvarno kako to uopste radi?
Najprostiji je RLE koji bukvalno pamti ponavljanje nekog stringa. Komplikovaniji su LZW, LZ77, itd.. to su matematicki kompleksniji algoritmi i zahtevaju dobro vladanje matematickim aparatom.
RLE radi otprilike onako kako si i ti pretpostavio - znaci neke nizove bajtova koji se ponavljaju menja na nacin <bajt> <broj-ponavljanja> naravno nije sve tako jednostavno da bi se izbegli zapisi tipa <01> <01> <02> <01> <03> <01> (za niz <01> <02> <03> u orig. fajlu) koriste se takozvane escape sekvence pa se recimo proglasi da kad se u zipovanom (RLE-ovanom fajlu ovde) naidje na neku specijalnu sekvencu bajtova (escape) menja se rezim rada (npr kad naidje na prvi bajt <00>) onda se bajtovi pisu onako kako idu (bez broja ponavljanja za njima) tako da moze da se dobije kraci zapis nego u originalu.
Inace taj algoritam se koristi u kompresiji slike bez gubitka kvaliteta (recimo bmp moze da bude sacuvan sa RLE kompresijom), dok se u nekoj "ozbiljnijoj" kompresiji koriste uglavnom LZW i Hofmanov kod (staticki ili dinamicki)
Ideja Hofmanovog koda je da prebrojis koliko se puta pojavljaju pojedini bajtovi u fajlu (da im odredis frekvencije) i da onda napravis drvo na sledeci nacin: spajanjem dva cvora dobijas cvor sa frek. jednakom zbiru frek. sinova, a uvek vrsis spajanje dva cvora sa trenutno najnizim frek. ne obracajuci paznju na nivo cvorova koje spajas (mozes da npr. spojis cvorove na dubini 2 i 3) dok ne dobijes jedno stablo. Onda iz tog stabla formiras kod na sledeci nacin: npr. svaki put kad skrenes u levo u stablu dopisujes nulu na pocetak koda, a 1 dopisujes pri skretanju desno (naravno kreces od korena, ides prema listovima). Na taj nacin dobijas kod koji nije jednake duzine - ima svojstvo da su najcesci znaci kodirani sa najmanjim brojem bitova i na ovaj nacin se originalni fajl moze da zapise na najkraci moguci nacin. Inace Hofmanovim kodom se dostize teorijski maximum kompresije (naravno bez gubitaka inf.), ne koristi se cesto iz razloga sto moras unapred da znas frek. svih znakova sto moze da bude problem i radi toga sto je kod nejednake duzine pa dekodiranje uvek mora da ide iz pocetka fajla (ne mozes da pocnes od recimo 223 bajta u fajlu jer ne znas gde se on nalazi u kompr. fajlu). Problem nepoznavanja frek. se resava upotrebom dinamickog Hofmanovog koda koji ima neki fiksni preduvidni bafer na osnovu koga pokusava da proceni frek. znakova i koji prilikom izvrsavanja moze da menja kodove za neke znake (naravno ne za one koje je vec iskoristio ali za neke koji se javljaju prvi put, da proceni njihov odnos i da im prema tome dodeli mesto u drvetu). Inace mislim da je ovu varijantu Hofmanovog koda koristio npr. "arj" program za kompresiju.
Za LZW neka napise neko drugi.
P.S. nadam se da nisam bio suvise konfuzan u objasnjenju, nazalost ne znam da li ovde nekako moze da se nacrta stablo koje bi sve razjasnilo.
P.P.S da li bi na ovo trebala da lici konferencija? (u kontekstu lekinog razocarenja) Ako je odgovor da onda je ovo moj mali doprinos, ako ne onda... :)
U svakom slucaju - pri izboru algoritma za losless kompresiju se uzima vise faktora - statistika podataka, zahtevi za memorijom, kompleksnoscu kao i neki drugi faktori, recimo patentna prava.
Registrovani: 9 ( tecaizbeca, proleter., mosfet BJT, ntesic, IMKER, Turmen, dlalic, scoolptor, zeoN_Rider )
Kompresovanje podataka
Re: Kompresovanje podataka