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

Kompresija random-like podataka

[es] :: Art of Programming :: Kompresija random-like podataka
(TOP topic, by Gojko Vujovic)
Strane: 1 2 3 4 5 6 ... Dalje > >>

[ Pregleda: 53413 | Odgovora: 127 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
213.244.208.*



+557 Profil

icon Re: Kompresija random-like podataka02.01.2006. u 11:00 - pre 222 meseci
Svaka cast Patricku ali ja bih i dalje voleo da vidim svoj algoritam na delu. Valjda ce se neko smilovati.
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
213.244.208.*



+557 Profil

icon Re: Kompresija random-like podataka02.01.2006. u 11:01 - pre 222 meseci
.

[Ovu poruku je menjao MajorFatal dana 02.01.2006. u 12:06 GMT+1]
Nemoj da pricas?
 
Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541



+710 Profil

icon Re: Kompresija random-like podataka02.01.2006. u 18:58 - pre 222 meseci
Srećnu novu svima želim... Malo kasnim sa čestitkom, onanisao sam za doček...
Citat:
BraMom: Više ne znam da li to negativno ili mozda pozitivno, to mu dođe kao početak interesovanja za teoriju informacija...

Naravno da je pozitivno, entuzijazam je najbolji stimulans za napredak, setimo se sopstvenih početaka, doduše mi smo lestvicu postavljali nešto niže od "kompresije slučajnih podataka". Iz neke dalje perspektive, i pobede i porazi su podjednako vredni za razvitak mladog uma - porazi, ruku na srce, nešto teže padaju, ali je, barem u početku, izvučena korist ekvivalentna.
Citat:
Ivan Dimkovic: E a ako nekom uspe da kompresuje proizvoljnu random sekvencu - od mene dobija 10 gajbi piva kojeg zeli

MajorFatal, za mene bi ovo bio dovoljan podstrek da naučim to malo programiranja neophodnog da implementiram tvoj algoritam. S obzirom da ovde u Srbiji ne raspolažem Dimkovićevim finansijskim resursima, bio bih spreman da dam svoj skroman doprinos u vidu 2 gajbe gorenavedenog piva.
Edit - sintaksa

[Ovu poruku je menjao jablan dana 02.01.2006. u 20:04 GMT+1]
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
213.244.208.*



+557 Profil

icon Re: Kompresija random-like podataka02.01.2006. u 21:32 - pre 221 meseci
Ama kad nesto ne ide onda ne ide. A ja sam pokusavao I to iz vise navrata da naucim da programiram I jednostavno nema sansi. Kontam po nesto ali kockice mi se jednostavno ne slazu u celinu. Konkretno prvo sam dosao u dodir sa Delphyjem u firmi Microcom u Bg. Tu sam naucio neke da kazem osnove. Onda sam bas u nameri da ne odustanem tako lako uzeo za diplomski da uradim neki program u Delphy-u. Toliko sam bio uspesan da je na kraju moj profesor kod koga sam uzeo diplomski morao da isprogramira 99% programa. Posle sam sam kod kuce provezbao onu knjigu od Laslo Krausa, neki primeri su mi radili a neki ne tek vec kod knjige od Paul Kimmela “Vodic za programere” vise nemam pojma sta se desava I veci deo jednostavno ne razumem. Imao sam najbolju volju ali...od C++ sam odustao kad mi nije poslo za rukom ni da iskompajliram program “Hallo world”, znaci da se ne upinjem vise. Ali da se ovo ne pretvori u moju tuznu ispovest.

Ono sto mene nervira jeste da iako na osnovu svojih skromnih iskustava sa programiranjem isto zamisljam kao sto ga zamislja mali Perica ipak mi se cini da bi za implementaciju ovog programa malo iskusnijem programeru trebalo jedno popodne. Sa druge strane za one manje iskusne ovo bi bila odlicna stilska vezba bilo bi tu itekako zanimljivog posla najvise oko odredjivanja koeficijenata upisivanja I tumacenja istih. Najgore od svega je da ste svojevremeno u okviru ovog istog podforuma kukali kako nemate sta da programirate, kao dajte da se nesto zanimljivo programira inace umresmo od dosade. Pa sta je sad?
U svakom slucaju ja cekam jos neko vreme da se neka dobra dusa smiluje na moje vapaje a onda se selim na Delphy, Kylix forum gde cu pokusati da uz vasu pomoc uradim program, s tim sto ce to tek biti plac majke bozije. Verujte mi da vam je lakse da to isprogramirate nego da se posle preganjate sa mnom i ucite me stvari koje meni jednostavno ne idu u glavu.

Dizem ulog na konkursu sada je nagrada 1 malo pivo I kesica “Prima” stapica.


[Ovu poruku je menjao Mihajlo Cvetanović dana 07.09.2011. u 15:56 GMT+1]
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
213.244.208.*



+557 Profil

icon Re: Kompresija random-like podataka06.01.2006. u 09:09 - pre 221 meseci
Ala ste se uspavali. Vec tri dana se niko ne javlja. Nadam se da to znaci da programirate.

Srecan bozic svima zelim uz najlepsi pozdrav HRISTOS SE RODI!
Nemoj da pricas?
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.jetstream.xtra.co.nz.



+3 Profil

icon Re: Kompresija random-like podataka06.01.2006. u 14:19 - pre 221 meseci
Vaistinu.

Sto se tice kompresije, pa niko nece da programira nesto za sta unapred zna da nece raditi. Ti hoces da kazes da ce tvoj algoritam da kompresuje bilo sta sto ima vise od 32 (ili koliko god) bitova? Zasto onda ne bi uzeo fajl od gigabajta pa ga kompresovao prvo na megabajte pa onda taj na kilobajte pa tako dalje sve dok ne dodjes do minimalnog fajla :-))) Drugim recima, ne razumem kako ne vidis zasto to ne bi radilo...

