Tema
Registracija

beskonacna kompresija - konacno resenje

Zaključano
Nova tema
Štampanje RSS teme Kopiraj vezu do teme Podeli na Facebook-u Podeli na X-u (Twitter) Idi na poslednju poruku
  • 49 odgovora
  • 20.020 pregleda
beskonacna kompresija - konacno resenje 04.02.2005. u 04:32 · pre 264 meseci #1
Evo kako bi se mogli kompresovati/dekompresovati fajlovi:
1. Utvrdim velicinu fajla koji treba da se kompresuje i oznacim je sa N
2. napravim generator koji moze da generise sve fajlove koji su iste velicine kao i zadati fajl
3. napravim brojac koji moze da broji do 2^N

I. Prilikom kompresije:
Pustim generator da generise fajlove redom pocev od fajla koji sadrzi sve nule pa sve do fajla koji sadrzi sve jedinice, usput generisane fajlove poredim sa fajlom koji treba da se kompresuje. Kada dodje do poklapanja sa zadatim fajlom zaustavljam brojac i kao kompresovan fajl pamtim sledece podatke: a)Duzinu ulaznog fajla i b)Stanje na brojacu u trenutku poklapanja.

II. Prilikom dekompresije:
Na osnovu podataka iz kompresovanog fajla ponovo pravim generator fajlova koji moze da generise sve fajlove velicine kao i fajl koji treba da dekompresujem. Pustam generator u rad da generise sve fajlove redom pocev od fajla koji sadrzi sve nule i usput prebrojavam generisane fajlove. Generator zaustavljam u trenutku kad izgenerise "moj" pocetni fajl tj. kad stanje na brojacu bude identicno onom stanju koje sam "upamtio" u kompresovanom fajlu. Snimim fajl.

PS. Bog mi je dosapnuo



Potpis
Nemoj da pricas?
Re: beskonacna kompresija - konacno resenje 04.02.2005. u 07:12 · pre 264 meseci #3
Citat:
zi::: Stanje na brojacu ce ti zauzeti isto toliko mesta kao i sam file, pa je bolje da ga zipujes ;)


Sušta istina :o)))). Bravo, slatko si me nasmejao.
Potpis
int rand(void);

Those who do not understand Unix are condemned to reinvent it, poorly.

Upali lampicu — koristi Jabber!
Re: beskonacna kompresija - konacno resenje 04.02.2005. u 08:24 · pre 264 meseci #4
Trebalo je da pustite čoveka da iskodira. Ne bi ga napravio, ali bi se malo trenirao.

Uzgred, brojač bi u trenutku kad pronađe dati fajl bio identičan tom fajlu, jer svaka sekvenca bajtova nije ništa drugo nego "brojač" same sebe.
Re: beskonacna kompresija - konacno resenje 04.02.2005. u 09:21 · pre 264 meseci #6
Nisi dobro cuo Boga - sigurno je pominjao ovo:

A Mathematical Theory of Communication (C. E. Shannon)

:-)
Potpis
DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.digicortex.net/node/1 Videos: http://www.digicortex.net/node/17 Gallery: http://www.digicortex.net/node/25
PowerMonkey - Redyce CPU Power Waste and gain performance! - https://github.com/psyq321/PowerMonkey
Re: beskonacna kompresija - konacno resenje 05.02.2005. u 06:04 · pre 264 meseci #8
Mozda sam bio malo konfuzan prilikom prvog javljanja pa:
Citat:
zi::: Stanje na brojacu ce ti zauzeti isto toliko mesta kao i sam file, pa je bolje da ga zipujes ;)

Kao "brojac" istancovanih fajlova od strane generatora mislim da bi mogla da se iskoristi bilo koja "jaca" varijabla tipa Double, Extended. Broje do1.1*10^4932 tj. to je zapis od 19-20 cifara, a zauzima 10 bajtova na disku i to bi bilo sacuvano u kompresovanom fajlu kao drugi podatak (pored duzine fajla).
Citat:
jablan: 
Uzgred, brojač bi u trenutku kad pronađe dati fajl bio identičan tom fajlu, jer svaka sekvenca bajtova nije ništa drugo nego "brojač" same sebe.

