Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Kompresovanje podataka

[es] :: Art of Programming :: Kompresovanje podataka

[ Pregleda: 7491 | Odgovora: 3 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Bager
Aleksandar Vuković
Budva, Podgorica

Član broj: 4813
Poruke: 148
*.crnagora.net.

ICQ: 119208214


Profil

icon Kompresovanje podataka29.07.2002. u 03:27 - pre 233 meseci
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?
 
Odgovor na temu

Ivan Dimkovic

Administrator
Član broj: 13
Poruke: 16206
*.verat.net



+7005 Profil

icon Re: Kompresovanje podataka29.07.2002. u 07:27 - pre 233 meseci
Pogledaj po netu teorije kompresije.

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.

DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.digicortex.net/node/1 Videos: http://www.digicortex.net/node/17 Gallery: http://www.digicortex.net/node/25
PowerMonkey - Redyce CPU Power Waste and gain performance! - https://github.com/psyq321/PowerMonkey
 
Odgovor na temu

rivan
Ivan Radovanović

Član broj: 1901
Poruke: 71
*.beg.sezampro.yu

ICQ: 212235650


Profil

icon Re: Kompresovanje podataka02.09.2002. u 22:27 - pre 232 meseci
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... :)
 
Odgovor na temu

Ivan Dimkovic

Administrator
Član broj: 13
Poruke: 16206
*.telemaxx.net



+7005 Profil

icon Re: Kompresovanje podataka03.09.2002. u 12:20 - pre 232 meseci
Evo jednog linka sa vrlo dobrim referencama za razne algoritme za kompresiju podataka:

http://datacompression.info/index.shtml

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.


DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.digicortex.net/node/1 Videos: http://www.digicortex.net/node/17 Gallery: http://www.digicortex.net/node/25
PowerMonkey - Redyce CPU Power Waste and gain performance! - https://github.com/psyq321/PowerMonkey
 
Odgovor na temu

[es] :: Art of Programming :: Kompresovanje podataka

[ Pregleda: 7491 | Odgovora: 3 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.