Evo malo na drugi nacin.
Zamisli da ti sa 32 bita mozes da kompresujes sekvencu od 64 bita. Broj mogucih zapisa od 64 bita je 2^64. Broj mogucih zapisa od 32 bita je 2^32. To znaci da dekompresijom mozes da dobijes samo 2^32 slucajeva a tih slucajeva bi trebalo da bude 2^64.
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
213.244.208.*



+557 Profil

icon Re: Kompresija random-like podataka07.01.2006. u 21:39 - pre 221 meseci
Hristos se rodi. Evo I na bozic se bavim kompresijom sto znaci da cu se istom baviti cele godine ako je verovati narodnom predanju.

Citat:
srki

Sto se tice kompresije, pa niko nece da programira nesto za sta unapred zna da nece raditi.


Ama kako znas da nece raditi? Zadnje do cega smo dosli je da Dimkovic tvrdi da ce koeficijenti zauzimati vise mesta nego sam fajl a ja tvrdim suprotno s tim da nijedan nije dokazao svoje stavove. S jedne strane on je belosvetski strucnjak s druge strane ja sam pokazao I dokazao da onakav nacin zapisivanja koeficijenata biva sve racionalniji za sve vece brojeve (zato sam svojevremeno I nazvao ovu kompresiju “beskonacna” a ne zato sto verujem da se moze kompresovati do beskonacno malih vrednosti, “konacno resenje” je otuda sto sam posle duze razmisljanja konacno dosao do resenja). Evo jos jedan primer just for the record: Gorepomenuti izraz 2^64 koji zauzima 32 bita tj. manje od 64 bita ipak zauzima celih 50% od fajla, dok na primer izraz 2^8000 koji zauzima 48 bita u odnosu na 8000 bita zauzima oko 0,5% od fajla. Itd za jos vece vrednosti jos vece iskoriscenje.

Citat:
srki:  Ti hoces da kazes da ce tvoj algoritam da kompresuje bilo sta sto ima vise od 32 (ili koliko god) bitova? Zasto onda ne bi uzeo fajl od gigabajta pa ga kompresovao prvo na megabajte pa onda taj na kilobajte pa tako dalje sve dok ne dodjes do minimalnog fajla :-))) Drugim recima, ne razumem kako ne vidis zasto to ne bi radilo...


Upravo ta granica od 32 ili kolko vec bita ispod koje dolazi do ekspanzije umesto do kompresije I sprecava da se ovom modelu prisije to da bi visestrukom primenom algoritma rezultujuci fajl tezio nuli sto bi ovaj model cinilo nemogucim. U stvari ti si se dobro izrazio: dolazilo bi se do minimalnih fajlova s tim sto ja ne verujem da bi kod ovog modela bilo mesta za visestruku kompresiju tj. kompresiju u vise nivoa, mislim da bi se vec u prvom koraku dobijali izuzetno mali tj. kompresovani fajlovi. Doduse to sto ja verujem I mislim nista ne znaci dok ne dokazem a da dokazem ne mogu jer ne znam da programiram a vi necete da mi pomognete tako da mi ostaje samo da kukam.

Citat:
srki

Evo malo na drugi nacin.
Zamisli da ti sa 32 bita mozes da kompresujes sekvencu od 64 bita. Broj mogucih zapisa od 64 bita je 2^64. Broj mogucih zapisa od 32 bita je 2^32. To znaci da dekompresijom mozes da dobijes samo 2^32 slucajeva a tih slucajeva bi trebalo da bude 2^64.


A sad ti zamisli da ja bilo koji niz od 32 bita mogu da procitam kako hocu. Na primer mogu da ga procitam s leva na desno pa s desna na levo I da ta dva niza spojim u tom slucaju dobio sam novi niz od 64 bita. Ili da citam svaki drugi bit pa ceo niz po redu pa svaki drugi unazad itd. Kao sto vidis u 32 bita moze da se krije I vise od 2^64 kombinacija samo naravno treba znati izvuci ih odatle. Upravo to bi trebalo da se postize onakvim eksponencijalnim nacinom zapisivanja koeficijenata. Bili bi kraci kad se zapisu a “duzi” kad se protumace. Evo malo I na drugi nacin sto bi ti reko: Evo ga jedan brojac:
1: 000
2: 001
3: 010
4: 011
5: 100
6: 101
7: 110
8: 111
A evo ga I drugi brojac:
1: 0
2: 1
3: 00
4: 01
5: 10
6: 11
7: 000
8: 001
Kao sto vidis I sa manjim brojem bita se moze izbrojati isti broj kombinacija tako sto se duzina niza uvede kao dodatna informacija.

Al ajde da se ne lazemo I meni je ovo najsumljiviji deo cele ove price. S jedne strane logika, zdrav razum I teorija informacija mi govore da je ovo nemoguce izvesti. S druge strane ja jednostavno ne mogu da skontam kako to da do bilo kog broja ne moze da se dodje uz pomoc nekoliko pravilno odabranih koeficijenata. Takodje mi nije jasno ako ceo fajl nosi sa sobom gomilu informacija npr. Informacije koje je odgovarajuci engine u stanju da protumaci, preciznu poziciju na brojacu, redosled pojavljivanja na brojacu I verovatno jos neke informacije kojih ja sad ne mogu da se setim pa ako ja od svih tih informacija odaberem samo jednu za pamcenje tj. redosled pojavljivanja na brojacu to je onda manje informacija za pamcenje od one ukupne mase prema tome trebalo bi da je potrebno I manje bita za njihovo predstavljanje.
Bah nije ni bitno. Odavno sam se pomirio sa sudbinom da od ovoga najverovatnije nece biti nista, mogu samo jos da se nadam. Opet dizem ulog na konkursu: nagrada je: 1 malo pivo I kesica “Prima” stapica, smoki ili cips “Pik Cacak” PO SOPSTVENOM IZBORU! I polovina novca od prodatih kompresora. U pitanju su naravno milionski iznosi ;)

