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

Kompresija random-like podataka 2

[es] :: Art of Programming :: Kompresija random-like podataka 2
(Zaključana tema (lock), by mmix)
Strane: 1 2 3 4

[ Pregleda: 19649 | Odgovora: 71 ] > FB > Twit

Postavi temu

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 Kompresija random-like podataka 202.02.2006. u 14:00 - pre 220 meseci
Jeste I sad neko isprogramira program po mom algoritmu I kako ja to posle da dokazem kad ga vise nema na net-u jer je tema ukinuta. Bolje da ja opet postujem algoritam pa nek stoji tu zlu ne trebalo vec ce se naci neko da ga implementira I tako cu obezbediti sebe, decu, unuke, praunuke ;) Dakle evo mene opet pa niste valjda pomislili da cu odustati zbog male prepreke kao sto je ukidanje teme koju sam pokrenuo? Ako je za utehu ovo je svakako moje poslednje pojavljivanje sa ovom idejom bar u okviru ovog podforuma.

Ovaj put cu biti malo oprezniji pa cu reci da je random-like podatke mozda moguce kompresovati na sledeci nacin: ako imamo fajl (koji hocemo da kompresujemo) duzine n bita I ako napravimo brojac takodje duzine n, koji broji od 0 do 2^n -1 nas fajl bi se nasao na tom brojacu na poziciji m (obzirom da su iste duzine fajl I brojac). Zapis (n,m) bi bio nas kompresovani fajl.
Dekompresija bi se vrsila na sledeci nacin: iz kompresovanog fajla bi procitali n I napravili brojac duzine n. Zatim bi procitali m, pustili brojac u rad I zaustavili kod m-tog fajla po redu. Stanje na brojacu u tom trenutku bi bio nas originalni fajl.
Da bi postojala kompresija m bi moralo biti izrazeno (I zapisano) kao a^b +x tj. a^b + c^d – e^f + .. +x^y + z tj. zbirom koeficijenata (faktora) I drugih brojeva osim 2, na najoptimalniji (najkraci) nacin. Tacna vrednost tog izraza bi se izracunavala tek prilikom dekompresije.
Prilikom kompresije ne bi bilo neophodno (a ni pozeljno) pravljenje brojaca. M se da izracunati na osnovu “tezinskih” koeficijenata direktno iz originalnog fajla. Na primer za fajl 0101 m je : 0*2^3 + 1*2^2 + 0*2^1 + 1*2^0 = 5.

Posto je ovo sajt za pomoc potrebna mi je pomoc I to vrlo specificna: naime potreban mi je neko da implementira ovaj nazovi algoritam I da uz pomoc programa u praksi proveri mogucnost/nemogucnost ovakve vrste kompresije. Sve ostale vrste pomoci su nepozeljne.

I posto sam na ovom sajtu imao I nekih neprijatnih iskustava npr. da ljudi prenebegavaju konkretna I precizna uputstva I pisu o samo njima interesantnim stvarima ovde cu navesti nekoliko vrsta pomoci koje sam svojevremeno dobijao na ovom sajtu a koje ovom prigodom smatram za veoma nepozeljne. Usput cu naravno iskoristiti priliku da jos jednom osvetlim neke momente u vezi sa ovom idejom:

1) Pomoc u vidu skretanja paznje na to da bi ovakav model kompresije bio u suprotnosti sa teorijom informacija od Kloda Shanona. A kako konkretnih dokaza da je teorija informacija pogresna za sada nema I ispravnost mog modela se dovodi u sumnju. Na ovaj argument odgovorili su sami ucesnici foruma skretanjem paznje na postojanje comp.compress fenomena gde se gomila ljudi bavila ovom istom tematikom kojom se I ja bavim do duse za sada bez rezultata, a koji su takodje bili upoznati sa postojanjem teorije informacija. Zagovornici teorije informacija naime kao da ne dozvoljavaju ni mikroskopsku mogucnost da je Shanon na pogresio vec recimo propustio da opise neki modus koji jednostavno nije bio tako ocigledan kao neki koje je opisao I mogucnost da bi razmisljanje u comp.compress stilu moglo konacno posle mnogobrojnih pokusaja da dovede do rezultata. Inace zahvaljuci prepisci koja je vodjena na ovom forumu a koja sada na zalost nije dostupna utvrdili smo da moj pristup problemu 100% nije obradjen na comp.compress stranicama te smatram da je samim tim vredan provere. Meni naravno nece biti zao ako I moj model zavrsi na comp.compress groblju tupavih ideja ali hocu da bude sahranjen dostojanstveno uz implementaciju a ne sa nekim frfljivim dokazom-pretpostavkom da model verovatno ne bi radio.

2) Pomoc u vidu dokaza da model nece raditi ono za sta je namenjen tj. da nece kompresovati podatke. Ovaj dokaz se uglavnom sastojao u besomucnom I na vise nacina dokazivanju da nizovi bita krace duzine od n mogu da daju mnogo manje razlicitih kombinacija od 2^n koliko je potrebno. Kako je imao jako malo veze sa mojim algoritmom ovo je trebao biti neki univerzalan dokaz da je ono sto pokusavam nemoguce izvesti u samoj osnovi I da su svi takvi pokusaji osudjeni na propast, zanemarujuci pri tom cinjenicu da je zapisivanjem uz pomoc koeficijenata (faktora) obezbedjeno visestruko citanje delova nizova bita I samim tim “produzavanje” kracih nizova bita na mozda I duze od n, te takodje cinjenicu da kraci nizovi bita mogu da daju veci broj kombinacija razlicitim nacinom citanja. Koliko god cvrst bio dokaz da je ovo sto pokusavam nemoguce cvrsto stoji I cinjenica da koeficijenti potrebni za opisivanje rednog broja inkrementacije fajla sa povecanjem duzine fajla zauzimaju procentualno sve manje od velicine istog a da sa povecanjem tih rednih brojeva ne raste potreba za vecim brojem koeficijenata jer brojevi postaju samo veci ali ne I slozeniji po bilo kom osnovu te da ih vrednosti koeficijenti takodje prate u pogledu velicine. Te na kraju u cilju skidanja sa vrata onih koji mi dokazuju da n bita tvori 2^n razlicitih kombinacija predlozio sam brojac koji bi malo drugacije radio u njemu bi se kombinacije bita ponavljale ali bi bile razlicito tumacene u zavisnosti od prethodne vrednosti na brojacu. Pocetak brojaca bi izgledao ovako:
0 .. 0
1 .. 1
2 .. 0
3 .. 00
4 .. 0
5 .. 01
6 .. 0
7 .. 10
8 .. 0
9 .. 11 itd… sa dva bitna mesta se moze kodovati 27 kombinacija tj. vise od 16 koliko daju 4 bitna mesta tj. sa nizovima duzine n/2 I manje moze se kodovati vise od 2^n kombinacija. Ukoliko neko bas dobije neodoljivu zelju da mi pomaze na nacin za koji sam rekao da je nepozeljan molim da pocne sa analizom mogucnosti konstrukcije/eksploatacije ovog I ovakvog brojaca posto su ucesnici rasprave vec dva puta uspeli da ga iskuliraju u jednoj drugoj temi.

3) Pomoc u vidu nagovaranja mene da se prihvatim programiranja. Iako sam vec na prvi takav predlog odgovorio opisom svojih programerskih (ne)mogucnosti ova vrsta pomoci se ponavljala I ponavljala. Ocene su se kretale od za to ti je potrebno “ono malo programiranja” do “zillion puta bi isprogramirao I da nijednom nisi seo za tastaturu”. A ja se samo pitam kad je vec tako lako sto neko ne sedne I za jedno prepodne uradi program pa da vec jednom stavimo tacku na ovu saradu. Ako ja kao priucen budem programirao sta da rade programeri? Da se bave zemljoradnjom, zemljoradnici politikom, politicari kuvanjem itd… Ja sam ipak za to da svako radi svoj posao tj. da ovaj program uradi neki profesionalac. Sto je najgore posto ga ipak verovatno niko nece uraditi na kraju cu biti prinudjen da prihvatim ovu vrstu pomoci.

