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: 35511 | Odgovora: 127 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.navman.com.



Profil

icon Re: Kompresija random-like podataka24.01.2006. u 23:21 - pre 4076 dana i 18h
Citat:
MajorFatal: U tvom postu od 14.01.2006. Druga recenica, zadnje tri reci.

Nisi lepo razumeo recenicu. Treba da se shvati "..u fajlu predstavlja broj n". Mada nije sada to bitno.

Citat:
Pa ako ih ti upises valjda ti najbolje znas koji su.

Ali ne zna onaj ko treba da otpakuje fajl.
Citat:
Imas fajl. Podatak n o duzini tog fajla upises u kompresovani fajl kao prvi podatak I odvojis nekakvim separatorom od drugog podatka (m) I to je cela mudrost ja stvarno ne znam sta tu ima toliko komplikovano.

Pa napisi mi tacno kako to da uradim. Koji bajt (ili niz bajtova) zelis da ti predstavlja separator?
 
Odgovor na temu

bojan_bozovic
Sir Lancelot

Član broj: 29028
Poruke: 2755
*.pat-pool.le.sbb.co.yu.



Profil

icon Re: Kompresija random-like podataka25.01.2006. u 06:49 - pre 4076 dana i 11h
Zato sto 2^n vrednosti razlicitih moras bas da prikazes sa 2^n vrednosti - spil karata ne mozes predstaviti sa 51 kartom. Ako imas 3 sedmice u hercu zaredom, mozes da stavis jedno papirce sa trojkom u spil ispred prve sedmice i dve uklonis (manje karata=kompresija). Isto je 101%. Nego, s obzirom da su dobri algoritmi za kompresiju znatno slozeniji (npr LZ) sto ti ne probas da nadjes neke algoritme za kompresiju pa da ih implementiras? Vec te to zanima vidim.

Ako imas mnogo vremena za gubljenje, uzmi sve vrednosti duzine n (tj 2^n njih, sve razlicite) pa probaj da kompresujes tvojom metodom npr vec 2^3 ili 2^4 ce da bude dosta - ne ide. Ne ide ni jednom metodom BTW. Ako nemas redundantnost - recimo niz koji se pionavlja, nema kompresije.

[Ovu poruku je menjao bojan_bozovic dana 25.01.2006. u 08:04 GMT+1]
 
Odgovor na temu

formeye
Ivan Čukić
KDE developer, Free Software Network
Serbia
BGD

Član broj: 5188
Poruke: 388
..njuel-bg.customer.sbb.co.yu.

Sajt: ivan.fomentgroup.org


Profil

icon Re: Kompresija random-like podataka25.01.2006. u 11:30 - pre 4076 dana i 6h
Citat:
Eeeeheej! Stoj! Pa ni ja tvoje: 2^(n-1) + 2^(n-2) +… nisam protumacio pogresno tj. da spajas nizove tih duzina pa bi dobio visestruko duzi niz od 2^n – 1 nego ispravno tj. da sabiras brojeve kombinacija koje su nizovi tih duzina u stanju da tvore.

Ne spajas nizove.
Pre svega, u postu kad napisem niz, mislim na konacan niz:
Ajde da pokusam sto preciznije mogu da kazem postavku zadatka i problem.
Kompresija je funkcija f koja preslikava skup nizova W na sebe samog koja mora biti bijekcija.
Znaci, nikakvog spajanja, povezivanja nizova nema. Svakom nizu iz domena moras da dodelis tacno jedan (i nijedan vise) niz iz kodomena. Obelezimo sa W_n skup nizova takvih da je njihova duzina n, a sa M_n skup nizova cija je duzina manja ili jednaka n.
Unija kad n ide od 0 do beskonacno skupova W_n je W.

Dokaz koji si imao prilike da procitas je dokaz da ne postoji bijekcija koja slika W_n na uniju skupova W_0, W_1, ..., W_n-1 = M_n-1. Sto znaci da mora postojati bar jedan niz A_n iz W_n takav da f(A_n) ne pripada M_n-1. Sto dalje znaci da je za to A_n, f(A_n) duzine vece ili jednake od n. Tu je kraj.

Citat:
Lepo sto sebe nazivate lavovima, moja ocena bi ipak pre bila da su u pitanju babe koje samo traze izgovor da ne rade svoj posao. Ja pocinjem I da sumnjam da ste vi u stanju ovo da isprogramirate.

Izvini, ali moj posao NIJE implementacija algoritama za koje je dokazano da ne rade ono sto bi trebalo. Posalji ideju u Politiku, mozda objave clanak da je neko "nas" uspeo da napravi kompresiju random podataka kao sto su objavljivali da je neka baba smislila postupak za trisekciju ugla!

Citat:
Da ja pustim vas da se vratite onome sto najbolje znate da radite: resavanje skolskih zadataka I prezvakavanje programa koji su u 1000 varijanti vec isprogramirani