Nemoj da pricas?
 
Odgovor na temu

kurt.hectic
Kurt Hectic

Član broj: 66049
Poruke: 25
*.ptt.yu.



Profil

icon Re: Kompresija random-like podataka08.01.2006. u 01:26 - pre 221 meseci
Citat:
Ama kako znas da nece raditi? ... ja sam pokazao I dokazao da onakav nacin zapisivanja koeficijenata biva sve racionalniji za sve vece brojeve
Nisi pokazao, nego si samo rekao. Ali kada si rekao nehotice si bio u pravu. Kod postaje efikasniji sa povećanjem kardinalnosti alfabeta koji se koristi za kodiranje.

To je prosta posledica slabog zakona o velikim brojevima ali ne dokazuje da tvoj način kodiranja išta kompresuje.
Citat:
primer just for the record: Gorepomenuti izraz 2ˆ64 koji zauzima 32 bita tj. manje od 64 bita ipak zauzima celih 50% od fajla, dok na primer izraz 2ˆ8000
Nije ti dobar primer. Kompresor treba da sabija podatke u srednjem, a ne da sabija podatke za nekoliko datih primera. Znači, za sve moguće ulazne nizove podataka, sa velikom verovatnoćom izlazni niz podataka mora da bude kraći. Da bi to pokazao nije ti potrebno da znaš programiranje. Programiranje dolazi tek na kraju kada je sve objašnjeno.
Citat:
A sad ti zamisli da ja bilo koji niz od 32 bita mogu da procitam kako hocu.
Tvoj rezultat je i dalje slabiji od rezultata teorije informacija. Tu se kaže da za bilo koju strategiju kodiranja nije moguće opisati izvor podataka bez gubitaka pomoću izvora manje entropije.

Pošto rezultat važi za bilo koju strategiju, važi i za čitanje unapred, unazad, svakog drugog, svakog trećeg itd. Sorry.

Ti se nadaš da ćeš ako opišeš kodiranje koje deluje fensi da nekako magično preskočiš fundamentalna ograničenja. To ne ide tako.
Citat:
Takodje mi nije jasno ako ceo fajl nosi sa sobom gomilu informacija npr. Informacije koje je odgovarajuci engine u stanju da protumaci, preciznu poziciju na brojacu, redosled pojavljivanja na brojacu I verovatno jos neke informacije kojih ja sad ne mogu da se setim pa ako ja od svih tih informacija odaberem samo jednu za pamcenje tj. redosled pojavljivanja na brojacu to je onda manje informacija za pamcenje od one ukupne mase
Ovo ti je ključna primedba. Tačno je da ako znaš dosta o izvoru da ćeš bolje da ga kompresuješ. Ako znaš nešto o izvoru, tj. ako imaš engine koji razume šta to izvor šalje, onda izvor sigurno nije "random-like", već ima neku skrivenu strukturu. "Random" podaci su po definiciji random baš zato što ne možeš da u njima pronađeš strukturu.

Računanjem entropije možeš da proveriš da li postoji struktura ili ne.

Ako struktura postoji, onda možeš da pređeš na smišljanje načina kako da je iskoristiš da bi kompresovao podatke. Zavisno od strukture podataka i zavisno od kvaliteta rekonstrukcije koju želimo postoje različite strategije.

Ako nikakva struktura ne postoji i podaci su stvarno "random", onda nema pomoći, to ti je kao da hoćeš da staviš kilo u pola kile: nemoguće. Ukratko, ne dobijaš pomoć jer tvoj napad na problem ne obećava.
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.jetstream.xtra.co.nz.



+3 Profil

icon Re: Kompresija random-like podataka08.01.2006. u 07:22 - pre 221 meseci
Citat:
MajorFatal
Ama kako znas da nece raditi? Zadnje do cega smo dosli je da Dimkovic tvrdi da ce koeficijenti zauzimati vise mesta nego sam fajl a ja tvrdim suprotno s tim da nijedan nije dokazao svoje stavove.

Pa Senon je to dokazao jos 1948. Tako mi znamo da to nece raditi:
http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf

Ja stvarno ne razumem kako me nisi shvatio. Ako imas fajl od 32 bita i pokusavas da ga otpakujes koliko razlicitih fajlova mozes da dobijes? Mozes da dobijes maksimalno 2^32 razlicita fajla. A koliko ima razlicitih fajlova od 64 bita? Ima ih 2^64. To znaci da otpakivanjem fajla od 32 bita ne mozes da dobijes bilo koji fajl.

[Ovu poruku je menjao srki dana 08.01.2006. u 08:27 GMT+1]
 
Odgovor na temu

ivan.mile

Član broj: 67586
Poruke: 22
*.yu
Via: [es] mailing liste



Profil

icon Re: Kompresija random-like podataka08.01.2006. u 10:45 - pre 221 meseci
Citat:

Evo malo I na drugi nacin sto bi ti reko: Evo ga jedan brojac:
1: 000
2: 001
3: 010
4: 011
5: 100
6: 101
7: 110
8: 111
A evo ga I drugi brojac:
1: 0
2: 1
3: 00
4: 01
5: 10
6: 11
7: 000
8: 001
Kao sto vidis I sa manjim brojem bita se moze izbrojati isti broj
kombinacija tako sto se duzina niza uvede kao dodatna informacija.