4) Pomoc u vidu dobrodusnog nagovaranja da svoj algoritam isprobam “na papiru” uz uveravanje da cu tako najpre videti da je nemoguce. Iako sam I na ovakvu prvu ponudu odmah odgovorio I ova pomoc se ponavljala I ponavljala. 15-tak koeficijenata (faktora) po 30-50 bita u proseku cini 450-750 bita za pocetak mogucnosti kompresije. Za nizove krace od te vrednosti nema smisla da proveravam jer sigurno nece raditi, za nizove duze od 450 bita jednostavno nema sanse da proverim na papiru. Moj digitron se zakucava vec kod vrednosti 2^33 I ne moze da prikaze vece vrednosti a ovde bi racunicu trebao da pocnem sa 2^450 + …Ako bi mi I poslo za rukom da nabavim neki softverski digitron koji radi sa tako velikim vrednostima najdalje dokle bih stigao je da rucno izracunam vrednost m za dati niz, ostao bi problem odredjivanja najoptimalnijih faktora za koji ne samo da ne znam kako bi se to radilo vec sam I prilicno uveren da za tako velike brojeve to moze da se odradi samo programski a nikako rucno tj. na papiru.
5) Pomoc u vidu poredjenja ovoga sto ja pokusavam sa raznim drugim ocigledno nemogucim stvarima: “kao staviti kilo u pola kile”, “kao sipati dva litra vode u flasu od litar”, “izvrsiti trisekciju ugla lenjirom I sestarom”, “predstaviti spil
karata jednom kartom”. Da se ne bi mucili da smisljate evo vam jos jedno poredjenje:”Jednako nemoguce kao okrenuti gravitaciju uzbrdo” to je naime odgovorio profesor Nikoli Tesli na neko njegovo pitanje valjda o mogucnosti konstrukcije elektromotora uz primenu obrtnog magnetnog polja. Mislim da su mnogo vise literature (nego sto je jedna teorija informacija) I mnogo veci naucni umovi stajali protiv mogucnosti dobijanja energije putem cepanja atoma pa je jedna grupa naucnika ne obaziruci se na ocigledne dokaze protiv ipak uspela to da uradi. Tipa koji je izmislio televiziju izbacili su iz patentnog zavoda sa recima “tu je neki ludak koji tvrdi da je sem zvuka I sliku moguce prenositi na daljinu”. Nije mi naravno ni na kraj pameti da se poredim sa ovako velikim ljudima vec samo da ilustrujem da je mnogo puta nesto dokazano nemoguce ipak postajalo moguce istorija je puna primera.

6) Pomoc u vidu zbijanja urnebesnih sala na moj racun, kao I na racun modela koji sam predlozio. No koment.
7) Pomoc u vidu napucavanja ljudi koji su moj model hteli da stave na proveru. No koment.

Posto smo videli sta sve nije pomoc po mom misljenju jos jednom cu istaci sta jeste:
Implementacija algoritma tj. potpuno funkcionalna verzija programa bi bila od velike pomoci.

Ovde cu iskoristiti priliku da odgovorim jedinom coveku koji je zasluzio bilo kakav odgovor sa prethodnog jam-sesiona:

Citat:
srki Pa napisi mi tacno kako to da uradim. Koji bajt (ili niz bajtova) zelis da ti predstavlja separator?


Ovo je samo predlog: koduj sa po 4 bita deset decimala, cetri osnovne racunske operacije, “^” I separator npr. /. Koji niz bitova (a ne bajtova) od mogucih 16 ce ti predstavljati separator (/) sam odluci. Inace ovime bi trebao da se bavis ti a ne ja. I uopste uzev poceo si vec da me pitas neke stvari koje se ticu programiranja a ja sa istim nemam blage veze tako da je mozda najbolje da sa algoritmom odes na podforum koji se bavi resavanjem problema iz tvog omiljenog programskog jezika pa da tamo pitas sve sto te zanima.

Posto je I pored mnogobrojnih upozorenja moguce sve I svasta na ovom forumu molio bih moderatora da ovaj put radi svoj posao kako treba tj. blagovremeno a ne kad voda vec dodje do guse (tj do njega) I na pravi nacin tj. brisanjem postova koji se ne slazu sa pravilima ovog foruma a ne brisanjem teme. Mada ja se iskreno nadam da ovaj put nece biti neke velike prepiske jer sam pokusao da je ogranicim.

Jos jednom cu ponoviti sustinu ovog posta ako nemate ili ne radite na implementaciji gorenavedenog algoritma molim vas da se I ne javljate tj. ne pomazete mi na bilo koji drugi nacin. Hvala.

Nemoj da pricas?
 
0

drstorm
Milos Andjelkovic
ETF

Član broj: 56314
Poruke: 3
*.ADSL.neobee.net.

Jabber: drstorm@jabber.sk
Sajt: www.softplus.co.yu


Profil

icon Re: Kompresija random-like podataka 222.05.2006. u 19:28 - pre 217 meseci
Koliko shvatam, ti si jako tvrdoglav dečko. Na prethodnoj temi o "beskonačnoj kompresiji" sam video da ti jednostavno ne shvataš zašto je to NEMOGUĆE.
Bez obzira što to ne smatraš za pomoć, pokušaću da ti objasnim.

Ako imaš fajl "11101001".
n=8
m=233

Tačno je da se ovaj fajl može ovako zapamti, međutim, najefikasniji način zapisa brojeva na računaru je binarni (ne znakovni, tj. ne pises u fajl znakove koji predstavljaju decimalne cifre i slično). Tako da ako hoćemo da upišemo broj 233 u "kompresovan" fajl, upisaćemo njegovu binarnu reprezentaciju: "11101001". Kao što vidiš, to je sadržaj samog fajla. Prema tome broj m ne treba računati. Broj m je sam sadržaj fajla. Jedina ušteda postoji kod fajlova koji POČINJU velikim brojem nula, u SVIM ostalim slučajevim "kompresovan" fajl će biti veći od originalnog.

Što se tiče alternativnih reprezentacija brojeva koje predlažeš (pomoću eksponenta), one neće pomoći, jer će eksponent zauzimati više mesta nego sam fajl u binarnom obliku. Međutim reprezentacija broja m je pravi problem. Broj m je JEDNAK sadržaju originalnog fajla, pa je smišljanje našina reprezentacije zapravo kompresija. To je ono što, u suštini rade sve današnje (i buduće) kompresije.

Da li shvataš o kolikom brojevima se radi? Ako imamo fajl od 1MB, to je 2^8388608, što je stvarno mnogo. Da li shvataš da ako bi generisao sve fajlove od, recimo 5MB dobio bi svu muziku ikada napravljenu i svu koja će ikada biti napravljena u svim formatima ikada. Takođe, će tu biti i sve knjige na svim jezicima, sve fotografije i sve ostalo što može da stane na 5 MB.

Ako i dalje ne shvataš, bolje bi ti išlo plivanje.
Life is a dream...
 
0

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
213.244.208.*



+557 Profil

icon Re: Kompresija random-like podataka 204.06.2006. u 11:39 - pre 216 meseci
Izvini sto ti odgovaram sa ovolikim zakasnjenjem, bio sam pretrpan obavezama ovih dana.

Citat:
drstorm: Koliko shvatam, ti si jako tvrdoglav dečko.

Koliko shvatam to je offtopic.

Citat:
drstorm: Na prethodnoj temi o "beskonačnoj kompresiji" sam video da ti jednostavno ne shvataš zašto je to NEMOGUĆE.

Prethodna tema o "beskonačnoj kompresiji" je neprecizna + verovatno pogresna u samoj svojoj postavci tako da komotno mozes da je zaboravis.

Citat:
drstorm: Bez obzira što to ne smatraš za pomoć, pokušaću da ti objasnim.
Ako imaš fajl "11101001".
n=8
m=233…


Ma neee, cini ti se:
1)
Citat:
MajorFatal: 4) Pomoc u vidu dobrodusnog nagovaranja da svoj algoritam isprobam “na papiru”…
n = 8 da se nisi pretrg’o, probaj sledeci put sa n = 750. Naravno za to ce ti trebati odgovarajuci program.
2)
Citat:
MajorFatal: Ukoliko neko bas dobije neodoljivu zelju da mi pomaze na nacin za koji sam rekao da je nepozeljan molim da pocne sa analizom mogucnosti konstrukcije/eksploatacije ovog I ovakvog brojaca posto su ucesnici rasprave vec dva puta uspeli da ga iskuliraju u jednoj drugoj temi.

