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.

Izvini sto ti odgovaram sa ovolikim zakasnjenjem, bio sam pretrpan obavezama ovih dana.


Koliko shvatam to je offtopic.


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



Ma neee, cini ti se:
1)
n = 8 da se nisi pretrg’o, probaj sledeci put sa n = 750. Naravno za to ce ti trebati odgovarajuci program.
2)

3)


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


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).


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.


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.


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


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)?


Offtopic.





Hvala.

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.

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.


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...

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]}

Razmislicu.

@bytEfLUSh
Onaj prvi citat to je trebala biti nesto kao sala na sopstveni racun.

Ne znam.

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.

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.

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

@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?

Ovo je definitivno najgluplja tema na čitavom ES forumu.

Sretno ...

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?

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.

zasto se ova diskusija jos uvek vodi?

eh da imam power of lock

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



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



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.



Na ovo ti je odgovorio RooTeR:



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



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”.



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?



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



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



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.

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.



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.



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.



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.

Ajde krenucu redom:


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?



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:



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.



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.



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.

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

Mozda bi ti bilo bolje da se drzis ustipaka... ;-)

Izvinjavam se sto malo kasnim sa odgovorom. Obaveze...

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).

On? Brojac? Brojac nikako ne moze predstavljati sam fajl vec samo stanje na brojacu moze predstavljati fajl u binarnom obliku.

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).

Dakle imamo fajl 0101 i nemamo 4-bitni brojac jer nam ne treba.

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.

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 |.

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.

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.

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".

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.

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.

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.

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.

(Upozorenje za one koji su odmah skrolovali na zadnji post u temi: premotaj tri posta unazad tu pocinje odgovor)

Dobro si me shvatio ali broj 1025 je jos uvek isuvise mali da bi zapisivanje faktorima bio racinalan nacin zapisivanja za njega. Probaj sa listingom broja 2^8000 sa prve strane rasprave "beskonacna kompresija..." (bkkr) gde je listing jednog decimalnog broja zauzeo celu jednu a4 stranu oko 2500 cifara. Ako svaka cifra zauzima po 4 bita to je 10000 bita na disku (na nacin na koji si ti odredio 16 bita za broj 1025), ako ga prevedes u binarni brojni sistem zauzece 8000 bita (na nacin na koji se 1025 m moze smestiti u 10 bita kod tebe) a faktor koji ga opisuje tj. iz kojeg se da izracunati tacna vrednost broja 2^8000 zauzima 48 bita iliti 6 Byta (po 1 Byte za svaku oznaku). I da imas gresku u racunu 1025 se ne moze smestiti u 10 bita vec najmanje u 11 (2^10 = 1024).

Dva upaljena bita su prvi i jedanaesti. Povecajmo broj upaljenih bita na maksimum tako sto cemo ih upaliti sve da bi smo proverili da li se izraz zaista komplikuje i da li ce trebati vise mesta da se zapise. Rezultat: faktor 2^11 koji opisuje br. 2048 koji odgovara situaciji svih jedanaest bita upaljeni ;) A faktor 2^11 je kraci za zapisivanje od faktora 4^5 + 1. Ma znam sta si hteo da kazes komplikuju se ovi izmedju "optimalnih" pozicija koje se daju opisati samo jednim faktorom 2^n, 2^(n-1) itd ali kad udjemo u zonu malo vecih brojeva u pomoc nam priskace to sto cemo moci da koristimo i faktore sa osnovicom razlicitom od 2 (3,4,5...) te takodje sto cemo moci da stavimo i neki mnozilac ispred s tim u vezi mozda sam ilustrujuci kako Mf treba da izgleda (M faktorski) trebao umesto a^b + c^d - itd... trebao da napisem a*(b^c) + d*(e^f) - itd...

Lepota zapisa broja faktorima je sto se sa veoma kratkim za zapisivanje faktorima mogu predstaviti veoma velike brojcane vrednosti. Leta gospodnjeg MMVI.

