Kompresija random-like podataka

Kompresija random-like podataka 25.12.2005. u 10:33 · pre 253 meseci #1

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

Potpis

Nemoj da pricas?

Re: Kompresija random-like podataka 25.12.2005. u 10:37 · pre 253 meseci #2

To nece ici, ako je signal slucajne prirode, zbir koeficijenata kojim hoces da ga opises ce zauzimati mnogo vise mesta od samog signala ;)

Probaj sa iole kompleksnijim signalom na papiru - pa ces videti da ne ide.

_{[Ovu poruku je menjao Ivan Dimkovic dana 25.12.2005. u 11:39 GMT+1]}

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: Kompresija random-like podataka 25.12.2005. u 10:42 · pre 253 meseci #3

Ja sam kontao da bilo koji moze da se predstavi sa desetak - petnaest sabiraka.

Potpis

Nemoj da pricas?

Re: Kompresija random-like podataka 25.12.2005. u 10:51 · pre 253 meseci #4

Citat:

Kompresija random-like podataka bi se vrsila na sledeci nacin: ako imamo fajl (koji hocemo da kompresujemo) duzine n bita I ako napravimo brojac takodje duzine n, koji broji od 0 do 2^n -1 nas fajl bi se nasao na tom brojacu na poziciji m (obzirom da su iste duzine fajl I brojac). Zapis (n,m) bi bio nas kompresovani fajl.

Pa zapis (n, m) je svakako vise podataka od predstavljanja samog broja? Tvoja "pozicija u brojacu" je zapravo sam broj.

Broj: 154, bin: 10011010
n = 8
m = 154 - tacno 154 puta moras da "brojis" do tog broja ;)

Objasni mi, sta si ti tu skratio?

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: Kompresija random-like podataka 25.12.2005. u 13:05 · pre 253 meseci #5

Na zalost za ovako malo n=8 ne moze da se "vidi" da kompresija moze da postoji za vece vrednosti n. Na primer zapis (m =) 2^6 zauzima 24 bita u memoriji tj. vise od 6 bita, ali zato zapis 2^32 zauzima ISTO prostora tj. 32 bita ( po 8 bita svaki znak i broj), dok vec zapis 2^64 zauzima manje prostora (opet 32 bita) u odnosu na 64.
Konkretno ono sto hocu da kazem je da bi m u ovom slucaju 154 trebalo zapisati kao npr: 2^7 + 5^2 + 1 s tim sto u ovom slucaju ne bi bilo kompresije jer bi ovaj zapis zauzimao 72 bita sto je vise od 8 bita ali za vece fajlove ovakav nacin zapisivanja bi dosao do izrazaja kao veoma racionalan tj. doneo bi nam kompresiju.

Potpis

Nemoj da pricas?

Re: Kompresija random-like podataka 25.12.2005. u 13:09 · pre 253 meseci #6

Taj zapis ti ne bi doneo kompresiju u generalnom slucaju (gde tvoj model ne zna koja ce informacija biti sledeca) jer za slucajnu sekvencu brojeva P tvoji koeficijenti bi zauzimali vise mesta nego sama sekvenca P.

Za individualne male slucajeve gde si pronasao mogucnost kompresije si sam zapravo napravio model licnim pogadjanjem koeficijenata - te koeficijente moras negde da uskladistis, sto zauzima prostor. Za generalni slucaj to ne moze da funkcionise sa dobitkom u prostoru, jer tvoj dekoder nema model koji bi dedukovao te koeficijente, vec oni moraju biti preneti, tj. pohranjeni u kompresovani signal.

Ako malo bolje razmislis, tvoja "kompresija slucajnih brojeva" je isto sto i "beskonacna kompresija" za koju si sam uvideo da je nemoguca - jer je sekvenca kompresovana nekim od poznatih algoritama za kompresiju zapravo vrlo bliska slucajnom nizu brojeva.

Dakle, ti bi svojom "kompresijom slucajnih brojeva" zapravo kompresovao nesto sto je vec svedeno na stanje blisko entropiji. Sto je protivno matematickoj teoriji informacija Kloda Sanona.

_{[Ovu poruku je menjao Ivan Dimkovic dana 25.12.2005. u 14:14 GMT+1]}

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: Kompresija random-like podataka 25.12.2005. u 21:59 · pre 253 meseci #7

