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: << < .. 2 3 4 5 6 7

[ Pregleda: 45362 | 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: 920
*.adsl.beocity.net.



+371 Profil

icon Re: Kompresija random-like podataka10.02.2012. u 05:55 - pre 110 meseci
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.


Dakle, imam 1. disk, sta ce mi dva? I posle tvrdite da ja komplikujem? Dakle imam 1. disk i na njemu OS, engine za kompresiju/dekompresiju i 1. fajl, kad taj jedan fajl kompresujem uz pomoc kompresora trebalo bi da se dobije fajl manji od onog pocetnog sto moze da utvrdi OS ili bilo koji fajl menager, kad se isti dekompresuje trebalo bi da se dobije originalni fajl, sta ce mi dva diska za nesto tako jednostavno?

Citat:
Nedeljko:
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.


Pa da mogu da uradim vec bih uradio?
Ja tvrdim i stojim iza toga a i Vi mozete da potvrdite da za duzinu niza bita m=153 recimo, postoji 2^153 razlicitih fajlova, od toga (2^153)-2 imaju razlicite i krace ekvivalente tj. mogu da se kompresuju, preostala 2.fajla mogu da imaju razlicite ekvivalente medjusobno, i od svih ostalih, ali ne i krace. Ne vidim nikakvu ekspanziju tu, a kompresija je moguca? Bez obzira na strukture pocetnih fajlova?

Inace hvala za definiciju: "Bez obzira na strukturu pocetnih fajlova", upravo se o tome ovde radi, i sam bih to tako formulisao, pomislice neko na osnovu naslova ili iz rasprave da hocu da kompresujem random podatke, kome bi to ikad zatrebalo osim za neke eksperimente, hocu da mogu da kompresujem podatke sa nekim razumnim stepenom kompresije a da me ne zanima da li su podaci izvorno slika, muzika, film, random podaci ili neki jako optimizovan program.

Citat:
Nedeljko:
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.


Zasto ne mogu da za 1. originalni fajl napravim 2. kompresovana fajla? Ako ce ta dva u zbiru da zauzimaju manje prostora nego pocetni, zasto ne bih mogao? Jos ako prvi od ta dva ima uputstva da 'pogleda' da li postoji 'parnjak' tj. drugi fajl sa istim imenom ali razlicitom ekstenzijom, ili istim imenom i dodatkom _2 u produzetku pa se posle prvog i drugi dekompresuje i zajedno daju rezultat: originalni fajl? Ili jos bolje taj posao da proveri da li postoji jos jedan fajl da obavi dekompresor?

Ne samo da mi ne smetaju danasnji fajl sistemi ili OS-evi vec je ovo upravo i moguce zbog toga sto i OS i engine za kompresiju znaju po nesto o fajlu tj. deo informacija odlazi na njih.

Odnosno ako je pocetni fajl dovoljno veliki, toliko da mogu da ga zamenim sa dva manja fajla, ako je recimo velicine N, mene vise ne zanima njegova struktura jer znam da svih (2^N)-2 fajlova mogu da zamenim sa pojedinacnim 'jednostrukim' manjim (kracim po broju bita upotrebljenih) fajlovima, a preostala 2. fajla mogu da zamenim sa po dva kompresovana fajla koji su u zbiru manji od originalnog fajla. To je dokaz da je za neke velicine fajlova kompresija bilo kakvih podataka pa i random podataka moguca U PRAKSI.

Citat:
Nedeljko:
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.


Pa, odgovaralo bi bitova kad vec moze, hvala za info od koristi je. :)
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

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



+371 Profil

icon Re: Kompresija random-like podataka10.02.2012. u 05:56 - pre 110 meseci
Citat:
negyxo:
Mnogi su ti vec kroz razne primere objasnili da to sto hoces da ne mozes da uradis - i ne mozes.


Navedi 1. od tih raznih primera?

Citat:
negyxo:
Da sam na tvom mestu i da me zaista mnogo zanima kompresija, ja bi se fokusirao na kompresiju na ne-random podatke.


Nee moozem :) Nije definisano na wikipediji sta su to random podaci pa ne mogu znati ni sta su to "ne-random" koje ti pominjes, a ako se malo bolje zapitas videces da ni ti ne znas...

Citat:
negyxo:
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 :-)


