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

algoritam za kompresiju

[es] :: Art of Programming :: algoritam za kompresiju

[ Pregleda: 4751 | Odgovora: 18 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

sallle
Sasa Ninkovic
GTECH
Beograd

Član broj: 146
Poruke: 480
*.rcub.bg.ac.yu

ICQ: 20785904


+4 Profil

icon algoritam za kompresiju23.11.2002. u 13:12 - pre 230 meseci

U glavi mi se mota neka ideja oko kompresovanja podataka. U sustini postupak bi trebalo da moze da zapakuje npr 128MB podataka na obicnu disketu (3,5 ili 5.25 ' :)).
Jedino sto treba resiti to je matematicki deo (sad ce neko da kaze: pa to je sve sto treba resiti u datom problemu).

I recimo ja uspem to da resim... Kako onda mogu da naplatim tu svoju ideju? Da li za algoritam ili postupak mogu da se poseduju autorska prava? (kod ove moje ideje cini mi se da sam algoritam nece biti kljucni, jer ce verovatno moci i neki drugi da se nadje, nego je kljuc u konceptu).

Same pojedinosti o konceptu ne smem da kazem ( u sustini i nema puno da se kaze - moze sve da se iskaze u jednoj recenici) da me ne bi neko preduhitrio :).

poz,
pohlepni sale

 
Odgovor na temu

ImPlant
Panajotis Zamos
bgd

Član broj: 730
Poruke: 238
*.verat.net

Jabber: aqw137@gmail.com
Sajt: weevify.com


Profil

icon Re: algoritam za kompresiju23.11.2002. u 14:30 - pre 230 meseci
to da li mozes da dobijes autorska prava na ideju (koncept) stvarno ne znam, to bi trebao da se pita neki pravnik.

'esi ono za 128MB > 1 disketu rekao onako primera ili stvarno imas takvu ideju i da li je ideja da smestis 128MB na 1disketu ili na otprilike 1.44MB ???


.
look
closer

DON'T
PANIC
 
Odgovor na temu

anon315

Član broj: 315
Poruke: 1657
*.beg.sezampro.yu



+13 Profil

icon Re: algoritam za kompresiju23.11.2002. u 15:22 - pre 230 meseci
Pa koje je tvoje pitanje ??? Nisi nam izložio matematički problem koji imaš. Što se tiče naplate, teorijski, najbolje je da napraviš program (ne open source) koji će to da šljaka. Ipak, potrudi se da postaviš pitanje vezano za matematički problem. Malo mi deluje nerealno to što pričaš, pa da vidimo

Što se tiče pohlepe, moraćeš da rizikuješ, jer ako ne pitaš onda ćeš morati sve sam, a to očigledno već ne možeš

[Ovu poruku je menjao seven dana 23.11.2002. u 22:48 GMT]
 
Odgovor na temu

Ivan Dimkovic

Administrator
Član broj: 13
Poruke: 16218
*.dip.t-dialin.net



+7025 Profil

icon Re: algoritam za kompresiju23.11.2002. u 15:25 - pre 230 meseci
Citat:

U sustini postupak bi trebalo da moze da zapakuje npr 128MB podataka na obicnu disketu (3,5 ili 5.25 ' :)).


Ni u kakvoj teoriji ti ne mozes spakovati podatke ispod tzv. procenjene "entropije" - tako da ako 128 MB podataka ima entropiju (statisticku napredvidivost) od 80 MB, ni jedan kompresioni metod ti nece pomoci da to smanjis...


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
 
Odgovor na temu

ventura

Član broj: 32
Poruke: 7781
*.net.yu



+6455 Profil

icon Re: algoritam za kompresiju23.11.2002. u 15:59 - pre 230 meseci
Meni je jednom pala jedna ideja na pamet.. bas oko te kompresije.. pravio sam i source po tome, radilo je, ali je bilo dosta bagovito i nepouzdano...

O cemu se radi...

recimo ovaj string je lako zapakovati:

AAAAAAAAAAAAABGAAAA1EEEEE
13ABG4A15E

Sve se svodi na kompresiju ponajvljajucih bitova.. I to su koristili prvi kompresori...

E sad, moj metod radi na sledecem principu..
Recimo da je ovo primer stringa:

ASFAAWAERNCMAXLSKAYHCGHASKAXNALWUTAGSDJASAKLLLASNXAGHGWAL

Kad se ovaj string prevede u neki binarni oblik 0 i 1, dobija se neki tamo rezultat... (sad da ne pisem binarno, jer nije pregledno)

E sad.. Pri ucitavanju stringa koji se kompresuje, odredi se koji se niz najcesce ponavlja... Recimo u ovom slucaju slova A, G, L, S ... lupam... A se recimo prikazuje kao 01001001, poenta je da se binarno skrate svi nizovi koji se najcesce koriste, a da se oni najmanje korisceni ostave isti... I takav string da se u dekompresoru, prevodom, vrati u originalan format...
I onda se na to moze primeniti onaj 'repetition' algoritam, i dobije se prilicno dobra kompresija...
 
Odgovor na temu

Ivan Dimkovic

Administrator
Član broj: 13
Poruke: 16218
*.dip.t-dialin.net



+7025 Profil

icon Re: algoritam za kompresiju23.11.2002. u 17:26 - pre 230 meseci
U svakom slucaju, ni jedan kompresor - koliko god "savrsen"(*) bio ne moze da uradi sledece:

1. Da komprimuje svaki fajl, marar za >jedan< bit manje
2. Da komprimuje svaki fajl sa istim stepenom kompresije

Oba se vrlo lako matematicki dokazuju, tako da..

(*) I "savrsenost" je relativan pojam, posto univerzalnog kompresora nema - neki vise "vole" odredjeni materijal - aritmeticka kompresija se do sada pokazala najboljom za potpuno nepoznat izvor.





Ventura: to sto ti predlazes je vec implementirano u mnogim algoritimima :)

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
 
Odgovor na temu

ventura

Član broj: 32
Poruke: 7781
*.net.yu



+6455 Profil

icon Re: algoritam za kompresiju23.11.2002. u 17:50 - pre 230 meseci
Pa naravno da postoje fajlovi koji ne mogu da se kompresuju ni za jedan jedini bit...

Isto kao sto je razlika izmedju kompresovanog TXT fajla i kompresovanog JPG fajla ocigledna...


Offtopic... Kad uzmes najbolji kripter, i fajl koji je kriptovan njime, on nesme da se kompresuje vise od 1% od originalne velicine...
 
Odgovor na temu

anon315

Član broj: 315
Poruke: 1657
*.beg.sezampro.yu



+13 Profil

icon Re: algoritam za kompresiju23.11.2002. u 18:10 - pre 230 meseci
Čovek samo hoće da kaže da ne možeš slona da strpaš u prosečan kontejner. Ukoliko ga iseckaš na parčiće moći ćeš dobar deo njega i da naguraš, ali celog ne, jer prosto i da ga samelješ i presuješ količina je količina ... opet neće stati ceo u đubre ...
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.verat.net



+3 Profil

icon Re: algoritam za kompresiju23.11.2002. u 18:36 - pre 230 meseci
Covek u opste nije rekao o kakvim podacima je rec i o kakvoj kompresiji je rec. Mozda je rec o nekoj kompresiji sa gubicima kao mp3 ili jpg (ne znam sta hoce da kompresuje) i mozda te podatke sto on hoce da kompresuje moze da smesti na jednu disketu.

Covek je lepo pitao da li moze da poseduje algoritam. Odgovor je da moze ali ne svuda. Zavisi od drzave. U Evropi ne moze a u Americi moze. Recimo za mp3 algoritam postoje autorska prava.
A to sta on hoce da kompresuje i kako to nije bitno i covek je to dao kao primer i nemojte odmah da ga napadate dok ne znate o cemu je rec. Samo mu pomozite sta je najbolje da radi ako ima tako neki algoritam koji kompresuje (sa gubicima) neke podatke... Da li da napravi komercijalan program (koji moze da se crackuje) ili da bude opensource a da u Americi patentira algoritam ili nesto trece da uradi...
 
Odgovor na temu

Ivan Dimkovic

Administrator
Član broj: 13
Poruke: 16218
*.dip.t-dialin.net



+7025 Profil

icon Re: algoritam za kompresiju23.11.2002. u 19:42 - pre 230 meseci
Nije bas tacno - mp3 je patentiran u skoro svim razvijenim zemljama, kao skup PCT patenata (npr "uredjaj za digitalno kodiranje audio signala", "metod i uredjaj za perceptualno kodiranje signala") - mozes i ti da fajlujes PCT patent(e) ali pripremi se:

1. PCT patenti su vrlo skupi, moras da ih potrvrdis u svakoj zemlji

2. Od zemlje do zemlje varira rok koji patent mora da "lezi" (u DE je recimo oko 2-3 godine) pa onda evaluacije, itd..

3. U USA je najlakse dobiti patent.


Moras i da uradis research da li postoji prior art (da li pokusavas da patentiras nesto sto vec postoji) - u svakom slucaju ce ti biti potreban patentni advokat, za pocetak oko $1000-$2000 a ako PCT prodje moraces da platis registraciju u svakoj zemlji ponaosob. U vecini slucajeva patente fajluju firme u kojima pronalazaci rade, uz obavezno deljenje profita - ne znam za YU ali znam da je u Nemackoj to osigurano u zakonu, tako da firme obicno plate extra kes ljudima samo da se odreknu prava na kompenzaciju :)



