Datova komprese

Samostatné vypracování náročnějšího programu v libovolném programovacím jazyce (obvykle v jazyce C++) a příslušné vývojové a uživatelské dokumentace jako završení výuky individuálního programování. Tento program se může stát základem pro individuální projekt požadovaný k bakalářské zkoušce z informatiky. Zápočet bude udělen za vypracování detailní specifikace a předvedení rozpracované verze díla.
Uživatelský avatar
Eubie
Matfyz(ák|ačka) level III
Příspěvky: 295
Registrován: 8. 10. 2005 15:35
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Datova komprese

Příspěvek od Eubie »

Milí spoužáci,
v rámci mého ročníkového projektu se potýkám s menším problém(k)em. Algoritmy, které můj RP používá vyžadují uložení řádově 5000 (délka signatur) x 500 000 (velikost slovníku) floatů, tedy 2.5mld floatů. Float má 32 potažmo 64bitů (a to bohužel i na cílovém serveru, kde to reálně poběží), což dává pěkných 10, resp. 20GB.

Pravděpodobně jediný stroj ÚFALu, který měl 32GB RAM se mi podařilo odpravit a tak zbývají jen ty 10GB stroje. Velikost signatur (první činitel), by bylo dobré moct co nejvíc zvyšovat, ale kvůli malé paměti se to nedá, protože například při délce signatur 8K je už potřeba 4mld floatů a to už je 32GB paměti. Potřeboval bych tedy poradit, jak to pokud možno zkomprimovat, myslím ty floaty v paměti. Ukládat ty floaty na disk je zcela nepřijatelné řešení, neboť pokud by tomu tak bylo, pak by se za běh programu několiksettisíckrát až několikmilionkrát četlo z disku těch několik GB floatů a to by trvalo opravdu dlouho.

A kde že je vlastnost, která podle mě dovoluje komprimaci? Všechny floaty jsou z N(0,1) (což není interval [0,1]...) tedy jsou hodně malý (vztaženo k MAX_FLOAT), dá se ošetřit, že žádný z nich neni větší než třeba 10 (nebo jakákoliv jiná konstanta blízká jedničce - zase blízká vůči MAX_FLOAT). Takže nacpat do jednoho floatu dvě čísla tak, že první vynásobim třeba číslem 10mld a druhý k tomu přičtu, se jeví jako první varianta, ale to je komprimace se ziskem jen 100%. Nemá někdo nějakej nápad, jak by to šlo ještě víc?
Díky
krystof
Matfyz(ák|ačka) level III
Příspěvky: 186
Registrován: 18. 1. 2005 15:15
Typ studia: Informatika Mgr.
Bydliště: Brno / 17. Listopad
Kontaktovat uživatele:

Re: Datova komprese

Příspěvek od krystof »

Hmmm, no to asi zavisi dost na tom, jak ty gb floatu pouzivas - jestli je treba mozny to mit na disku a balik dat zpracovat nejdriv podle prvnich 100000 signatur, pak podle dalsich a tak dal...
Anebo to treba nejak paralelizovat - budes mit dvacet pocitacu v labu po 2gb pameti a hned mas 40gb a navic by to jeste mohlo byt i rychlejsi
No a treba taky zalezi na tom, jakou presnost u tech signatur potrebujes a udelat nejakou ztratovou kompresi - o tom moc nevim ale treba fft na tech 5000 cisel a u nejakych koeficientu treba snizit presnost...
Uživatelský avatar
Eubie
Matfyz(ák|ačka) level III
Příspěvky: 295
Registrován: 8. 10. 2005 15:35
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Příspěvek od Eubie »

Ahoj Kryštofe,
je to přesně jak řikáš, strašně to závisí na tom, jak se ty floaty používají. Nakonec mě řešení napadlo ještě večer, ale řikal jsem si, co kdyby někoho napadlo ještě nějaký lepší, raděj počkám. Nakonec jsem to vyřešil tak, si všechny ty gigabajty nageneruju na disk, ale procházím to chytře, takže za celej běh programu se ty gigabajty projdou všehovšudy jen dvakrát, jednou při tvorbě a podruhé při jediným čtení. Sice to je dost pomalý (načíst do paměti giga dat je pomalejší než jsem si myslel), ale rychleji to asi nejde a je takhle možný s dost velkým diskem vytvářet libovolně dlouhé signatury.
Díky za odpověď.
krystof
Matfyz(ák|ačka) level III
Příspěvky: 186
Registrován: 18. 1. 2005 15:15
Typ studia: Informatika Mgr.
Bydliště: Brno / 17. Listopad
Kontaktovat uživatele:

Příspěvek od krystof »

Eubie píše:(načíst do paměti giga dat je pomalejší než jsem si myslel
heh no presne na tohle - cteni velkych souvislych kusu dat - je imho vhodny raid0. Pri takovyhle operacich jsou dva disky opravdu prakticky dvakrat rychlejsi nez jeden, (a rek bych ze je levnejsi koupit jeden novy disk nez 2gb ram:))
Uživatelský avatar
Eubie
Matfyz(ák|ačka) level III
Příspěvky: 295
Registrován: 8. 10. 2005 15:35
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Příspěvek od Eubie »

No v mým případě, by těch GB ram bylo potřeba opravdu hodně, tak sto:) Ale RAID0 si nemůžu dovolit, běží to vše na serverech MFF, snad tam maj aspoň SCSI.
Uživatelský avatar
Dawe
Supermatfyz(ák|ačka)
Příspěvky: 360
Registrován: 12. 10. 2004 12:32
Typ studia: Informatika Mgr.
Bydliště: Doma a nebo na koleji

Příspěvek od Dawe »

Třeba už ti to je k ničemu a třeba to je blbost, ale jestli nepotřebuješ tak velkou přesnost jakou poskytuje float, co třeba to cpát do longu a přenásobovat to? Když víš že je to mezi 0 a 1, mělo by to celkem dobře jít...
Uživatelský avatar
Eubie
Matfyz(ák|ačka) level III
Příspěvky: 295
Registrován: 8. 10. 2005 15:35
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Příspěvek od Eubie »

Ahoj Dawe,
už jsem to naimplementoval jak jsem řikal, s tim diskem. To řešení, který popisuješ, je pokud se nepletu to, který sem myslel hned v prvním postu na toto téma. Jeho nevýhoda ale je, že tim získáš jenom několikanásobek paměti a to "několika" je docela malý (2, 3..), zatímco s dost velkym diskem si můžu tu paměť natáhnout mnohem víckrát ( za cenu času.. ), což je rozhodující.
Naimplementoval sem, jak sem řikal, to řešení s diskem a potom sem si řikal, že pokud ty velikánský soubory budu psát a číst komprimovaně, bude to míň místa a bude to rychlejší. První věc se potvrdila, úspora místa je asi 75%, ale čtení i zápis do komprimovanýho souboru je POMALEJŠÍ a to výrazně. Nemá někdo páru proč? Používám knihovnu zlib, která kombinuje LZ77 a Huffmanovo kódování. Ani jedna z těchhle metod by neměla bejt závislá na velikosti zpracovávanýho souboru ( na čemž třeba závisejí nějaký slovníkový metody, kde roste slovník nade všechny meze, pokud se proti tomu nezakročí ) a přesto to zakomprimování a odkomprimování dat zabere víc času než ty přečtení nekompřimovaných dat z disku (a to mi moc nejde do hlavy).
Uživatelský avatar
twoflower
Supermatfyz(ák|ačka)
Příspěvky: 445
Registrován: 22. 9. 2004 21:07
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Příspěvek od twoflower »

Jakeho pouzivas Huffmana? Statickeho nebo adaptivniho?
Uživatelský avatar
Eubie
Matfyz(ák|ačka) level III
Příspěvky: 295
Registrován: 8. 10. 2005 15:35
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Příspěvek od Eubie »

Já ne, to zlib:) Není řečeno. Asi adaptivní, neboť pokud by to bylo statický, bylo by nejdřív potřeba znát počet výskytů všech bytů a to by znamenalo jedno čtení navíc.

Navíc nevim, co se přesně indexuje, jestli jen byty, nebo sekvence bytů. Pokud to druhý, asi by to byla odpověď na otázku, proč to tak trvá - Huffmanův strom by byl prostě příliš velkej.
Odpovědět

Zpět na „PRG033 Ročníkový projekt - specifikace“