Hvala za hint. Citao sam nesto malo, koliko mogu da razumem. Kod lzv a on je dictionary based za sada mi se ne svidja to sto se na pocetku pravi tabela sa svih 265 integera, pa onda pregleda fajl i trazi nizove bita duzine 8, pa ih menja odgovarajucim integerima? Tako ako nadje slovo A menja ga kodom za broj (integer) 65., a u sustini niz bita 01000001 menja tim istim nizom: 01000001? No dobro onda trazi kombinacije od po 2. slova ili nizove od po 16. bita i kako nikad nisu svi iskorisceni iz celog moguceg opsega menja ih odgovarajucim integerima po redu? Zvuci dobro u teoriji, ali zasto je onda lzv-d (ako se tako zove) uspesniji od lzv-a, lzv-d posle osmobitnih kodnih reci prelazi na devetobitne pa desetobitne itd. redom? Deluje da ima vise redundanse tamo gde je razlika u duzini niza bita koji se pregleda za 1. bit nego za celu duzinu kodne reci koju ljudi najcesce koriste - jos osam bita na onih prvih 8. i duzinu kojom najcesce koduju bilo koji prirodni izvor signala? Zasto se onda ona tabela na pocetku ne pravi od najmanje moguce duzine kodne reci 1. bit? Eto to mi na primer nije jasno kod dictionary based ako sam uopste dobro skapirao (ili bar otprilike) kako to funkcionise.
Nemoj da pricas?
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

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



+2728 Profil

icon Re: Kompresija random-like podataka10.02.2012. u 07:10 - pre 110 meseci
Citat:
MajorFatal: Pa da mogu da uradim vec bih uradio?


O čemu onda pričamo? Ni ti ni mi ostali ne mislimo da to možeš da uradiš. U čemu je onda spor?

Uzgred, možeš ti i jedan fajl od gigabajt da komprimuješ sa deset miliona fajlova od kojih nijedan nema ni bajt sadržaja, koristeći samo prateće informacije kao što je na primer ime fajla, ali to nije to.
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: 893
*.dynamic.isp.telekom.rs.



+171 Profil

icon Re: Kompresija random-like podataka10.02.2012. u 10:02 - pre 110 meseci
Citat:
MajorFatal:Navedi 1. od tih raznih primera?


Ah, pa imas bukvlano prvih par postova sa pocetka teme... ali necu da ulazim u te vode, definitivno nisam uporan toliko :-)

Citat:

Nee moozem :) Nije definisano na wikipediji sta su to random podaci pa ne mogu znati ni sta su to "ne-random" koje ti pominjes, a ako se malo bolje zapitas videces da ni ti ne znas...


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

Meni je sasvim dovoljno ovo i od toga bi poceo:

Citat:

Kolmogrov's definition of a random string was that it is random if has no description shorter than itself via a universal Turing machine



Sto se tice dictionary-based kompresije, nema tu nista preterano specijalno - zamenjujes cesto koriscene sekvence bitova sa manjom sekvencom bitova i to je to. Fazon je samo da namestis sto bolji algoritam koji ti detektuje ta ponavljanja i zatim kreiras dictionary koji je nista vise nego jedna ogromna maping tabela.
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

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



+371 Profil

icon Re: Kompresija random-like podataka22.02.2012. u 14:47 - pre 109 meseci
Ala Vi spinujete :) Mislim bas imate cudan nacin rasprave.

Citat:
Nedeljko: O čemu onda pričamo? Ni ti ni mi ostali ne mislimo da to možeš da uradiš. U čemu je onda spor?

Spor je u tome sto nisam ni tvrdio da bilo sta mogu da uradim, nego da je moguce da se uradi, da je izvodljivo, ostvarljivo u praksi itd..., kada sam napisao "Pa da mogu da uradim vec bih uradio" samo sam hteo da Vam skrenem paznju da me vec po drugi put i to u kratkom vremenskom roku nabedjujete za nesto, prvi put je bilo "Ako ti ne odgovaraju fajl sistemi - opisi svoj" , a hteo sam i da Vam potvrdim da bi hipoteticka situacija koju ste predstavili bila manje vise dobra ilustracija toga sto bih hteo da postignem ali uz male izmene:

Za ovako postavljene stvari:

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.


...ne samo da ja ne mogu da uradim (sto nisam ni tvrdio) vec ne bih mogao ni da potvrdim da mislim da je moguce, ostvarljivo itd... jer osim sto smatram da je uvodjenje 2. diska bespotrebno komplikovanje (i to samo iz razloga da bi se razumeli o cemu pricamo, kao da dosad nije jasno: o mogucnosti kompresije random-like podataka) vec i mislim da su neprecizno postavljene stvari pa da kao takve ne mogu da se potvrde da su moguce tj. izvodljive u praksi:

Zaboravili ste da napomenete gde bi bio pothranjen program koji ce da sadrzaj prvog diska upise 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, tako da bude n<m bez obzira na strukturu fajla sa prvog diska samo pod uslovom da je npr. m>100"

1.) Samo na prvom disku: NE MOZE, jer ako se sadrzaj prvog diska obrise sta ili ko ce da restaurise podatke?
2.) Samo na drugom disku: NE MOZE, jer bi ovo bilo slicno kao onaj uslov o samoraspakujucoj arhivi, ne bi bilo u radu poredjenje sadrzaja prvog i drugog diska kada je drugi dodatno opterecen programom za restauriranje podataka.
3.) Na oba diska, moze, ali onda mora da se promeni i ova recenica iz:

Citat:
Nedeljko:
Za oba diska se mogu napraviti njihove slike zauzetih delova u vidu fajlova (jedan disk, jedan fajl).


u: Za oba diska se mogu napraviti njihove slike zauzetih delova u vidu fajlova(jedan disk, jedan fajl, jedan program)

4.) Na nekom trecem disku van ova prethodna dva, moze, ali pogledajte koliko to dodatno komplikuje vec bespotrebno zakomplikovan model, pored prethodna dva diska koja ste Vi predlozili sada bi tu bio i treci?

Za varijante pod 3.) i 4.) mogu da potvrdim da mislim da su ostvarljive u praksi cak sta vise mislim da imam matematicki, logicki dokaz da je to moguce.
Za varijante 1.) i 2.) mislim da nisu vredne raspravljanja.
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

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



+371 Profil

icon Re: Kompresija random-like podataka22.02.2012. u 14:49 - pre 109 meseci
Citat:
Nedeljko: Uzgred, možeš ti i jedan fajl od gigabajt da komprimuješ sa deset miliona fajlova od kojih nijedan nema ni bajt sadržaja, koristeći samo prateće informacije kao što je na primer ime fajla, ali to nije to.


Sto se mene tice ako potvrdite da moze bar jos jedan fajl duzine gigabajt da se komprimuje sa nekim drugim setom od deset miliona fajlova to potvrdjuje da je moguca kompresija random like fajlova i random fajlova u praksi, to jest svih fajlova iz razloga sto i preostalih (2^gigabajt)-2 fajla duzine gigabajt bi mogli da se kompresuju sa po jednim kompresovanim fajlom, pa makar i "to ne bilo to" i donja granica za mogucnost postojanja kompresije bila na duzini fajla od jedan gigabajt.

Kako ste odabrali vrednosti 1. Gigabajt i 10. miliona fajlova, da li moze fajl od Megabajt da se komprimuje sa 10.000 fajlova ili od 1.Kb sa 10 razlicitih fajlova, gde je donja granica?

Uzgrad, u grupi resenja koja bi mogla da se okarakterisu kao moguce ali "to nije to": mogu i da uvedem jos jednu ekstenziju za kompresovane fajlove, tako bih dobio jos jedan set od (2^N)-2 fajlova koji mogu da mi posluze kao kompresovana verzija originalnih fajlova. Sa dve ekstenzije imao bih: 2*(2^N)-4 fajlova na raspolaganju za kompresiju originalnog seta od 2^N fajlova. Svakog takvog seta duzine N.

Ali zasto bih kad imam i savrseno legalno i legitimno resenje: Bar dve distribucije nula i jedinica se nikad nece pojaviti kao originalni fajlovi: ona sa svim nulama i ona sa svim jedinicama: bas iz razloga postojanja OS-a i fajl sistema jer za njihove potrebe da bi fajl uopste postojao moraju da se koduju vise od jedne osobine fajla: ime, estenzija, duzina itd... tj. svi atributi, kako je za taj zadatak neophodna bar jedna nula i bar jedna jedinica tj. od oba simbola najmanje po jedan tako da sada imamo 2^N-2 originalna fajla i 2^N-2 kracih kombinacija bita koje bi mogle da posluze kao kompresovane verzije pocetnih fajlova tj. postoji 1-1 preslikavanje. Da li je to potreban i dovoljan uslov da bi kompresija mogla da postoji u praksi ili samo potreban?
Nemoj da pricas?
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

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



+2728 Profil

icon Re: Kompresija random-like podataka22.02.2012. u 18:04 - pre 109 meseci
To nije to zato što i imena tih fajlova moraju negde da se pamte.

Ako ne bi bilo ograničenja za dužinu imena fajla, lepo bih mogao da napravim fajl čije bi ime bilo heksadekadni zapis fajla koji se komprimuje i gotovo, ali to nije praktično, jer time ne štedim prostor na disku. Biće zauzeto više prostora nego originalnim fajlom. Zato se problem tako ne formuliše.

Gde bi bio pohranjem program, nebitno je. Može da bude u memoriji računara, samo da može da komprimuje i dekomprimuje fajl.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

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



+2728 Profil

icon Re: Kompresija random-like podataka22.02.2012. u 18:07 - pre 109 meseci
Citat:
MajorFatal: Spor je u tome sto nisam ni tvrdio da bilo sta mogu da uradim, nego da je moguce da se uradi, da je izvodljivo, ostvarljivo u praksi itd...


A na osnovu čega onda tvrdiš da to može da se uradi kad ni sam ne znaš kako?
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

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

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

Postavi temu Odgovori

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