Ne vredjam se, ali ni bez ovakvih ideja necu daleko dogurati na ovom ili nekom drugom polju tako da mi dodje na isto.
E sad analiza mesta dge sam pogresio. Znaci kompresija je bila u redu (sa podrazumevanom vrednoscu da ne treba praviti brojac) a prilikom opisa procesa dekompresije sam napisao sledece:
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.
Samo po sebi nije netacno ali zaista imam brojac viska a sve sto je viska treba ukloniti. Znaci iz M faktorski (Mf) racuna se M decimalno (Md) a Md se prevodi u M binarno (Mb) bez pravljenja brojaca. Mb kada se "izracuna" reprezentuje originalni fajl u slucaju da mu se duzina poklapa sa N a ako je krace nadopunjuje se nulama na pocetku niza bita kojim je predstavljen do duzine N. Kad malo bolje razmislim mozda nisam slucajno prezentovao dekompresiju na ovaj nacin pravljenjem brojaca duzine N i pustanjem u rad istog ne moze se promasiti kad tad ce natrcati na originalni fajl jer su iste duzine i to originalni fajl "ceo u kompletu" a ovim postupkom Prevodjenjem iz Md u Mb dobija se samo deo fajla od pojave prve jedinice do kraja fajla tako da se mora nadopunjavati nulama, na onaj prvi nacin bilo je ociglednije da se originalni fajl da rekunstruisati na osnovu opskurnih informacija iz kompresovanog fajla.
Sledi potpuna redefinicija postupka kompresije i dekompresije fajlova iz razloga skracivanja postupka i uklanjanja dvosmislenosti koje su nastale pominjanjem i koriscenjem brojaca u postupcima kompresije i dekompresije:
Dakle celokupni binarni sadrzaj fajla se tretira kao jedan veliki binarni broj (Mb) te se veoma lako taj broj prevodi u broj u decimalnom brojnom sistemu (Md) koji se zatim faktorizuje na optimalan nacin te se dobija zapis Mf. Za sve fajlove za koje zapis Nd|Mf zauzima manje mesta nego originalni fajl (dge je Nd broj koji predstavlja duzinu originalnog fajla u bitima) dobija se kompresija, za ostale ekspanzija ili bez promene velicine. Dekompresija se vrsi tako sto se iz izraza Mf izracuna decimalna vrednost Md koja se zatim prevodi u broj u binarnom brojnom sistemu Mb koji se zatim u slucaju da je kraci od vrednosti koju oznacava Nd nadopunjuje na pocetku nulama do vrednosti koju oznacava Nd. Right?
Granicna duzina originalnog fajla ispod koje ne bi trebalo ni razmisljati o postojanju kompresije je na 56 bita. Naime vec na toj duzimi nekoliko fajlova se da kompresovati po ovom sistemu. Zapis 56|2^0 zauzima manje mesta (48 bita) nego originalni fajl koji sa da rekonstruisati iz njega. Izmedju 56|2^0 i 56|9^9 ima oko 50-tak slicnih fajlova. Jos uvek nisu neke ekstra random like strukture ali to je zato sto jos uvek sebi nismo priustili duzinu fajla koja bi nam omogucila stavljanje bilo kakvog mnozioca ispred faktora. Right?

Koliko se pise o ovome mogao si da naucis programiranje i pokazes svetu kako to radi (i da li uopste radi)

Pa ucim, ucim al sporo ide sacuvaj boze.

Bolje ti je da uzmeš matematiku u šake, da jesi, ne bi ni postojala ova tema.

Moze biti nego meni matematika ide srednje zalosno da dzabe ne uzimam?

Sama faktorizacija broja i njegova predstava u kompresovanom fajlu bi trebalo da predstavlja srž tvog algoritma a ne ovo što si ti dao. Tvoj ceo algoritam je nalaženje broja m a hoćeš da ti neko drugi smisli alogritam za faktorizaciju. Ako uporedimo kompleksnost ovog šti si ti dao je 1% konačnog algoritma.

http://en.wikipedia.org/wiki/Integer_factorization

Hvala za link. Ama nisam znao da je ova faktorizacija tako zajebana. Javicu se kad/ako isprocesiram pristigle informacije.

http://prize.hutter1.net/