3)
Citat:
MajorFatal: …ako nemate ili ne radite na implementaciji gorenavedenog algoritma molim vas da se I ne javljate tj. ne pomazete mi na bilo koji drugi nacin. Hvala.


Koje ti se od ovih pravila najvise dopalo sto si ga prekrsio I zasto? Kako si se osecao tom prilikom?

Citat:
drstorm: Tačno je da se ovaj fajl može ovako zapamti, međutim, najefikasniji način zapisa brojeva na računaru je binarni (ne znakovni, tj. ne pises u fajl znakove koji predstavljaju decimalne cifre i slično).

Kako kad I kako koji fajl/broj. Npr. izracunaj vrednost izraza koji se pojavljuje pri kraju tvoga posta 2^8388608 dobices broj koji se sastoji od oko 2,5 miliona cifara. Hajde sad taj broj da zapisemo na najefikasniji nacin. Ti odaberi zapisivanje bitima za koje tvrdis da je najefikasniji nacin I rezultat ce biti oko 20 mil. bita u memoriji (2,5 mil. cifara * 8 bita). Ja cu odabrati zapisavanje koeficijentima I zapisacu samo 2^8388608 sto je zapis koji zauzima 72 bita u memoriji (9 karaktera po 8 bita).

Citat:
drstorm: Što se tiče alternativnih reprezentacija brojeva koje predlažeš (pomoću eksponenta), one neće pomoći, jer će eksponent zauzimati više mesta nego sam fajl u binarnom obliku.

Pogledaj prethodni primer I sve ce ti biti jasno. Ipak, upravo ovako je pocela I krlp(1) rasprava koju ovom prilikom (malo skracenu) prilazem u attachmentu. Verujem da si imao priliku da to citas da do ovog tvog posta ne bi ni doslo posto se neke stvari odatle ponavljaju I ovde.

Citat:
drstorm: Jedina ušteda postoji kod fajlova koji POČINJU velikim brojem nula, u SVIM ostalim slučajevim "kompresovan" fajl će biti veći od originalnog.

KADA? Kada jedina usteda postoji kod fajlova koji pocinju velikim brojem nula? Kada ti kazes: zapamticu samo zadnji deo fajla, dodacu informaciju “sve ispred su nule” i fajl je te I te duzine (n)? Pa ces dobiti kompresiju? U tom slucaju sta fali fajlovima koji pocinju velikim brojem jedinica? Ili dugackim nizom naizmenicno 0 I 1? Ili bilo kojim grugim uniformnim nizom? Ili koji se zavrsavaju tako? Ili koji takav sastav imaju u sredini, pred kraj ili odmah posle random like pocetka? Nista im ne fali na sve se da primeniti isti system kompresije ali je taj sistem statisticki a kako mnogo vise ima fajlova koji su celom svojom strukturom random like ja tim sistemom nisam zadovoljan I tragam za nekim drugacijim I boljim.

Citat:
drstorm: Da li shvataš o kolikom brojevima se radi? Ako imamo fajl od 1MB, to je 2^8388608, što je stvarno mnogo.

Moj problem je u tome sto sam ja jednom prilikom nacuo da je osnovna namena racunara da barataju velikim brojevima umesto nas.

Citat:
drstorm: Da li shvataš da ako bi generisao sve fajlove od, recimo 5MB dobio bi svu muziku ikada napravljenu i svu koja će ikada biti napravljena u svim formatima ikada. Takođe, će tu biti i sve knjige na svim jezicima, sve fotografije i sve ostalo što može da stane na 5 MB.

Sve fotografije ikad? Ako je svemir beskonacan a trebalo bi da jeste kako moze biti opisan konacnim skupom podataka ma kako potonji bio velik (2^5Mb)?

Citat:
drstorm: Ako i dalje ne shvataš, bolje bi ti išlo plivanje.

Offtopic.


Citat:
MajorFatal: …ako nemate ili ne radite na implementaciji gorenavedenog algoritma molim vas da se I ne javljate tj. ne pomazete mi na bilo koji drugi nacin. Hvala.

Citat:
MajorFatal: …ako nemate ili ne radite na implementaciji gorenavedenog algoritma molim vas da se I ne javljate tj. ne pomazete mi na bilo koji drugi nacin. Hvala.

Citat:
MajorFatal: …ako nemate ili ne radite na implementaciji gorenavedenog algoritma molim vas da se I ne javljate tj. ne pomazete mi na bilo koji drugi nacin. Hvala.

Hvala.

Nemoj da pricas?
Prikačeni fajlovi
 
0

bojan_bozovic

Član broj: 29028
Poruke: 3292
*.pat-pool.le.sbb.co.yu.

Sajt: angelstudio.org


+392 Profil

icon Re: Kompresija random-like podataka 204.06.2006. u 12:59 - pre 216 meseci
Je li, Major Fatal, zasto ga sam ne implementiras, jer, ocigledno, niko ovde nije zainteresovan (sto si mogao videti u prethodnoj temi koju si postavio), umesto da smaras? Dalje, zasto bi ti iko implementirao algoritam za *** DZABE ***, a ako hoces platiti, postuj u "IT Berza Poslova" forumu. Platis, napisu ti program bez obzira kakav je algoritam, i gotovo.
 
0

BytEfLUSh
Neven Pintarić
Nano-mage Engineer, Slave SysAdmin
Sombor

Član broj: 21153
Poruke: 5499
*.129.nat-pool-bgd.sbb.co.yu.



+14 Profil

icon Re: Kompresija random-like podataka 205.06.2006. u 08:44 - pre 216 meseci
Neću se[/ upuštati u (ne)ispravnost tvog načina razmišljanja što se tiče te "kompresije", samo bih ti skrenuo pažnju na jednu stvar.

Citat:
MajorFatal: Jeste I sad neko isprogramira program po mom algoritmu I kako ja to posle da dokazem kad ga vise nema na net-u jer je tema ukinuta. Bolje da ja opet postujem algoritam pa nek stoji tu zlu ne trebalo vec ce se naci neko da ga implementira I tako cu obezbediti sebe, decu, unuke, praunuke ;)

Algoritam više nije tvoj. To što si ga objavio na netu upravo znači da daješ drugima mogućnost da ga koriste... Nisi patentirao svoj algoritam, već si ga prvo ponudio javnosti. Sorry but jbg...


EDIT:

Tek sad sam ovo video...
Citat:
Sve fotografije ikad? Ako je svemir beskonacan a trebalo bi da jeste...

Otkud znaš da jeste? I dalje se polemiše oko toga, tako da osim ako imaš nekih konkretnih dokaza - nemoj da iznosiš dezinformacije na forum.


[Ovu poruku je menjao BytEfLUSh dana 05.06.2006. u 14:32 GMT+1]
Putuj planeto, super smo se družili
nama je lepo, taman kako smo zaslužili!
 
0

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
213.244.208.*



+557 Profil

icon Re: Kompresija random-like podataka 205.06.2006. u 15:07 - pre 216 meseci
Citat:
bojan_bozovic: Je li, Major Fatal, zasto ga sam ne implementiras, jer, ocigledno, niko ovde nije zainteresovan (sto si mogao videti u prethodnoj temi koju si postavio), umesto da smaras?

Citat:
MajorFatal: 3) Pomoc u vidu nagovaranja mene da se prihvatim programiranja...

Citat:
bojan_bozovic:  Platis, napisu ti program bez obzira kakav je algoritam, i gotovo.

Razmislicu.

@bytEfLUSh
Onaj prvi citat to je trebala biti nesto kao sala na sopstveni racun.
Citat:
BytEfLUSh: Otkud znaš da jeste? I dalje se polemiše oko toga, tako da osim ako imaš nekih konkretnih dokaza - nemoj da iznosiš dezinformacije na forum.

Ne znam.
Citat:
MajorFatal: Ako je svemir beskonacan a trebalo bi da jeste...

Nemoj da pricas?
 