A mi tebe da pustimo da se vratis svom poslu - da trosis samo svoje, a ne i nase vreme, na besmislice koje ti, zahvaljujuci nedovoljnom poznavanju materije, deluju pametno.

Do sada si odrzavao komunikaciju na nekom nivou i trudio sam se da ti objasnim gde nisi u pravu. Posle ovog posta, gde se trudis da uvredis ljude koji zele da ti pomognu, slobodno od mene ne ocekuj vise nikakvu pomoc.

To sto zelis je dokazano da je nemoguce i kraj.

Over and out.

@yooyo
:)
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
 
Odgovor na temu

ntojzan
Sandor II Tojzan
Becej

Član broj: 36657
Poruke: 168
*.bbtec.net.



Profil

icon Re: Kompresija random-like podataka25.01.2006. u 11:52 - pre 4076 dana i 6h
@MajorFatal:

Da bi kompresovao random-like podatke, moras prvo definisati sta su to random-like podaci. Potom moras ustanoviti koliki je procenat tih random-like podataka u odnosu na ukupan broj podataka da bi ustanovio da li je uopste moguce napisati program koji ce moci da smanji random-like podatke a poveca ostale. Tek posto je taj uslov zadovoljen, mozes krenuti u izradu bilo kakvog algoritma. Inace uslov za to jeste da manje od 50% ukupnih kombinacija cine random-like podaci.

Inace razlika izmedju random-like i random podataka jeste sto random podaci podrazumevaju SVE moguce kombinacije, dok se pod random-like obicno podrazumevaju kombinacije koje se ne mogu kompresovati statistickim metodama.

Ako se budes malo vise posvetio izucavanju teme, shvatices da preko 99% kombinacija cine upravo random-like podaci, znaci svi pokusaji da se ti podaci kompresuju su unapred osudjeni na propast. Uopste nije bitno koji je algoritam u pitanju.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8190
*.dynamic.sbb.rs.



Profil

icon Re: Kompresija random-like podataka30.10.2008. u 11:13 - pre 3067 dana i 6h
Imam ja 100% korektan algoritam za kompresiju bilo kakvog niza bajtova sa sledecim osobinama:

1. Radi u konacnom vremenu za ma kakve fajlove bilo koje duzine.
2. Kada se fajl zapakuja, pa otpakuje, dobija se fajl identican polaznom.

Sta mislite, kako je to moguce.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

mmix
Miljan Mitrović
Profesorkin muz
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 5775



Profil

icon Re: Kompresija random-like podataka30.10.2008. u 11:24 - pre 3067 dana i 6h
Hmmm, sa 0% stepenom kompresije
Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan, sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv… - Z.Đinđić
 
Odgovor na temu

Shadowed
Vojvodina

Član broj: 649
Poruke: 12124



Profil

icon Re: Kompresija random-like podataka30.10.2008. u 11:31 - pre 3067 dana i 6h
Tako sto je stepen kompresije manji ili jednak nuli? :)
 
Odgovor na temu

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Član broj: 15993
Poruke: 352
212.200.249.*



Profil

icon Re: Kompresija random-like podataka30.10.2008. u 11:32 - pre 3067 dana i 6h
Uh, pa taj sa 0% kompresije je jednostavan.

Mislim da je Nedeljko u opstem slucaju mislio na negativan procenat.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8190
*.dynamic.sbb.rs.



Profil

icon Re: Kompresija random-like podataka30.10.2008. u 13:41 - pre 3067 dana i 4h
Svidja mi se kako razmisljate.

Da, nigde nisam rekao da komprimovani fajl mora biti kraci od originalnog. To je to.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

misk0
.: Lugano :. _.: CH :.

SuperModerator
Član broj: 634
Poruke: 2824
*.adsl.ticino.com.

ICQ: 46802502


Profil

icon Re: Kompresija random-like podataka31.10.2008. u 08:26 - pre 3066 dana i 9h
Nigdje nije receno da je voda mokra pa je to podrazumjevano... ako se kaze 'kompresovan' onda se smatra 'sazet, smanjen, umanjen' ili kako hoces. Uostalom, svi arhiveri vracaju fajl u byte identican koliko znam, tako da.... what's the point?

:: Nemoj se svadjati sa budalom, ljudi cesto nece primjetiti razliku ::
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8190
*.dynamic.sbb.rs.



Profil

icon Re: Kompresija random-like podataka31.10.2008. u 12:42 - pre 3066 dana i 5h
Da, svi arhiveri vracaju fajl identican pocetnom, s tim da arhiva moze biti duza od polaznog fajla. Generisi (pseudo)slucajan niz vrednosti u opsegu 0-255 i upisi ih binarno u neki fajl, pa ga komprimuj cime god hoces i dobices arhivu koja je duza od samog fajla koji si komprimovao.
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: 8190
*.dynamic.sbb.rs.



Profil

icon Re: Kompresija random-like podataka31.10.2008. u 13:00 - pre 3066 dana i 4h
Evo, pomocu programa

Code:

#include <fstream>
#include <cstdlib>

using namespace std;