Hm...samo da kazem da ovo sto covek hoce nije faktorizacija.

Faktorizacija bi bilo nesto tipa:
120/2=60
60/2=30
30/2=15
15/3=5
5/5=1

120=2^3 * 3 * 5

a ovde se trazilo to isto sa sabiranjem, tipa:

11^2 + (-1)^1

toliko....

Hvala. Jos kada bi bilo brze za izracunavanje... npr 16 meseci za broj od 200 cifara ;)

Bump ;)

Izvinite sto prosle nedelje nisam ucestvovao u raspravi ;) (fazon od 1 drugara kad jedno 3 godine nismo isli na neka predavanja: "Aj da se pojavimo i da kazemo izvinite sto nismo bili prosle nedelje ")

Ama, verovatno sam ja opet nesto prevideo, pogresno skontao, ali meni se cini, kompresija random-like, tj. svih podataka je ipak mozda moguca: evo i kako:

Od svih 2^n konbinacija koje moze da napravi 1 brojac duzine n, (2^n) - 2 kombinacija se mogu predstaviti nizovima bita kracim od originalnih, a preostale dve kombinacije bita se mogu predestaviti visestrukim nizovima bita, ciji je zbir (broja bita) kraci od duzine broja bita originalnih kombinacija. Sve ovo vazi za n>=3.

A, sta kazete?

Cutanje je znak odobravanja ;)

Gde se Shanon i ja slazemo:

3. Suppose there are two events, x and y, in question with m possibilities for the first and n for the second.
Let p(i; j) be the probability of the joint occurrence of i for the first and j for the second. The entropy of the
joint event is
H(x;y) = 􀀀åi; j p(i; j) log p(i; j)
while
H(x) = 􀀀åi; j p(i; j) logåj p(i; j)
H(y) = 􀀀åi; j p(i; j) logåi p(i; j):
It is easily shown that
H(x;y) <= H(x)+H(y)

with equality only if the events are independent (i.e., p(i; j) = p(i)p( j)). The uncertainty of a joint event is
less than or equal to the sum of the individual uncertainties.

Tj. "neodredjenost" nekog "zajednickog" dogadjaja 2 dogadjaja je manja ili jednaka zbiru neodredjenosti posebnih dogadjaja, tj. ako uzmemo sve moguce dogadjaje koji se mogu desiti (stanja na brojacu) njihov ukupni zbir neodredjenosti je manji nego kad bi sabirali svaku "neodredjenost" za svaki dogadjaj posebno. (Tj. nosi manju kolicinu informacija, tj. da se kompresovati).

Gde se "vidi" da cika Shanona i mene nisu interesovale iste stvari ili bar ne identicne:

1. H = 0 if and only if all the pi but one are zero, this one having the value unity. Thus only when we
are certain of the outcome does H vanish. Otherwise H is positive.

Imao sam negde jos bolji citat, al sam zagubio: naravno da ako hoces da prenosis informacije (cime se bavio Shanon) da su ti potrebne i nule i jedinice (ako ti je binarni br. sistem sredstvo prenosenja) jer inace informacija ne bi ni postajala ili bi imao samo 2 moguce kombinacije bita tj. samo 2 razlicite informacije, ali za skladistenje podataka to nije uslov tj. mogu se iskoristiti i preostale 2 kombinacije bita: fajl sastavljen samo od nula i fajl sastavljen samo od jedinica, tj. kod Shanona fajl (informacija) "koji sadrzi bar 1 jedinicu" nosi najmanju kolicinu entropije (ovo "bar 1 jedinicu" se odnosi na: krenuvsi od prvog fajla - kombinacije bita po redu - onog sa svim nulama, prvi koji dobija bar 1 jedinicu tj. fajl sa svim nulama i 1 jedinicom, a vazi i obrnuto fajl sa svim jedinicama koji sadrzi bar 1 nulu krecuci se unazad kroz moguca stanja brojaca od zadnjeg tj. fajla sa svim jedinicama ka prvom, sto Shanon nije posebno naglasio ali smatram da se podrazumeva). Za skladistenje podataka mislim (smatram :) da vazi bas naprotiv tj. tacnije da fajl sastavljen samo od nula ili samo od jedinica ima manju entropiju od fajla koji sadrzi bar 1 jedinicu (ili vise, tj. bar 1 nulu ili vise, tj. razlicite bite po znaku) jer inace ako bi doslovno shvatili Shanona ispalo bi da fajl sastavljen samo od nula recimo ima negativnu entropiju? (sto je nemoguce, tj. naravno da je moguce ako se tako definise ali vazi samo za prenos informacija ali ne i za skladistenje). Posebna prica bi bila o tome sto Shanona kao da je zanimala samo entropija izvora signala ali ne i samog signala kao da se to moze razdvojiti sto je opet bilo uslovljeno onim cime se bavio: prenosom signala najvise.