Citat:

Ivan Dimkovic: Taj zapis ti ne bi doneo kompresiju u generalnom slucaju (gde tvoj model ne zna koja ce informacija biti sledeca) jer za slucajnu sekvencu brojeva P tvoji koeficijenti bi zauzimali vise mesta nego sama sekvenca P.

Ne razumem ono da moj model ne zna koja ce informacija biti sledeca. Da li si napravio lapsus kada si napisao za slucajnu sekvencu brojeva P hoteci da kazes za slucajnu sekvencu bita P koeficijenti bi zauzimali vise mesta nego sama sekvenca? Mislim da sam u prethodnom postu pokazao kako je onaj nacin zapisivanja koeficijenata sve racionalniji za sve vece brojeve. Ako ipak tu treba da stoji “za slucajnu sekvencu brojeva P” onda ne znam na koju sekvencu brojeva mislis. Kod mene se originalni fajl ceo posmatra kao neka vrsta broja (malo veceg doduse) I jedan je, nema sekvence takvih brojeva.

Citat:

Ivan Dimkovic:

Za individualne male slucajeve gde si pronasao mogucnost kompresije si sam zapravo napravio model licnim pogadjanjem koeficijenata - te koeficijente moras negde da uskladistis, sto zauzima prostor.

Naravno ali ovo vazi za svaku vrstu kompresije ako se ne varam neki prostor mora biti iskoriscen.

Citat:

Ivan Dimkovic:

Za generalni slucaj to ne moze da funkcionise sa dobitkom u prostoru, jer tvoj dekoder nema model koji bi dedukovao te koeficijente, vec oni moraju biti preneti, tj. pohranjeni u kompresovani signal.

Prilikom dekompresije iz koeficijenata bi se racunala “puna vrednost” datog broja tj. redosled pojavljivanja originalnog fajla na brojacu.

Citat:

Ivan Dimkovic:

Ako malo bolje razmislis, tvoja "kompresija slucajnih brojeva" je isto sto i "beskonacna kompresija" za koju si sam uvideo da je nemoguca - jer je sekvenca kompresovana nekim od poznatih algoritama za kompresiju zapravo vrlo bliska slucajnom nizu brojeva.

Naravno da je isto, sto sam I naglasio u “beskonacnoj kompresiji” I pozvao ljude da ucestvuju u okviru ove teme jer sam tamo napravio isuvise gresaka ali nisam uvideo da je nemoguca sto dokazuju I ovi napori

Potpis

Nemoj da pricas?

Re: Kompresija random-like podataka 26.12.2005. u 08:57 · pre 253 meseci #8

Bilo kakva kompresija podataka je moguca ako i samo ako postoji visak informacija.
Ako su podaci slucajni (po definiciji slucajnosti), tada ne postoji visak podataka i, samim tim, kompresija je nemoguca.

Potpis

While you were hanging yourself on someone else's words
Dying to believe in what you heard
I was staring straight into the shining sun

Re: Kompresija random-like podataka 26.12.2005. u 11:23 · pre 253 meseci #9

Citat:

Ne razumem ono da moj model ne zna koja ce informacija biti sledeca. Da li si napravio lapsus kada si napisao za slucajnu sekvencu brojeva P hoteci da kazes za slucajnu sekvencu bita P koeficijenti bi zauzimali vise mesta nego sama sekvenca? Mislim da sam u prethodnom postu pokazao kako je onaj nacin zapisivanja koeficijenata sve racionalniji za sve vece brojeve. Ako ipak tu treba da stoji “za slucajnu sekvencu brojeva P” onda ne znam na koju sekvencu brojeva mislis. Kod mene se originalni fajl ceo posmatra kao neka vrsta broja (malo veceg doduse) I jedan je, nema sekvence takvih brojeva.

Nisi pokazao, pokazao si samo jedan podesen primer.

Probaj sa nekoliko slucajnih nizova - i probaj na papiru da uskladistis, i videces da ne ide, da je informacija koja je potrebna da se "opise" pseudo-slucajni niz uvek veca od samog niza.

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: Kompresija random-like podataka 26.12.2005. u 20:44 · pre 253 meseci #10

Citat:

formeye: Bilo kakva kompresija podataka je moguca ako i samo ako postoji visak informacija.
Ako su podaci slucajni (po definiciji slucajnosti), tada ne postoji visak podataka i, samim tim, kompresija je nemoguca.

Ako slucalne podatke lociram na brojacu tada mi ceo fajl postaje visak informacija I odlucujem se da pamtim samo njegov redosled pojavljivanja na brojacu sto je mnogo krace. Ovo mi je pak dovoljno da kasnije regenerisem tj. dekompresujem fajl.

Citat:

Ivan Dimkovic: Nisi pokazao, pokazao si samo jedan podesen primer.

Probaj sa nekoliko slucajnih nizova - i probaj na papiru da uskladistis, i videces da ne ide, da je informacija koja je potrebna da se "opise" pseudo-slucajni niz uvek veca od samog niza.

Probao bih ja ali kako da probam sa primerima gde je niz bita (fajl) duzi od 32 bita sto mi je neophodno da bi kompresija radila to na papiru vec ide malo teze pa sam ja mislio da nadjem nekog crnca na elitesecurity-u da uradi programcic za mene uz pomoc koga bi se veoma lako i brzo utvrdilo da li kompresija postoji ili ne.

Potpis

Nemoj da pricas?

Re: Kompresija random-like podataka 27.12.2005. u 14:36 · pre 253 meseci #11

Ja ne znam da li MajorFatal zajebava sve ovde na forumu:))

Re: Kompresija random-like podataka 29.12.2005. u 20:11 · pre 253 meseci #12

Pa izgleda da najvise zajebavam sam sebe sto ocekujem da bilo sta bude od ovoga. U svakom slucaju hvala svima na aktivnom ucescu u raspravi. Ja odustajem.

Potpis

Nemoj da pricas?

Re: Kompresija random-like podataka 29.12.2005. u 23:28 · pre 253 meseci #13

Iako ti sada to možda ne izgleda tako, najbolje bi ipak bilo da odustaneš.

Re: Kompresija random-like podataka 30.12.2005. u 13:04 · pre 253 meseci #14

Srecna svima nova 2006-ta godina i bozicni praznici uz najlepsi pozdrav HRISTOS SE RODI!

Potpis

Nemoj da pricas?

Re: Kompresija random-like podataka 30.12.2005. u 13:18 · pre 253 meseci #15

Citat:

MajorFatal: Srecna svima nova 2006-ta godina i bozicni praznici uz najlepsi pozdrav HRISTOS SE RODI!

...što se lako može kompresovati u:

Code:

AGwAeQAgAFIAZQBwAG8AcgB0ACAAUABlAHIAcwBvAG4AYQBsACAAQwBhAHIAZAAHAAcATgBhAG0A
ZQA6ACAATQBsAGEAZABlAG4AIABKAGEAYgBsAGEAbgBvAHYAaQAHAQcARABhAHQAZQA6ACAAVAB1
AGUAcwBkAGEAeQAsACAATgBvAHYAZQBtAGIAZQByACAAMQAxACwAIAAyADAAMAAzAAcAVwBlAGUA
awA6ACAABwAHAAcABwAgACAABwBEAGUAcwBjAHIAaQBwAHQAaQBvAG4ABwBTAHQAYQB0AHUAcwAH
AEMAbwBtAG0AZQBuAHQAcwAHAEEAdAB0AGEAYwBoAC4AIABOAGEAbQBlAAcABwBFAG4AZAAgAG8A
ZgAgAEQAYQB5ACAAcwB0AGEAdAB1AHMAIAByAGUAcABvAHIAdAAgACAAKABwAHIAZQB2AGkAbwB1
AHMAIABkAGEAeQApAAcABwAxAC4ABwBjAGwAZQBhAG4AaQBuAGcAIABjAG8AZABlAAcAQwBvAG0A
cABsAGUAdABlAGQABwAHAAcABwAyAC4ABwBmAGkAeABpAG4AZwAgAGIAdQBnAHMAIAAmACAAdABl
AHMAdABpAG4AZwAHAEMAbwBtAHAAbABlAHQAZQBkAAcABwAHAAcAMwAuAAcAYwBvAHAAAAYAADYI
AAA4CAAAQggAAEQIAABkCAAAZggAAGgIAAB0CAAAqAgAAKoIAAC0CAAAtggAALgIAAC6CAAAvAgA
AL4IAADp2MSwn4p0xGVTxLBT2EEwAAAAAAAAAAAAAAAAIBVouD0rABZoPAboAENKEgBPSgMAUUoD
AF5KAwBhShIAACMVaFYzNQAWaDwG6AA1CIFDShIAT0oDAFFKAwBeSgMAYUoSACMVaFYzNQAWaLEn
gQA1CIFDShIAT0oDAFFKAwBeSgMAYUoSAB0WaDZTmgA1CIFDShIAT0oDAFFKAwBeSgMAYUoSACsV
aDZTmgAWaLEngQA1CIFDShIAT0oDAFFKAwBeSgMAYUoSAG1IGghzSBoIKBZoNlOaADUIgTYIgUNK
EgBPSgMAUUoDAF5KAwBhShIAbUgaCHNIGggAIBZoNlOaADUIgTYIgUNKEgBPSgMAUUoDAF5KAwBh
ShIAACYVaFYzNQAWaDUhMAA1CIE2CIFDShIAT0oDAFFKAwBeSgMAYUoSAAAmFWhWMzUAFmixJ4EA
NQiBNgiBQ0oSAE9KAwBRSgMAXkoDAGFKEgAAIBVouD0rABZosSeBAENKEgBPSgMAUUoDAF5KAwBh
ShIAACwVaIBUkAAWaLEngQA1CIFCKghDShQAT0oDAFFKAwBeSgMAYUoUAHBo////ABAABgAANggA