int main() {
    const int bytes = 100000;
    ofstream out("random.bin");
    
    for (int i=0; i<bytes; ++i) {
    unsigned char value = rand();
    
    out.put(value);
    }
    
    return 0;
}


generisao sam fajl random.bin duzine 100,000 bajtova. Kada sam ga komprimovao bzip2 kompresorom, dobio sam fajl vece duzine za 807 bajtova. Naravno, rezultati ce zavisiti od generatora pseudoslucajnih brojeva, pocetnog seed-a i izabrane kompresije i njenih parametara.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
Prikačeni fajlovi
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

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



Profil

icon Re: Kompresija random-like podataka26.08.2011. u 04:31 - pre 2037 dana i 14h
@bojan_bozovic

Citat: "Zato sto 2^n vrednosti razlicitih moras bas da prikazes sa 2^n vrednosti - spil karata ne mozes predstaviti sa 51 kartom."

Sa 2^n vrednosti kracih po broju upotrebljenih bita. Spil karata mozes predstaviti i 1 kartom ako je na primer posaljes u koverti preko okeana, tvoj sagovornik sa druge strane ce znati da treba da odigra partiju karata, a ako mu posaljes kockicu za jamb da treba da odigra partiju jamba. Spil karata mozes predstaviti i sa nekoliko karaktera: "S", "p", "i", "l", "k", "a", "r"... itd bas kao sto si ti u ovom postu pa ce sagovornik znati na sta mislis jer je spil karata za igranje opste poznata stvar, ono sto si hteo da kazes je da ne moze da se predstavi promesan spil karata sa jednom kartom ili sa 51., kartom odnosno ne spil vec redosled karata u njemu, pa sad opet zavisi, ako je spil tek stigao iz fabrike jos neraspakovan mozes jer su karte obicno u takvom spilu poredjane "po redu" (od manje ka vecoj, po znakovima), ili ako u takvom spilu fali 1. karta opet ces moci da rekonstruises spil: znaces i koja karta fali i gde joj je tacno pozicija, pa cak i ako vise karata nedostaje znaces ih sve koje su i gde su im pozicije, pa cak i ako sve nedostaju na osnovu informacije "nov spil karata" ti mozes da rekonstruises i zamislis kako to izgleda ili kupis ako hoces da igras, pa i kad je spil promesan mozes ponekad da ga rekonstruises npr: ako je neki profi krupije koji sece spil tacno na pola pa onda te dve polovine izmesa kao u onim filmovima iz Las Vegasa ako je to uradio kako treba znaces svaka karta gde je zavrsila vec na osnovu prve, ono sto si zaboravio da kazes u svom izlaganju je nesto kao: "dobro, pravedno, povoljno za igru" promesan spil karata, odnosno redosled karti u njemu se ne moze predstaviti 1. kartom ili 51. kartom, sad ti treba i neki idealni (matematicki idealan) "mesac" tj. krupije ili krupijerka u koga ces da imas poverenja da ce "dobro", po tvojoj proceni dobrog, da promesa karte, kako je br. kombinacija nacina na koji 1. spil karata moze da se promesa nekoliko biliona valjda, to je po pravilu "dovoljno dobro" za prosecnu partiju tablica, ali za profesionalne potrebe u kazinu recimo, verovatno si primetio da krupijei izmesaju desetak, petnaest spilova i sloze ih 1. do drugog, za potrebe poker aparata, mehanicke naprave koja bi trbalo da na posten nacin izmesa karte potrebno je smisliti random funkciju takvu da ne moze da bude "rekonstruisana" tj. da potencijalni igrac ne moze da uoci pravilo po kome su karte promesane i prikazuju se na ekranu, ipak s vremena na vreme okoreli pokerasi uspevaju da "zakucaju" poker aparat tj. da pogode svih 10. ili 12. ili vec koliko karata koje bi trebalo da su izabrane metodom "slucajnog izbora", sta mislis kako im to polazi za rukom, uocavaju "pravilo" ili dovoljan broj pokusaja? Redosled karata u dovoljno dobro promesanom spilu karata ne mozes predstaviti sa 1. kartom, ali to nema veze sa ovom temom o kojoj pisem. 2^n razlicitih vrednosti ako pod tim podrazumevas sve vrednosti iz nekog opsega, moras da prikazes sa 2^n vrednosti, ali u vezi sa ovim o cemu sam pisao mozes da upotrebis manji broj bita nego za prikazivanje originalnih vrednosti

Citat: "Ako imas 3 sedmice u hercu zaredom, mozes da stavis jedno papirce sa trojkom u spil ispred prve sedmice i dve uklonis (manje karata=kompresija)."

Pricamo o danasnjim, savremenim racunarima. Ne mozes da stavis papirce jer nije spil karata i papircica, vec spil karata, tj. to bi bilo kao da u "bit streamu" (nizu bita valjda) imas space (razmak) ili dvojku osim nule i jedinice, znaci ne moze.

Citat: "Isto je 101%."