Izvinjavam se zbog lose sredjenih citata, samo sam prekopirao iz teksta "Matematicka teorija Informacija" od C.E.Shanona, stvarno ne umem bolje da sredim ako neko moze da nadje ova dva citata i da ih postavi ovde u sredjenom obliku bio bih veoma zahvalan.

Ono sto me je svojevremeno pomalo zabrinulo je:

This compression contest is motivated by the fact that being able to compress well is closely related to acting intelligently, thus reducing the slippery concept of intelligence to hard file size numbers. In order to compress data, one has to find regularities in them, which is intrinsically difficult (many researchers live from analyzing data and finding compact models). So compressors beating the current "dumb" compressors need to be smart(er). Since the prize wants to stimulate developing "universally" smart compressors, we need a "universal" corpus of data. Arguably the online encyclopedia Wikipedia is a good snapshot of the Human World Knowledge. So the ultimate compressor of it should "understand" all human knowledge, i.e. be really smart. enwik8 is a hopefully representative 100MB extract from Wikipedia.

Nisam ni znao da se bavim ovako vaznim stvarima, kompresor bi trebao (mogao) "da razume sve ljudsko znanje"? a negde sam nacuo (od Dilana :) da je "inteligencija bez ljubavi demonska", pa tako, ono jes da se nisu pretrgli sa nagradom za tako sofisticiran kompresor (150e) ali ako stvarno uz pomoc njega moze da se pronadje "kamen mudrosti" kome bi jos trebala bilo kakva nagrada osim toga?

Uzdravlje! I budite mi dobri!

Tebe to još drži?

hahahahahhahahha

MajorFatal postao si moj idol :D.

1.) 000 -> 0
2.) 001 -> 1
3.) 010 -> 00
4.) 011 -> 01
5.) 100 -> 10
6.) 101 -> 11
7.) 110 -> 0 1
8.) 111 -> 1 0

Za svih 8. razlicitih kombinacija 8. drugih razlicitih kombinacija bita koje su krace od originalnih: poslednje 2 su krace po broju bita koji su upotrebljeni.

Kako se dekomprimuje 00? Kao 000000 ili kao 010?

E Nedeljko, stalno pokvaris nesto To su detalji, ispeglace on to tokom kodiranja

Kao 010. 000000 bi bilo 0 0

Jal me zezate jal ne razumem? Nedeljko gde si iskopao tu kombinaciju sa 6 nula? Nema je navedene u prethodnom postu? Shadoved, hvala za podsecanje/sugestiju postoje jos i 0 0 i 1 1 sto znaci da ima i viska kombinacija sto znaci da je moguca kompresija. Svestan sam naravno da je za sada jedini moguci engine papir ili elektronski papir tj. da 1 bit tesko da moze biti racunan kao fajl u bilo kom fajl sistemu ali zato dok ispregledam sve aktuelne fajl sisteme mozda i nadjem neki odgovarajuci.
Ok, tek sad kontam, Nedeljko, da li sugerises da su mi za poslednje dve kombinacije potrebni i heder i futer da bi ono bili fajlovi? Znam to, osim ako postoji neki fajl sistem gde bi fajlovi bili jednoznacno odredjeni cak i ako imaju samo heder recimo a da engine prepoznaje kraj fajla po sadrzaju samog fajla, ili u nekoj hardverskoj izvedbi to ne bi bio neophodan uslov.
Ja bih ipak sa 0 0 i 1 1 kodirao prva sledeca 2 (po velicini/duzini) fajla tj. 0000 i 0001, tako da svih 8 kombinacija duzine 3 i jos 2 kombinacije duzine 4 na samo 3 bitna mesta.
Ako zezate, nemojte, bitno mi je ovo ;)