I, na kraju, covek je rekao "kompresovanje podataka" a ne "kompresovanje slike / zvuka / videa" tako da se podrazumeva kompresija bez gubitaka - 16:1 ce raditi samo na fajlovima cija je entropija blizu 16:1 i ako je algoritam dobar - za ostale jednostavno nece biti tako.


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
 
Odgovor na temu

sallle
Sasa Ninkovic
GTECH
Beograd

Član broj: 146
Poruke: 480
*.etf.bg.ac.yu

ICQ: 20785904


+4 Profil

icon Re: algoritam za kompresiju23.11.2002. u 20:18 - pre 230 meseci

Ja ne bih da transportujem slona, ja bih da napravim istog takvog kod sebe :))).

poz,
sale
 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.rcub.bg.ac.yu

Sajt: localhost


+4 Profil

icon Re: algoritam za kompresiju24.11.2002. u 14:49 - pre 230 meseci
ventura: to sto ti piricash se zove Huffman coding, i to koriste i zip/arj/rar/gz i vecina drugih kompresija (nisam siguran, ali verovatno i kompresije slika/muzike/...)

sallle: to sto pricash, kao sto neko rece, je nemoguce. naime, moguce je za odredjen tip podataka (text, html, slike, muzika, ...) ali za bilo kakve binarne podatke nije moguce.