Da je to sto si napisao ispravno, napisao bi ispravno tj. 100%. Ne pise se 101 nego lol :)

Citat: "Nego, s obzirom da su dobri algoritmi za kompresiju znatno slozeniji (npr LZ) sto ti ne probas da nadjes neke algoritme za kompresiju pa da ih implementiras? Vec te to zanima vidim."

Bas zato sto su slozeniji kao i danasnji programski jezici ili sam ja pogresno ucio.


Citat: "Ako imas mnogo vremena za gubljenje, uzmi sve vrednosti duzine n (tj 2^n njih, sve razlicite) pa probaj da kompresujes tvojom metodom npr vec 2^3 ili 2^4 ce da bude dosta - ne ide."

Odgovoreno na drugoj temi: http://www.elitesecurity.org/t...ompresija-random-like-podataka

Citat: "Ne ide ni jednom metodom BTW. Ako nemas redundantnost - recimo niz koji se pionavlja, nema kompresije."

U duzem random nizu ako je stvarno random (slucajan), neprestano se ponavljaju (tj. postoji redundantnost) kraci random nizovi. Nisu identicni pa da imas ponavljanje u statistickom smislu pa da brojis broj ponavljanja istog niza bita ili neke kodne reci vec su isti u jednoj svojoj osobini a to je da su takodje random kao i ceo niz neki delovi koda su manje random neki vise, ako bas mnogo skratis duzinu kodne raci kojom pregledas niz, uocices da mozda ti kraci nizovi vise i nisu toliko random tj. da ih prepoznajes po sadrzaju i tada ima mesta za statistiku i prebrajanje medjutim obicno ih tada ima i vise sto bi povecalo broj informacija za opisivanje originalnog fajla, ako produzis kodnu rec za pregledanje fajla uocices da ih sada ima manje ali su slozeniji za opisivanje. Jedini za sada dobar nacin je valjda taj LZ a on se shalta sa klasicnih metoda tamo gde moze tako da radi preko nekih prirucnih tamo gde je situacija sa bitima manje povoljna a neke delove koda jednostavno preskace i ne pokusava da ih kompresuje jer bi samo dobio losiji rezultat (za ove potrebe) tj. ekspanziju tog dela koda? Kontam i da bi LZ ili bilo koji bolji algoritam za kompresiju morao da uocava "trendove" u random nizu bita tj. da konstatuje duze ili krace delove koda koji odgovaraju gorenavedenim?
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

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



Profil

icon Re: Kompresija random-like podataka26.08.2011. u 04:43 - pre 2037 dana i 14h
Citat:
Nedeljko
...generisao sam fajl random.bin duzine 100,000 bajtova. Kada sam ga komprimovao bzip2 kompresorom, dobio sam fajl vece duzine za 807 bajtova. Naravno, rezultati ce zavisiti od generatora pseudoslucajnih brojeva, pocetnog seed-a i izabrane kompresije i njenih parametara.


Kakva je struktura novonastalog fajla od 100.807 bajtova? Da li je uredjene strukture pa je pogodan za klasicne nacine kompresije? Onda bi imao odlican rezultat : jos jednom bzip2 i dobices fajl velicine 10.000 bajtova.
Verovatno nije uredjen vec opet random? Ako na novonastali fajl od 100.807 bajtova ponovo primenis bzip2 dobices ponovo jos veci i opet random fajl? Ako bi postupak ponovio dovoljan br. puta (iteracija) mogao bi da dobijes i fajl od milion bajta koji je takodje random strukture? I to uvek istim postupkom bzip2? Da li bzip2 ima "inverz funkciju" tj. umesto recimo ponavljanja da prebraja promene ili tako nesto? Ako bi imao inverz i ako bi ti random fajl od milion bajta bio pocetni fajl za kompresiju uz pomoc dovoljnog broja ponavljanja mogao bi da ga svedes na 100.000 bajta? Tj. bar neki random fajl bi ipak mogao da se kompresuje? Ovakvom ili nekom drugom metodom. Ovo je jos jedan "namesten" primer jer vazi samo u 1. slucaju i za 1. specificni fajl ali je dobar za ilustraciju.
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

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



Profil

icon Re: Kompresija random-like podataka29.08.2011. u 00:49 - pre 2034 dana i 18h
Citat:
formeye: Ne spajas nizove.
Pre svega, u postu kad napisem niz, mislim na konacan niz:
Ajde da pokusam sto preciznije mogu da kazem postavku zadatka i problem.
Kompresija je funkcija f koja preslikava skup nizova W na sebe samog koja mora biti bijekcija.
Znaci, nikakvog spajanja, povezivanja nizova nema. Svakom nizu iz domena moras da dodelis tacno jedan (i nijedan vise) niz iz kodomena. Obelezimo sa W_n skup nizova takvih da je njihova duzina n, a sa M_n skup nizova cija je duzina manja ili jednaka n.
Unija kad n ide od 0 do beskonacno skupova W_n je W.