0

BytEfLUSh
Neven Pintarić
Nano-mage Engineer, Slave SysAdmin
Sombor

Član broj: 21153
Poruke: 5499
*.129.nat-pool-bgd.sbb.co.yu.



+14 Profil

icon Re: Kompresija random-like podataka 205.06.2006. u 15:29 - pre 216 meseci
Citat:
MajorFatal: Onaj prvi citat to je trebala biti nesto kao sala na sopstveni racun.

Svaka čast na argumentovanom odgovoru. U svakom slučaju, mislim da ću ti ukrasti algoritam za jedan svoj program jer, vidiš, nisi ga patentirao... =)

Što se svemira tiče - sad vidiš da ti kontraargument ne drži vodu.

Putuj planeto, super smo se družili
nama je lepo, taman kako smo zaslužili!
 
0

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: Kompresija random-like podataka 220.06.2006. u 13:53 - pre 216 meseci
Gledam ovu temu odavno, i više nisam mogao da izdržim a da ne odgovorim...

MajorFatal: osnovni problem sa tvojim "algoritmom" je to što on NE POSTOJI. Naime cela tvoja rasprava je bespredmetna. Tvoj takozvani brojač je u stvari sam originalni falj koji želiš da komprimuješ, što je već pedesetak ljudi već primetilo. Ono što ti želiš je da nekakav sadržaj FAKTORIZUJEŠ! Teoretski, neki broj bi se mogao predstaviti kao suma faktora stepenovanih na neki stepen, ali kao što su svi primetili, slučajne podatke ne možeš komprimovati.
Ono što je problem u "tvom" pristupu problemu je što ne daješ način na koji bi se došlo do tih faktora (brojač je samo bacanje prašine u oči). Nalaženje svih faktora nekog broja sa n (binarnih) cifara, pa onda traženje najkraćeg ili dovoljno kratkog zapisa lako može da ispadne NP problem (ne polinomijalni). Zato za rešavanje takvog problema u opštem slučaju (za dovoljno veliko n) ne može nikada da se završi, tj. takav problem je nerešiv u nekom konačnom vremenskom intervalu.
 
0

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.ADSL.neobee.net.



Profil

icon Re: Kompresija random-like podataka 220.06.2006. u 15:15 - pre 216 meseci
On moze da se zavrshi u nekom konachnom vremenskom periodu, ali je taj period dovoljno veliki da se ne isplati :)
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
0

yooyo

Član broj: 4891
Poruke: 1101
195.252.89.*



Profil

icon Re: Kompresija random-like podataka 221.06.2006. u 21:04 - pre 216 meseci
@MajorFatal:

Interesantna ideja... Reci mi da li bi bilo moguce komprimovati tvojom metodom file koji je vec komprimovan tvojom metodom? Ako je moguce koliko bi se smanjio, a ako nije moguce, zasto?

 
0

toroman
Srećko Toroman
www.wowd.com
Beograd / Banja Luka

Član broj: 52673
Poruke: 159
*.dialup.blic.net.

Sajt: toroman.wordpress.com


Profil

icon Re: Kompresija random-like podataka 223.06.2006. u 01:18 - pre 216 meseci
Ovo je definitivno najgluplja tema na čitavom ES forumu.

Sretno ...
Programeri su odgovorili na Hamletovo pitanje "Biti il ne biti?" :
0x2B | ~0x2B = 0xFF
(kao ono - ff - teško pitanje!)
 
0

peka
Beograd

Član broj: 3947
Poruke: 124
..taman-bg.customer.sbb.co.yu.



+2 Profil

icon Re: Kompresija random-like podataka 229.06.2006. u 01:12 - pre 216 meseci
Ali ovaj lik je toliko uporan da je to nevjerovatno...

I sam si vec rekao da ne znas da programiras. Zasto onda ne vjerujes ljudima (i to ne jednom, nego gomili) koji ZNAJU da programiraju i posto znaju o cemu se radi, ZNAJU da je to NEMOGUCE?
IRC is just multiplayer notepad.
 
0

NikolaVeber
NikolaVeber
neradnik na porodiljskom bolovanju
Karlsruhe

Član broj: 5115
Poruke: 1254
*.sap-ag.de.

Jabber: nikolaveber@jabber.org
ICQ: 121532865


Profil

icon Re: Kompresija random-like podataka 229.06.2006. u 09:04 - pre 216 meseci
Evo dva pitanja na koje bi trebalo odgovoriti:

- koliki je faktor kompresije
- koliko je algoritam zahtevan (u funkciji vremena i memorije)

Pomenute vrednosti treba izracunati za best/worst case, kao i dati procenu gde lezi "srednja vrednost".

I onda uporediti to sa postojecim algoritmima za kompresiju. Ako se matematicki dokaze da je toliko bolje, sigurno ce svi skeptici zacutati, a i neko ce se sigurno naci da to iskodira.
Pop Servis "Paradise Tours"
Java User Group Karlsruhe
IT Dan - Srbija

Officer, I saw the driver who hit me - his name was Johnny Walker.
 
0

--SOULMaTe--
Nemanja Skoric
Novi Sad

Član broj: 1464
Poruke: 173
..mtsns-ns.customer.sbb.co.yu.



Profil

icon Re: Kompresija random-like podataka 229.06.2006. u 22:58 - pre 216 meseci
zasto se ova diskusija jos uvek vodi?

eh da imam power of lock
Don’t do drugs, sleep deprivation is better.
 
0

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
213.244.208.*



+557 Profil

icon Re: Kompresija random-like podataka 201.07.2006. u 23:42 - pre 215 meseci
Citat:
djoka_l: Tvoj takozvani brojač je u stvari sam originalni falj koji želiš da komprimuješ, što je već pedesetak ljudi već primetilo.


Nije tako. Fajl odgovara samo jednom stanju na brojacu a ne celom brojacu.

Citat:
djoka_l: Teoretski, neki broj bi se mogao predstaviti kao suma faktora stepenovanih na neki stepen, ali kao što su svi primetili, slučajne podatke ne možeš komprimovati.


Teoretski i prakticno ova tvoja recenica ima ozbiljan problem sama sa sobom. Iz prvog dela recenice nikako ne proizilazi drugi.

Citat:
djoka_l: Ono što je problem u "tvom" pristupu problemu je što ne daješ način na koji bi se došlo do tih faktora (brojač je samo bacanje prašine u oči).


Nijednom recju ili recenicom do sada nisam brojac predlagao kao nacin dolazenja do faktora, vec sam vise puta naglasio da nemam pojma kako bi se faktorizacija radila ni kako se inace radi I da ocekujem da taj problem resi neko ko zna kako se taj problem reseva ili kako bi ga trebalo resavati. I bio bih veoma zahvalan ako bi neko prilozio neki efikasan algoritam za faktorizaciju brojeva ili bar neki link.

Citat:
djoka_l: Nalaženje svih faktora nekog broja sa n (binarnih) cifara, pa onda traženje najkraćeg ili dovoljno kratkog zapisa lako može da ispadne NP problem (ne polinomijalni). Zato za rešavanje takvog problema u opštem slučaju (za dovoljno veliko n) ne može nikada da se završi, tj. takav problem je nerešiv u nekom konačnom vremenskom intervalu.


Na ovo ti je odgovorio RooTeR:

Citat:
RooTeR: On moze da se zavrshi u nekom konachnom vremenskom periodu, ali je taj period dovoljno veliki da se ne isplati :)


A ja opet za sada necu da raspravljam o isplativosti ni vremensko memorijskoj ni ekonomskoj ni bilo kojoj drugoj.

Citat:
yooyo: Interesantna ideja... Reci mi da li bi bilo moguce komprimovati tvojom metodom file koji je vec komprimovan tvojom metodom? Ako je moguce koliko bi se smanjio, a ako nije moguce, zasto?