Ovaj drugi brojač neće raditi kako treba. Zašto? Zato što si napravio
prefiksne kodne reči. Npr. ako očitaš 0000001 šta si ti ustvari očitao?
Da li 000 001 ili 00 0 001 ili 0 0 0 0 0 1 ili 0 0 0 001... ? Drugim
rečima, otkud znaš gde ti je granica između dve kodne reči, kako
razlikuješ da li ti je stigla 3 (00) ili dve 1 (0 0)?
 
Odgovor na temu

formeye
Ivan Čukić
KDE developer, Free Software Network
Serbia
BGD

Član broj: 5188
Poruke: 388
..shall-bg.customer.sbb.co.yu.

Sajt: ivan.fomentgroup.org


Profil

icon Re: Kompresija random-like podataka08.01.2006. u 13:39 - pre 221 meseci
Citat:
Evo malo I na drugi nacin sto bi ti reko: Evo ga jedan brojac:
1: 000
2: 001
3: 010
4: 011
5: 100
6: 101
7: 110
8: 111
A evo ga I drugi brojac:
1: 0
2: 1
3: 00
4: 01
5: 10
6: 11
7: 000
8: 001
Kao sto vidis I sa manjim brojem bita se moze izbrojati isti broj
kombinacija tako sto se duzina niza uvede kao dodatna informacija.

Moras da pamtis i duzinu, a u ovom slucaju duzina ide od 1-3 bita. Za zapis duzine ti je, dakle, potrebno 2 bita. Sto znaci da bi ti drugi brojac izgledao ovako:
[duzina] [vrednost]
1: 01 0
2. 01 1
3. 10 00
4. 10 01
...
Tako da ovo ispadne ekspanzija...

[Ovu poruku je menjao formeye dana 08.01.2006. u 14:39 GMT+1]
While you were hanging yourself on someone else's words
Dying to believe in what you heard
I was staring straight into the shining sun
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
213.244.208.*



+557 Profil

icon Re: Kompresija random-like podataka09.01.2006. u 22:33 - pre 221 meseci
Citat: Nisi pokazao, nego si samo rekao. Ali kada si rekao nehotice si bio u pravu.

Ili sam pokazao, ili rekao ili nehotice bio u pravu. Dogovori se pa kazi.

Citat: Kompresor treba da sabija podatke u srednjem, a ne da sabija podatke za nekoliko datih primera. Znači, za sve moguće ulazne nizove podataka, sa velikom verovatnoćom izlazni niz podataka mora da bude kraći.

U srednjem sta? Ovde ne razumem sta si napisao.
Posto sam po tvom priznanju I nehotice bio u pravu smatram da je stvar dokazana I da ce zaz sve primere izlazni niz podataka biti kraci. Primere svako moze odabrati po sopstvenom nahodjenju. Inace kako znas da je nehotice, ja sam bre razmisljo o tome.

Citat: Pošto rezultat važi za bilo koju strategiju, važi i za čitanje unapred, unazad, svakog drugog, svakog trećeg itd. Sorry.

Otkud znam. Ja sam se nado da ce cudnih nacina citanja da me spase operator ^ (na) on obezbedjuje da se vise puta citaju nizovi bita ispred I iza njega I time bi se dobijala prividna ekspanzija inace kraceg niza bita dok bi se o pravilima citanja brinuo odgovarajuci engine. Nisam znao da nije moguce opisati izvor podataka bez gubitka pomocu izvora manje entropije.



Citat:
kurt.hectic:  Ako znaš nešto o izvoru, tj. ako imaš engine koji razume šta to izvor šalje, onda izvor sigurno nije "random-like", već ima neku skrivenu strukturu.


Ja kolko znam EXE fajlovi sa jedne strane su smisleni tj. postoji engine koji razume sta to oni salju, a sa druge strane toliko su rastrkane structure da mogu da se posmatraju kao random-like o cemu svedoci I slab uspeh uobicajenih nacina kompresije nad njima.

Citat:
srki

Ja stvarno ne razumem kako me nisi shvatio. Ako imas fajl od 32 bita i pokusavas da ga otpakujes koliko razlicitih fajlova mozes da dobijes? Mozes da dobijes maksimalno 2^32 razlicita fajla. A koliko ima razlicitih fajlova od 64 bita? Ima ih 2^64. To znaci da otpakivanjem fajla od 32 bita ne mozes da dobijes bilo koji fajl.


Nema potrebe da se ponavljas, za ovako postavljeno pitanje vec sam ponizno priznao da nemam pravi odgovor. Mada tako kako ti postavljas stvari gledajuci nijedna vrsta kompresije ne bi bila moguca jer nijedan kraci fajl ne bi mogao da se raspakuje u nijedan duzi zbog broja kombinacija koje su u stanju da tvore kraci I duzi fajl.

Ovde cu ja ponoviti ono sto meni I dalje nije jasno. Kako to da redni broj pojavljivanja fajla na brojacu ne moze da se dobije sa nekih desetak petnaest sabiraka – koeficijenata? U primeru sa 2^8000 gde isti zapis zauzima oko 0,5% od duzine fajla svi sabirci zajedno bi zauzimali 5-10%od velicine fajla. A ti I Dimkovic pak hocete da me ubedite da bi mi trebalo 200 I vise sabiraka. Pa to onda ne bi bio broj nego neosvojiva tvrdjava. Svako ko je gledao kviz “Brojke I slova” ili Muzicku/TV slagalicu tj. igru “Moj broj” svedok je koliki je procenat takmicara dolazio u veoma kratkom vremenu do tacnog broja I to sa unapred zadatim koeficijentima. A ovde bi se koeficijenti birali po sopstvenom nahodjenju oni koji najvise odgovaraju za postavljeni cilj (broj) I to bez vremenskog ogranicenja.


