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

Kompresija random-like podataka

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

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

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
109.93.0.*



+557 Profil

icon Re: Kompresija random-like podataka07.10.2011. u 16:59 - pre 151 meseci
Citat:
Nedeljko: Pa, ne možeš ni velike random-like fajlove da komprimiješ. Imao si gomilu brojača, koje si negde morao da pamtiš, jer bez njih nema dekompresije.

Nije nikakav problem "komprimovati" niz tako da se ne može posle dekomprimovati.


Zasto bi pamtio sve 'iteracije' do kojih je dolazilo u medjuvremenu ako ti uvek isti algoritam daje uvek iste rezultate pocevsi od istih pocetnih vrednosti? Zasto bi pamtio gomilu brojaca?

Dovoljna ti je bilo koja iteracija do koje bi dolazilo u medjuvremenu i algoritam tj.program za kompresiju/dekompresiju? Polazis od prvog random (ili random-like fajla) Rf1 velicine 100.000 bajta, primenjujes na njega algoritam bzip2 (ili neki drugi ) nazvacemo ga A1 (algoritam1) dobices veci fajl od pocetnog koji je najverovatnije ponovo random strukture bar gledajuci iz ugla bzip2 tj. A1 tj. primenjenog algoritma, novi fajl je velicine 100.807 bajta, nazvacemo ga Rf2 (random fajl 2), ponovo bzip2 (A1) dobices Rf3 (jos veci od pocetnog i od Rf2 primeti i da imas prirastaj jer pocevsi od 100.807 uvecanje za recimo 10% je vece (u broju bajtova) nego kad kreces od 100.000 bajta) itd... ponovo bzip2 vise puta dobijaces sve vece fajlove koji su takodje random strukture Rf4, Rf5, Rf6.. Rf1000. 1000.- ti fajl po redu bi mogao da ima i milion bajta ili vec zavisi od toga koliko puta je primenjen bzip2. Ako bi postojao inverz algoritma bzip2 (A2 recimo) i ako bi nam Rf1000 fajl od milon bajta bio pocetni fajl random strukture uz pomoc inverza bzip2 (A2) mogli bi smo uz dovoljan broj primena tog algoritma da smanjimo Rf1000 na Rf1, tj sa milion bajta na 100.000 bajta, jedino sto ne bi mogli je da idemo ispod 100.000 bajta jer niko ne garantuje da bi inverz bzip2 (A2) bio uspesan nad takvim rasporedom bita u Rf1, takodje u nekom trenutku neki od predvidjenih random fajlova recimo Rf538 bi mogao da ima takav raspored bita koji lici na neku uredjenu strukturu ili je jako slican fajlu pogodnom za statisticke nacine kompresije, u tom slucaju bzip2 ce da odradi svoj posao kako treba i Rf539 ce biti manji od Rf538, mada verovatnoca da se desi ovako nesto je veoma mala mada nije ni nemoguce...

Medjutim, posto ovo skoro pa nista ne dokazuje osim da je pojedine random fajlove (Rf1000) moguce kompresovati i to pod uslovom da postoji bzip2 inverz, da ne bi gurali raspravu u pogresnom smeru...
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
109.93.0.*



+557 Profil

icon Re: Kompresija random-like podataka07.10.2011. u 17:00 - pre 151 meseci
Na primer 'sadrzaj fajla' tj. duzina 7. bita. Uglaste zagrade 'glume' fajl sistem: Pokusacu da dokazem da je moguce nacinom koji sam predlozio kompresovati sve fajlove iz jednog opsega i ujedno da predlozim nacin za izvodjenje toga u praksi na danasnjim racunarima sa danasnjim fajl sistemima: Svih 'fajlova' duzine 7.bita ima tacno 2^7 tj. 128. fajlova sve ukupno.
126. 'fajlova' se moze zameniti kombinacijama bita duzine 1., 2., 3. .. 6. bita jer: 2^1=2 + 2^2=4 + 2^3=8 + .. 2^6=64 = 126. Preostala dva 'fajla' duzine 7. bita (a pod rednim brojevima 127. i 128.) mogu se 'zameniti' (kompresovati, kodovati...) sa po dva fajla duzine 1. bit a da pri tom oba ta fajla budu jasno razgraniceni od strane fajl sistema odnosno operativnog sistema pod kojim se to radi:

Slikom:

1.) [0000000] -> [0]
2.) [0000001] -> [1]
3.) [0000010] -> [00]
4.) [0000011] -> [01]
5.) [0000100] -> [10]
6.) [0000101] -> [11]
7.) [0000110] -> [000]
itd...
.
.
.
125.) [1111100] -> [111110]
126.) [1111101] -> [111111]
-----------------------------------
127.) [1111110] -> [1][0]
128.) [1111111] -> [0][1]

Da ne pisem bas svih 128. kombinacija od po 7. bita :) Svaki fajl ima svoj 'heder' i 'futer' (pocetak i kraj). Dakle za svih 128. razlicitih kombinacija bita duzine 7. tj. 'fajlova' duzine 7. bita pronadjeno je 128. razlicitih kombinacija kracih po broju upotrebljenih bita. Ima 126. 'jednostrukih' fajlova i dva 'dupla' fajla ( koji se sastoje od po dva 'fajla' duzine 1. bit ).
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
109.93.0.*



+557 Profil

icon Re: Kompresija random-like podataka07.10.2011. u 17:01 - pre 151 meseci
7. bita za 'sadrzaj fajla' je odabrano da bi za 'poslednja 2' 'fajla' moglo da se napise i ovako:


-----------------------------------
127.) [1111110] -> [[1][0]]
128.) [1111111] -> [[0][1]]