Da, ali zasto stajes samo na tim kombinacijama, mozes progresivno da gradis maping tabelu i dalje

dakle
0010 -> 0 01
0011 -> 0 10
...


itd
taj space u binarnom streamu ti je mnogo jak izum, ja bi to patentirao

Pa, hajde, imaš niz 000000. Kako bi ga kodirao? Ili možda kodiraš samo nizove od 3 bita?

Na mikro sekund pojacas struju na hardu on se malo vise okrene i eto ti razmak ;).

1.) 000 <- 0
2.) 001 <- 1
3.) 010 <- 00
4.) 011 <- 01
5.) 100 <- 10
6.) 101 <- 11
7.) 110 <- 0 1
8.) 111 <- 1 0

Veoma lepo i slikovito opisan proces dekompresije. Samo pratite strelicu pa se nadam da nece biti dilema u sta se dekompresuje 00 ili bilo koji drugi niz od navedenih.



Ne samo da ne stajem nego necu ni da pocinjem to cete vi programeri da odradite. Znam sta je space ali ne znam sta su maping tabela i binarni stream a nisam mogao ni da pronadjem nigde na netu tako da ne mogu da ti odgovorim. Pa patentiraj, ko ti brani?

On samo hoće da ti sugeriše kako i taj razmak moraš da kodiraš nekim nulama i jedinicama, ako predstavljaš podatke u binarnom sistemu i ako ti kodovi nisu fiksne dužine kada bi razmak mogao i da se podrazumeva.

Kako da ne :)

Shadowed, resistance is futile.

Istina, u vreme komodora meni je pala na pamet genijalna ideja koja je u stvari vrlo slična majorovoj. Kontao sam ovako memorije ima od 0000 do ffff, to je 65536 bajtova, pa sam razmišljao da napišem neki program koji se nebi zaustavljao na slovu "f" nego da imam i "g" i "h" itd (na taj način bi se softverski povećala fizička memorija računara)... Mnogo jaka ideja, doduše tad sam bio klinja, nekih 15 godina. Šta reći, osim da mi je MajorFatal ustvari ukrao ideju, malo izmenio i sad hoće da postane slavan preko mojih leđa lol

A šta se dobija time što se ne zaustavi na 0 i 1, nego se uvedu još i 2, 3, 4, 5, 6 i 7 ili čak još 8, 9, A, B, C, D, E i F?

Ništa!

To sto si napisao bi bilo tacno kada bi se na levoj strani na spisku fajlova numerisanih od 1 do 8 i u punoj duzini nalazio bar jedan fajl sa razmakom, odnosno 2 fajla sa razmakom izmedju njih pa kad bi neko pomislio od ta 2 fajla da je to 1 fajl sa obe razlicite vrednosti bita iskoriscene i plus sa razmakom, tada bi i razmak (space) bio neki dodatni signal koji bi naravno morao da se koduje odgovarajucom (novom) kombinacijom bita nula i jedinica ili samo nula ili samo jedinica, kako to nije tako i kako podatke zaista predstavljam u binarnom sistemu ali je moj trenutni "engine" papir, nisi u pravu jer: poslednja 2 reda na desnoj strani predstavljaju po 2 fajla u praksi razdvojena svojim hederima i futerima kako bar ja zamisljam vecinu fajl sistema tj. u praksi space ne mora ni da postoji bitno je da dva fajla plus njihovi hederi i futeri zajedno sabrani i smesteni u neku vrstu registra ili memorije budu u zbiru (broj upotrebljenih bita za sve to gore navedeno) kraci od prostora koji zauzimaju originalne kombinacije bita (fajlova) navedene na levoj strani "crteza" sto je slikovito predstavljeno kao 0_1 i 1_0, tako da ako bi se nasao neko ovde da poznaje osobine fat32 ili ext fajl sistema ili neznamtinijakojeg tj. duzine (u bitima) hedera i futera istih mogao bi brzo da nem odgovori gde je donja granica (eventualne) mogucnosti postojanja (izvedbe) u praksi ovakve kompresije.

