Random access u kompresovanom fajlu

Problem je sledeci:
Poveci fajl je zapakovan na neki nacin (svejedno koji), meni iz njega treba s vremena na vreme da izvucem po jedan podatak. Broj tih podataka u fajlu je oko 300 000, a fajl je sortiran i binarno mogu da ga pretrazim i skocim na mesto de se nalazi podatak potreban u tom trenutku, onda taj podatak iscitam i to je to... Kada pomocu zliba (gzlib) spakujem podatke, dobijem oko 100 puta sporije citanje jednog podatka u poredjenju sa jednostavnim citanjem pomocu fstreama. Brzina citanja izgleda da ne ovisi o stepenu kompresije (koji se lako menja). Samo da napomenem da sam ID-jeve podataka strpao u drugi fajl, pa pretragu vrsim na tom nezapakovanom fajlu koji se sastoji samo od intidzera.
Samo citanje jednog podatka je prema mojim merenjima 100X sporije. Meni je ovo usporenje neprihvatljivo, a stepen kompresije mi je skoro nebitan (ipak mora da bude nesto manji od originala, ali recimo da se radi o desetak posto), kao i brzina pakovanja / raspakivanja (koja apsolutno ne igra nikakvu ulogu).
Jedina stvar koja mi jeste bitna je brzina pristupa jednom podatku u tom fajlu i nisam ogranicen izborom biblioteke (sve sto radi posao je OK, cena nije problem...).
Predlozi, saveti, sugestije?

Potpis

De si Deda...

Ovako na brzinu bih predlozio sledece - Podeli podatke u blokove, od po npr 4kb ili vec koliko ti odgovara, pa te blokove pakuj i sacuvaj u fajlu. Napravi indeks koji pokazuje koji opseg podataka se nalazi u kom bloku. Prilikom pretrage, u indeksu vidis gde se nalazi podatak, raspakujes samo taj blok i izvuces ga.

Da, to je veoma pametno resenje. Da li mozda znas za neku biblioteku koja ce makar delimicno automatizovati ovaj proces? Pokusavao sam sa gzip-om, ali ne mogu bas provaliti kako da izvedem ovo. Pokusacu jos par ideja koje mi padaju napamet, a ako neko ima iskustva sa slicnim problemom, neka se ne libi da uleti sa bilo kakvim savetom, sve je dobrodoslo :)
Kada (ako) napravim ovo, ostavicu kod ovde ako nekome zatreba, jer sam ustanovio da je za ovaj problem jako tesko naci resenje na internetu. Svima je izgleda ideja da raspakuju ceo fajl, pa da ga onda koriste. Cak i ove funkcije koje sluze za random access ustvari rade tako sto otpakuju ceo fajl do trazenog bajta, pa izvade podatak, pa vrate sve kako je i bilo.

Potpis

De si Deda...

A da li podaci bash moraju da budu u komprimovanom fajlu? Cini mi se da bi to mnogo lakse islo sa jednom sqlite bazicom koja je veoma brza. Ali naravno ja ne znam ono sto ti znas pa je moguce da ovo sto sam rekao nema nikakvog smisla

Potpis

Tko leti vrijedi

Krenuo sam sa sqlite bazom. Bilo mi je presporo. Sad mi je preveliko. Ne moze mi covek udovoljiti :)

Potpis

De si Deda...

Presporo?? Bas cudno... sqlite je prilicno brz, no pitanje je sta su ti ciljevi i koliko zelis da patis razvijajuci to.

Jesi li probao NexusDB? http://www.nexusdb.com/ Embedded verzija je free.

Potpis

Tko leti vrijedi

Ne znam, ali blokovska obrada podataka iz fajla je prilicno standardan pristup. Umesto da citas 20 ili 30 bajtova jednog zapisa iz fajla, ti ucitas blok, pa iz bloka izvuces to sta ti treba. I samo citanje sa diska koje obavlja operativni sistem je ovako odradjeno. Trebalo bi da postoji neka ovakva biblioteka. Mozda treba ponovo da potrazis.
Ovo ne bi trebalo da bude previse tesko za pisanje. Za konkretnije detalje implementacije bih morao znati da li podatke menjas ili samo citas iz ovog fajla.

What he said. :)

Imam skoro istu situaciju i resavam je bas tako kako je obucina predlozio. Za samu kompresiju/dekompresiju koristim http://www.zlib.net/ (free, standardan, testiran, brz, implementacije na raznim platformama, etc).
Sto manje blokove uzmes - to ce ti kompresija biti losija ali ces i imati i manje 'viska' tokom svake dekompresije.
Mozes i da napravis jedan pocetni dictionary za sve blokove (ili vise njih ako grupises blokove po slicnosti podataka) da dodatno optimizujes nivo kompresije.