Citat:
ivan.mile: Ovaj drugi brojač neće raditi kako treba. Zašto? Zato što si napravio
prefiksne kodne reči. Npr. ako očitaš 0000001 šta si ti ustvari očitao?
Da li 000 001 ili 00 0 001 ili 0 0 0 0 0 1 ili 0 0 0 001... ? Drugim
rečima, otkud znaš gde ti je granica između dve kodne reči, kako
razlikuješ da li ti je stigla 3 (00) ili dve 1 (0 0)?


Znam gde mi je granica izmedju dve kodne reci tako sto mi sa brojaca u odredjenom trenutku stize tacno jedna kodna rec koju onda tumacim ili koristim vec na bilo koji smislen nacin, I ne pada mi napamet da ih pisem zajedno jednu do druge u tom obliku pa da onda ne znam gde mi je granica izmedju dve kodne reci. Konkretno ako je stanje na zaustavljenom brojacu 00 to je 3 a ne dve jedinice. A 0000001 je 128 (ako se nisam zabrojo) mozes proveriti ako nastavis drugi brojac.

Citat:
formeye: Moras da pamtis i duzinu, a u ovom slucaju duzina ide od 1-3 bita. Za zapis duzine ti je, dakle, potrebno 2 bita. Sto znaci da bi ti drugi brojac izgledao ovako:
[duzina] [vrednost]
1: 01 0
2. 01 1
3. 10 00
4. 10 01
...
Tako da ovo ispadne ekspanzija...


Informacija o duzini je sadrzana u samom nizu a vec sam napomenuo da stanja sa brojaca u ovom obliku ne bih pisao jedna do drugih tj. nije mi potrebna posebna informacija o duzini da bih razdvajao kodne reci.

Citat:
kurt.hectic

Ako nikakva struktura ne postoji i podaci su stvarno "random", onda nema pomoći, to ti je kao da hoćeš da staviš kilo u pola kile: nemoguće. Ukratko, ne dobijaš pomoć jer tvoj napad na problem ne obećava.


Pa I nikakva struktura je nekakva struktura, takozvana “nikakva” bice da I za nju ima leka. Neki pametan cova rece da su za citav razvoj civilizacije zasluzni ljudi koji su pokusavali I uspevali da urade nemoguce. A da necu dobiti pomoc na sajtu specijalizovanom za pomoc sam skapirao davnih dana. Da ne zivim tu gde zivim cudio bih se, ovako nista.

Vec ste se navikli da sa svakim novim javljanjem dizem ulog na konkursu pa tako I ovog puta: 1 malo pivo, stapici “Prima”, smoki ili cips “Pik Cacak” po sopstvenom izboru I 49% akcija od preduzeca koje ce prodavati kompresore. Jeste da deluje da je manja ponuda nego prosli put kad sam nudio polovinu zarade tj. 50% ali podela fifti-fifti implicira ortacko ili drustvo sa ogranicenom odgovornoscu sto su ekonomski dokazano propali I neefikasni modeli tako da je 49% u solidnom I ekonomski uspesnom modelu akcionarskog drustva mnogo bolja ponuda. Eto ga jos jedan primer kako je manje u stvari vece I kako stvari nisu uvek onakve kakvim se cine na prvi pogled.

Nemoj da pricas?
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.navman.com.



+3 Profil

icon Re: Kompresija random-like podataka09.01.2006. u 23:56 - pre 221 meseci
Citat:
A da necu dobiti pomoc na sajtu specijalizovanom za pomoc sam skapirao davnih dana. Da ne zivim tu gde zivim cudio bih se, ovako nista.

A nego sta radimo nego ti pomazemo? Pomazemo ti da shvatis da je ovo uzaludno i da ne gubis vreme. Ja ne razumem kakvu vrstu pomoci bi hteo. Sta bi ti rekao kada bi te neko pitao da mu pomognes da stavi dva litra vode u flasu koja prima litar? Verovatno bi mu objasnio da ne moze (bez obzira na to kako sipa) pa bi se on kao ti ljutio sto neces da mu pomognes. Ja stvarno ne razumem ovakav tvoj stav pa koliko nas se javilo i ostavilo komentar u cilju da ti pomognemo a ti kazes da niko nece da ti pomogne. mi hocemo da ti pomognemo ali to sto se tebi ne svidja nacin na koji ti pomazemo je samo tvoj problem. Cak smo ti i ostavili link sa dokazima da tvoja kompresija nece raditi.

Citat:
Mada tako kako ti postavljas stvari gledajuci nijedna vrsta kompresije ne bi bila moguca jer nijedan kraci fajl ne bi mogao da se raspakuje u nijedan duzi zbog broja kombinacija koje su u stanju da tvore kraci I duzi fajl.


Ne nego to samo znaci da bilo koja kompresija ne moze da spakuje sve fajlove. Ako pokusas da spakujes random fajl sa RAR-om ili ZIP-om dobices veci fajl od originala.

Citat:
Kako to da redni broj pojavljivanja fajla na brojacu ne moze da se dobije sa nekih desetak petnaest sabiraka – koeficijenata? U primeru sa 2^8000 gde isti zapis zauzima oko 0,5% od duzine fajla svi sabirci zajedno bi zauzimali 5-10%od velicine fajla.