??? ne razumem, kada bi razmak mogao da se podrazumeva?

Fajlovi su ti ovde nepotrebna komplikacija koja te skreće sa teme.

Zamisli da imaš samo jedan tok - npr. magnetnu traku - na koji upisuješ tvoj kompresovani zapis. Kao separator između dva bloka („dva fajla“ kako ti kažeš) možeš da uzmeš šta god ti je najzgodnije. Razmišljaj u tom smeru. Šta bi ti odabrao kao separator (razmak)?

@Nedeljko

Ako se ovo odnosi na mene, odgovor: naravno da se dobija: Ako bi imao memorijske lokacije od 0000 do gggg onda ne bi imao 64k nego nekih 80k.

Naravno, davno sam shvatio da je ideja glupost, lepo zvuci ali nema nista od toga.

Memorija je tolika kolika je - 65536 bajtova. Da li ćeš ti adrese zapisivati sa šesnaest binarnih cifara ili četiri heksadekadne, sasvim je svejedno. Možeš da koristiš i pet dekadnih cifara, ali onda zapisi u opsegu od 65536 do 99999 ne znače ništa, već samo oni u opsegu od 00000 do 65535 predstavljaju adrese.

Ne bih odabrao nikakav separator (razmak):



vec bih recimo u heder kompresovanog fajla ubacio informaciju kolike su po redu duzine binarnih zapisa nejednake duzine, na osnovu te informacije engine koji cita magnetnu traku ne bi imao dilema gde pocinje koji fajl (binarni zapis) a gde se zavrsava, i koliko ih ima.

Izračunaj sad koliki bi heder bio! ;)

I taj header je predstavljen binarnim zapisom. Tebi header predstavlja separator sadržaja „dva fajla“, razmak. Header mora da ima svoje kodiranje koje ga nedvosmisleno razdvaja od okolnog sadržaja.

Jedna varijanta je da header bude fiksne dužine tako da program koji čita zna da uvek čita npr. dva bajta za dužinu, pa toliko bajtova za blok do sledećeg headera.

Sada u svoj račun dužine kompresovanog teksta uračunaj ta dva "izgubljena" bajta. Ili predloži neko drugo rešenje za separator sa kraćim gubicima.

@Nedeljko

upravo tako, ali tad to nisam znao

...koji se takodje sastoji od bita, ali to vec uspesno rade operativni sistemi i ostali specijalizovani programi, "prepoznaju" fajlove koji im trebaju na osnovu raznoraznih informacija koje su pothranjene na raznim mestima neke u os-u neke u samom programu...



A druga bi bila da heder ipak ne bude fixne duzine ali da program koji cita zna da cita ono sto treba da cita bilo 2 bilo 1 ili 3 ili vise vec po potrebi bajta za duzinu kao i za sve ostalo sto je vec smesteno u hederu...



Obavljeno, i postavio uslov koji mora da se zadovolji da bi kompresija (i dekompresija) zazivela u praksi. 2 bajta nece da mi zafali kad kompresujem fajl od 4,7 giga? Ali ni za fajl od 4,7 giga tesko da ce header biti duzine 2 bajta vec vise?

Kada na disk snimiš prazan fajl, on obzirom da ima ime i podatke o atributima i drugim stvarima, već zauzima neki prostor na disku. Taj heder je negde uspisan, radio to tvoj program ili OS, sasvim svejedno. Onda moraš i to da uračunaš u ukupan utrošeni prostor.



I gde je proračun ukupnog zauzetog prostora sa hederima?