Sada su i 'poslednja 2' 'fajla' zapakovana u svoje zagrade i potencijalni engine moze da ih razgranici od okoline kao posebne fajlove a da unutra pronadje po dva posebna fajla.
Za sada vizuelno deluje da ima kompresije jer je na spisku fajlova sa desne strane svaki zapis kraci, medjutim dve uglaste zagrade ako bi bile deo nekog fajl sistema mogle bi da budu 'teske' i 15Kbita recimo, u tom slucaju ako bi neko racunao gde je donja granica u velicini fajlova za postojanje ovakve kompresije morao bi da uzme u obzir da su sa desne strane upotrebljena tri para zagrada tj. 2 * 15Kbit (zagrade) + 7 bita bi morala biti najmanja velicina (duzina) 'sadrazaja fajla' koji moze da se kompresuje.


[Ovu poruku je menjao MajorFatal dana 07.10.2011. u 18:26 GMT+1]

[Ovu poruku je menjao MajorFatal dana 07.10.2011. u 18:27 GMT+1]
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
*.dynamic.isp.telekom.rs.



+557 Profil

icon Re: Kompresija random-like podataka19.10.2011. u 10:08 - pre 151 meseci
Ona 'poslednja 2' fajla bi mogla da se koduju (kompresuju) i ovako:

127.) [1111110] -> [ ]
128.) [1111111] -> [ [0]]

1 'prazan fajl' tj. samo heder i futer bez 'sadrzaja' u bitima i jedan fajl sa sadrzajem od 1. bita koji je opet zapakovan u veci fajl, tada bi donja granica kompresije bila na 15Kbita + 7. bita (samo 1 par zagrada tj. heder, futer zapakovani u fajl u slucaju drugog fajla) ali za potrebe objasnjavanja eventualne izvedbe ove kompresije u praksi ja ipak predlazem 'duple' ili bolje reci 'visestruke' fajlove kao u prethodnim postovima.
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
*.dynamic.isp.telekom.rs.



+557 Profil

icon Re: Kompresija random-like podataka19.10.2011. u 10:09 - pre 151 meseci
U iskrenoj nadi da prethodne redove neko nije protumacio kao da tvrdim da 7. bita moze da se kompresuje...

Posle ovoga jedino sto jos preostaje da se vidi je da li odredjeni OS i fajl sistem podrzavaju (omogucavaju) postojanje fajlova duzine samo 1 bit (zbog duplih 'fajlova' na crtezu sa desne strane ciji je sadrzaj po dva fajla velicine 1 bit ), ukoliko to nije slucaj tj. ukoliko i tu postoji neka donja granica u velicini fajla na primer X bita (mogu da pretpostavim recimo da je 1 bajt najmanja moguca velicina fajla na nekom fajl sistemu ako je tako bilo lakse za izvedbu ljudima koji su ga pravili) u tom slucaju broj bita potreban za obelezavanje 2 para uglastih zagrada (tj. dva hedera i futera za pojedinacne fajlove) + 2X (velicina sadrzaja u bitima 2 fajla sa desne strane zapakovana u 1 'dupli' fajl) + 7 bita bi bila donja granica za velicinu sadrzaja fajla koji moze da se kompresuje ovom metodom. SVAKOG fajla iznad te granice.
Nemoj da pricas?
 
Odgovor na temu

BiF

Član broj: 39763
Poruke: 90
*.adsl-a-11.sezampro.rs.



Profil

icon Re: Kompresija random-like podataka20.10.2011. u 16:42 - pre 151 meseci
Bespotrebno kompliikujes sa file-sistemom.
Na kraju sve moras da svedes na nule i jedinice: nema uglastih zagrada, razmaknica itd.
Otvori notepad, otkucaj jedno slovo, i snimi taj fajl na disk, pa onda idi na properties tog fajla. Obrati pažnju na "Size" i "Size on disk"

Pozdrav i želim ti sve najbolje u kompresiji.
Nijedan nepušač još nije preživeo.
 
Odgovor na temu

Stijak
Beograd

Član broj: 97934
Poruke: 300
*.adsl.alicedsl.de.

Sajt: www.stijak.com


+37 Profil

icon Re: Kompresija random-like podataka27.10.2011. u 00:27 - pre 151 meseci
he he he - smiješno mi sve ovo... Kao što ti neko već reče kakve uglaste zagrade - kakve gluposti - sistem pamti samo nule i jedinice... Čak i kada je sadržaj fajla manji - moraš uzeti koliko podataka zapamti file sistem vodeći računa o tim file-ovima... I da su podaci u nekom nizu nula jedinica i ti tu moraš skontati šta je nula, šta je jedinica, šta je početak file-a šta kraj, kako se koji file zove i gdje se nalazi... Kod ovog tvog sistema kompresije sedam bitova ničega toga nema - sem što si lupio neke uglaste zagrade... I ti sad misliš da bi kod većih brojeva došlo do kompresije - tj. težina file sistema postala manja - ali ne baš...

Inače - ako zanemariš podatke koji se nalaze u file sistemu - evo ti odličnog kompresionog algoritma - snimaš u file-ove samo jedinice - kada se god pojavi nula - file na tom mjestu presječeš i povećaš numeraciju kojom označavaš te file-ove... Dekompresor kasnije samo spoji te file-ove i doda koliko nula treba...

Znači ako su kompresovani fileovi ekstenzije data 10110001011110100 kompresuješ kao 1.data u kome se nalazi 1, 2.data u kome se nalazi 11, 5. data u kome se nalazi 1, 6.data u kome se nalazi 1 7.data u kome se nalazi 1111 i 8.data u kome se nalazi 1 i 10.data koji je prazan... To onda možeš pojednostaviti pišući samo broj jedinica - pa ti npr. 7.data ti bude 100 (binarna četvorka za 4 jedinice) - pa to možeš pojednostaviti i npr umjesto 7.data pisati 7.1.data u kome je 1 i 7.3.data koji je prazan... i tako od 19 bitova dobiješ samo 5... He he - a praveći sve ove file-ove si potrošio nekoliko kilobajta u filesistemu (što se ne može teorijski izbjeći, ali se može umanjiti - i u najboljem slučaju bi opet bilo više nego ovih 11 bite-ova koliko je razlika) i ko zna koliko još u zaokružavanju file-ova u sektore.

