Kompresija random-like podataka 2

(Upozorenje za one koji su odmah skrolovali na zadnji post u temi: premotaj tri posta unazad tu pocinje odgovor)

Dobro si me shvatio ali broj 1025 je jos uvek isuvise mali da bi zapisivanje faktorima bio racinalan nacin zapisivanja za njega. Probaj sa listingom broja 2^8000 sa prve strane rasprave "beskonacna kompresija..." (bkkr) gde je listing jednog decimalnog broja zauzeo celu jednu a4 stranu oko 2500 cifara. Ako svaka cifra zauzima po 4 bita to je 10000 bita na disku (na nacin na koji si ti odredio 16 bita za broj 1025), ako ga prevedes u binarni brojni sistem zauzece 8000 bita (na nacin na koji se 1025 m moze smestiti u 10 bita kod tebe) a faktor koji ga opisuje tj. iz kojeg se da izracunati tacna vrednost broja 2^8000 zauzima 48 bita iliti 6 Byta (po 1 Byte za svaku oznaku). I da imas gresku u racunu 1025 se ne moze smestiti u 10 bita vec najmanje u 11 (2^10 = 1024).

Dva upaljena bita su prvi i jedanaesti. Povecajmo broj upaljenih bita na maksimum tako sto cemo ih upaliti sve da bi smo proverili da li se izraz zaista komplikuje i da li ce trebati vise mesta da se zapise. Rezultat: faktor 2^11 koji opisuje br. 2048 koji odgovara situaciji svih jedanaest bita upaljeni ;) A faktor 2^11 je kraci za zapisivanje od faktora 4^5 + 1. Ma znam sta si hteo da kazes komplikuju se ovi izmedju "optimalnih" pozicija koje se daju opisati samo jednim faktorom 2^n, 2^(n-1) itd ali kad udjemo u zonu malo vecih brojeva u pomoc nam priskace to sto cemo moci da koristimo i faktore sa osnovicom razlicitom od 2 (3,4,5...) te takodje sto cemo moci da stavimo i neki mnozilac ispred s tim u vezi mozda sam ilustrujuci kako Mf treba da izgleda (M faktorski) trebao umesto a^b + c^d - itd... trebao da napisem a*(b^c) + d*(e^f) - itd...

Lepota zapisa broja faktorima je sto se sa veoma kratkim za zapisivanje faktorima mogu predstaviti veoma velike brojcane vrednosti. Leta gospodnjeg MMVI.

Ne vredjam se, ali ni bez ovakvih ideja necu daleko dogurati na ovom ili nekom drugom polju tako da mi dodje na isto.
E sad analiza mesta dge sam pogresio. Znaci kompresija je bila u redu (sa podrazumevanom vrednoscu da ne treba praviti brojac) a prilikom opisa procesa dekompresije sam napisao sledece:
Citat: 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.
Samo po sebi nije netacno ali zaista imam brojac viska a sve sto je viska treba ukloniti. Znaci iz M faktorski (Mf) racuna se M decimalno (Md) a Md se prevodi u M binarno (Mb) bez pravljenja brojaca. Mb kada se "izracuna" reprezentuje originalni fajl u slucaju da mu se duzina poklapa sa N a ako je krace nadopunjuje se nulama na pocetku niza bita kojim je predstavljen do duzine N. Kad malo bolje razmislim mozda nisam slucajno prezentovao dekompresiju na ovaj nacin pravljenjem brojaca duzine N i pustanjem u rad istog ne moze se promasiti kad tad ce natrcati na originalni fajl jer su iste duzine i to originalni fajl "ceo u kompletu" a ovim postupkom Prevodjenjem iz Md u Mb dobija se samo deo fajla od pojave prve jedinice do kraja fajla tako da se mora nadopunjavati nulama, na onaj prvi nacin bilo je ociglednije da se originalni fajl da rekunstruisati na osnovu opskurnih informacija iz kompresovanog fajla.
Sledi potpuna redefinicija postupka kompresije i dekompresije fajlova iz razloga skracivanja postupka i uklanjanja dvosmislenosti koje su nastale pominjanjem i koriscenjem brojaca u postupcima kompresije i dekompresije:
Dakle celokupni binarni sadrzaj fajla se tretira kao jedan veliki binarni broj (Mb) te se veoma lako taj broj prevodi u broj u decimalnom brojnom sistemu (Md) koji se zatim faktorizuje na optimalan nacin te se dobija zapis Mf. Za sve fajlove za koje zapis Nd|Mf zauzima manje mesta nego originalni fajl (dge je Nd broj koji predstavlja duzinu originalnog fajla u bitima) dobija se kompresija, za ostale ekspanzija ili bez promene velicine. Dekompresija se vrsi tako sto se iz izraza Mf izracuna decimalna vrednost Md koja se zatim prevodi u broj u binarnom brojnom sistemu Mb koji se zatim u slucaju da je kraci od vrednosti koju oznacava Nd nadopunjuje na pocetku nulama do vrednosti koju oznacava Nd. Right?
Granicna duzina originalnog fajla ispod koje ne bi trebalo ni razmisljati o postojanju kompresije je na 56 bita. Naime vec na toj duzimi nekoliko fajlova se da kompresovati po ovom sistemu. Zapis 56|2^0 zauzima manje mesta (48 bita) nego originalni fajl koji sa da rekonstruisati iz njega. Izmedju 56|2^0 i 56|9^9 ima oko 50-tak slicnih fajlova. Jos uvek nisu neke ekstra random like strukture ali to je zato sto jos uvek sebi nismo priustili duzinu fajla koja bi nam omogucila stavljanje bilo kakvog mnozioca ispred faktora. Right?