Dokaz koji si imao prilike da procitas je dokaz da ne postoji bijekcija koja slika W_n na uniju skupova W_0, W_1, ..., W_n-1 = M_n-1. Sto znaci da mora postojati bar jedan niz A_n iz W_n takav da f(A_n) ne pripada M_n-1. Sto dalje znaci da je za to A_n, f(A_n) duzine vece ili jednake od n. Tu je kraj.


Takodje, a nadam se preciznije, odgovoreno na drugoj temi, u postovima posle 18.06: http://www.elitesecurity.org/t...ompresija-random-like-podataka

Ovi 2^(n-1), 2^(n-2) itd... fajlovi (tj. "manji", "kraci" brojaci, tj. sve kombinacije koje su u stanju da naprave) opisuju (2^n)-2 razlicitih kombinacija jednake duzine iz originalnog opsega fajlova jednake duzine a kojih ima sve ukupno 2^n, preostala 2 fajla bi trebalo da se mogu zameniti, kodovati, kompresovati ili sta vec uz pomoc po dva razlicita fajla ali ovo se mozda moze izvesti u praksi u zavisnosti od osobina fajl sistema na kome bi se to radilo...

Citat:
formeye
A mi tebe da pustimo da se vratis svom poslu - da trosis samo svoje, a ne i nase vreme, na besmislice koje ti, zahvaljujuci nedovoljnom poznavanju materije, deluju pametno.

Do sada si odrzavao komunikaciju na nekom nivou i trudio sam se da ti objasnim gde nisi u pravu. Posle ovog posta, gde se trudis da uvredis ljude koji zele da ti pomognu, slobodno od mene ne ocekuj vise nikakvu pomoc.


-U pravu si, izvini...

Citat:
formeye
To sto zelis je dokazano da je nemoguce i kraj.


by Shanon pretpostavljam?

Citat:
formeye
Over and out.

@yooyo
:)


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 se slucajno predomislis navedi tu definiciju slucajnosti koju spominjes u zagradi "po definiciji slucajnosti".
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

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



Profil

icon Re: Kompresija random-like podataka29.08.2011. u 01:01 - pre 2034 dana i 17h
Citat:
ntojzan: @MajorFatal:

Da bi kompresovao random-like podatke, moras prvo definisati sta su to random-like podaci.


Nista ja ne moram :) A i zasto bih kad ima pametnijih i pismenijih ljudi od mene? (mada imao bih neke svoje ideje). Ako pregledas ovih par tema o kompresiji nacices nekoliko razlicitih vidjenja i tumacenja termina "random" i "random-like" cak si i ti dao jednu koja uopste nije losa, cak sta vise:
ntojzan: "Inace razlika izmedju random-like i random podataka jeste sto random podaci podrazumevaju SVE moguce kombinacije, dok se pod random-like obicno podrazumevaju kombinacije koje se ne mogu kompresovati statistickim metodama.

U trenutku dok ovo pisem "random-like" nije definisano (ili opisano) na wikipediji a i za termin "random" nije bas najsjajnija situacija: http://en.wikipedia.org/wiki/Random

Randomness has somewhat disparate meanings as used in several different fields. It also has common meanings which may have loose connections with some of those more definite meanings. The Oxford English Dictionary defines "random" thus:

Having no definite aim or purpose; not sent or guided in a particular direction; made, done, occurring, etc., without method or conscious choice; haphazard.
Closely connected, therefore, with the concepts of chance, probability, and information entropy, randomness implies a lack of predictability. Randomness is a concept of non-order or non-coherence in a sequence of symbols or steps, such that there is no intelligible pattern or combination.

Tj. u prevodu: "Bez svrhe, nije poslato u odredjenom smeru, napravljeno bez metoda odluke, hazarderski, nedostatak predvidljivosti, bez reda ili inteligentnog obrasca ponasanja"? Pa prilicno negativna definicija? Vise sta nije, nego sta jeste?

"Iskreno receno terminologiju "random-like" sam samo preuzeo sa comp-compress arhiva jer je najvise licilo na nesto cime se bavim vec duze vreme.

Citat:
ntojzan
Potom moras ustanoviti koliki je procenat tih random-like podataka u odnosu na ukupan broj podataka da bi ustanovio da li je uopste moguce napisati program koji ce moci da smanji random-like podatke a poveca ostale. Tek posto je taj uslov zadovoljen, mozes krenuti u izradu bilo kakvog algoritma.

Kao sto rekoh, nista ja ne moram, ima i pametnijih i spretnijih od mene a sasvim sigurno koji bolje programiraju.

Citat:
ntojzan
Inace uslov za to jeste da manje od 50% ukupnih kombinacija cine random-like podaci.


E da sam znao da je Shannon ne bi se toliko zamislio svojevremeno nad ovim sto si napisao, uz sve duzno postovanje Vi ponekad nekriticki prenosite neke stvari koje same po sebi nisu netacne ali ne mora da znaci da ne bi mogle da budu prosirene ili nadopunjene ili kritikovane ili gledane iz nekog drugog ugla, recimo. Ceo citat od Shannona:

The ratio of the entropy of a source to the maximum value it could have while still restricted to the same
symbols will be called its relative entropy. This is the maximum compression possible when we encode into
the same alphabet. One minus the relative entropy is the redundancy. The redundancy of ordinary English,
not considering statistical structure over greater distances than about eight letters, is roughly 50%.
This
means that when we write English half of what we write is determined by the structure of the language and
half is chosen freely. The figure 50% was found by several independent methods which all gave results in
-this neighborhood. One is by calculation of the entropy of the approximations to English. A second method
is to delete a certain fraction of the letters from a sample of English text and then let someone attempt to
restore them. If they can be restored when 50% are deleted the redundancy must be greater than 50%. A
third method depends on certain known results in cryptography.
Two extremes of redundancy in English prose are represented by Basic English and by James Joyce’s
book “FinnegansWake”. The Basic English vocabulary is limited to 850 words and the redundancy is very
high. This is reflected in the expansion that occurs when a passage is translated into Basic English. Joyce
on the other hand enlarges the vocabulary and is alleged to achieve a compression of semantic content.
The redundancy of a language is related to the existence of crossword puzzles. If the redundancy is
zero any sequence of letters is a reasonable text in the language and any two-dimensional array of letters
forms a crossword puzzle. If the redundancy is too high the language imposes too many constraints for large
crossword puzzles to be possible. A more detailed analysis shows that if we assume the constraints imposed
by the language are of a rather chaotic and random nature, large crossword puzzles are just possible when
the redundancy is 50%. If the redundancy is 33%, three-dimensional crossword puzzles should be possible,
etc.

"Inace uslov za to jeste da manje od 50% ukupnih kombinacija cine random-like podaci." - dakle to se odnosi na "standardan (svakodnevni) Engleski" jezik, koji se za moj ukus isuvise cesto pojavljuje i kod Shannona i kod McKoj-a (Dejvida Mekkeja (David MacKay), (ona treca knjiga sto mi je filmil preporucio je i dalje malo nedostupna on-line i i dalje je malo skupa), I sta sad? Da svi citamo Jojsa? (Koji je za svoje vreme bio kao super, a ovih dana je kao bas zastareo i nije vise toliko atraktivan, kazu kriticari?).

The redundancy of a language is related to the existence of crossword puzzles. If the redundancy is
zero any sequence of letters is a reasonable text in the language and any two-dimensional array of letters
forms a crossword puzzle. If the redundancy is too high the language imposes too many constraints for large
crossword puzzles to be possible. A more detailed analysis shows that if we assume the constraints imposed
by the language are of a rather chaotic and random nature, large crossword puzzles are just possible when
the redundancy is 50%. If the redundancy is 33%, three-dimensional crossword puzzles should be possible,
etc.

3D ukrstenice ne postoje jer bi bile necitljive, kako da citas slova po dubini ako ih ona ispred zaklanjaju? (mada na danasnjim racunarima, ko zna?) ali zato postoje osmosmerke kako na srpskom tako i na engleskom, nesto kao 3D ukrstenica prilagodjena za 2D engine (papir, ekran). Inace redundansa "svakodnevnog" srpskog je oko 70% bar tako kazu nasi strucnjaci za jezik?

Citat:
ntojzan
Ako se budes malo vise posvetio izucavanju teme, shvatices da preko 99% kombinacija cine upravo random-like podaci, znaci svi pokusaji da se ti podaci kompresuju su unapred osudjeni na propast. Uopste nije bitno koji je algoritam u pitanju.


Ako bi mi verovao da sam se bas dosta do sada posvetio proucavanju teme i takoreci sagoreo, bas vise ne mogu, rekao bih i da sto se velicina fajla povecava da i random-like i random podaci zauzimaju jos vise mesta ali i da veoma optimizovan fajl (kao src, bin, exe) veoma lici na veoma random fajl tj. nema ili ima veoma malo redundanse (ponavljanja) nizova bita, ali cemu, lakse je reci "dokazano je da je nemoguce"? i kraj i tacka i ostalo...
Nemoj da pricas?
 
Odgovor na temu

Cola
Slađan Čolić
Banja Luka

Član broj: 23736
Poruke: 159
*.teol.net.

Sajt: www.knjigaimena.com


Profil

icon Re: Kompresija random-like podataka04.09.2011. u 11:14 - pre 2028 dana i 7h
Jako zanimljiva tema moram priznati :)

Sećam se kada sam ja na kraju srednje došao do iste ideje za kompresiju podataka :)
dva danan nisam mogao spavati imao sam osećaj da sam otkrio sasvim nešto novo.
Sve je super izgledalo na ogromnim fajlovima da ih kompresujem pomoću 'brojača'. Tako kompresovani podaci bi se o5 mogli kompresovati i tako u nedogled. I sve mi je lijepo funkcionilao dok se nisam spustio na manje brojebe i nikako mi nije bilo jasno kako ne mogu njih da kompresujem.