Ili još bolji sistem - podatke napišeš u imena praznih file-ova i pretvoriš ogroman file kompresijom u ništa... pa ovaj moj file gore snimiš kao 10110001011110100.data (može i efikasnije u hex ili nekom jačem encoding-u - ali nije sad bitno - i ako je previše za jedno ime - podjeliš i smisliš način da ih numerišeš... ;) Kako je ovo dobro ;) Čak i kada ideš na propertires piše file on disk 0! Ha ha ha - mislim da sam nadmašio tvoju ideju...

A inače - ne kontam zašto ti treba pomoć drugih - ne treba ti ni program za to - treba ti samo moćan digitron koji može da radi sa velikim brojevima takav ti je i windowsow, imaš ih po netu koliko hoćeš, imaš jedan na http://www.wolframalpha.com/ (samo treba naučiti komande... Iznalupaš se cifara - da bude dovoljno dugačak da bi tvoja metoda radila (preko 32 - da dobiješ neki kvazirandom broj i pokušaš skontati način da to kompresuješ svojom metodom......

Znači naprimer 1307652984 (mada će tebi trebati veći brojevi) izvadiš logoritam po dva, pa skontaš koloko ti je još ostalo, pa logoritam od ostatka po 3, pa sve tako i ručno to sve središ - zapišeš brojeve koje moraš zapamtiti poslije kompresije - to bi bili cjelobrojne vrijednosti ovih logoritama... I vidiš da li je to duže ili kraće od originala... Koliko kontam ti bi file skraćivao kao 1^x + 2^y + 3^z +... pa moraš pamtiti ove x,y,z...

[Ovu poruku je menjao Stijak dana 27.10.2011. u 01:56 GMT+1]
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
*.adsl.beocity.net.



+557 Profil

icon Re: Kompresija random-like podataka17.12.2011. u 00:47 - pre 149 meseci
Al' sam zabagovo ;) vise od mesec dana za 1. odgovor...

Citat:
BiF: Bespotrebno kompliikujes sa file-sistemom.
Na kraju sve moras da svedes na nule i jedinice: nema uglastih zagrada, razmaknica itd.
Otvori notepad, otkucaj jedno slovo, i snimi taj fajl na disk, pa onda idi na properties tog fajla. Obrati pažnju na "Size" i "Size on disk"

Pozdrav i želim ti sve najbolje u kompresiji.


Citat:
BiF: Bespotrebno kompliikujes sa file-sistemom.


1.) U ovoj poruci: http://www.elitesecurity.org/t158990-1#2890236 sam pokusao da na najjednostavniji i najkraci nacin izlozim ideju pa ako mislis da nije mnogo komplikovano, u svakom slucaju ne pominje se fajl sistem.

2.) Mozda bespotrebno komplikujem sa fajl sistemom, ali kako da fajlove razdvojim od fajl sistema, engine-a koji ih cita, kompresora/dekompresora, os-a? Bez toga ni fajl ne postoji vec je samo gomila nabacanih bita? U svakom slucaju za 2^N - 2 fajlova jednakih duzina moguce je naci 2^N - 2 kombinacije bita krace po duzini. Preostaju jos 2 fajla koja ne moraju da dozive ekspanziju vec mogu da ostanu iste duzine kao i originalni fajlovi koje bi trebalo da zamene. Za sve duzine fajlova iznad 8. bita to je vise od 99,9% fajlova koji se mogu kompresovati i manje od 0,1% fajlova koji ne mogu. Sa povecanjem broja bita koji ucestvuju u duzini fajla, procenat fajlova koji ne bi mogli da se kompresuju meri se promilima pa jos manjim delovima procenta...

3.) Do uvodjenja zagrada da glume fajl sistem je doslo tako sto sam u jednom trenutku pogresio i poceo da poredim duzinu 'dvostrukih' fajlova sa sadrzajem 'jednostrukih' a takodje 'kompresovanih' umesto sa originalnim, i tako sto je Nedeljko nesto sto je trebalo da ilustruje fajl protumacio kao kodnu rec, i tako sto cim sam napisao space izmedju 2 'fajla' ljudi su pozeleli da ga koduju i tako sto...

Citat:
BiF
Na kraju sve moras da svedes na nule i jedinice: nema uglastih zagrada, razmaknica itd.


Za pocetak evo ti par uglastih zagrada i razmaknica: [ ] [[ ] ]], znaci ima ih, onda definisi to "sve" koje pominjes jer ne verujem da si mislio i na nebo i na oblake kao u onom filmu "Matrix", te takodje svi podatci na kompjuteru su vec u vidu nula i jedinica tako da je i taj deo price odradjen.

Citat:
BiF: Otvori notepad, otkucaj jedno slovo, i snimi taj fajl na disk, pa onda idi na properties tog fajla. Obrati pažnju na "Size" i "Size on disk"