duzina 2 fajla (ta makar bili i "prazni") + odgovarajuci hederi i futeri tj. bilo sta sto garantuje pravilno citanje ta dva sadrzaja ta dva fajla, moze da bude i jedan heder za oba u tom slucaju heder bi morao da sadrzi informaciju gde se zavrsava prvi a pocinje drugi ili gde je futer prvog a heder drugog (jer je sadrzaj oba fajla sasvim sigurno zapisan u bitima), ali ono sto je bitno je da sve te informacije o sadrzaju oba fajla sa pripadajucim bitima koji cine heder i futer ili oba u zbiru moraju da zauzimaju manje ili jednako mesta od najduzeg po broju bita "jednostrukog" fajla (a cija je duzina n-1 da bi kompresija/dekompresija postojala), nego eto zapetljah se, upravo sam skontao da i prethodni "jednostruki" a razliciti fajlovi moraju imati svoje hedere i futere, tako da i dalje nije nemoguce ali ne mogu lepo da objasnim, moja greska, aj zanemarite i zaboravite.

Odnosno, kako i fajlovi jednakih duzina u bitima na crtezu "sa leve strane"* imaju svoje hedere i futere (sto i njima produzava duzinu izrazenu u bitima tj. prostor koji zauzimaju), ona dva gorepominjana fajla (na crtezu sa desne strane) sa svojim hederima i futerima ili nekim drugim odgovarajucim opisom moraju bar za 1 bit biti kraci od odgovarajuceg fajla spomenutog na pocetku ove recenice (a na "crtezu" sa leve strane). Malo zapetljano ali tako je kako je. Uspesno ste me zbunili sa vasim 6nula fajlovima i magnetnim trakama...

*sa leve strane gledajuci iz pravca gleve prema ekranu a ne obrnuto, dakle "vase levo" :)

Hvala Peko, ali te linkove smo vec imali prilike da citamo u jednoj drugoj raspravi ovde na ES-u, a da je teren "klizav" to priznajem al zato samo polako i natenane.

http://www.elitesecurity.org/t93798-2#992371

http://en.wikipedia.org/wiki/Claude_Shannon

http://youtu.be/Z86V_ICUCD4

Pitanja, komentari? Bilo sta?

Pa, ništa, implementiraj, vidi kako radi i biće ti jasno.

Nedeljko, nisam te bas najbolje razumeo, sta ce mi biti jasno?

Samo implementiraj i isprobaj. Onda će ti se samo razjasniti šta treba.

U kom smislu sta treba? O cemu pricas?

Razjasnice ti se ono sto treba da ti se razjasni cim budes implementirao svoju zamisao i isprobao je.

Kako da ne :) Hvala Shadowed sto advokatises, pitanje je bilo upuceno Nedeljku. Inace "Kako da ne" (onomatopeja kokoske valjda ;), "Ja b' patentirao", ko je ciji idol (mada od sveg srca predlazem Shakiru ;) i koga cega ili sta "to" jos uvek drzi smatram za offtopic.
"Zamisli", "Pa hajde koduj", "Razmisljaj u tom pravcu" i "Implementiraj" smatram za upravni, naredbodavni ili tako nekako govor u svakom slucaju bezobrazluk, na neka od tih pitanja sam odgovorio samo zato sto mi se ucinilo da cu bolje razjasniti neke stvari.
O mojim (ne)sposobnostima za programiranje sam pisao vec nekoliko puta, u medjuvremenu se nista nije promenilo tako da...



Reci vec jednom sta? Sta ce se razjasniti? Izgovori? Ustvrdi? Bilo sta?

Kao sto rekoh - sve sto je potrebno.

Ok, ako ne bi bilo ni pitanja ni komentara, a deluje mi da ne bi bilo zainteresovanih ni za dalju raspravu, sto se mene tice moze lock.

Nedeljko, hvala za sugestiju, ne bavim se programiranjem tako da najverovatnije nista od toga, hvala i za prilozen kod u onoj drugoj raspravi osvojio si malo pivo jer niko drugi nista nije prilozio. Ako budem stigao dopisacu i sta mislim o kodu.
Ako bi neko pomislio da ipak nesto moze da se isprogramira na osnovu ovog do sada napisanog na PP slobodno.
Zahvaljujem se svim ucesnicima u sve tri rasprave o kompresiji koje sam pokrenuo.