Ovde se mozda nismo najbolje razumeli. Nisam pominjao da brojac "trazi" ili "pronalazi" dati fajl. U ovoj poruci sam objasnio sta podrazumevam pod brojacem. Kod mene generator je taj koji stancuje fajlove po redu i ciji bi se sadrzaj u odredjenom trenutku poklopio sa sadrzajem pocetnog fajla. Ako bi bio konstruisan onako kako ja mislim da bi mozda moglo tj. kao string boolean varijabli zauzimao bi i vise nego pocetni fajl tj. posto je boolean verijabla velicine 1 bajt tj. 8 bita, generator bi u trenutku pronalazenja zadatog fajla zauzimao 8 puta vise tj. za svaki bit jos 8 bitova, ali to je samo priveremeno. Kad odrade posao i generator i brojac se brisu i ostaje samo zapis kompresovanog fajla koji je dovoljan da se fajl kasnije regenerise tj. dekompresuje u ovom slucaju ponovo napravi.
Citat:
jablan: Trebalo je da pustite čoveka da iskodira. Ne bi ga napravio, ali bi se malo trenirao. :)

Nije dosta sto sam otkrio resenje, sad jos i da kodiram? ;)
Napravicu ako se bas niko ne prihvati posla ali sa mojim znanjem Delphi-ja to ce biti dugooootrajan proces.
Citat:
caboom: po Szasz-u se ovo naziva shizofrenija...

Ne, nego Vera.

Dakle jos jednom ali natenane:
Hocu da kompresujem fajl npr: 11010010
Na osnovu duzine fajla (8) program mi pravi generator koji stancuje sve redom fajlove duzine 8 bita
00000000
00000001
..
Brojac (varijabla) ih broji.
U trenutku kad generator istancuje fajl 11010010 zapisujem da je to npr. 175-ti fajl po redu.
Zapis kompresovanog fajla izgleda otprilike ovako 8/175 sto mi je dovoljno da fajl kasnije "regenerisem" tj. ponovo napravim po sledecem postupku:

Program iscita kompresovani fajl 8/175 napravi generator, pusti ga u rad i zaustavi kod 175 tog po redu fajla koji ovaj izgenerise - sto je ujedno i moj pocetni fajl.

U ovom primeru naravno nismo imali kompresiju jer 8 bita zauzima manje mesta od zapisa 8/175 (40 bita) ali kod vecih fajlova?
Vec fajl velicine oko 1KB zapisujem npr: kao 8976/2^6000 + 274 sto je zapis koji zauzima 136 bita. Dakle umesto 8976 bita - 136 bita
itd..
Sa jos vecim fajlovima jos vece iskoriscenje..
Potpis
Nemoj da pricas?
Re: beskonacna kompresija - konacno resenje 05.02.2005. u 08:35 · pre 264 meseci #9
Grešiš, ovaj grešiš silno sine!

Zaista će ti za datoteku od 1kb u najboljem slučaju trebati samo jedan bajt da bi je kodirao, ali u najgorem (ako su sve jedinice) će ti trebati 2409, tako da si dobio ekspanziju sa faktorom 2.5.

Code:

>>> x = 1000*8        # u bitovima
>>> y = 2**x        # 2^x
>>> print y
173766203193809456599982445949435627061939786100117250547173286503262376
022458008465094333630120854338003194362163007597987225472483598640843335
685441710193966274131338557192586399006789292714554767500194796127964596
906605976605873665859580600161998556511368530960400907199253450604168622
770350228527124626728538626805418833470107651091641919900725415994689920
112219170907023561354484047025713734651608777544579846111001059482132180
956689444108315785401642188044178788629853592228467331730519810763559577
944882016286493908631503101121166109571682295769470379514531105239965209
245314082665518579335511291525230373316486697786532335206274149240813489
201828773854353041855598709390675430960381072270432383913542702130202430
186637321862331068861776780211082856984506050024895394320139435868484643
843368002496089956046419964019877586845530207748994394501505588146979082
629871366088121763790555364513243984244004147636040219136443410377798011
608722717131323621700159335786445601947601694025107888293017058178562647
175461026384343438874861406516767158373279032321096262126551620255666605
185789463207944391905756886829667520553014724372245300878786091700563444
079107099009003380230356461989260377273986023281444076082783406824471703
499844642915587790146384758051663547775336021829171033411043796977042190
519657861762804226147480755555085278062866268677842432851421790544407006
581148631979148571299417963950579210719961422405768071335213324842709316
205032078384168750091017964584060285240107161561019930505687950233196051
962261970932008838279760834318101044311710769457048672103958655016388894
770892065267451228938951370237422841366052736174160431593023473217066764
172949768821843606479073866252864377064398085101223216558344281956767163
876579889759124956035672317578122141070933058555310274598884089982879647
974020264495921703064439532898207943134374576254840272047075633856749514
044298135927611328433323640657533550512376900773273703275329924651465759
145114579174356770593439987135755889403613364529029604049868233807295134
382284730745937309910703657676103447124097631074153287120040247837143656
624045055614076111832245239612708339272798262887437416818440064925049838
443370805645609424314780108030016683461562597569371539974003402697903023
830108053034645133078208043917492087248958344081026378788915528519967248
989338592027124423914083391771884524464968645052058218151010508471258285
907685355807229880747677634789376


Što je sve, samo ne broj od 19-20 cifara .

A da ne pričam o tome da će ti za datoteku veličine 1kb sa procesorom od
3 GHz trebati, u najgorem slučaju:

Code:

629724589381059130970437218052604287388344517286791514630620013420534811
997021122218940108828444061527879953475983937080478457173601502648558873
977827463194775219726529525232247586456437242569235223237641502239489008
141646650017662049212077263760232501671988587955355900555386861651694653
802820281681251818252296248479447827317922921981742117491938160450423715
707107236743580348461564278559519223931321220354351837758212145691571287
079399304589098301810691411336445562911696717505498774119445570644196484
543313822883575808623262669859991699542227642855223525094336106544774984
581119383436683986864939086487027517998429723079409781859368519391220878
458464788919160113994341919948812897587812829855883104709511858122064326
254393425608215803659407045774743991391266398582646206857068333219122431
845212736450278886882727998912363509623578342208430798367418961176266879
139926672784379806445442358894121853460912327448141694340956042537500948
063791828409522438574180386266744951611225969504631036794292448280650312
297822085903977092392771640634801617646151454378112133531027108268705534
484994793099747741921275954300454883500089600537237446107074333915211437
555653761719951367073843813833660858425694075818815960291307555354322329
128957899962266399022920772818959004766746473252051291625149659263036132
926208095103298637919405506831504233032058667383642939955866458448963566
649085424292051066534094237698699756178739662266319023466019152144340495
053388701834343517036377345017251160542535194466260529483539719624541755
317322501021993325649637001950065392156667280774982503819521109720913585
456592249284087950057807386523964779901618961274771441592460220399604131
959664306812508539824142444925941788303247391103947294913185047317413799
654199788936453417538857423998413209650406097540444569829977857443211016
793579272653191646968324755012712702523644909236936551594823635053814285
874821105775209568867593102332150288150963618081009289248858174427287668
134792270690573206470392067608015834614819759835578763680032738302874300
145990906522930020695454293238035250866484130876832960498804986001100444
386624105291281118475919546324231134568378136143500097189389232895012823
234655380320393651934406421794653487937821981479203957287828523222088221
461578796240650623607335087038820349528732130466863734104934146988357066
715005407070828527629496962281236951746642911691158288580888992068052061
7079269254447701 godina
256 dana
14 h
0 min
51 s


Ukoliko ti je poređenje stringova jedna procesorska instrukcija .
Re: beskonacna kompresija - konacno resenje 05.02.2005. u 08:47 · pre 264 meseci #10
Citat:

U trenutku kad generator istancuje fajl 11010010 zapisujem da je to npr. 175-ti fajl po redu.

Fajl je 210. po redu, ako brojiš od nule. Binarni zapis broja 210 je... 11010010. Dakle, brojač je jedak samom fajlu.

Pročitaj ipak link koji ti je dao Ivan.
Re: beskonacna kompresija - konacno resenje 05.02.2005. u 09:54 · pre 264 meseci #11
Citat:

Kao "brojac" istancovanih fajlova od strane generatora mislim da bi mogla da se iskoristi bilo koja "jaca" varijabla tipa Double, Extended. Broje do1.1*10^4932 tj. to je zapis od 19-20 cifara, a zauzima 10 bajtova na disku i to bi bilo sacuvano u kompresovanom fajlu kao drugi podatak (pored duzin0e fajla).


Pa ti bi sve kombinacije da svedes na 16 bajtova a to je ne moguce. Zdrav razum ti valda govori da onaj broj sto si naveo da je konacan a kombinacija je beskonacno.

Re: beskonacna kompresija - konacno resenje 05.02.2005. u 12:24 · pre 264 meseci #13
Ma to se opet Marko Tasic javlja sa usavrsenom verzijom svoje prethodne savrsene kompresije.
Ova kompresija je jos genijalnija jer sve informacije ovoga sveta moze da smesti u jedan double...
Sta li je sledece? Dokaz da se ni iz cega moze napraviti sve? Nova teorija nastanka univerzuma?
Re: beskonacna kompresija - konacno resenje 05.02.2005. u 15:29 · pre 264 meseci #14
Citat:
jablan: Nego, da ti nisi iz Leskovca, možda? ;)

Ja znam na šta si ciljao, pa se ne vređam, ali neki drugi korisnik ni kriv ni dužan, a igrom slučaja iz Leskovca, mogao bi da se uvredi zbog ovakve izjave.
Potpis
VMware VCP/Microsoft MCSE 2003/HP ASE
Re: beskonacna kompresija - konacno resenje 05.02.2005. u 16:42 · pre 264 meseci #15
Ja inace na ovu pretpostavku gledam sasvim pozitivno: drago mi je da vidim da neko razmislja, dodje do (na zalost jako pogresnog) zakljucka, i kasnije bude sretan zbog toga i odluci to podeliti sa drugima. Vazno da se istrazuje, ali, izgleda da je jos vaznije da se pre toga nesto i nauci. Knjiga, hvala Bogu, ima dovoljno.

Naslusao sam se mnogo slicnih primera, npr. kada je prijatelj u srednjoj skoli odusevljeno pricao da je smislio podmornicu od obicnog metala koja moze da ide na proizvoljnu dubinu u moru, ili pametnih likova koji su se ubijali da dokazu (pa su na kraju i 'dokazali') da je pisac neke fakultetske matematicke knjige pogresio u nekoj onovnoj teoremi i slicno.

Ja sam takodje upao u slicnu zamku: setajuci pored reke, nadosao sam na jednostavan dokaz da je kardinalni broj partitivnog skupa prirodnih brojeva jednak kardinalnom skupu realnih brojeva (skraceno: 2 na alef0 = c). Bio sam sretan dok rezultat nisam ispricao cimeru, koji me je pitao, aha, a ovaj slucaj? ... svejedno, zaboravi :) :)
Re: beskonacna kompresija - konacno resenje 05.02.2005. u 23:02 · pre 264 meseci #16
Citat:
Dusan Marjanovic: Ja znam na šta si ciljao, pa se ne vređam, ali neki drugi korisnik ni kriv ni dužan, a igrom slučaja iz Leskovca, mogao bi da se uvredi zbog ovakve izjave.

Uh pa nije čovek napisao nešto ne znam ni ja koliko strašno pa da se neko treći uvredi zbog fore, štaviše kao što zi:: reče, sve je prilično pozitivno. Da je sreća pa da ceo Leskovac (ma šta Leskovac, Srbija!) razmišlja o kompresijama...