Hvala za savet ali samo si jos zaboravio da kazes sta bi trebalo da zakljucim iz tog malog eksperimenta? Size: 1. byte, Size on disk: 8. KB (kodovanje ASCII jelte), ako izbrisem i to jedno slovo: Size: 0. byte, Size on disk: 0. byte (sto je nemoguce jer negde moraju da postoje podaci i da postoji fajl i da je txt ekstenzije i gde sam ga snimio itd...), ako upisem 2. slova: Size: 2. bytes, Size on disk: 8. KB (i dalje, isto kao kad je jedno slovo u pitanju) ali ako dva fajla od po 1. slovo tj. 1. byte snimim u folder velicina foldera nece biti 8KB kao sto sistem rezervise za fajl velicine 2. bajt-a, vec 16 KB (duplo vise) sto znaci da moraju da budu razdvojeni fajlovi svaki posebno i da se svakom posebno pristupa sto opet znaci da bi donja granica velicine kompresovanog fajla morala da bude 16 KB + 1 byte ako bi se radilo na windousima i ako bi velicinu foldera sa dva fajla unutra poistovetili sa 'spoljasnjim' uglastim zagradama koje sam nacrtao oko ona dva 'dvostruka fajla' na jednom od skorasnjih 'crteza' tj. to bi bila i najmanja moguca duzina sadrzaja originalnog fajla koji moze da se kompresuje...

Citat:
BiF: Pozdrav i želim ti sve najbolje u kompresiji.


Hvala! Hvala i sto se nisi naljutio za onu 'prozivku' od pre par poruka ("nisam cuo za BiF-a" ;) drago mi je da upoznam 'kolegu', ako me sta cudi da nema i vise ljudi koji su se bavili ovom problematikom, meni je ovo tako zanimljiva glavolomka da me vec godinama drzi.
Nemoj da pricas?
 
Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249



+96 Profil

icon Re: Kompresija random-like podataka17.12.2011. u 17:25 - pre 149 meseci
Apsolutno sve na hard disku mora da se pretvori u namagnetisane čestice koje drže informaciju. Jedna namagnetisana čestica može da drži samo jedan bit informacije, to jest jedna čestica može da predstavlja ili nulu ili jedinicu. Čestica ne može da predstavlja ni otvorenu ni zatvorenu zagradu, niti bilo šta drugo što nije nula ili jedinica. Da bi predstavio i svoje zagrade i bilo šta drugo u fajl sistemu moraš nekako da ih konvertuješ u niz nula i jedinica. Ne možeš da preskočiš tu konverziju simbola u niz nula i jedinica, jer se na hard disku fizički vide samo nule i jedinice.

Niko se nije bavio ovim problemom na ovaj način, jer problem ne može da se reši na taj način. Kome god da ispričaš svoje rešenje reći će ti isto. To nije rešenje.
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
*.adsl.beocity.net.



+557 Profil

icon Re: Kompresija random-like podataka18.12.2011. u 15:36 - pre 149 meseci
Jasno mi je to ali mi nije jasno iz cega si ti zakljucio da ja ne mislim da je tako? U ovoj poruci http://www.elitesecurity.org/t151770-5#2966226 sam napisao da svi oni podaci koje sam ilustrovao zagradama mogu da imaju i 15 KB podataka tj. sve ono sto ne spada u sadrzaj fajla tj. sluzi kao opis fajla ili nacina raspakivanja, bzip2 fajl ima 4. uvodna bajta koja sluze tome, takodje sam objasnio kako bi taj deo fajla ucestvovao u ukupnoj racunici, zagrade su tu samo da ilustruju da ako originalni fajl ima zaglavlje ima i kompresovani pa se porede ili samo sadrzaji tih fajlova ili svi ukupni podaci koji ucestvuju prilikom raspakivanja fajla, ali zaista je nebitno, za 99% fajlova moguce je naci krace ekvivalente, za ona preostala dva bitno je da ne mora da dodje do ekspanzije dakle kompresija random fajlova je moguca ili bar moguca za 99% fajlova.
Nemoj da pricas?
 
Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249



+96 Profil

icon Re: Kompresija random-like podataka18.12.2011. u 19:57 - pre 149 meseci
Izvini, izgubio sam te.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.3gnet.mts.telekom.rs.



+2789 Profil

icon Re: Kompresija random-like podataka18.12.2011. u 22:12 - pre 149 meseci
Slušaj ovako:

Ako želiš da komprimuješ proizvoljan niz bitova tako da se posle komprimovani oblik može dekomprimovati i dobiti original, onda različitim nizovima bitova na ulazu moraju odgogvarati različiti nizovi bitova na izlazu.

Ako želiš da komprimovani oblik nikada ne bude duži od nekomprimovanog, onda

prazan niz bitova moraš komprimovati njime samim.

Nizova dužine 1 ima 2. Obzirom da si na komprimovanje praznog niza već potrošio prazan niz, ostaje ti da nizove dužine 1 komprimuješ nizovima dužine 1, čime ćeš i njih sve potrošiti.

Nizova dužine 2 ima 4. Obzirom da si nizove dužine ne veće od 1 već potrošio, nizove dužine 2 moraš komprimovati nizovima dužine 2. Time ćeš i njih sve potrošiti.

Nizova dužine 3 ima 8. Obzirom da si nizove dužine 2 i manje već potrošio, nizove dužine 3 moraš komprimovati njima samima, čime ćeš i njih sve potrošiti.

I tako dalje.

Stoga bilo kakva transformacija koja dopušta vraćanje originala i koja ne produžava nijedan niz bitova, neće nijedan niz bitova skratiti.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
*.adsl.beocity.net.



+557 Profil

icon Re: Kompresija random-like podataka19.12.2011. u 18:00 - pre 149 meseci
Citat:
Mihajlo Cvetanović: Izvini, izgubio sam te.


Ma nema problema.

Citat:
Nedeljko: Slušaj ovako:

Ako želiš da komprimuješ proizvoljan niz bitova tako da se posle komprimovani oblik može dekomprimovati i dobiti original, onda različitim nizovima bitova na ulazu moraju odgogvarati različiti nizovi bitova na izlazu.