---

Koliko se pise o ovome mogao si da naucis programiranje i pokazes svetu kako to radi (i da li uopste radi)

---

Pa ucim, ucim al sporo ide sacuvaj boze.

---

Bolje ti je da uzmeš matematiku u šake, da jesi, ne bi ni postojala ova tema.

Moze biti nego meni matematika ide srednje zalosno da dzabe ne uzimam?

---

Sama faktorizacija broja i njegova predstava u kompresovanom fajlu bi trebalo da predstavlja srž tvog algoritma a ne ovo što si ti dao. Tvoj ceo algoritam je nalaženje broja m a hoćeš da ti neko drugi smisli alogritam za faktorizaciju. Ako uporedimo kompleksnost ovog šti si ti dao je 1% konačnog algoritma.

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

---

Hvala za link. Ama nisam znao da je ova faktorizacija tako zajebana. Javicu se kad/ako isprocesiram pristigle informacije.

---

http://prize.hutter1.net/

---

Hm...samo da kazem da ovo sto covek hoce nije faktorizacija.

Faktorizacija bi bilo nesto tipa:
120/2=60
60/2=30
30/2=15
15/3=5
5/5=1

120=2^3 * 3 * 5

a ovde se trazilo to isto sa sabiranjem, tipa:

11^2 + (-1)^1

toliko....

Hvala. Jos kada bi bilo brze za izracunavanje... npr 16 meseci za broj od 200 cifara ;)

---

Bump ;)

Izvinite sto prosle nedelje nisam ucestvovao u raspravi ;) (fazon od 1 drugara kad jedno 3 godine nismo isli na neka predavanja: "Aj da se pojavimo i da kazemo izvinite sto nismo bili prosle nedelje ")

Ama, verovatno sam ja opet nesto prevideo, pogresno skontao, ali meni se cini, kompresija random-like, tj. svih podataka je ipak mozda moguca: evo i kako:

Od svih 2^n konbinacija koje moze da napravi 1 brojac duzine n, (2^n) - 2 kombinacija se mogu predstaviti nizovima bita kracim od originalnih, a preostale dve kombinacije bita se mogu predestaviti visestrukim nizovima bita, ciji je zbir (broja bita) kraci od duzine broja bita originalnih kombinacija. Sve ovo vazi za n>=3.

A, sta kazete?

---

Cutanje je znak odobravanja ;)

Gde se Shanon i ja slazemo:

3. Suppose there are two events, x and y, in question with m possibilities for the first and n for the second.
Let p(i; j) be the probability of the joint occurrence of i for the first and j for the second. The entropy of the
joint event is
H(x;y) = 􀀀åi; j p(i; j) log p(i; j)
while
H(x) = 􀀀åi; j p(i; j) logåj p(i; j)
H(y) = 􀀀åi; j p(i; j) logåi p(i; j):
It is easily shown that
H(x;y) <= H(x)+H(y)

with equality only if the events are independent (i.e., p(i; j) = p(i)p( j)). The uncertainty of a joint event is
less than or equal to the sum of the individual uncertainties.

Tj. "neodredjenost" nekog "zajednickog" dogadjaja 2 dogadjaja je manja ili jednaka zbiru neodredjenosti posebnih dogadjaja, tj. ako uzmemo sve moguce dogadjaje koji se mogu desiti (stanja na brojacu) njihov ukupni zbir neodredjenosti je manji nego kad bi sabirali svaku "neodredjenost" za svaki dogadjaj posebno. (Tj. nosi manju kolicinu informacija, tj. da se kompresovati).

Gde se "vidi" da cika Shanona i mene nisu interesovale iste stvari ili bar ne identicne:

1. H = 0 if and only if all the pi but one are zero, this one having the value unity. Thus only when we
are certain of the outcome does H vanish. Otherwise H is positive.