Interesantno pitanje…Reci mi zasto sam nisi odgovorio na njega? Posto bi rezultujuci fajl posle kompresije bio opet random like structure naravno da bi opet mogao da se komprimuje, ali koliko puta bi to bilo izvodljivo, dokle bi bilo racionalno I imalo smisla te kada bi prestala kompresija a pocela ekspanzija o svemu tome detaljnije mozes da procitas ako preuzmes prikaceni fajl koji sam ljubazno prilozio uz drugu poruku u okviru ove teme. Tu ces videti da sam na ovo tvoje pitanje vec odgovarao i to u dva navrata: 7.01.2006. i 13.01.2006.
I kad si vec tu ostao sam ti duzan odgovor sa prethodne sesije (takodje u prikacenom fajlu). Naravno da se ne ljutim zbog poslovice o magarcu. Evo I ja sam se setio jedne: ”Ne bacaj bisere pred svinje”. Ona takodje nije da bi blo koga uvredila I takodje se nadam da se niko nece uvrediti.
Sto se tice “ociglednog primera” ocigledno je da ne zadovoljava osnovni uslov da bi ova kompresija bila moguca tj. ne sadrzi dovoljan broj bitova.
btw. lepa paznja od tebe sto si potrudio da napravis onakav fajl bas je onako random like sa slucajnim rasporedom nola I jedinica. Ali nisi morao toliko da se trudis. Kao sto mozda nisi primetio kod ovakvog nacina kompresije osnovnu ulogu bi igrala pozicija fajla na brojacu sasvim je svejedno da li je vise ili manje random ili uniforman. Mogao bi da bude I vise uniforman ali na losijoj poziciji za faktorisanje pa bi stepen kompresije kod njega bio manji nego kod nekog fajla koji je vise random ali je na pristupacnijoj poziciji. S tim u vezi moguce da sam pogresio (ne bi mi bilo prvi put) moguce da bi bolji naslov za temu bio “kompresija I random like podataka”.

Citat:
toroman: Ovo je definitivno najgluplja tema na čitavom ES forumu.


Hvala! Volem da sam naj u bilo kom smislu I takve pohvale mi uvek prijaju. Nego trebao si I obrazloziti: Najgluplja sama po sebi ili zato sto se glupaci javljaju?

Citat:
toroman: Sretno ...


E pa sad ovo vec nije lepo sto mi radis. G0vno ti pod nos da me ne ureknes ;)

Citat:
peka: Ali ovaj lik je toliko uporan da je to nevjerovatno...


A sta bi tek rekao za likove koji uporno konstatuju kako sam ja uporan???

Citat:
peka: I sam si vec rekao da ne znas da programiras. Zasto onda ne vjerujes ljudima (i to ne jednom, nego gomili) koji ZNAJU da programiraju i posto znaju o cemu se radi, ZNAJU da je to NEMOGUCE?


A sta je to sto je nemoguce? Ako mislis da je nemoguce kompresovati podatke po modelu koji sam predlozio mozda si u pravu a mozda I nisi jos nista nije dokazano. Medjutim izvesno je da je moguce isprogramirati program koji bi to proverio a ja sam samo tu uslugu I trazio ovde. Inace stvari su se promenile (da se pohvalim) ja poceo da programiram, uskoro mi vise nece trebati vasa pomoc.

Nemoj da pricas?
 
0

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
213.244.208.*



+557 Profil

icon Re: Kompresija random-like podataka 201.07.2006. u 23:44 - pre 215 meseci
Citat:
NikolaVeber: Evo dva pitanja na koje bi trebalo odgovoriti:
- koliki je faktor kompresije


Mislim da bi ispravnije bilo pitati “koliki bi bio factor kompresije kada bi kompresija uopste postojala" jer ispravnost ili ostvarivost ovog modela jos nije dokazana. Ipak da ti odgovorim: Faktor kompresije po ovakvom modelu bi jako varirao od fajla do fajla. Ima fajlova cija bi pozicija na brojacu mogla biti opisana jednim jedinim eksponentom nekog celog broja I tu bi factor kompresije naravno bio enormno veliki mnogo veci nego kod klasicnih nacina kompresije. Problem je u tome sto bi takvi fajlovi bili u veoma velikoj manjini u odnosu na ukupan broj fajlova te takodje to sto bi se “odmicuci” od takvih optimalnih pozicija broj faktora neophodnih za opisivanje pozicije fajla na brojacu prilicno brzo povecavao. Ako tome jos dodas da nije uopste izvesno da bi za bas sve fajlove bilo moguce naci odgovarajuce optimalne faktore tj. one koji bi u memoriji zauzimali manje prostora nego sam originalni fajl tj. da ova kompresija mozda ne bi mogla da kompresuje bas sve podatke (osim onih veoma malih fajlova koje ne bi mogla da kompresuje po drugom uslovu) dolazis do veoma neizvesne racunice koja sem sto je neizvesna uz to jos I ne postoji jer se niko do sada nije ozbiljno pozabavio njome. Da skratim precizan I dobro obrazlozen odgovor na to pitanje bi ujedno I bio odgovor na to za koje I kakve fajlove bi ovakav nacin kompresije bio racionalan.

Citat:
NikolaVeber: - koliko je algoritam zahtevan (u funkciji vremena i memorije)


Skoro nimalo. Zahteva nesto malo vremena jednog prosecno sposopnog programera uz odgovarajucu upotrebu njegove memorije. E da u stvari hteo si da pitas koliko bi program uradjen po ovom algoritmu bio zahtevan. Osim sto ce I tu da zavisi od toga ko ga uradi izgleda prilicno mnogo. Pocev od baratanja veoma velikim brojevima pa do faktorizacije istih. Zato bi prvo morao da se uradi program koji barata sa nesto skromnijim vrednostima tipa velicina fajla ~ 1000 bita.

Citat:
--SOULMaTe--: zasto se ova diskusija jos uvek vodi?


Uglavnom zato sto se svako malo pojavi neko kao ti prokomentarise nesto I potera diskusiju napred a onda se jos I pita zasto se ista vodi. “Diskusija” je bas lepo bila potonula sa prve na one manje vidljive strane ES-a kad ju je nicim izazvan drstorm izvukao iz prasine. Ako sam njega i mogao da razumem jer mu nije bila pristupacna prethodna polemika na ovu temu vas ostale a pogotovu vas offtopic ostale stvarno ne mogu. Onaj “nije mogao da izdrzi”, onaj drugi misli da je tema najgluplja, ti se pitas nesto naglas I postujes svoje zelje u vezi lockovanja + meni moderator (necu ga imenovati zna se koji je) zabranio da pisem ono “Ako ne radite na implementaciji…” kao ne mogu da odredjujem sta ce ko da pise I eto ti zasto se diskusija vodi.

Citat:
--SOULMaTe--: eh da imam power of lock


A ja power of delete. Ma nemoj da zalis evo meni je kukao jedan moderator posao uopste nije neki. Umesto da cita samo ono sto ga zanima mora da cita sve. Ti naravno kao I svi ostali imas power of skip-ower temu za koju mislis da nije vredna paznje kao I power of edit I delete nad svojim postom. Ali ne vredi mi sto ovo pisem ko da gledam kako je krenulo veoma uskoro ce se pojaviti offtopic manijaci koji ce da uniste I ruiniraju temu a mene da sprece da na brz nacin saznam jos po nesto sto bi me zanimalo u vezi onog sto stoji u naslovu teme. Pa neka pomoci cu vam. Evo sta se jednom desilo. Moja baba Mileva (bog da joj dusu prosti) je pravila ustipke. Svi ustipci su bili lepo nadosli I rumeni a samo je jedan bio bled I nacisto spljeskan. Kad smo je pitali sto je ovaj takav ispricala nam je da nikako nije hteo da se okrene na drugu stranu da se isprzi. Ona ga okrene a on se opet prevrne na stranu na kojoj je vec bio gotov. E onda ona ona lepo uzme I ispljeska ga takoreci kompresuje pa se vise nije prevrtao. Eto uspesno sam offtopic izlaganje povezao sa temom pa cak ni autor teme ne moze da se ljuti na mene. Otvaram ovu temu za sva vasa slicna iskustva. Pisite o tome kako vase babe prave ustipke. Ne bi bilo lose ni da se prilozi neki recept (algoritam takoreci) za pravljenje ustipaka. Povlacim I sve za sta sam vas zamolio u prvom postu. Obavezno mi posaljite bar jedan post u kome pise da je ovo sto predlazem u suprotnosti sa teorijom informacija, jedan gde pise da je nemoguce, I jedan da algoritam proverim na papiru. Stvarno covece kao sto mozes da editujes svoj post tako bi trebalo da mozes da editujes I svoju temu jer kao autor teme valjda najbolje znas I sta si hteo da pitas I ko ti je na to pitanje odgovorio a ko nije. Ne verujem da bi mi ovaj predlog prosao na “uredite ovaj forum” diskusiji. Lock ili delete sasvim svejedno verujem da ce ova tema veoma uskoro da zavrsi svoju karijeru.