Ne! Ne zelim! Ne zelim da komprimujem proizvoljan niz bitova tako da se posle komprimovani oblik može dekomprimovati i dobiti original, vec mislim da je moguce komprimovati 99,9% proizvoljnih nizova bita koji su duzi od odredjene granice u duzini niza bita tako da se posle komprimovani oblik može dekomprimovati i dobiti original.

Citat:
Nedeljko:  onda različitim nizovima bitova na ulazu moraju odgogvarati različiti nizovi bitova na izlazu.


...i kraci da bismo to mogli nazvati kompresijom.

Citat:
Nedeljko
Ako želiš da komprimovani oblik nikada ne bude duži od nekomprimovanog, onda

prazan niz bitova moraš komprimovati njime samim.

Nizova dužine 1 ima 2. Obzirom da si na komprimovanje praznog niza već potrošio prazan niz, ostaje ti da nizove dužine 1 komprimuješ nizovima dužine 1, čime ćeš i njih sve potrošiti.

Nizova dužine 2 ima 4. Obzirom da si nizove dužine ne veće od 1 već potrošio, nizove dužine 2 moraš komprimovati nizovima dužine 2. Time ćeš i njih sve potrošiti.

Nizova dužine 3 ima 8. Obzirom da si nizove dužine 2 i manje već potrošio, nizove dužine 3 moraš komprimovati njima samima, čime ćeš i njih sve potrošiti.

I tako dalje.


Kao sto rekoh, ne zelim, al ajde, ...itd nizova duzine 4 ima 16, nizova duzine N ima 2^N, ali ako bih uveo granicu za mogucnost kompresije recimo na 7 KB jer pretpostavljam da nikad niko ne bi otkucao 1 slovo u notpedu pa posle toga jos pozeleo da ga sacuva i kompresuje, nizova duzine krace od te granice ima: 2^7000 + 2^6999 +2^2998 + .. + 2^1 + 2^0 = mnogo, znaci svi oni ne bi mogli da budu komprimovani a svi nizovi bita iznad te granice duzine bita bi mogli kao sto danas popularnim metodama mogu da budu komprimovani nizovi koji nisu random a ne mogu oni koji su random ili random like.

Citat:
Nedeljko: Stoga bilo kakva transformacija koja dopušta vraćanje originala i koja ne produžava nijedan niz bitova, neće nijedan niz bitova skratiti.


Kao sto rekoh vise puta tokom ove tri rasprave koje sam pokrenuo produzavace nizove bita krace od odredjene granice a komprimovace one duze od te granicne vrednosti...
Nemoj da pricas?
 
Odgovor na temu

BiF

Član broj: 39763
Poruke: 90
109.121.53.*



Profil

icon Re: Kompresija random-like podataka08.01.2012. u 17:06 - pre 148 meseci
primer sa notepad-om pokazuje da ti se vise isplati da kompresovane podatke ubacis u jedan file, a ne u vise file-ova (2, 5, 50,...), jer ces tako ustedeti prostor. sto se tice uglastih zagrada i razmaknica, naravno da postoje u smislu u kom si ih ti naveo. hteo sam da ti kazem da i te uglaste zagrade i razmaknice moras da pretvoris u nule i jedinice.
Nijedan nepušač još nije preživeo.
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
*.adsl.beocity.net.



+557 Profil

icon Re: Kompresija random-like podataka06.02.2012. u 16:48 - pre 147 meseci
Citat:
Stijak:
he he he - smiješno mi sve ovo...

A meni nimalo.

Citat:
Stijak:
Kao što ti neko već reče kakve uglaste zagrade - kakve gluposti - sistem pamti samo nule i jedinice...


Rece BiF, ali izgleda da se nismo bas najbolje razumeli, ne zelim ja da u niz bita utaknem i poneku uglastu zagradu, svestan sam da bi i ta zagrada morala biti kodovana nulama i jedinicama, zagradama sam samo hteo da ilustrujem postojanje zaglavlja u kompresovanom fajlu i to da i taj deo fajla nosi neku kolicinu informacija te zauzima neki prostor te se mora uzeti u obzir kada se razmatra da li bi kompresija mogla da postoji ili ne, a ako da, u kolikoj meri, hvala ti za epitet, nisu gluposti nego pametne, mudre i skoro pa genijalne stvari ali si ti tupav jadan pa posto ne razumes cini ti se da su gluposti u pitanju, a "sistem" nek pamti sta hoce.

Citat:
Stijak:
Čak i kada je sadržaj fajla manji - moraš uzeti koliko podataka zapamti file sistem vodeći računa o tim file-ovima...


Negde je fajl napisano tako, a ponegde kao 'fajl' pod znacima navoda pa obrati paznju...dakle nisu uvek fajlovi u bukvalnom smislu te reci u pitanju, pogotovo ne takvi da bi OS mogao ili morao da ih vidi kao fajlove. Verovatno je na tim mestima trebalo da koristim izraz: 'niz bita'.

Citat:
Stijak:
I da su podaci u nekom nizu nula jedinica i ti tu moraš skontati šta je nula, šta je jedinica, šta je početak file-a šta kraj, kako se koji file zove i gdje se nalazi...


Pa recimo ako bih imao niz od 20. bita a u zaglavlju takvog fajla podatak: 7,5,8. znao bih da se u nizu od 20. bita krije 3. "fajla" od po 7. bita, 5. bita i 8. bita, "sistem" ne mora da ima nista sa tim ovo bi dekompresor morao da zna, da pravilno protumaci i dekompresuje fajl, a taman posla da im svima dajem imena.

Citat:
Stijak:
Kod ovog tvog sistema kompresije sedam bitova ničega toga nema - sem što si lupio neke uglaste zagrade...