Jednostavno, pre nekog vremena se (isto) pojavio momak sa sumnjivim predlogom za kompresiju, pa pomislih da nisu neki rod.

Ajde da ispoštujem protokol: izvinjavam se ako sam ikog uvredio svojim komentarom.
Re: beskonacna kompresija - konacno resenje 07.02.2005. u 03:22 · pre 264 meseci #17
A gde je ono: “Tako se ne prave aeroplani, a bogami ni kompresori”?
Necu koristiti varijablu za lociranje zeljenog fajla, vec nov fajl koji se sastoji samo iz nula tj. sve dok ne dodj do “poklapanja” sa pocetnim fajlom za svaki novo napravljeni fajl generisacu po jednu novu nulu I smestati je u novi fajl “sa strane”. Takav novonastali fajl posto je izuzetno jednolik tj. sastavljen je samo od nula savrsen je za pamcenje/kompresovanje uz pomoc “stare” vreste kompresije x*0 (pa I red je da “stara” vrsta kompresije pomogne “novoj” narocito sad prilikom nastajanja;) Tako bih fajl 11010010 iz mog prvog javljanja zapisao kao 10/210*0, a “najgori” (po Alef-u) (da ne kazem i “najozloglaseniji”;) tj. poslednji fajl iz primera sa 1K bi bio umesto 8000/2^8000 ili 8000/y, a y je brojka od oko 2500 cifara ili preciznije 2409 (zahvaljujuci Alef-u opet), dakle poslednji fajl bi bio 8000/301B*0;1b*0 sto bi tumacili kao 301 “prazan” bajt tj. bajt sastavljen samo od nula I jos jedan bit 0. Pretposlednji bi bio 8000/301B*0 sto bi tumacili kao 301 “praznih” bajtova tj. bajtova sastavljenih samo od nula. Prilikom odabira nacina zapisivanja fajlova odlucio sam se za najvece “brojeve” koje sam nasao na trenutnom trzistu. Naime Kilo, Mega, Giga, Tera..su sjajni za ovaj trenutni posao. Nisu brojevi u bukvalnom smislu reci ali su mnogo bolje resenje nego da zapisujem 2500 cifara u svoj kompresovani fajl. Ako bi hteo da kompresujem fajl velicine oko 1MB a ako je ekspanzija za njega I dalje oko 2,5 a generator/brojac ga nasao negde na ¾ puta tj.pred kraj trazenja, zapis bi otprilike bio 8000000/2M700B5b*0 tj. 2 Mega 700 bajta I 5 bita koji su svi nule. Primecujem naravno da broj oznaka u kompresovanom fajlu raste ali to je zanemarljivo u odnosu rast samog fajla koji zelimo da kompresujemo. Ko sto rekoh veci fajl – vece iskoriscenje tj. veci stepen kompresije.
Potpis
Nemoj da pricas?
Re: beskonacna kompresija - konacno resenje 07.02.2005. u 03:23 · pre 264 meseci #18
Duzan sam naravno I par objasnjenja u vezi sa javljanjem od 05.02.2005:
Do zbrke sa koriscenjem varijable u cilju lociranja trazenog fajla doslo je na sledeci nacin: Stvarno sam mislio da vrednost varijable Extended mogu da zapisem sa 20 cifara. U mojoj knjizi na srpskom jeziku lepo pise: Opis varijable Extended: Broj cifara: 19-20; Velicina 10 bajtova. Kada sam kasnije pogledao prirucnu pomoc Delphi-ja lepo je na engleskom pisalo sve isto sto sam primetio da je kolona Significant digits (eng. Znacajne cifre) prevedena kao Broj cifara. Valjda se misli da je onih par hiljada cifara posle prvih 19-20 beznacajno? Size in bytes: I dalje 10.