kako mozes da zapakujesh jedan bajt? nikako naravno, jer se jednim bajtom moze napisati 256 razlicitih vrednosti. da dva bajta mozes napisati 65536 razlicitih vrednosti, a toliko nema sanse da ih predstavish sa jednim (ili nula ;) bajtom....

etc, da ne duzim, 128 miliona bajtova moze da sadrzi 256128,000,000 razlicitih vrednosti. toliko vrednosti ne mozes da predstavish (u opstem slucaju) ni sa 128,000,000-1 bajtova, a kamoli sa 1,440,000 bajtova...

 
Odgovor na temu

ImPlant
Panajotis Zamos
bgd

Član broj: 730
Poruke: 238
*.verat.net

Jabber: aqw137@gmail.com
Sajt: weevify.com


Profil

icon Re: algoritam za kompresiju25.11.2002. u 08:26 - pre 230 meseci
Citat:
sallle:

...
I recimo ja uspem to da resim... Kako onda mogu da naplatim tu svoju ideju? Da li za algoritam ili postupak mogu da se poseduju autorska prava? (kod ove moje ideje cini mi se da sam algoritam nece biti kljucni, jer ce verovatno moci i neki drugi da se nadje, nego je kljuc u konceptu).
...


mislim da je ovo zapravo bilo pitanje i da je zato promasilo teme

kad smo vec kod kompresije sve zavisi od toga sta se kompresuje jer je u nekim slucajevima moguce i kompresije od 100 i vise puta slika od 1024x768 pixela, potpuno crna kad se zipuje (znaci ne gubi se uopste na kvalitetu) dobije se oko 23KB dok je original bio >2.2MB (kad se prebaci u jpg dobije se malo vise od 10KB ali tu se gubi na kvalitetu)

.
look
closer

DON'T
PANIC
 
Odgovor na temu

Ivan Dimkovic

Administrator
Član broj: 13
Poruke: 16218
*.telemaxx.net



+7025 Profil

icon Re: algoritam za kompresiju25.11.2002. u 11:29 - pre 230 meseci
Mislim da sam sa terminom kompresione entropije pokrio "kompresibilnost" podataka - znaci, sa "savrsenim" alfabetom je moguce neki string opisati sa najmanje podataka. Limit velicine tog stringa se naziva kompresiona entropija, i doticnu je vrlo jednostavno izracunati.

String koji se sastoji od potpuno slucajnih podataka (random) ima entropiju od tacno 1, dakle - nije ga moguce kompresovati.


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
 