Imao sam negde jos bolji citat, al sam zagubio: naravno da ako hoces da prenosis informacije (cime se bavio Shanon) da su ti potrebne i nule i jedinice (ako ti je binarni br. sistem sredstvo prenosenja) jer inace informacija ne bi ni postajala ili bi imao samo 2 moguce kombinacije bita tj. samo 2 razlicite informacije, ali za skladistenje podataka to nije uslov tj. mogu se iskoristiti i preostale 2 kombinacije bita: fajl sastavljen samo od nula i fajl sastavljen samo od jedinica, tj. kod Shanona fajl (informacija) "koji sadrzi bar 1 jedinicu" nosi najmanju kolicinu entropije (ovo "bar 1 jedinicu" se odnosi na: krenuvsi od prvog fajla - kombinacije bita po redu - onog sa svim nulama, prvi koji dobija bar 1 jedinicu tj. fajl sa svim nulama i 1 jedinicom, a vazi i obrnuto fajl sa svim jedinicama koji sadrzi bar 1 nulu krecuci se unazad kroz moguca stanja brojaca od zadnjeg tj. fajla sa svim jedinicama ka prvom, sto Shanon nije posebno naglasio ali smatram da se podrazumeva). Za skladistenje podataka mislim (smatram :) da vazi bas naprotiv tj. tacnije da fajl sastavljen samo od nula ili samo od jedinica ima manju entropiju od fajla koji sadrzi bar 1 jedinicu (ili vise, tj. bar 1 nulu ili vise, tj. razlicite bite po znaku) jer inace ako bi doslovno shvatili Shanona ispalo bi da fajl sastavljen samo od nula recimo ima negativnu entropiju? (sto je nemoguce, tj. naravno da je moguce ako se tako definise ali vazi samo za prenos informacija ali ne i za skladistenje). Posebna prica bi bila o tome sto Shanona kao da je zanimala samo entropija izvora signala ali ne i samog signala kao da se to moze razdvojiti sto je opet bilo uslovljeno onim cime se bavio: prenosom signala najvise.

Izvinjavam se zbog lose sredjenih citata, samo sam prekopirao iz teksta "Matematicka teorija Informacija" od C.E.Shanona, stvarno ne umem bolje da sredim ako neko moze da nadje ova dva citata i da ih postavi ovde u sredjenom obliku bio bih veoma zahvalan.

Ono sto me je svojevremeno pomalo zabrinulo je:

This compression contest is motivated by the fact that being able to compress well is closely related to acting intelligently, thus reducing the slippery concept of intelligence to hard file size numbers. In order to compress data, one has to find regularities in them, which is intrinsically difficult (many researchers live from analyzing data and finding compact models). So compressors beating the current "dumb" compressors need to be smart(er). Since the prize wants to stimulate developing "universally" smart compressors, we need a "universal" corpus of data. Arguably the online encyclopedia Wikipedia is a good snapshot of the Human World Knowledge. So the ultimate compressor of it should "understand" all human knowledge, i.e. be really smart. enwik8 is a hopefully representative 100MB extract from Wikipedia.

Nisam ni znao da se bavim ovako vaznim stvarima, kompresor bi trebao (mogao) "da razume sve ljudsko znanje"? a negde sam nacuo (od Dilana :) da je "inteligencija bez ljubavi demonska", pa tako, ono jes da se nisu pretrgli sa nagradom za tako sofisticiran kompresor (150e) ali ako stvarno uz pomoc njega moze da se pronadje "kamen mudrosti" kome bi jos trebala bilo kakva nagrada osim toga?

Uzdravlje! I budite mi dobri!

---

Tebe to još drži?

hahahahahhahahha

MajorFatal postao si moj idol :D.

---

1.) 000 -> 0
2.) 001 -> 1
3.) 010 -> 00
4.) 011 -> 01
5.) 100 -> 10
6.) 101 -> 11
7.) 110 -> 0 1
8.) 111 -> 1 0

Za svih 8. razlicitih kombinacija 8. drugih razlicitih kombinacija bita koje su krace od originalnih: poslednje 2 su krace po broju bita koji su upotrebljeni.

---

Kako se dekomprimuje 00? Kao 000000 ili kao 010?

---

E Nedeljko, stalno pokvaris nesto To su detalji, ispeglace on to tokom kodiranja

---

Kao 010. 000000 bi bilo 0 0

---

Jal me zezate jal ne razumem? Nedeljko gde si iskopao tu kombinaciju sa 6 nula? Nema je navedene u prethodnom postu? Shadoved, hvala za podsecanje/sugestiju postoje jos i 0 0 i 1 1 sto znaci da ima i viska kombinacija sto znaci da je moguca kompresija. Svestan sam naravno da je za sada jedini moguci engine papir ili elektronski papir tj. da 1 bit tesko da moze biti racunan kao fajl u bilo kom fajl sistemu ali zato dok ispregledam sve aktuelne fajl sisteme mozda i nadjem neki odgovarajuci.
Ok, tek sad kontam, Nedeljko, da li sugerises da su mi za poslednje dve kombinacije potrebni i heder i futer da bi ono bili fajlovi? Znam to, osim ako postoji neki fajl sistem gde bi fajlovi bili jednoznacno odredjeni cak i ako imaju samo heder recimo a da engine prepoznaje kraj fajla po sadrzaju samog fajla, ili u nekoj hardverskoj izvedbi to ne bi bio neophodan uslov.
Ja bih ipak sa 0 0 i 1 1 kodirao prva sledeca 2 (po velicini/duzini) fajla tj. 0000 i 0001, tako da svih 8 kombinacija duzine 3 i jos 2 kombinacije duzine 4 na samo 3 bitna mesta.
Ako zezate, nemojte, bitno mi je ovo ;)

---