Potpuno se slazem ... Ako su performanse citanja fajlova jako zahtevne(npr. indeksiranje tih "300000" video fajlova i frameova u real-time ...itd) ne verujem da ces naci besplatno i automatizovano resenje za instant upotrebu vec da zasuces rukave ako ce to na kraju da se isplati ...
Sqlite je dosta brz ...uostalom ne bi ga google toliko sponzorisao.(Mozzila, Firefox,Symbiam...itd)

Potpis

Viva lollapalooza

Tip podataka koji cuvam u fajlu je struktura koja opisuje jednu tacku i njene sukcesore. Radi se o pathfinderu, a meni treba da vadim jedan po jedan takav Junction u zavisnosti od toga gde me put vodi. Zato mi je bitno da citanje jednog podatka bude sto brze, jer u slucajevima jako dugog puta ponekad vadim i hiljade komada bez unapred odredjenog redosleda. Sve je indeksirano unapred (npr. Svi su poredjani po ID komponenti, po kojoj se i traze u fajlu, pa mogu da ih trazim i binarno, a cak sam i to ubrzao tako sto sam napravio nezapakovan fajl u kome cuvam te IDjeve u istom redosledu, pa trazenje obavljam tu - na kraju samo iz fajla procitam podatak na datom mestu). Opet ponavljam - ne mora nista biti besplatno, a ne mora biti ni skroz automatizovano. SQLite3 sam dugo koristio (sa wrapperom CppSQLite3), ali mi se pokazalo presporim za neke druge stvari, pogotovo grafiku, jer u istoj bazi imam i sve ulice Srbije, Crne Gore i Bosne (ali bas sve), pa kada pokusam da procitam ulice koje su mi u ekranu u tom trenutku, moram proci kroz tabelu od 300 000 segmenata. To je uzasno koliko je sporo, pa sam se odlucio da napravim fajlove u kojima sam sortirao ulice po kvadrantima u kojima se nalaze. Mozda bi ovo mogao i sa SQLite-om, ali sam pretpostavio da bi bio problem imati desetine hiljada tabela (za svajki kvadrat po jednu). Ako bih nekako drugacije organizovao podatke, opet nailazim na problem da postavim upit tipa: daj mi sve kojima je x izmedju x1 i x2 i y izmedju y1 i y2.
Na kraju sam zavrsio sa gomilom fajlova specijalizovanih za po jedan zadatak i sve je bilo OK, dok nije ispalo da mi ukupni podaci zauzimaju oko 300 MB, a treba da stanu na karticu od 256. Zato kazem da mi stepen kompresije nije toliko bitan, ali mora da postoji.



Shvatam ja da je obucinin predlog dobar, ali postavljaju se sledeci problemi:
-Meni su svi podaci u fajlu jednake velicine, kada zapakujem komad po komad onda vise nisu jednake velicine i kako da ih opet izjednacim. Na kraju je potrebno da podatak u fajlu trazim tako sto kazem seekg(redniBroj * velicinaJednogPodatka). Ili ima neki drugi nacin koji je meni nepoznat?
-dictionary je kod zliba pomenut informativno. Googlanje me uvek vodi na iste prepisane stranice i nikako ne mogu ustanoviti sta je to uopste. Moze li neki link ili nacin upotrebe ove opcije, jer sam vec ranije pomislio da bi me kontanje toga dovelo do resenja?
- zlib u svim primerima pokazuje otpakivanje celog fajla. Ne sumnjam da se ovo pakovanje komad po komad moze obaviti, ali nigde nisam nasao kako. Cak i shvatam kako bih to odradio, ali ostaje problem zaokruzivanja velicina da budu iste. Pretpostavljam da se moze uzeti jedan podatak, zapakovati, pa smestiti u obican fajl kao binarni podatak i prilikom citanja sve izvesti suprotno. Voleo bih da negde vidim primer toga, jer kad pokusam da izvedem ovo, na kraju zavrsim sa gomilom besmislenih bajtova.

Potpis

De si Deda...

Meni se i dalje cini da bi bilo uputnije potrositi vreme na dizajn adekvatne baze podataka nego na upotrebu zlib biblioteke. Mozda mozemo da pripomognemo u ovom slucaju. Imas li neku shemu baze vec uradjenu pa da krenemo od toga?

Potpis

Tko leti vrijedi