Nemoj da pricas?
 
0

yooyo

Član broj: 4891
Poruke: 1101
195.252.89.*



Profil

icon Re: Kompresija random-like podataka 202.07.2006. u 22:35 - pre 215 meseci
Ajde krenucu redom:
Citat:
Ovaj put cu biti malo oprezniji pa cu reci da je random-like podatke mozda moguce kompresovati na sledeci nacin: ako imamo fajl (koji hocemo da kompresujemo) duzine n bita I ako napravimo brojac takodje duzine n, koji broji od 0 do 2^n -1 nas fajl bi se nasao na tom brojacu na poziciji m (obzirom da su iste duzine fajl I brojac). Zapis (n,m) bi bio nas kompresovani fajl.


Kada tvoj brojac nadje vrednost originalnog fajla on u stvari predstavlja sam file. Uzecu tvoj primer... Imamo file 0101 i 4-bitni brojac. Brojac ces povecati 5 puta i dobice vrednost identicnu originalnom fajlu. Binarni zapis broja 5 je 0101. Zapisacemo kompresovani file u obliku (4,5) koji je veci od originalnog fajla za duzinu potrebnu da se broj 4 upise u nekom obliku.

0000 - pocetno stanje
0001 - povecavamo brojac za 1 (1. put)
0010 - povecavamo brojac za 1 (2. put)
0011 - povecavamo brojac za 1 (3. put)
0100 - povecavamo brojac za 1 (4. put)
0101 - povecavamo brojac za 1 (5. put)
i sada je brojac identican originalnom fajlu... zar ne?

Citat:
Dekompresija bi se vrsila na sledeci nacin: iz kompresovanog fajla bi procitali n I napravili brojac duzine n. Zatim bi procitali m, pustili brojac u rad I zaustavili kod m-tog fajla po redu. Stanje na brojacu u tom trenutku bi bio nas originalni fajl.


Tacno... ali vrednost m iz kompresovanog fajla je originalni file, tako da nema potrebe da se broji od pocetka.

Ukratko, nema potrebe da koristis nikakav brojac jer je BINARNA reprezentacija takvog brojaca IDENTICNA originalnom fajlu.

Dalje... ti predlazes kompresiju brojaca. Da vidimo sta predlazes:

Citat:
Da bi postojala kompresija m bi moralo biti izrazeno (I zapisano) kao a^b +x tj. a^b + c^d – e^f + .. +x^y + z tj. zbirom koeficijenata (faktora) I drugih brojeva osim 2, na najoptimalniji (najkraci) nacin. Tacna vrednost tog izraza bi se izracunavala tek prilikom dekompresije.
Prilikom kompresije ne bi bilo neophodno (a ni pozeljno) pravljenje brojaca. M se da izracunati na osnovu “tezinskih” koeficijenata direktno iz originalnog fajla.


Ti predlazes da se m (tj. originalni file) predstavi kao izraz a^b + c^d + ... + z. Prvo pitanje je sa koliko bita bi predstavio a, b, c, d, ... z? Ukratko.. moralo bi da zbir duzina u bitovima svih koeficijenata bude kraca od n (tj. duzine fajla). Dalje... vrednost a^b ce upaliti neke bitove ali zato sabiranje rezultata sa c^d moze da dovede do paljenja nekih drugih bitova ali isto tako i gasenje vec postojecih (upaljenih) bitova.

Citat:
Te na kraju u cilju skidanja sa vrata onih koji mi dokazuju da n bita tvori 2^n razlicitih kombinacija predlozio sam brojac koji bi malo drugacije radio u njemu bi se kombinacije bita ponavljale ali bi bile razlicito tumacene u zavisnosti od prethodne vrednosti na brojacu. Pocetak brojaca bi izgledao ovako:
0 .. 0
1 .. 1
2 .. 0
3 .. 00
4 .. 0
5 .. 01
6 .. 0
7 .. 10
8 .. 0
9 .. 11 itd… sa dva bitna mesta se moze kodovati 27 kombinacija tj. vise od 16 koliko daju 4 bitna mesta tj. sa nizovima duzine n/2 I manje moze se kodovati vise od 2^n kombinacija. Ukoliko neko bas dobije neodoljivu zelju da mi pomaze na nacin za koji sam rekao da je nepozeljan molim da pocne sa analizom mogucnosti konstrukcije/eksploatacije ovog I ovakvog brojaca posto su ucesnici rasprave vec dva puta uspeli da ga iskuliraju u jednoj drugoj temi.


Da li to znaci da bi trebali da imamo sacuvanu i prethodnu vrednost m?

Sa 2 bitna mesta se moze kodirati iskljucivo 4 razlicite kombinacije. Nije moguce kodirati 27 razlicitih vrednosti. Kada nesto zapisujes sa 2 bitna mesta onda se ta 2 bita uvek koriste i nemozes da neku vrednost predstavis samo sa jednim bitom a neku drugu sa dva bita. Ukoliko zelis da zapisujes dvobitnu vrednost kao jedan ili dva bita onda moras ubacivati nekakav marker u zapis da bi onaj koji cita znao kao da procita vrednost. Obzirom da je zapis binaran mozes ubaciti ili 0 ili 1 kao marker, sto samo povecava konfuziju.

Citat:
Ovo je samo predlog: koduj sa po 4 bita deset decimala, cetri osnovne racunske operacije, “^” I separator npr. /. Koji niz bitova (a ne bajtova) od mogucih 16 ce ti predstavljati separator (/) sam odluci. Inace ovime bi trebao da se bavis ti a ne ja. I uopste uzev poceo si vec da me pitas neke stvari koje se ticu programiranja a ja sa istim nemam blage veze tako da je mozda najbolje da sa algoritmom odes na podforum koji se bavi resavanjem problema iz tvog omiljenog programskog jezika pa da tamo pitas sve sto te zanima.


Evo primera... 1025. Binarno (nekompresovano) ovaj broj ce racunar smestiti u 16 bita iako moze da se zapise u 10 bita. Da vidimo tvoj nacin zapisa:
neka su:
brojevi 0..9 su zapisani na regularan nacin
+ .. 1100
- .. 1101
* .. 1110
/ .. 1111
^ .. 1011
1025 = 4^5 + 1 sto bi bilo zapisano na tvoj nacin:
4 -> 0100
^ -> 1011
5 -> 0101
+ -> 1100
1 -> 0001
sve u svemu... 20 bitova. Mozda te nisam dobro shvatio pa bi bilo lepo da ti zapises ovaj broj na najbolji i najkraci moguci nacin.
Broj 1025 je jednostavan jer ima samo dva upaljena bita (prvi i poslednji). Sa povecanjem broja upaljenih bitova izraz se komplikuje i trebaci vise mesta da se zapise.
Kao sto vidis, nepotrebno su potroseni bitovi za kodiranje operacija. Lepota zapisa broja u nekom sistemu (binarni, decimalni, hexadecimalni, ...) je sto se unapred zna osnova sistema, a pozicija cifre i njena vrednost ucestvuju u jednostavnom izrazu (vrednost*osnova^pozicija + vrednost*osnova^pozicija + ...), tako da nema potrebe da se pisu matematicke operacije.

 
0

peka
Beograd

Član broj: 3947
Poruke: 124
..taman-bg.customer.sbb.co.yu.



+2 Profil

icon Re: Kompresija random-like podataka 203.07.2006. u 00:48 - pre 215 meseci
Citat:
Inace stvari su se promenile (da se pohvalim) ja poceo da programiram...


Bez uvrede, ali sa ovakvim idejama neces daleko dogurati na tom polju.

Mozda bi ti bilo bolje da se drzis ustipaka... ;-)
IRC is just multiplayer notepad.
 