Sistem kompresije 7. bitova?? Lupio??? Opet ti hvala za epitet. Kad te lupim videces sve zvezde i "sistem kompresije sedam bitova" tamo gde ga nema :) Vrati se na ovu poruku: http://www.elitesecurity.org/t151770-5#2974005 i procitaj pocetak poruke, i sad kao u monopolu nekoliko polja (poruka) unazad i eto te u zatvoru, sad ti treba 2. sestice da bi izasao.

Citat:
Stijak:
I ti sad misliš da bi kod većih brojeva došlo do kompresije - tj. težina file sistema postala manja - ali ne baš...


Pa sad, to sam ja slucajno imao notepad na kompu pa su rezultati ispali takvi kakvi su, ali da sam recimo imao Blender i otvorim dokument upisem 1. slovo i sacuvam, pa odem na propretis: Size: 67. KB, Size On Disk: 68. KB, kao sto vidis sa povecanjem fajla kolicina osnovnih podataka koji su potrebni za opisivanje atributa tog tog fajla postaje zanemarljivo mala u odnosu na velicinu samog fajla, tj. 1KB na 67KB, a za 1.bit je bilo 7KB.
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
*.adsl.beocity.net.



+557 Profil

icon Re: Kompresija random-like podataka06.02.2012. u 16:48 - pre 147 meseci
Citat:
Stijak:
Inače - ako zanemariš podatke koji se nalaze u file sistemu -

Ne zanemarujem nego bas naprotiv uzimam u obzir.

Citat:
Stijak:
evo ti odličnog kompresionog algoritma - snimaš u file-ove samo jedinice - kada se god pojavi nula - file na tom mjestu presječeš i povećaš numeraciju kojom označavaš te file-ove... Dekompresor kasnije samo spoji te file-ove i doda koliko nula treba...


Bas je odlican, samo... koliko nula treba dodati? Moras i taj podatak da pamtis ako hoces da rekonstruises originalni fajl.
Deluje mi kao da si hteo da niz bita razdvojis na mnogo manjih "fajlova" koji su svi iste strukture ispred nule pa ih slede jedinice i da onda otseces sve "leading zero" (vodece nule) ali ovde nule ne ucestvuju samo kao brojcana vrednost nego su neka kodirana informacija tako da ne mozes tek tako da ih odseces ili bar ne a da ne znas (ne pamtis) koliko ih je bilo, a informacija koliko je nula bilo bi opet zauzimala neki prostor u kompresovanom fajlu.
I to nije jedini deo rezona koji ne valja kod tvog predloga, cak i da mogu da se zanemare podaci koji su predvidjeni da ih procita file sistem i da ne moras da pamtis broj nula koje si odsekao sta ces sa fajlovima koji imaju mnogo vise jedinica nego nula? Recimo fajl se sastoji od 98% jedinica i samo 2% nula, iskoriscenje za takav fajl kod ovog tvog predloga bi bilo 2% tj. fajl bi kompresijom skratio za samo 2%. Inace pravljenje vise fajlova na mesto jednog ne mora uvek da bude problem, ima fajlova za koje bi zamena bila samo 2 nova fajla recimo, a u vezi ovog tvog sistema "najnezgodniji" fajl bi bio strukture 01010101... itd tj. naizmenicno nule i jedinice bas bi bilo mnogo seckanja na manje fajlove duzine 1. bit.
Inace bas mi nije jasna logika kojom si se vodio kad si ovo napisao, recimo da mozes da zanemaris podatke koje potrosi svaki fajl u file sistemu i da tebi neko kaze: "evo ti odlicnog kompresionog algoritma - snimas u file-ove samo nule - kad god se pojavi jedinica - file na tom mestu preseces i povecas numeraciju kojom oznacavas te file-ove...Dekompresor kasnije samo spoji te file-ove i doda koliko jedinica treba..."? sta bi mu rekao tj. zasto nije moguce tako?[/quote]

Citat:
Stijak:
Znači ako su kompresovani fileovi ekstenzije data 10110001011110100 kompresuješ kao 1.data u kome se nalazi 1, 2.data u kome se nalazi 11, 5. data u kome se nalazi 1, 6.data u kome se nalazi 1 7.data u kome se nalazi 1111 i 8.data u kome se nalazi 1 i 10.data koji je prazan... To onda možeš pojednostaviti pišući samo broj jedinica - pa ti npr. 7.data ti bude 100 (binarna četvorka za 4 jedinice) - pa to možeš pojednostaviti i npr umjesto 7.data pisati 7.1.data u kome je 1 i 7.3.data koji je prazan... i tako od 19 bitova dobiješ samo 5... He he - a praveći sve ove file-ove si potrošio nekoliko kilobajta u filesistemu (što se ne može teorijski izbjeći, ali se može umanjiti - i u najboljem slučaju bi opet bilo više nego ovih 11 bite-ova koliko je razlika) i ko zna koliko još u zaokružavanju file-ova u sektore.


Dva puta si "pojednostavio" 7.data pa ti to nece raditi :) Tvoj sistem kompresije 7. bita je isuvise dobar, moras da smislis neki malo manje efikasan da bi radio :)

Citat:
Stijak:
Ili još bolji sistem - podatke napišeš u imena praznih file-ova i pretvoriš ogroman file kompresijom u ništa... pa ovaj moj file gore snimiš kao 10110001011110100.data (može i efikasnije u hex ili nekom jačem encoding-u - ali nije sad bitno - i ako je previše za jedno ime - podjeliš i smisliš način da ih numerišeš... ;) Kako je ovo dobro ;) Čak i kada ideš na propertires piše file on disk 0! Ha ha ha - mislim da sam nadmašio tvoju ideju...


Naravno da jesi. Da i ja nekom jednom kazem: "Tvoja ideja je vec obradjena na comp.compress" :)