A sta ti predstavlja redni broj fajla? Zar nije to sam taj fajl?
Recimo ako poredjas (u binarnom zapisu brojeve po redu:
000 ( a to je 0 dekadno)
001 ( to je 1 dekadno)
010 (2 dekadno)
011 (3 dekadno)
100 (4 dekadno)
101 (5 dekadno)
...
Ako ti hoces da zapises fajl pod rednim brojem 5 to znaci da moras da upises 101 tj. nista nisi skratio. Ne razumem zasto kazes da bi kompresija radila za 32 bita a ne bi radila za npr. 8 bitova? Koji je minimalni broj bitova da bi tvoj kompresija kao radila?

Ajde ovako, posto zelis da ti pomognemo posaljes mi 500 evra i ja ti uradim program. Ako kompresija radi za bilo koji fajl ja ti vratim tih 500 evra i odreknem se svih autorskih prava i prava na bilo kakvu buducu zaradu?
 
Odgovor na temu

Yu Raider
Ivan Djordjevic
Bg

Član broj: 40731
Poruke: 273
..shall-bg.customer.sbb.co.yu.



+2 Profil

icon Re: Kompresija random-like podataka11.01.2006. u 17:29 - pre 221 meseci
Citat:
srki:
Ajde ovako, posto zelis da ti pomognemo posaljes mi 500 evra i ja ti uradim program. Ako kompresija radi za bilo koji fajl ja ti vratim tih 500 evra i odreknem se svih autorskih prava i prava na bilo kakvu buducu zaradu?


Eeeee Srbijo, Srbijo...

@MajorFatal
Iz iskustva znam da ti verovatno niko nece napisati program, moj savet je da se ipak zavatis malo programiranja. Pa nije bwe tolko tesko, ja, koji sam star 13 godina sam (skoro) napravio program za pravljenje autorunova... Doduse ne znam bas mnogo o otvaranju i pisanju binarnih fajlova (zapravo, nista ne znam o tome)... Ali da bi ti dogurao dotle nemoj da ocekujes da ce to biti prvi program koji si napravio, to jednostavno ne ide tako, moras da pocnes od Hello World stvarcica...

Sto se tice kompajlera, preporucujem Bloodshed Dev-C++ (www.bloodshed.net).
Takodje, uopste i ne moras da koristis C++, mozes da to isto uradis i iz Visual BASIC-a na primer, u sv. slucaju izbor je na tebi...

Srecno!

[Ovu poruku je menjao Yu Raider dana 11.01.2006. u 18:35 GMT+1]
SLIder.
 
Odgovor na temu

formeye
Ivan Čukić
KDE developer, Free Software Network
Serbia
BGD

Član broj: 5188
Poruke: 388
..shall-bg.customer.sbb.co.yu.

Sajt: ivan.fomentgroup.org


Profil

icon Re: Kompresija random-like podataka11.01.2006. u 19:01 - pre 221 meseci
Citat:
@MajorFatal
Iz iskustva znam da ti verovatno niko nece napisati program, moj savet je da se ipak zavatis malo programiranja. Pa nije bwe tolko tesko, ja, koji sam star 13 godina sam (skoro) napravio program za pravljenje autorunova... Doduse ne znam bas mnogo o


Da postoji iole bilo kakva sansa da ovo proradi, nasao bi se neko da napise program - kolega i ja smo radili kompresiju za slike iako je, generalno, uzaludno jer i ovako ima dosta formata...

@MajorFatal
Da li tvrdis da ovom tvojom kompresijom je moguce svaki fajl kompresovati na fajl manji od njega samog?
While you were hanging yourself on someone else's words
Dying to believe in what you heard
I was staring straight into the shining sun
 
Odgovor na temu

Ivan Dimkovic

Administrator
Član broj: 13
Poruke: 16683
*.nero.com.



+7169 Profil

icon Re: Kompresija random-like podataka11.01.2006. u 19:38 - pre 221 meseci
Citat:

Eeeee Srbijo, Srbijo...


Bas tako, eto par nas pokusava da objasni coveku da to ne ide, iz valjda nekog iskustva - pa mora i na plasticni nacin sa "500 eura" ;-)

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

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.navman.com.



+3 Profil

icon Re: Kompresija random-like podataka11.01.2006. u 21:47 - pre 221 meseci
Ma moze i za 100€ :-)
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
195.252.103.*



+557 Profil

icon Re: Kompresija random-like podataka11.01.2006. u 23:14 - pre 221 meseci
Citat: Ja ne razumem kakvu vrstu pomoci bi hteo.

Hteo bih da mi neko uradi program koji ja sam ne mogu da uradim.

Citat: Sta bi ti rekao kada bi te neko pitao da mu pomognes da stavi dva litra vode u flasu koja prima litar? Verovatno bi mu objasnio da ne moze (bez obzira na to kako sipa) pa bi se on kao ti ljutio sto neces da mu pomognes.

Ne bih nista objasnjavo nego bih sipo dok se sve ne prelije, isto tako ocekujem od vas da uradite program pa ako isti ne bude kompresovao podatke tek tad cu da poverujem da ova moja ideja nije dobra.

Citat: mi hocemo da ti pomognemo ali to sto se tebi ne svidja nacin na koji ti pomazemo je samo tvoj problem.

Pa normalno da mi se ne svidjaju jalove rasprave, teoretisanje, zajebavanje I provokacije. Inace ofiro vas je Jablan kada je rekao da je za implementaciju ovog programa potrebno “nesto malo programiranja” pa kad je tako sta cekate? Nemojte se vise brukati nego uradite program.

Citat: Cak smo ti i ostavili link sa dokazima da tvoja kompresija nece raditi.

Link je da izvines samo sa dokazima da niko pre mene nije razmisljao na ovaj nacin.
Citat:
srki: A sta ti predstavlja redni broj fajla? Zar nije to sam taj fajl?


Pa sad I jeste I nije. Jeste jer je svaki fajl “brojac samog sebe” a nije jer postoji I drugi redni broj fajla tj. dekadni zapis pozicije fajla a na njega sam ja konkretno mislio kada sam pominjao redni br. fajla koji se da krace zapisati uz pomoc gorepominjanih koeficijenata.