Odgovor na temu

Shadowed
Vojvodina

Član broj: 649
Poruke: 12798



+4738 Profil

icon Re: algoritam za kompresiju25.11.2002. u 12:16 - pre 230 meseci
Citat:
ImPlant:
(kad se prebaci u jpg dobije se malo vise od 10KB ali tu se gubi na kvalitetu)
.

Bas si pametan . Kako si ti to izgubio na kvalitetu potpuno crne slike ???
 
Odgovor na temu

sallle
Sasa Ninkovic
GTECH
Beograd

Član broj: 146
Poruke: 480
*.rcub.bg.ac.yu

ICQ: 20785904


+4 Profil

icon Re: algoritam za kompresiju25.11.2002. u 18:13 - pre 230 meseci
izgleda da mi post promenio kategoriju (poco na matematici).

Men se i dalje cini da je ovo matematika, al ok.

1. Sta me fasciniralo, u numerickoj matematici, kad od neke proste jednacine koju jako lako mozemo da napisemo, resavanjem dobijamo mnogo duga resenja (sa gomilom decimala), npr sin(1). Taj niz cifara se menjao u zavisnosti od broja iteracija, i naravno ulazne velicine. Znaci teoretski postoji takav hard disk od 2GB koji moze da se zapise samo sa funkcijom: sin(1), brojem iteracije, i verovatno nekim brojem registara(koji se koriste prilikom operacija...).
Ideja mi je bila da se za svaki niz nadje neka prosta f-ja generatrisa koja ce ga u n-toj iteraciji generisati.

Sta je ovde problem, f-je ocigledno moraju biti 1-1, znaci kolko imam izlaznih kombinacija tolko moram da imam i ulaznih kombinacija(podataka).
Tako da ne mogu da dobijem ustedu u prostoru.


2. Posle mi je palo na pamet, da pravim "virtuelnu masinu". Problem sa velicinom ulaznih podataka da resim tako, sto cu na neki nacin da koristim memoriju racunara(Da mi 64MB rama budu ulazni podatak, i da se koriste prilikom iteracija) al sam se opet preso, 64MB rama prilikom racunanja ne znaci 64MB ulaznih podataka, vec jedan ulazni podatak.

Ovde sam razmisljo u pravcu da pokusam da kineticku energiju prenesem u potencijalnu, naime manjak podataka da zamenim procesorskim vremenom koje ce da ih reprodukuje, al ne ide...

Mozda ce nekom ovo sve delovati smesno... al ok :)

Eto tolko o idejama koje su trebale da mi donesu slavu novac i tako to...

zakljucak:

cini mi se ipak da ima prostora u trazenju f-ja koje su u stanju da izgenerisu neki niz brojeva, i da bi se odredjeni podaci ili delova podataka mogli zamenjivati jednacinama koje ce da generisu te podatke (samo ih treba naci)...

poz,
naivni sale

p.s. malo je bezveze sto mi se sve ove ideje motaju po glavi skoro god dana(al nikad nisam preterano razmisljo), i evo sad sedoh 15 min sa papirom i olovkom i provalih da nema leba od ovog...
 
Odgovor na temu

anon315

Član broj: 315
Poruke: 1657
*.beg.sezampro.yu



+13 Profil

icon Re: algoritam za kompresiju25.11.2002. u 18:39 - pre 230 meseci
Poruku sam premestio u ovaj forum zato što je tvoja, da tako kažem, inicijalizaciona poruka najviše odgovarala upravo ovom forumu (kompresija, algoritam, matematičke metode). Sada već ima više matematike, ali da ne bi šetali ljude "tamo-vamo" neka ipak ostane ovde.

Što se tiče same ideje, trenutno nemam dovoljno znanje da mogu da da dam neki adekvatan odgovor ili mišljenje, ali ono što mi se čini, možda grešim, je da je nemoguće kreirati funkciju koja bi na osnovu jednog parametra izgenerisala sve te podatke (upravo zbog 1-1). A sa druge strane, zamisli i da može tako nešto, opet mi se čini nemogućim da se kreira takva odgovarajuća funkcija koja će generisati tebi baš potrebne podatke !? A kamoli opšti algoritam za kreiranje funkcije koja će biti u stanju da bilo koje date podatke spakuje. Ustvari, da li uopšte postoji pravilo ili podaci prosto predstavljaju gomilu kodiranog đubreta koje je nemoguće dekodirati, ha, kad malo bolje razmislim ovo ima veze i sa reverse engineering-om, hehehe ...
 