This assumes of course that the information available to the decompressor is
only the bit sequence of the compressed data. If external information such as a
file name, a number of iterations, or a bit length is necessary to decompress
the data, the bits necessary to provide the extra information must be included
in the bit count of the compressed data. Otherwise, it would be sufficient to
consider any input data as a number, use this as the file name, iteration count
or bit length, and pretend that the compressed size is zero. For an example of
storing information in the file name, see the program lmfjyh in the 1993
International Obfuscated C Code Contest, available on all comp.sources.misc
archives (Volume 39, Issue 104).

Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
*.adsl.beocity.net.



+557 Profil

icon Re: Kompresija random-like podataka06.02.2012. u 16:50 - pre 147 meseci
Citat:
Stijak:
A inače - ne kontam zašto ti treba pomoć drugih - ne treba ti ni program za to - treba ti samo moćan digitron koji može da radi sa velikim brojevima takav ti je i windowsow, imaš ih po netu koliko hoćeš, imaš jedan na http://www.wolframalpha.com/ (samo treba naučiti komande... Iznalupaš se cifara - da bude dovoljno dugačak da bi tvoja metoda radila (preko 32 - da dobiješ neki kvazirandom broj i pokušaš skontati način da to kompresuješ svojom metodom......


Da, da, caskom cu da proverim sve brojeve vece od 2^32.
Nema potrebe sada je tu najmocniji digitron: Nedeljko, on ima sistem kako da svaki rezultat svakog zadatka sve de na 42. tako da ce biti:
Fajl proizvoljne duzine i sastava x (puta) Nedeljkova racunica = 42. (bita, duzina fajla :)

Citat:
Stijak:
Znači naprimer 1307652984 (mada će tebi trebati veći brojevi) izvadiš logoritam po dva, pa skontaš koloko ti je još ostalo, pa logoritam od ostatka po 3, pa sve tako i ručno to sve središ - zapišeš brojeve koje moraš zapamtiti poslije kompresije - to bi bili cjelobrojne vrijednosti ovih logoritama... I vidiš da li je to duže ili kraće od originala... Koliko kontam ti bi file skraćivao kao 1^x + 2^y + 3^z +... pa moraš pamtiti ove x,y,z...


Clan 1^x cu sigurno da zadrzim :) on ce mnogo da doprinese kompresovanom obliku fajla :)

Citat:
BiF: primer sa notepad-om pokazuje da ti se vise isplati da kompresovane podatke ubacis u jedan file, a ne u vise file-ova (2, 5, 50,...), jer ces tako ustedeti prostor.

U jedan fajl je i ubaceno i taj jedan sam nazvao "visestruki" (dvostruki) jer se pojedini delovi niza bita u njemu tumace kao posebne dodatne kombinacije.

Citat:
BiF
sto se tice uglastih zagrada i razmaknica, naravno da postoje u smislu u kom si ih ti naveo. hteo sam da ti kazem da i te uglaste zagrade i razmaknice moras da pretvoris u nule i jedinice.

Umesto uglastih zagrada tamo gde sam ih pisao zamisli nizove bita kakve hoces i koliki ti odgovaraju za opisivanje kompresovanog fajla i sve je ok.
Kad tu kolicinu bita saberes plus "sadrzaj" fajla dobices donju granicu velicine kompresovanog fajla. Kad mogu windousi da naprave folder i da u njemu dva posebna fajla i da sve to bude 16KB mozes i ti kompresovan fajl u kome ce biti dva posebna "fajla", ako je najmanji moguci prostor koji bi takvo sto zauzimalo 16KB najmanji moguci fajl koji bi mogao da se kompresuje na taj nacin bio bi dugacak 16KB + 1. bit.
Nemoj da pricas?
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.3gnet.mts.telekom.rs.



+2789 Profil

icon Re: Kompresija random-like podataka06.02.2012. u 20:44 - pre 147 meseci
Pisao ti reč "fajl" pod znacima navoda ili ne, on mora biti zapamćen na fizičkom nosiocu, a taj fizički nosilac je konačan niz bitova, koji mogu menjati vrednost. Napravi ti svoj fajl sistem, kakav god hoćeš, ali ćeš morati da znaš gde jedan fajl počinje, a gde se završava itd. Za to su takođe potrebno da budu zabeležene neke dodatne informacije. To sve moraš uzeti u obzir, tako da ako ti ne odgovaraju postojeći fajl sistemi, onda prvo opiši svoj.

Dakle, imaš dva diska. Na jednom je tačno jedan fajl koji zajedno sa svim pratećim informacija zauzuma m bitova. Drugi disk je potpuno slobodan. Treba ti program koji će sadržaj prvog diska da upiše na drugi disk tako da se na osnovu sadržaja drugog diska može restaurirati sadržaj prvog diska, ako bi se recimo taj sadržaj obrisao. Pritom će sadržaj drugog diska zauzimati n bitova zajedno sa svim fajlovima i ostalim potrebnim informacijama. Ti tvrdiš da to možeš da uradiš tako da bude n<m bez obzira na strukturu fajla sa prvog diska samo pod uslovom da je npr. m>100.

Dakle, sve ti se svodi na to da od jednog niza nula i jedinica napraviš drugi niz nula i jedinica, odnosno da bespotrebno komplikuješ priču uvođenjem više fajlova, jer ti se opet sve svodi na to da od jednog fajla praviš drugi fajl. Za oba diska se mogu napraviti njihove slike zauzetih delova u vidu fajlova (jedan disk, jedan fajl). Nije problem da se dopusti da fajl ne bude proizvoljno dugačak niz bajtova, već bitova ako ti tako više odgovara.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

negyxo
Aleksandar Perkuchin

Član broj: 29751
Poruke: 898
*.dynamic.isp.telekom.rs.



+171 Profil