0

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
212.62.51.*



+557 Profil

icon Re: Kompresija random-like podataka 223.07.2006. u 11:21 - pre 215 meseci
Izvinjavam se sto malo kasnim sa odgovorom. Obaveze...
Citat:
yooyo: Kada tvoj brojac nadje vrednost originalnog fajla on u stvari predstavlja sam file.

Nisam napisao ni da brojac trazi ni da nalazi originalni fajl. Ustvari priznajem da sam se (opet) malo nespretnije izrazio ali to je posledica toga sto sam u isto vreme i u istom postu pokusao da izlozim i princip rada ove kompresije i postupak pomocu koga bi se doslo do nje. Napisao sam "ako napravimo brojac" a trebalo je da pise "ako bi napravili brojac" znaci ako bi ga napravili originalni fajl bi se nasao na njemu nasao u smislu da bi bio jedno od potencijalnih stanja tog brojaca bez nekog posebnog postupka trazenja ili pronalazenja fajla. Mislio sam da je dovoljno to sto sam pri kraju posta istakao da nije potrebno a ni pozeljno prilikom postupka kompresije praviti brojac pa da jednoznacno determinisem sta sam mislio pod onim "bi se nasao". A najtacnije ono sto sam pokusao da kazem je da fajl procitan u binarnom obliku i protumacen kao jedan veliki binarni broj u svakom slucaju ima svoj decimalni reprezent u decimalnom brojnom sistemu (a koji opet na svoj nacin obelezava poziciju fajla na potencijalnom brojacu).
Citat:
yooyo: Kada tvoj brojac nadje vrednost originalnog fajla on u stvari predstavlja sam file.

On? Brojac? Brojac nikako ne moze predstavljati sam fajl vec samo stanje na brojacu moze predstavljati fajl u binarnom obliku.
Citat:
yooyo: Uzecu tvoj primer... Imamo file 0101 i 4-bitni brojac.

Taj primer koji navodis sa 0101 je trebao da ilustruje nesto drugo kako se ceo originalni fajl ma koje duzine bio posmatra kao jedan veliki binarni broj i kako se iz njega bez pravljenja brojaca moze izracunati decimalna vrednost pozicije fajla na brojacu (kad bi ga pravili)(a koja se kasnije faktorizuje).
Citat:
yooyo: Uzecu tvoj primer... Imamo file 0101 i 4-bitni brojac.

Dakle imamo fajl 0101 i nemamo 4-bitni brojac jer nam ne treba.
Citat:
yooyo: Brojac ces povecati 5 puta i dobice vrednost identicnu originalnom fajlu. Binarni zapis broja 5 je 0101.

Brojac necu povecati 5 puta jer ga necu ni praviti ali cu za fajl 0101 koji imam od pocetka izracunati njegovu decimalnu vrednost po dobro poznatom sistemu 0*2^3 + 1*2^2 +...=5.
Citat:
yooyo: Zapisacemo kompresovani file u obliku (4,5) koji je veci od originalnog fajla za duzinu potrebnu da se broj 4 upise u nekom obliku.

Bicu dosledan sebi tj. svom predlogu kompresije pa kompresovani fajl necu zapisati u obliku koji ti predlazes (4,5) a koji inace u tom slucaju ne bi bio veci od originalnog fajla za duzinu potrebnu da se broj 4 upise u nekom obliku vec jos vise jer ni 5 ne mozes upisati samo sa 4 bita jer mora biti kodovano na neki nacin a tesko da bi moglo samo sa 4 bita s obzirom na sve oznake koje bi nam bile potrebne za opis kompresovanog fajla, ono sto sam predlagao "koduj sa po 4 bita..." je bio samo predlog na primer u tih 16 oznaka (0..9,+,-..^,|) nisu usle zagrade a definitivno bi bile potrebne za razdvajanje faktora pa cak si ih i ti upotrebio ovde kada si napisao (4,5) te takodje prevideo si taj mali zarez izmedju cetvorke i petice jes da je mali i neugledan i da se jedva vidi na ekranu kao neka tackica rek'o bi covek ne moze zauzimati vise od 1 bit ali jok taj zarez predstavlja separator u ovom slucaju te takodje mora biti kodovan tj. i on ce zauzeti koliko i druge oznake potrebne za opis kompresovanog fajla konkretno najmanje 5 bita za sada jer nam 5 bitnih mesta obezbedjuje da mozemo da kodujemo 32 razlicite oznake pa bi tu stale sve dosad navedene plus zagrade, dakle 18 ukupno (za sada, ko zna mozda nam zatreba jos neka), sve u svemu tako kako ti predlazes u obliku (4,5) kompresovani fajl bi zauzimao 25 bita (po 5 bita za svaku oznaku u njemu - zagrade, zarez, cetvorka i petica) a ne samo "za duzinu potrebnu da se broj 4 upise u nekom obliku". Nego da se ne bi vise smarali oko toga kako cemo kodovati oznake koje nam ulaze u kompresovani fajl tih pet bita u odnosu na osam i nije neka usteda nije u tome sustina ove kompresije pa predlazem za svaku oznaku po 1 byte lakse je za racunanje.
Ko sto rekoh ostacu dosledan sebi tj. svom predlogu kompresije pa cu broj 5 koji sam dobio faktorizovati na optimalan nacin i posle dvoumljenja izmedju 2^2+1 i 4^0+1 (naravno pustio bih da kompjuterski program razmislja umesto mene) zapisao bih "kompresovani" fajl kao npr: (4|2^2+1). Ako bi svaka oznaka bila po 1 byte zauzimao bi 9 byta mnogo vise nego originalni fajl 0101 (4 bita)."Kompresovani" pod znacima navoda jer u ovom slucaju nema kompresije vec samo ekspanzije sto je i logicno i sto sam nekoliko puta naglasavao da za "male" fajlove nema kompresije vec samo ekspanzije i sto sam pokusao da objasnim tako sto nacin zapisivanja faktorima postaje racionalan tek za velike brojeve i sto sam ilustrovao primerom "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 je iz posta od 07.01 2006. u krlp1 raspravi. Naravno mene ne brine sto je po mom sistemu "kompresovani" fajl duzi za zapisivanje nego onako kako si ti predlozio (4|2^2+1) > (4,5) jer to vazi samo za izuzetno male fajlove a za one velike nacin zapisivanja faktorima je mnogo racionalniji te takodje uz pomoc njega se moze dobiti i kompresija a ako bi vrednost m zapisivali brojevima decimalnog brojnog sistema kako ti predlazes uvek bi se dobila ekspanzija i za male i za fajlove srednje velicine i za one velike.
Da remiziram prvo smo se pogresno razumeli kada si ti skapirao da prilikom kompresije treba praviti brojac te da taj brojac "trazi" i "pronalazi" fajl iako sam napisao da prilikom kompresije nije potrebno ni pozeljno praviti brojac, izvini ako sam te stilom izlaganja doveo u zabunu ali stvarno sam mislio da je ta recenica pred kraj dovoljna da odagna svaku sumnju u vezi postupka kompresije znaci fajl "bi se nasao" na brojacu ako bi taj brojac uopste bio pravljen je pravilno tumacenje a u prevodu: fajl posmatran kao binarni broj ima svoj decimalni reprezent (koji se kasnije da faktorizovati). S druge strane nikako mi se ne svidja tvoj izbor primera koji je trebao da ilustruje nesto sasvim drugo i to jos sa recima "uzecu tvoj primer". To je zvucalo nesto kao evo na tvom sopstvenom primeru cu ti pokazati da nisi u pravu. I sta onda radis uzmes "fajl" duzine 4 bita i trazis da se kompresuje? 4 bita? Da se kompresuje? I onda kao evo zapis koji smo dobili po tvom metodu (4,5) je duzi od originalnog fajla. Pa covece ne po mom metodu nego po bilo kom uzmi gorenavedeni ili bilo koji fajl te duzine po sopstvenom izboru podesi i nivo entropije kako ti volja ugasi ili upali bilo koji od ta cetri bita i bas da vidim kako ce bilo koji do sada poznati ili nepoznati algoritam ili program pa zvao se gzip ili vec kako da sazvace ta cetri bita i da ih predstavi nekim kracim zapisom. Nema sanse. Ne bih ni obracao paznju na ovaj "primer" da nisi kroz njega totalno pogresno predstavio postupak kompresije pa sam morao da ispravljam.
Ako nista naveo si me na razmisljanje pa sam redefinisao i postupak kompresije i dekompresije prvo sebi pa cu i vama kasnije u ovom postu da ne skacem sa teme na temu nadam se da ce biti jasnije tj. manje dvosmisleno mada i sad nisam bas siguran da sam ja pograsio vec pre da si ti lose razumeo. Te takodje hvala ti sto si kao separator iskoristio zarez to mi je skrenulo paznju na cinjenicu da sam predlozio da se za potrebe zapisa kompresovanog fajla koduju pored decimala i cetri osnovne racunske operacije ali ih nisam zapisao njihovim simbolima a da jesam sigurno bih primetio da bi znak / vec bio iskoriscen za deljenje te nikako ne bi mogao posluziti i kao separator (uradio sam to po inerciji jer se cesto koristi kao separator npr. prilikom predstavljanja putanje do nekog fajla) ali posto mi se ni zarez ne svidja jer ce cesto desavati da su i ispred njega i iza njega cifre decimalnog brojnog sistema neko bi ih kad tad pomesao sa realnim brojevima ili jos gore to bi moglo inspirisati nekog da "otkrije" da se ovaj tip kompresije jos uspesnije da napraviti koristeci blagodeti izracunavanja realnih brojeva odsad kao simbol za separator izmedju n (decimalno) i m (predstavljeno faktorima) koristicu uspravnu crtu |.