Npr 4 bita 16 kombinacija kako njih da upišem u 3 ili manje bita.
Onda sam se bacio na matematiku da riješim misteriju i riješio je: Početna ideja mi nije bila dobra jer je 'brojač' predstavljao sam podatak.

Ako ništa bar sam se ta da dana osjećao kao milioner, kao neko ko je izmislio teleport ili nešto što bi se sa tim moglo uporediti.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8190
89.216.32.*



Profil

icon Re: Kompresija random-like podataka06.09.2011. u 10:14 - pre 2026 dana i 8h
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.
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: 260
109.93.0.*



Profil

icon Re: Kompresija random-like podataka07.10.2011. u 16:58 - pre 1995 dana i 1h
Sejo se malo muci dok razmislja :) a i imao sam nekih privatnih obaveza ovih dana.

Cola:

Citat:
Cola: Jako zanimljiva tema moram priznati :)


Pa priznaj ako bas moras :) Hvala za pohvalu, medjutim da li je tema zanimljiva ili ne to je off topic, zar ne?

Citat:
Cola
Sećam se kada sam ja na kraju srednje došao do iste ideje za kompresiju podataka :)


Neverovatno! A ja na pocetku srednje! Mozda smo se sretali po hodnicima? Jesi li bio kad je dolazio onaj rock band? :) Tvoja secanja iz srednje skole su off topic zar ne? :)

Citat:
Cola
Sećam se kada sam ja na kraju srednje došao do iste ideje za kompresiju podataka :)


Eh, sad, bas do iste ideje? Zapravo mislim da pokusavas da maznes moju sjajnu ideju i gotovo resenje decenijskog problema. Za tebe i onog BiF-a prvi put cujem, da li ste negde objavljivali svoja zapazanja? Ovde na ES-u mi je prethodnik bio neki sale [link ako nadjem] cini mi se, ili sallle ili tako nekako, ne mogu sad da trazim po linkovima, naci cu, a koji je dobro opisao i psihicko stanje prilikom razresavanja ovog problema "neka ideja koja uhvati i ne pusta", kao sto vidis po datumima objavljivanja tema bavim se ovim vec godinama.





Citat:
Cola
dva danan nisam mogao spavati imao sam osećaj da sam otkrio sasvim nešto novo..


Nije to nista, ja jednom 7 dana nisam spavao i zaglavio sam u bolnicu zbog toga, nemoj to da radis.

Citat:
Cola
Sve je super izgledalo na ogromnim fajlovima da ih kompresujem pomoću 'brojača'. Tako kompresovani podaci bi se o5 mogli kompresovati i tako u nedogled. I sve mi je lijepo funkcionilao dok se nisam spustio na manje brojebe i nikako mi nije bilo jasno kako ne mogu njih da kompresujem..


Eh, bas pomocu 'brojaca'? Ali hvala ti sto si 'brojac' stavio pod navodnike. Nije brojac u bukvalnom smislu u pitanju a nadam se da je do sada postalo jasno sta podrazumevam pod 'brojac': bilo kakvu konstrukciju, niz tranzistora, flip-flopova, prostor na magnetnoj traci... bilo cega sto moze da cuva i promeni stanje koje bi oznacavalo stanje nule ili jedinice. Pod 'fajl' sam podrazumevao bilo kakav niz bita nula i jedinica, najcesce smislen za onaj engine koji bi mogao da ga cita, a besmislen ili random za neki drugi engine, ili od pocetka u potpunosti random file koji je, opet, najcesce malo tezi za napraviti.
Kao sto sam vec nekoliko puta pisao [link] postoji donja granica u broju bita koji cine sadrzaj fajla za mogucnost kompresije, ispod kojeg broja dolazi do ekspanzije umesto do kompresije.
O 05 i 05 http://www.elitesecurity.org/t151770-1#1010244 http://www.elitesecurity.org/t151770-2#1012083 sam takodje vec pisao u nekoliko navrata http://www.elitesecurity.org/t158990-0#1202828 tako da 05 sigurno necu. Nije brojebe nego brojeve :)
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 260
109.93.0.*



Profil

icon Re: Kompresija random-like podataka07.10.2011. u 16:58 - pre 1995 dana i 1h
Citat:
Cola
Npr 4 bita 16 kombinacija kako njih da upišem u 3 ili manje bita..


Nikako, ako mene pitas, ali i o mogucnosti/nemogucnosti kompresovanja 4 bita sam takodje vec pisao http://www.elitesecurity.org/t158990-0#1223880 (pri kraju posta) ako nista sad comp compres ima novo poglavlje: unapredili smo i "caunting" argument nasa verzija glasi: "ne mogu 4 goluba da se natrpaju u 3 rupe"? "Counting argument" iliti "Pingeon hole argument" zvuci dosta mudro dok je na engleskom i dok ne procitas o cemu se tamo radi a to je da neki ljudi u raspravi dokazuju da 16 golubova ne moze da se smesti u 15 za to predvidjenih rupa? To i ne zvuci kao neka mnogo razumna rasprava bar ne za odrasle ili razumne ljude, zar ne?