Te sad ja imam par pitanja za tebe Alef. U najboljem slucaju 1 bajt za kodovanje, u najgorem slucaju 2409 (bita) tj 301 bajt? Siguran sam za ShortInt varijablu da se nece mrdnuti sa za nju predvidjene velicine od 1 bajt ma sta upisao u nju. Ima raspon vrednosti -127 +127 tj 256 razlicitih vrednosti, pretpostavljam I da je konstruisana kao neka vrsta brojaca? Ako je iskoristim za zapisivanje vrednosti -127, -1, 0, 1 ili 127 uvek ce u memoriji zauzimati 1 bajt koliko je I predvidjeno za nju? Kao I Integer -32768 +32768 uvek ce zauzimati 2 bajta I kad u nju upisem 1 I kad upisem 32000? A LongInt 4 bajta. Na koji nacin varijabla Extended uspeva da se “smanji” na 1 bajt ako u nju upisem manji broj tj. ako fajl nadjem na pocetku pretrage, a da se prosiri na 300 bajta ako upisem veci broj tj. ako fajl nadjem pri kraju pretrage. Kako je konstrusana? Ako je za nju po specifikaciji rezervisano 10 bajtova gde dobija dozvolu da se prosiri/smanji, ko joj daje tu dozvolu?

Sto se tice drugog dela koda, o poredjenju stringova stvarno ne znam nista. Ni kako se porede ni koliko bi vremena trebalo za to. Ipak ako budem mogao uploadovacu program BerMetar koji simulira BER merenje na digitalnoj liniji tako sto generise pseudoslucajnu sekvencu bita, koduje je AMI ili HDB3 kodom zatim umece pogresne bite u kod I na kraju prilikom dekodovanja na osnovu krsenja pravila kodovanja zakljucuje koliko pogresnih bita je ubaceno. Program poredi veoma duge nizove bita (do 400000000 ~ 47,6GB) koji doduse ni u jednom trenutku nisu nigde zapisani vec samo neko vreme postoje u registrima. Poredjenje 2 niza od po 47GB bit po bit obavi se za ~ 45 sec.
-
Sorry nisam mogao da uploadujem program (cak ni zipovan):(
Potpis
Nemoj da pricas?
Re: beskonacna kompresija - konacno resenje 07.02.2005. u 22:05 · pre 264 meseci #19
Pozd.
Da napomenem, bez ulazhenja u dubinu gorenavedenog ... mislim da do trenutka kada bi tehnologija dostigla procesnu moc za rad nekog "naprednijeg" nachina kompresije od kopresija koje danas postoje, ta ista tehnologija bi u sferi velichina hard diskova (ili kako se jelda tada budu zvali) i brzine komunikacija verovatno pojam kompresije napravila besmislenim
Svako dobro.
Re: beskonacna kompresija - konacno resenje 07.02.2005. u 22:22 · pre 264 meseci #20
Citat:

U trenutku kad generator istancuje fajl 11010010 zapisujem da je to npr. 175-ti fajl po redu.


MajorFatal, ovo sto si ti opisao se ostro krsi sa Shannonovom teorijom informacija (mislim da bi stvarno trebalo da procitas taj rad) - sspasic ti je vec pokazao gde si pogresio u rezonu.

Nije nista strasno, svi mi ponekad pogresimo u rezonu - nemoj samo previse da "odlutas" :-) Ako si nameracio da uzmes pare od venture capitala, mislim da bi morao malo bolje da smislis strategiju, oni su posebno alergicni na ideju revolucionarnih kompresija - pogotovu posle fijaska sa ZeoSync i slicnim firmama :-)

Procitaj i arhive USENET grupe comp.compression - pogotovu FAQ, gde su primeri vrlo slicni tvojem opisani i pokazano je zasto ne rade (groups.google.com)
Potpis
DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.digicortex.net/node/1 Videos: http://www.digicortex.net/node/17 Gallery: http://www.digicortex.net/node/25
PowerMonkey - Redyce CPU Power Waste and gain performance! - https://github.com/psyq321/PowerMonkey
Tema je zaključana, nove poruke nisu moguće.

Premeštanje teme