Mislim da je njegova stvar previse low-level da bi neka standardna baza podataka mogla to da podrzi. Mislim, ta baza ce ionako biti jos jedan layer iznad neke zlib-like kompresije (ako ne bas i njega) - ako uopste ima kompresiju.
Doduse nisam se odavno bavio time pa mi ne zameri ako je memory overhead baze zanemarljivo mali. Vredi probati? :)



1.) Pakujes blok-po-blok jednake velicine, a output ti je u vidu odvojenih fajlova. Kolika je velicina zapakovanih blokova ti nije bitna.
2.) Kad hoces da dobijes podatke o nekoj tacki, pronadjes u kom bloku je, otpakujes ceo blok i procitas tacku.
3.) Onda napravis caching tako da u svakom trenutku mozes imati n otpakovanih blokova (kolko vec stane u ostatak memorije) tako da ako su uzastopne tacke u istim blokovima ne moras da ih opet otpakujes.

Ako ti sama blok-by-blok kompresija radi posao dovoljno da spakujes sve u 256 - ignorisi custom dictionary - ne znam da ti kazem kako tacno to da uradis, to mi samo stoji u todo listi za neku slicnu stvar koju sam radio, ali jos nisam odradio :)

ps, da li mozes tvoje podatke kompresovati na neki drugi nacin?
Sta tacno ti sadrzi tacka, i sta su tacno 'sukcesori'? Indexi na druge tacke? Koliko tacaka imas sve zajedno? Kako su grupisane?

Naravno ...
jer ako kazes da ti je pod sqlite-om sporo radilo ne znaci da je spor nego je mozda los relacioni model baze koji je za ovakvu vrstu slucaja inace potrebno.
Sigurno da postoji sansa da se negde upiti optimizuju kao i relacije izmedju takvih tabela,pa da se postave indexi kolko god je to moguce ...
Ideja celog tvog projekta je interesantna , tako da podrzavam ideju kiklopa .

Potpis

Viva lollapalooza

Hteo bih jos da se nadovezem na prethodni post .
Sa optimizacijom sqlite-a ces mozda dobiti i do 30% poboljsanja ..



Za ovu pricu bi ti trebao napredniji model algoritma za ponalazenje "suksesora" tj. susednih tacaka koje cine putanju .
Cilj bi bio predikcija sukcesora tj. predvidjanje sledecih tacaka tako da ne treba da vadis jedan po jedan "Junction" i uz koriscenje dvostruko povezanh lista (putanje mogu da imaju 2 smera))
i STL biblioteke mozda ces dobiti poboljsane performanse ....

Malo sam googlao pa sam naleteo na resenje koje MS nudi sa svojim SQL2005
Data Mining model: http://technet.microsoft.com/en-us/library/aa964125.aspx



Da li si probao da u jednu tabelu stavljas vise kvadrata (mislim da je baza ogranicena na neki veliki broj tabela )
i da uz pomocu gore pomenutog algoritma zadas neki upit za dobijanje y(putanja)=f(x1,x2)

Potpis

Viva lollapalooza

Uf... vidim ja da sam vas vise zbunio objasnjavanjem moje "baze" nego sto sam pojasnio. Evo sta ja u stvari imam kao podatak:


Fajl je niz Junctiona. Svaki Junction ima odredjeni broj JuncPtr-ova koji su mu successori. To znaci da se iz njega moze otici na njih, a nikako ne vazi obrnuto. Posto su Juctioni poredjani po ID-ju, ja ih iz programa zatrazim funkcijom
Junction getJunction(int ID);
Kada ga dobijem, pathfinding deo nastavlja da se brine o tome koji successor je pogodniji za nastavljanje puta, a onda se pomocu successorovog ID-ja opet postavi upit za trazenje Junctiona i tako dok jedan od njih nema ID cilja. U pitanju je A* pretrazivanje, ali to nema previse veze sa nasom temom (ali kad vec objasnjavam...).
Ako se pitate zasto sam ovako slozio podatke, odgovor lezi u brzini. Imam u drugim tabelama spisak segmenata koji imaju po dva Junctiona na krajevima, pa se i iz toga moze zakljuciti odakle - dokle postoji put. Ovo je sumanuto sporo, pa sam sve stvari koje se mogu izracunati unapred vec izracunao, da bih u real time-u samo skakutao po fajlu.
Iz gore navedenog se moze zakljuciti da je meni dosta prostora otislo u prazno, jer nema svaki Junction 8 successora, niti svaki successor ima 8 forbidden IDjeva (to su ID-jevi iz kojih je zabranjeno skrenuti). Meni velicina tog fajla ne znaci previse, jer ga i najmanji stepen kompresije smanji za vise od pola usled ovakve gomile nula koje se nalaze u njemu. Jedina stvar koja me interesuje je brzina pristupa jednom elementu.