icon Re: Kompresija random-like podataka06.02.2012. u 21:01 - pre 147 meseci
@MajorFatal

Mnogi su ti vec kroz razne primere objasnili da to sto hoces da ne mozes da uradis - i ne mozes. Da sam na tvom mestu i da me zaista mnogo zanima kompresija, ja bi se fokusirao na kompresiju na ne-random podatke. Od njih ces nesto mozda i nauciti i mozda uspeti da namestis nesto korisno, ovako samo gubis vreme na nesto sto je nemoguce. Cisto mali hint - reci koje se upotrebljavaju se nalaze poprilicno u jednom opsegu, kao i neke kombinacije reci - mozes pogledati na netu dictionary based algoritme, malo dalje ako pustis mastu na volju javice ti se mnoge nove ideje, imaces posla posle na razmisljanje koliko hoces :-)
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
*.adsl.beocity.net.



+557 Profil

icon Re: Kompresija random-like podataka10.02.2012. u 05:55 - pre 147 meseci
Citat:
Nedeljko:
Pisao ti reč "fajl" pod znacima navoda ili ne, on mora biti zapamćen na fizičkom nosiocu, a taj fizički nosilac je konačan niz bitova, koji mogu menjati vrednost. Napravi ti svoj fajl sistem, kakav god hoćeš, ali ćeš morati da znaš gde jedan fajl počinje, a gde se završava itd. Za to su takođe potrebno da budu zabeležene neke dodatne informacije. To sve moraš uzeti u obzir, tako da ako ti ne odgovaraju postojeći fajl sistemi, onda prvo opiši svoj.


U svim ovim porukama:

http://www.elitesecurity.org/t151770-5#2974833
http://www.elitesecurity.org/t151770-5#2979060
http://www.elitesecurity.org/t151770-5#3013226
http://www.elitesecurity.org/t151770-5#3027974

ljudi su mi skretali paznju na to o cemu ti pricas, a u ovoj poruci:

http://www.elitesecurity.org/t151770-5#3013776

sam valjda najkompletnije odgovorio. Ne vidim potrebu za ponavljanjem? Ali cu dodati jos samo ovo:

Citat:
Nedeljko:
...ali ćeš morati da znaš gde jedan fajl počinje, a gde se završava itd. Za to su takođe potrebno da budu zabeležene neke dodatne informacije.


Ali postoji ekvivalencija, i za originalni (pocetni, onaj koji treba da se kompresuje) fajl takodje mora da se zna gde pocinja a gde zavrsava, pa su za to takodje potrebne da se zabeleze neke dodatne informacije, zato sam uglaste zagrade koje bi trebalo da ilustruju te dodatne informacije crtao i sa leve i sa desne strane crteza tj. i oko originalnog fajla i oko kompresovanog oblika.

Nigde, nijednom recju nisam rekao da mi ne odgovaraju postojeci fajl sistemi?

Citat:
Nedeljko:
Dakle, imaš dva diska. Na jednom je tačno jedan fajl koji zajedno sa svim pratećim informacija zauzuma m bitova. Drugi disk je potpuno slobodan. Treba ti program koji će sadržaj prvog diska da upiše na drugi disk tako da se na osnovu sadržaja drugog diska može restaurirati sadržaj prvog diska, ako bi se recimo taj sadržaj obrisao. Pritom će sadržaj drugog diska zauzimati n bitova zajedno sa svim fajlovima i ostalim potrebnim informacijama. Ti tvrdiš da to možeš da uradiš tako da bude n<m bez obzira na strukturu fajla sa prvog diska samo pod uslovom da je npr. m>100.


Neverovatna stvar ali, Stijaku sam na ono "Smijesno smi sve ovo" hteo da odgovorim: meni nimalo, osim..., jedino..., ako... pa bila je tu jedna ekipa od onih sa "CompCommpress" koji su fajl kompresovali na jednoj masini a dekompresovali na drugoj, u cilju da dokazu da su postigli kompresiju, nista mi nije bilo smesnije od toga sto nisu mogli da se razumeju sta im je fajl, sta nesto sto sam nazvao 'sadrzaj fajla' a sta fajl sa zaglavljem, sta engine koji ga cita u izvornom obliku a sta engine za kompresiju/dekompresiju i koje podatke o fajlu sadrzi OS i da li isti spadaju u fajl ili izvan njega. Takodje je valjda smesna kad ne bi bila tuzna 'filozofska' rasprava ako imaju fajl od 20Mega ali nemaju kompresor, pa kad na masinu snime kompresor koji sam zauzima recimo 40Mega i onda uz pomoc njega kompresuju gorepomenuti fajl na 2Mega da li su dobili kompresiju obzirom da sada kompresor i novonastali kompresovani fajl zauzimaju ukupno 42Mega tj. vise nego pocetni fajl sam??? Od svega je najtuznije sto kao posledica slicnih rasprava i nerazumevanja tematike sada na wikipediji na onom konkursu za kompresiju zahtevaju samoraspakujucu arhivu? Posto treba da se kompresuje 100Mega da ne bi neko isporucio kompresor od 110Mega u kome je kompletna arhiva od 100Mega pothranjena pa kad dobije za kompresiju fajl od 100Mega materijala sa wikipedije mogao bi da ga "kompresuje" i na velicinu od 1.bit a prilikom dekompresije da samo isporuci onih originalnih 100Mega koje vec ima pothranjene u sebi? Paranoja! I sad neko ko bi isprogramirao dobar kompresor/dekompresor velicine recimo 40Mega a koji bi arhivu od 100Mega sazvakao na recimo 1,2Mega ne moze da ucestvuje jer se zahteva samoraspakujuca arhiva?
Nemoj da pricas?
 
Odgovor na temu

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

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

Postavi temu Odgovori

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