Citat:
srki
Recimo ako poredjas (u binarnom zapisu brojeve po redu:
000 ( a to je 0 dekadno)
001 ( to je 1 dekadno)
010 (2 dekadno)
011 (3 dekadno)
100 (4 dekadno)
101 (5 dekadno)
...
Ako ti hoces da zapises fajl pod rednim brojem 5 to znaci da moras da upises 101 tj. nista nisi skratio. Ne razumem zasto kazes da bi kompresija radila za 32 bita a ne bi radila za npr. 8 bitova?


Uvek nadjete najgore primere, al ajde:

Odaberemo fajl 101 (5 dekadno). Binarni I dekadni zapis su nam isti jer je broj 5 kodovan sa 3 bita tj. 101. Postoji I treci zapis uz pomoc koeficijenata I izgledao bi ovako: 2^2 +1. On bi zauzimao vise prostora u memoriji I od binarnog I od dekadnog tj. zauzimao bi 15 bita (po 3 bita za svaki znak I broj-I to pod uslovom da smo preostale kombinacije iza 101 iskoristili da kodujemo operatore ^ I +)

Pogledajmo jos jedan mali ali za nijansu normalniji primer gde smo se odlucili da sve brojeve dekadnog sistema kodujemo sa po 4 bita:
Odaberemo fajl 1110. Fajl je 14-ti po redu kad bi ga gledali kao deo izlaznih vrednosti brojaca sa 4 bitna mesta. Redni broj fajla 14 bi nam ovaj put zauzimao vise mesta u memoriji nego u prethodnom primeru tj 8 bita (po 4 bita za jedinicu I cetvorku) tj. vise od binarnog zapisa samog fajla (4 bita). I da ne zaboravimo zapis uz pomoc koeficijenata za br. 14 bi mogao da izgleda ovako: 3^2 +5 sto zauzima 20 bita (po 4 bita za svaki broj I znak) ponovo vise I od binarnog I od dekadnog.

E sad bih iskoristio priliku da ponovim cinjenicu vezanu za zapisivanje brojeva koeficijentima. Dakle na 32 bita se nalazi granica od koje iduci ka visim vrednostima zapisivanje uz pomoc koeficijenata postaje sve racionalnije. Zapis 2^31 (zauzima 32 bita) zauzima vise mesta od niza koji pokusava da opise a zapis 2^33 (takodje zauzima 32 bita) zauzima manje mesta. Sto idemo ka vecim vrednostima zapis je sve racionalniji: 2^64 zauzima 32 bita u odnosu na 64 to je 50%, 2^8000 zauzima 48 bita u odnosu na 8000 to je manje od 0,5% itd.

E sad da predjemo na primer koji bi odgovarao ovoj vrsti kompresije:
Odabracemo fajl sa 8000 jedinica jedna do druge. To je 8000 bita u memoriji. Dekadni zapis je broj sa oko 2500 cifara tj. 20000 bita. Dok je zapis koeficijentima 2^8000 tj. 48 bita. E sad ovaj primer na zalost ne moze da posluzi kao dokaz da zapisivanjem koeficijentima dolazi do kompresije jer je “namesten” tj. bio je dovoljan samo 1 koeficijen za opis rednog broja fajla. Meni je potreban dokaz da bi ovakav nacin zapisivanja bio racionalan za svaki broj iz opsega 0 do 2^8000 -1 a to se moze postici samo odgovarajucim programom. Opet na osnovu toga sto samo 1 koeficijent koji zauzima 48 bita tj. 0,5% duzine niza obuhvata ceo opseg vrednosti koje treba da se opisu sklon sam da verujem da bi I one vrednosti izmedju mogle da se opisu sa relativno malim brojem koeficijenata tj. da mi za bilo koji fajl duzine 8000 bita tj. njegov redni broj nije potrebno vise od 200 sabiraka da bih ga dobio.
Mislim da je stvar jos ociglednija za jos vece fajlove. Ne mogu da zamislim da bi za fajl duzine megabajta bilo potrebno 2000 ili koliko vec sabiraka. Jeste da bi redni brojevi takvih fajlova bili veci ali nisu nip o cemu slozeniji a I vrednosti koeficijenata bi bile vece a citav opseg vrednosti bi se dao opisati sa jednim koeficijentom npr 2^8388608 sto je 72 bita.

Citat:
srki:  Koji je minimalni broj bitova da bi tvoj kompresija kao radila?


To cemo utvrditi eksperimentalnim putem kad budemo imali program. Za sada mogu samo da lupim da je to negde izmedju 32 I 320 bita.

Citat:
srki

Ajde ovako, posto zelis da ti pomognemo posaljes mi 500 evra i ja ti uradim program. Ako kompresija radi za bilo koji fajl ja ti vratim tih 500 evra i odreknem se svih autorskih prava i prava na bilo kakvu buducu zaradu?


Jeste da ovo ne zavredjuje nikakav komentar al cisto da se ne bi ponovilo. Mnogo je kume. Da imam 500 evra odma bi se zenio. Vidim da nisi odavde pa cisto da te upoznam sa prilikama. U mom malom gradicu za 500 evra bi moro da rintam najmanje pola godine I to bez da jedem I pijem. Znaci nista od dogovora. Za sada samo pored uobicajenih malo pivo itd. Nudim 51% akcija od firme koja ce prodavati kompresore. Znaci kontrolni paket akcija na izvolte.

Citat:
Yu Raider

@MajorFatal
Iz iskustva znam da ti verovatno niko nece napisati program, moj savet je da se ipak zavatis malo programiranja.


Poznajuci sopstvene programerske mogucnosti to mi je stvarno zadnja solucija. Ono sto sam pretio da cu da se selim na Delphi, Kylix forum to ja samo zavaravam samog sebe. Jedino se tesim ako ipak dodje do toga da cu mozda nauciti nesto novo a mozda I prokinem pa pocnem da programiram. Vec sam pisao sta me sve nervira u ovoj situaciji ali da dodam jos I ovo: neke kolege ovde pisu programe bukvalno u hodu bez imalo razmisljanja I zapinjanja za njih bi bio cipkin dim da isprogramiraju ovo ali nece. Inace hvala na podrsci.

Citat:
formeye
@MajorFatal
Da li tvrdis da ovom tvojom kompresijom je moguce svaki fajl kompresovati na fajl manji od njega samog?


Ne. Samo fajlove koji su veci od odredjene granicne vrednosti za koju jos ne znam tacno gde je. Dakle kompresija ne bi radila za izuzetno male fajlove.

Citat:
Ivan Dimkovic: Bas tako, eto par nas pokusava da objasni coveku da to ne ide, iz valjda nekog iskustva - pa mora i na plasticni nacin sa "500 eura" ;-)