Odgovor na temu

Ivan Dimkovic

Administrator
Član broj: 13
Poruke: 16218
*.dip.t-dialin.net



+7025 Profil

icon Re: algoritam za kompresiju25.11.2002. u 19:26 - pre 230 meseci
Evo malo pojasnjenja:

"Magic Function Theory":

http://www.dogma.net/markn/FAQ.html#Q19

pokusaji:

http://www.faqs.org/faqs/compression-faq/part1/section-8.html

i:

http://www.ddj.com/documents/s=325/ddj0201cm/


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
 
Odgovor na temu

dRock9
Kragujevac - Beograd

Član broj: 4217
Poruke: 54
*.ptt.yu



Profil

icon Re: algoritam za kompresiju26.11.2002. u 01:45 - pre 230 meseci
xmmm,
ne motam se bas preterano po forumima, pa ne sagledam, bas svaku poruku kad treba

Posto si nam otkrio svoju "revolucionarnu" ideju, da malo pojasnim stvar:
Pronalazenje funkcije generatrise je poprilican problem, na nacin na koji si ti opisao i nije lako resiv. Posto sam tok diskusije gledao od pocetka ka kraju, u jednom trenutku sam pomislio da je tvoja ideja da napravis nacin modeliranja zapisa podataka, tako da u svojoj arhivi opises zapis, a zatim prosledis konkretan zapis podataka - da bi mogao da nadjes sto bolje univerzalno resenje za razlicite tipove podataka (ono sa slonom me je potstaklo na to). Ovde ne mislim na razlicite tipove kao slika, zvuk, itd, vec na uredjenje podataka - da li se ponavlja ovo ili ono ili sta vec. Sto se tice nalazenja tvojih funkcija, evo jednog malog objasnjenja. Naime, svaka funkcija (dokazano u matematici) se moze razloziti kao kombinacija parnih i neparnih funkcija (takve su npr. cos i sin). Algoritam za tako nesto postoji i poznat je pod nazivom FFT (Brza Furijeova Transformacija) i uglavnom se primenjuje kod A-D konverzije i ti od jedne funkcije dobijes polinom u kome figurisu dve adekvatne funkcije. Suludo bi bilo da pokusavam da ti ovde objasnjavam nacin rada FFT-a, za vise informacija o njemu savetujem da pogledas "knjizicu" Introduction to Algorithms (MIT Press). Nalazenje konkretne slozene funkcije nije uopste jednostavna - zapravo, ako sam te dobro razumeo zelis da neku krivu ili sta god prevedes u matematicki oblik, a to nije ni uvek izvodljivo. Osim toga, samo izracunavanje vrednosti funkcije nije uvek jednoznacno, tako da u pitanje dovodis validnost podataka koje preneses tvojim arhiverom. Posto si pominjao numericku analizu, verovatno si upucen u aproksimaciju (Tejlorov polinom i ostalo). To je upravo jedan od nacina pribliznog odredjivanja funkcije u nekom matematickom obliku, ali uzmimo za primer da prenosis jedan izvrsni fajl. Dovoljno je promeniti par bitova i nisi uradio nista (s tim u vezi ti je potrebna ona bijekcija koju si pominjao). Priblizne metode se koriste, ali kod podataka gde apsolutna korektnost istih nije presudna (npr. slike, zvuk, ...). Za to se koriste drugi algoritmi koji daju bolje rezultate uz prihvatljiva odstupanja (otuda potice vektorska kompresija - npr. LZW). Cak i realizacija takvih algoritama nije bash trivijalna - npr. fraktalna kompresija slika je manje-vise izvodljiva za crno-bele slike, ali vec uvodjenjem boja stvar se neverovatno komplikuje.

Ideje koje dobijamo su vrlo bitna stvar, za zdrav razvoj uma i sazrevanje i ima ih svako od nas. Medjutim kao i nacin razmisljanja, uglavnom su produkt okruzenja i iskustva tako da ces se za mnoge stvari razocarati, ali polako, ima vremena za prave stvari koje ces moci da primenis i unovcis - ne postaje se genijalac bash preko noci

nadam se da nisam bash mnogo smorio, pozdrav
 
Odgovor na temu

[es] :: Art of Programming :: algoritam za kompresiju

[ Pregleda: 4751 | Odgovora: 18 ] > FB > Twit

Postavi temu Odgovori

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