Sto se tice primera sa 'fajlovima' duzine 3 bita (i manje za 'kompresovane' 'fajlove') koji sam koristio na onoj drugoj temi [krlp2] to je samo ilustracija, koncept nesto sto bi trebalo da pomogne da dokazem da je moguce kompresovati i random-like fajlove tj. sve fajlove, pod odredjenim uslovima naravno.
Ako si pazljivo citao mogao si da primetis da su na 8. fajlova kracih po broju bita upotrebljenih za njihovo opisivanje 'pretekle' jos 2 kombinacije koje ja nisam naveo 0_0 i 1_1 (hvala Shadowed) medjutim dok je podloga po kojoj pisemo jos uvek papir a 'engine' koji cita podatke nase oko, mozak itd. ima jos nekih 'kombinacija' kojim mogu da se opisu ona dva poslednja fajla tj:

_0_ i
_1_ su takodje savrseno legalne kombinacije pod uslovom kad bi recimo pojedinacni biti ili mesta predvidjena za njihovo upisivanje mogli da se citaju ili tumace kao posebne kombinacije,
kao na primer kad bi ona tablica istinosnih vrednosti duzine 3. bila upisana u neku tabelu u relacionoj bazi podataka pa kad bi nad pojedinacnim bitima mogao da se primeni view (pogled) (i kad bi view uvek bio fiksne duzine bez obzirz nad kolikom kolicinom podataka je primenjen), kako za sada nisam siguran da je to moguce u praksi ne bih da to predlazem kao resenje za realizaciju ove kompresije i dekompresije.

Takodje:
0__ i
1__ su takodje legalne kombinacije, jedino ne mogu da se upotrebe
__0 i
__1 jer su vec navedene na spisku 'kracih' fajlova kao prve dve kombinacije [link], takodje vaze i sve kombinacije od 2 bita upotrebljena ali na drugim pozicijama:

00_
01_
10_
11_ ako pazljivo prebrojis trebalo bi da dobijes 15. kombinacija od dva i jedan bit na razlicitim pozicijama i jos 8. kombinacija od po 3. bita, zajedno (ukupno) 23. kombinacije dovoljno za svih 16. kombinacija od po 4. bita, ili preciznije za svih 16. kombinacija jednakih po duzini medjusobno.

Problem sa papirom kao 'podlogom' po kojoj pisemo i okom, mozgom, itd. kao 'enginom' koji cita je sto za ove potrebe ima malo nezgodnu osobinu a to je da ovaj put papir ne moze
najuspesnije da opise stanje u racunaru u tom trenutku, mogu da napisem 'mesto rezervisano za bit' ali u praksi to mesto je uvek popunjeno ili nulom ili jedinicom tako da...uglavnom iz tog razloga sam odabrao za opisivanje ona poslednja dva 'fajla' sa spiska svih fajlova odredjene duzine kombinacije:

0_1 i
1_0 jer mislim da ako bi neko pokusao da isprogramira ovo u praksi da bi mu bilo mnogo lakse da se organizuje onako kako sam napisao a to je: posto pojedinacni fajlovi na onom 'crtezu' koji sam prilozio u stvari predstavljaju cele, kompletne neke fajlove, crtez predstavlja da dva pojedinacna fajla (u ovom slucaju prava fajla bez navodnika) moraju biti razliciti i zajedno kraci po broju upotrebljenih bita od odgovarajucih (pripadajucih) fajlova u punoj duzini a koje hocemo da kompresujemo.

Nagovesto sam da je teren malo klizav i da je potrebna koncentracija.

Citat:
Cola
Onda sam se bacio na matematiku da riješim misteriju i riješio je: Početna ideja mi nije bila dobra jer je 'brojač' predstavljao sam podatak..


To vazi ( i 'countin argument' uopste ) za fajlove jednake medjusobno po 'duzini' tj. broju upotrebljenih bita a ako je i 'brojac' tako konstruisan, ali ako se bavis matematikom mozes slobodno da prilozis tu svoju racunicu u okviru ove teme :) bas me zanima kako si racunao nesto sto je zi:: svojevremeno ispisao u jednoj recenici http://www.elitesecurity.org/t93798-0#604994


Citat:
Cola
Ako ništa bar sam se ta da dana osjećao kao milioner, kao neko ko je izmislio teleport ili nešto što bi se sa tim moglo uporediti.


Dva dana :) A nisi se osjecao kao bilijarder? :) Kad isprogramiras softwer koji je ekvivalent 'filozofskom kamenu mudrosti' http://www.hutter1.net/ai/aixigentle.pdf mocice i teleport i vremeplov i djunta sa sitnim nutom, naravno to nek ti uradi onaj ko ti je rekao da moze :)
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: 35511 | Odgovora: 127 ] > FB > Twit

Postavi temu Odgovori

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