Nemoj da pricas?
 
0

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
212.62.51.*



+557 Profil

icon Re: Kompresija random-like podataka 223.07.2006. u 11:23 - pre 215 meseci
Citat:
yooyo: Tacno... ali vrednost m iz kompresovanog fajla je originalni file, tako da nema potrebe da se broji od pocetka.

Netacno...vrednost m u kompresovanom fajlu je zapisana u faktorskom obliku i nije identicna originalnom fajlu tj. nije identicno zapisana (vrednost joj jeste identicna orig. fajlu) opet cu preuzeti krivicu na sebe verovatno nisam lepo objasnio verovatno sam trebao konkretnije da naznacim u kom trenutku procesa m biva zapisano binarno, kad decimalno i kad faktorski. Ali da nema potrebe da se broji od pocetka to si u pravu i tek sad sam primetio da sam napravio gresku izlazuci opis postupka dekompresije i prosto ne mogu da verujem. Bolje da odmah napisem kako bi pravilno isao postupak dekompresije: iz kompresovanog fajla uzima se skup faktora koji opisuju m i izracunava se njihova tacna vrednost tj. dobija se m u dec. brojnom sistemu. Iz takvog m se jednostavnim prevodjenjem u binarni brojni sistem (deljenje sa 2, belezenje ostatka) dobija m binarno tj. originalni fajl. U slucaju da je zapis m binarno kraci od n m binarno se nadopunjuje nulama na pocetku fajla do duzine n. Uf opet je malo konfuzno objasnjeno, znaci ponovo cu na kraju ovog posta dati nov redefinisan opis postupka kompresije i dekompresije sustina je ista ali ce biti tacnije formulisano i opisano.
Citat:
yooyo: Ukratko, nema potrebe da koristis nikakav brojac jer je BINARNA reprezentacija takvog brojaca IDENTICNA originalnom fajlu.

U pravu si brojac je izbacen i iz postupka kompresije i iz postupka dekompresije, ko sto rekoh kasnije detaljnije uz jos jednom konstataciju prosto ne mogu da verujem da sam pogresio.
Citat:
yooyo: Dalje... ti predlazes kompresiju brojaca. Da vidimo sta predlazes:

Sorry ne mogu da se slozim nisam predlagao kompresiju brojaca ako je u postupku dekompresije i postojao brojac u prethodnoj verziji opisa postupka (a sad ce biti izbacen), brojac nije bio predvidjen ni za pravljenje a kamoli za kompresiju opet se vracam na ono "Prilikom kompresije nije potrebno ni pozeljno praviti brojac".
Citat:
yooyo: Prvo pitanje je sa koliko bita bi predstavio a, b, c, d, ... z?

Prvi predlog je bio sa po 4 ali posto nam trebaju i zagrade sa po 5 ali zbog lakoce racunanja ja sam na kraju predlozio 8 tj. 1 Byte na dalje cu podrazumevati da su sve oznake u kompresovanom fajlu kodovane sa po 1 Byte dok se drugacije ne dogovorimo.
Citat:
yooyo: Ukratko.. moralo bi da zbir duzina u bitovima svih koeficijenata bude kraca od n (tj. duzine fajla).

Potreban ali ne i dovoljan uslov. Zbir duzina u bitovima svih koeficijenata u kompresovanom fajlu mora biti najmanje kraca od n za duzinu da se i n izrazeno brojkama dec.broj. sistema smesti u taj isti kompresovani fajl. Seti se struktura fajla je (n|m) ili mozda bolje da pocnem da koristim precizniji i opisniji sistem izrazavanja tj. struktura kompresovanog fajla je (Nd|Mf). Nd je duzina originalnog fajla izrazena brojkama dec. broj. sistema, a Mf je Md faktorski izrazeno gde je Md ili M decimalno decimalni reprezent pozicije originalnog fajla na potencijalnom brojacu kada bi ovaj bio pravljen tacnije decimalna vrednost originalnog fajla posmatranog kao binarni broj (sto je isto). Bah opet konfuzno i tesko razumljivo ali ja drugacije ne umem da objasnim.
Citat:
yooyo: Dalje... vrednost a^b ce upaliti neke bitove ali zato sabiranje rezultata sa c^d moze da dovede do paljenja nekih drugih bitova ali isto tako i gasenje vec postojecih (upaljenih) bitova.

Bojim se da ovo ne razumem, zvuci mi kao da ces da pojedine faktore iz da kazemo celokupnog "faktorskog izraza" koji determinise Md (M decimalno) da prepisujes jedne preko drugih tj. da ces da ih sabiras (i vrsis ostale operacije) u njihovom binarnom obliku. Ne, ceo "faktorski izraz" (Mf) ostaje zapisan kao takav u kopresovanom fajlu tj. kad se dekompresuje izracunavas prvo vrednost (decimalnu vrednost) a^b, pamtis je pa izracunavas c^d pa po pravilima sabiranja u dec. broj. sistemu ih sabiras i tako dalje. Ako nisam pogodio sta si mislio molim te da mi ovo gore sa paljenjem i gasenjem bita objasnis.
Citat:
yooyo: Da li to znaci da bi trebali da imamo sacuvanu i prethodnu vrednost m?

Ne, al ja se sad ne bi mnogo zadrzavao na predlogu pravljenja ovakvog brojaca. Em brojac izbacujem i iz postupka kompresije i iz postupka dekompresije, em je ovo opet trebala biti samo ilustracija koncepta gde se jedna bitna kombinacija deleci se na dva dela, na razlicite nacine, sto u stvari predstavljaju ta dva stanja aktuelno i prethodno, moze iskoristiti vise puta za obelezavanje / kodovanje razlicitih vrednosti. Ko ne veruje neka ipak razmisli kako je to Patrick iz onog linka koji je prilozio blaza u krlp1 uspeo da deleci originalni fajl random strukture na vise (200) manjih delova postigne da ti manji fajlovi sadrze kolicinski manje informacija nego originalni fajl a da se ipak daju raspakovati u originalni fajl. I da ovu "nategnutu" verziju brojaca sam napravio upinjuci se da dokazem nesto u sta sam verovao a to je da se na neki volseban nacin ipak mogu svi fajlovi iz nekog opsega kompresovati po ovoj metodi, posto vise ne verujem da ne razglabamo.

Nemoj da pricas?
 
0

[es] :: Art of Programming :: Kompresija random-like podataka 2
(Zaključana tema (lock), by mmix)
Strane: 1 2 3 4

[ Pregleda: 19649 | Odgovora: 71 ] > FB > Twit

Postavi temu

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