Ako i dalje postoji jaka struja koja zagovara upotrebu baze u ovom slucaju, iznecu i bazu ovde, nije nikakav problem.

A citajuci vase komentare, pala mi je jedna ideja na pamet:
Jedan po jedan podatak pakujem u memoriji (koristeci zlib). Onda pogledam koliko bajta tezi konkretan spakovan podatak, pa u jedan drugi fajl pisem redni broj i tacnu poziciju i velicinu u bajtovima u spakovanom fajlu (kada kazem spakovanom fajlu, mislim na obican fajl sa spakovanim podacima). Posle se pretraga vrsi po fajlu koji sadrzi indekse i mesta na kojima pocinje i zavrsava trazeni zapakovani podatak i eto ga super brzo citanje.
Sta mislite?

Potpis

De si Deda...

Ne zagovaram "baznu struju" nego onu koja radi posao :)
Ako ne gresim tvoj malo uprosceni algoritam kolko sam shvatio izgleda ovako :

1 uneti pocetnu i krajnju tacku (x1 i x2) tj. zadaj query
2 otvori fajl i nadji blok za tacku tj. Junction strukturu ... X(n) ,X(n+1) ...
3 smesti blok u memoriju i raspakovati ga zlib-om ili cime god ...
4 izvaditi podatak iz raspakovanog bloka
5 staviti nadjeni podatak (ID ili koordinate ) i smestiti ga u listu tacaka putanje
6 proveri da li je nadjena tacka jednaka x2 ako nije onda ->
7 goto 2

Cini mi se da jedan veliki problem koji ovde nazirem je update blokova u odredjenim fajlovima
tj da li imas na umu da ce ti blokovi tj. Junction-i (JuncPtr successor[8];) da se menjaju tj. da dodajes nove putanje ili su samo read-only ?
U svakom slucaju razvijas sopstveni dbms za koji ce ti trebati dosta vremena da ga usavrsis a vec mozda postoje gotova resenja ...
Mozda ne bi bilo lose da probas da iskoristis i jedno i drugo .
Tvoj db sistem u sprezi sa sqlite-om koji bi mozda keshirao rezultate pretrage ili bi posle olaksao nalazenje najkrace putanje u narednim query-ijima


Happy coding !!!

Potpis

Viva lollapalooza

Ja sam veoma low level u ovoj prici, jer mi je mala i memorija i storage i slab mi je procesor i mnogo je podataka (WinCE).
Ceo fajl koji pravim ce biti read only. To je realna mapa sa realnim ulicama, moj softver je cita i kada ti uneses putanju (npr. Od ulice Petra Petrovica u Uzicu do Srpskih vladara u Beogradu) on vidi koji su to Junctioni i onda nadje putanju medju njima. Nacin na koji trazi putanju je prilicno standardan za mnoge oblasti (posebno igre). Ovako bi izgledao precizniji opis algoritma:
1) Imam pocetni i krajnji ID
2) aktivniID = pocetniID
3) izvadi iz baze Junction koji ima isti ID kao i aktivniID
4) izdvoji sve successore aktivnog ID-ja i odredi kojim redom (u odnosu na prioritet i duzinu) se nastavlja putanja
5) ID successora koji je najpogodniji za nastavak puta dobija status aktivnogID-ja i ide se na tacku 3)

Ono sto nije standardno je da sam kompletnu matematiku vec ubacio u "bazu" (duzina, ID segmenta koji je izmedju dva Junctiona, prioritet, od kog parenta postoji zabrana...)
Ne postoji update nikada, ta mapa se samo jednom pakuje, a korisnici sve dobijaju na PNA uredjaju integrisano sa softverom. Sve je vec testirano i radi, a meni ostaje samo da resim jos par problema kao sto je ovo prokleto pakovanje.
Inace, i meni je padalo na pamet resenje sa kombinacijom sqlite-a i mojih specijalnih fajlova, ali to bi zahtevalo jos dosta testiranja. Nekakav sopstveni sistem sam vec napravio i dokazao da moze da radi real time i to radi dobro. Sada sam zapeo na smanjenju velicine fajlova, pa bi mi najdraze resenje bilo ono koje ne zahteva dvonedeljni rad (sefovi vec skacu po glavi, jer razvoj komplet softvera traje vec 10 meseci, a planirano je 6. Doduse, oni su krivi za otezanja, ali je i nervoza jasna jer ne dobijaju ni dinara dok ceo paket ne krene da se prodaje). S druge strane, ako sam pogresio u nekim osnovnim konceptima, i dalje nije kasno za promenu, pa sam otvoren za apsolutno svaki savet koji date. I naravno, takodje sam i zahvalan za isti...

