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 za***ana. 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 ;)