Od tebe se I ocekivalo da podrzavas ucene. Umesto da si ukorio bezobraznika…

Citat:
srki: Ma moze i za 100€ :-)


da se nadjemo na 20 evra, litar rakije iz Valjevskog kraja i kilo duvan cvaraka?
Nemoj da pricas?
 
Odgovor na temu

Ivan Dimkovic

Administrator
Član broj: 13
Poruke: 16683
*.vodafone-net.de.



+7169 Profil

icon Re: Kompresija random-like podataka11.01.2006. u 23:44 - pre 221 meseci
Nisi ti citao comp.compression izgleda - tvoja teorija je odavno obradjena ;)

http://www.faqs.org/faqs/compression-faq/part1/

Citat:

Yet another popular idea is to split the input bit stream into a sequence of
large numbers, and factorize those numbers. Unfortunately, the number of bits
required to encode the factors and their exponents is on average not smaller
than the number of bits of the original bit stream, so this scheme too cannot
compress all data.
Another idea also related to primes is to encode each
number as an index into a table of primes and an offset relative to the indexed
prime; this idea doesn't work either because the number of bits required to
encode the index, the offset and the separation between index and offset
is on average not smaller than the number of bits of the original bit stream.


Dakle, po 100-ti put - tvoj metod generalno ne radi, moze da upali za par namestenih slucajeva, ali u proseku ce informacija za skladistenje koeficijenata (faktora) biti veca od samog originalnog broja, pod uslovom da skladistis originalni broj na optimalan nacin. Nema potrebe da pravis program za to, postoji matematicki dokaz da je to sto hoces nemoguce.

Cak najobicnija RLE metoda radi bolje za tvoju namestenu sekvencu od 8000 jedinica - RLE metoda daje 16 bita, tvoja metoda daje 48 bita.

Postoje daleko optimalniji nacini reprezentacije originalnog signala, recimo aritmeticko kodiranje - i ako uporedis aritmeticki kodiran signal, sa serijom tvojih "koeficijenata" - doci ces do zakljucka da je aritmeticki kodiran signal uvek kraci i blizi entropiji.

U suprotnom, ti si opet izmislio kompresiju slucajnih podataka - a to smo valjda vec pokrili.

Hajde ovako,

- Pretpostavimo da tvoj metod radi za svaki fajl, tj. dovoljno dugu sekvencu M pseudo-slucajnog sadrzaja - sto je ono sto ti tvrdis.

- Zatim, pretpostavimo da si ti sekvencu M kompresovao vec jednom tvojim metodom i dobio sekvencu N, koja je i dalje duza od tvoje minimalne duzine, i zadovoljava tvoj uslov za kompresiju da je "dovoljno dugacka"

- Sada ces sekvencu N opet pohraniti u tvoj metod, i, po tebi - dobiti sekvencu X, koja je kraca od sekvence N

- Ponavljamo ovo dovoljno veliki broj puta...

Sta dobijamo na kraju? Beskonacnu kompresiju?

Back to the drawing board.

[Ovu poruku je menjao Ivan Dimkovic dana 12.01.2006. u 00:45 GMT+1]
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

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.navman.com.



+3 Profil

icon Re: Kompresija random-like podataka12.01.2006. u 00:27 - pre 221 meseci
Citat:
MajorFatal: da se nadjemo na 20 evra, litar rakije iz Valjevskog kraja i kilo duvan cvaraka?


Jao brate, ma mogu i samo cvarci, za njih bi sada dao sta god da mi trazis!!! Ajde ti mi to nekako posaljes a ja uradim program i ako radi ja se odricem zarade i posaljem ti 10000€. Moze?

Inace nisi lepo razumeo moj primer sa sipanjem vode. To je isto kao da ti neko kaze da ako na neki poseban nacin sipas mozes da uguras 2 litra a ne objasni ti tacno koji je to poseban nacin. Drugim recima ti treba da nam das tacan format kompresovanog fajla. Gde zapisujes broj koeficijenata, koliko bitova to zauzima, koliko bitova ti zauzimaju koeficijenti i kako se to odredjuje itd...Kako da ti pomognemo ako ni ti nisi tacno objasnio kako izgleda taj fajl. Objasni nam cemu ti sluzi svaki bit u tom fajlu.

[Ovu poruku je menjao srki dana 12.01.2006. u 01:28 GMT+1]
 
Odgovor na temu

[es] :: Art of Programming :: Kompresija random-like podataka
(TOP topic, by Gojko Vujovic)
Strane: 1 2 3 4 5 6 ... Dalje > >>

[ Pregleda: 53413 | Odgovora: 127 ] > FB > Twit

Postavi temu Odgovori

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