Potpis

De si Deda...

El mozes mozda da probas nesto jednostavno tipa optimizujes podatke u strukturi i/ili ih zapakujes tako da se otpakuju tokom samog procesiranja? Nisam stigao da se udubim u sve sto si napisao, ali pojasni mi par stvari:

Zasto imas JuncPtr i Junction kao odvojene tipove? Sta predstavljaju ID, segmentID, length, frc, fow, xpos, ypos i forbidden[8]?
Sta ti znaci successor? Da li je to nod na koji mozes da ides - da li je to drugi Junction?

Mozda je moguce reorganizovati podatke tako da se izbace viskovi i da se koriste manji tipovi (tipa, ako imas manje od 65k ID-ova ili segmentID-ova, onda mozes koristiti unsigned short umesto int-a).

Svakako da je moguce reorganizovati podatke tako da sve bude nesto manje. Te detalje ostavljam za sam kraj. unsigned short nece raditi posao jer ih samo u Srbiji imam 190 000., a posebno ne mogu garantovati za ubuduce. Za sada se radi o odredjenom broju ulica, ali vec je u planu da se ubacuju mape Madjarske, Makedonije, Hrvatske... Cak nisam siguran da ce u nekoj daljoj buducnosti i int biti dovoljan. Zato izbegavam ovaj tip optimizacije, jer se bojim da mi povecava kolicinu rada na apdejtima programa.
Opis atributa:

successor je nesto na sta mozes otici iz datog Junctiona. On ima svoj ID i negde drugde je opisan kao Junction sa svojim successorima. Kada se gleda situacija u kojoj je on samo successor nekom Junctionu, onda je u njemu opisana putanja izmedju njih.

ID = jedinstvani ID Junctiona. Sluzi da bi se kasnije mogao naci u bazi kao Junction, i da se vide njegovi successori.

segmentID = Svaka dva Junctiona su povezana segmentom. Taj segment je opisan u nekoj drugoj tabeli (fajlu) i tamo imamo razne parametre koji ga konkretnije opisuju. Ovde stoje samo one osobine koje nas zanimaju za pathfinding. Osobine koje omogucavaju crtanje segmenta nas ovde ne zanimaju.

frc, fow = Ovo su osobine tog segmenta koji povezuje te dve tacke. frc i fow su standardizovane velicine i jedna opisuje prioritet puta, a druga tip puta (frc = 1 za autoput, frc = 2 za put sa dve trake fow = 4 za ukljucenje na autoput...)

xpos i ypos = pozicije te tacke u realnom prostoru. Imamo xpos za Junction, i xpos za successor. Ovi podaci nam sluze zbog heuristike, jer se gleda priblizavanje ciljnom Junctinu kada se odlucuje kojim putem se nastavlja.
length - duzinu segmenta koji spaja dve tacke ne mozemo dobiti prostim povlacenjem linije izmedju (xpos, xpos) i successorovih (xpos, ypos) zato sto se moze raditi o krivoj liniji. Ovde je sacuvan jedini podatak koji nas o toj krivoj liniji zanima, a to je njena duzina. Koristi se da bi se dobila cena kostanja putovanja po datom segmentu (uzima se u obzir frc, fow i length, pa u zavisnosti od izbora vozila dobijamo cost).

forbidden = postoje skretanja koja su fizicki moguca, ali su zabranjena. Ja te situacije opisujem tako sto vidim koje tri tacke (Junctiona) obrazuju trojku kojom ne sme da se ide. Zamisli raskrsnicu Kneza MIlosa i Bulevara. Ti mozes ici od te raskrsnice prema Zvezdari ako dolazis iz jednog pravce, ali ne smes ako dolazis od Takvuda. To opisujem tako sto na u forbiddene upisem ID Junctiona iz koga je nemoguce skrenuti u dati segment.

P.S. Sada se bacam na pravljenje pakovanja kakvo sam opisao u prethodnom postu. Nakon toga cu baciti kod ovde, pa ako neko bude imao savet, primedbu ili kritiku bicu zahvalan za istu.

Potpis

De si Deda...

Ne rece mi zasto koristis JuncPtr? Cini mi se kao da su neki podaci duplicirani. Jedan Junction ti je skoro pola kilobajta, a cini se da je mnogo stvari suvisno.
Zasto ulagati resurse u sistem za kompresiju/dekompresiju ako prostom reorganizacijom mozda mozes smanjiti koriscenje memorije par puta i na kraju imati bolje rezultate nego sa kompresijom?