Re: Kompresija random-like podataka 30.12.2005. u 18:42 · pre 253 meseci #16

Srećni praznici svima i posebno Jablanu.

Svake godine se pojavi bar jedan post o nekoj "super" kompresiji. Više ne znam da li to negativno ili mozda pozitivno, to mu dođe kao početak interesovanja za teoriju informacija...

Re: Kompresija random-like podataka 31.12.2005. u 09:21 · pre 253 meseci #17

Srećno sve svima vama.

Citat:

BraMom: Svake godine se pojavi bar jedan post o nekoj "super" kompresiji. Više ne znam da li to negativno ili mozda pozitivno, to mu dođe kao početak interesovanja za teoriju informacija...

Nadaj se, nadaj... :)))

Potpis

While you were hanging yourself on someone else's words
Dying to believe in what you heard
I was staring straight into the shining sun

Re: Kompresija random-like podataka 31.12.2005. u 09:38 · pre 253 meseci #18

Cisto da imate sta da citate 31-vog u noc posto vecina vas onanista nece ici nigde za novu godinu ;)
Da si Jablane isprogramirao program i utvrdio da dolazi do ekspanzije a ne do kompresije ja bih ti se zahvalio do neba, priznao da sam majmun i odustao od daljeg insistiranja na kompresiji. Ovako ostaje mi samo da se kiselo nasmejem na salu koja je smesna koliko i ova moja o onanistima (znaci nimalo).

Citat:

BraMom:

Svake godine se pojavi bar jedan post o nekoj "super" kompresiji.

Sto samo svedoci da jedna takva nova kompresija mora da postoji i samo ceka da bude otkrivena.
U novoj godini sam odlucio da primenim radikalno drugaciji nacin pristupa problemu. Dakle 31-vog tacno u ponoc otvara se KONKURS! Prvi ko isporuci bilo kakav program uradjen po uputstvima iz prvog posta u okviru ove teme ima od mene MALO PIVO ispred prodavnice ili dragstora PO SOPSTVENOM IZBORU! Sta sad kazete momci? Malo pivo mozda ceka samo Vas.
Jos jednom srecna nova godina svima.

Potpis

Nemoj da pricas?

Re: Kompresija random-like podataka 31.12.2005. u 10:08 · pre 253 meseci #19

E a ako nekom uspe da kompresuje proizvoljnu random sekvencu - od mene dobija 10 gajbi piva kojeg zeli ;-)))))

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: Kompresija random-like podataka 31.12.2005. u 12:27 · pre 253 meseci #20

Loseless kompresija proizvoljne random sekvence ne predstavlja narocit problem.
Vise na: http://www.geocities.com/patchnpuki/other/compression.htm

_{[Ovu poruku je menjao blaza dana 31.12.2005. u 20:14 GMT+1]}

Potpis

O_o

Srodne teme