Diskuze: Machr na algoritmy - Komprese

Java Java Machr na algoritmy - Komprese

Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

Ahoj programátoři, v pravidelné minisoutěži na tento týden budeme programovat kompresní algoritmus. Program si na vstupu vyžádá soubor a ten zkomprimuje vaším algoritmem tak, aby měl menší velikost. Zkomprimovaný soubor půjde také rozbalit do původní podoby. Opět platí, že to nemusí být dokonalé, hlavní je, aby to fungovalo a zkusili jste si něco nového. Algoritmus zkusím na několika různých souborech a výsledky zprůměruji. Autor nejefektivnějšího algoritmu (který zmenšil soubor nejvíce) získává placku a samolepky. Můžete použít libovolný jazyk, archivace pár kb by neměla trvat minuty :)

Deadline se dáme výjimečně v pondělí 11.11. v 18:00.

Odpovědět  +1 5.11.2013 9:48
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na David Čápka
Luboš Běhounek (Satik):

Musí ta komprese bejt univerzální?
Že bych poslal svoji kompresi videa :D

Btw předpokládám, že žádné knihovní kompresní fce/třídy se používat nesmějí (např. v C# DeflateStream, GZipStream, ZipArchive apod.).

Editováno 5.11.2013 10:48
Nahoru Odpovědět  +2 5.11.2013 10:45
:)
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Luboš Běhounek (Satik)
David Čápka:

Jo, měla by zkomprimovat cokoli. Hotová řešení samozřejmě ne :P

Nahoru Odpovědět  +1 5.11.2013 10:55
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Nahoru Odpovědět  -2 5.11.2013 14:37
Časem je vše možné.
Avatar
Kit
Redaktor
Avatar
Odpovídá na Jakub Lásko[Saarix]
Kit:

To bys pak nebyl "machr na algoritmy", ale "machr na používání hotových algoritmů". Tato soutěž je podle mne spíš o tom, zda takový algoritmus dokážeme vymyslet.

Nahoru Odpovědět  +6 5.11.2013 15:45
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Odpovídá na Kit
Jakub Lásko[Saarix]:

Pravda no budu se muset zamyslet.

Nahoru Odpovědět 5.11.2013 16:06
Časem je vše možné.
Avatar
Odpovídá na Kit
Luboš Běhounek (Satik):

Tak ono by třeba mohl komprese kombinovat, u toho svého videokodeku taky používám asi 3 různé kompresní funkce a pak to ještě ukládám do zipu přes .NET funkce.

Nahoru Odpovědět  +1 5.11.2013 16:53
:)
Avatar
Silvinios
Redaktor
Avatar
Odpovídá na Kit
Silvinios:

Obávám se, že v oblasti bezztrátové komprese toho už moc k vymýšlení není...
Podle mě jde spíš o to zkusit si naprogramovat několik známých algoritmů a ty pak šikovně zkombinovat tak, aby sdracovy testy vyšly příznivě.

 
Nahoru Odpovědět 5.11.2013 18:54
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Silvinios
David Čápka:

To není problém, hlavně je nepoužít hotové :)

Nahoru Odpovědět  +1 5.11.2013 18:59
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Ondřej Hanák
Redaktor
Avatar
Ondřej Hanák:

Končí se v pondělí ? To se musí zdokumentovat :D

 
Nahoru Odpovědět  +3 5.11.2013 19:16
Avatar
 
Nahoru Odpovědět  +2 5.11.2013 19:39
Avatar
David Čápka
Tým ITnetwork
Avatar
Nahoru Odpovědět 5.11.2013 19:42
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Neaktivní uživatel:

mozna to bylo predvidani 2012, majove se zpozdily o 11 mesicu :D
a tou velkou zmenou je David Čápkavo rozhodnuti xD

Nahoru Odpovědět  +2 5.11.2013 19:43
Neaktivní uživatelský účet
Avatar
Kit
Redaktor
Avatar
Odpovídá na David Čápka
Kit:

Chystáš jako odměnu Svatomartinské víno? :)

Nahoru Odpovědět  +2 5.11.2013 21:06
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Luboš Běhounek (Satik):

budete se nekdo ucastnit? :)

Nahoru Odpovědět 11.11.2013 14:27
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Michael Olšavský:

Díval jsem se na to, ale zmohl jsem se pouze na zkrácení několika písmen v řadě... Nechce se mi do delších řešení :-) Navíc to vypadá složitě a práce mám dostatek :-D Ty ano?

 
Nahoru Odpovědět 11.11.2013 16:26
Avatar
Luboš Běhounek (Satik):

Já mám RLE a slovníkovou kompresi (ale neměl jsem čas dodělat ke slovníku dekompresi) :)

https://www.dropbox.com/…zbtw/RLE.zip

Nahoru Odpovědět 11.11.2013 17:51
:)
Avatar
martinsakra
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
martinsakra:

já jsem poslal verzi RLE šel jsem po bytech, a nejvíc mi zabralo dekomprimovat soubor bez toho aniž bych ztratil cokoliv :D

Nahoru Odpovědět 11.11.2013 18:06
Democracy is two wolves and a lamb voting on what to have for lunch. Liberty is a well-armed lamb contesting the vote.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Luboš Běhounek (Satik)
David Čápka:

Nějak mi to nejde spustit, můžeš sem ještě hodit binárku?

Nahoru Odpovědět 11.11.2013 18:21
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

Ani jedním algoritmem se mi bohužel nepodařilo rozbalit následující obrázek: https://dl.dropboxusercontent.com/…/obrazek.bmp. Texťáky se zdá, že fungují. Čekám ještě na binárku od Satika.

Nahoru Odpovědět 11.11.2013 18:34
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
martinsakra
Redaktor
Avatar
Odpovídá na David Čápka
martinsakra:

zvláštní na bmp to moje fakt nefunguje, ale nevim čím to, jpg/png/doc/pdf jsem
zkoušel a fungují
a chybí mi tam jeden byte, někde se ztratil :D

Editováno 11.11.2013 18:53
Nahoru Odpovědět 11.11.2013 18:52
Democracy is two wolves and a lamb voting on what to have for lunch. Liberty is a well-armed lamb contesting the vote.
Avatar
Silvinios
Redaktor
Avatar
Odpovídá na David Čápka
Silvinios:

Máš pravdu, v programu mám bohužel chybu :(

Mimo soutěž posílám opravenou verzi:
http://leteckaposta.cz/131416025

 
Nahoru Odpovědět 11.11.2013 19:01
Avatar
martinsakra
Redaktor
Avatar
Odpovídá na Silvinios
martinsakra:

já evidentně taky,ale ani za boha ji nemůžu najít. Zkusmo jsem dal komprimovat i video wmv - a (i když komprimovaný soubor byl trochu větší) tak po rozbalení normálně funguje, všechno krom bmp

Nahoru Odpovědět 11.11.2013 19:24
Democracy is two wolves and a lamb voting on what to have for lunch. Liberty is a well-armed lamb contesting the vote.
Avatar
Odpovídá na David Čápka
Luboš Běhounek (Satik):

Binarku tam nemam, je to jen knihovna, v unittestu co u toho je si muzes kdyztak hodit na zkousku jmeno souboru, co chces zkusit zkomprimovat a ulozi to i ten zkomprimovanej, muzes pak porovnat velikost.

Spravnost kontroluje ten unittest - jede bajt po bajtu a porovnava puvodni a rozbaleny soubor.

Pokud by to bylo nutny, tak dopisu i aplikaci, co udela zabaleny a pak rozbaleny soubor :)

Jinak (univerzalni) RLE funguje pro bmp jen na odstiny sedi, u takovehohle bmp by bylo idealni komprimovat kazdy barevny kanal zvlast, pak by to dopadlo mnohem mnohem lip :)

Editováno 11.11.2013 19:36
Nahoru Odpovědět 11.11.2013 19:33
:)
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Luboš Běhounek (Satik)
David Čápka:

Hlavně že jsem psal do pravidel abyste je tam dávali, přeložit mi to nejde, jinak bych ti o ní nepsal :)

Nahoru Odpovědět 12.11.2013 11:10
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Silvinios
Redaktor
Avatar
Odpovídá na David Čápka
Silvinios:

Budou zveřejněny výsledky? Zajímalo by mě, jak úlohu řešili ostatní a jaké algoritmy byly použity.

 
Nahoru Odpovědět 12.11.2013 20:04
Avatar
coells
Redaktor
Avatar
coells:

Pro legraci přidávám ještě svoje řešení: http://leteckaposta.cz/226014235
Jedná se o jednoduchou variantu LZ modelu. Samozřejmě je to pomalé, protože rychlá implementace vyžaduje řadu triků, ale i tak funguje obstojně.

Pro kompresi obrázku uvedeného výše:
SimpleLZ 5 obrazek.bmp obrazek.lz
SimpleLZ d obrazek.lz obrazek.orig

 
Nahoru Odpovědět  +1 13.11.2013 19:42
Avatar
Silvinios
Redaktor
Avatar
Odpovídá na coells
Silvinios:

Dobrá práce! Já jsem se pokoušel o LZ-78 resp. LZW, ale tvůj LZ-77 dává mnohem lepší kompresní poměr.

 
Nahoru Odpovědět 14.11.2013 7:22
Avatar
coells
Redaktor
Avatar
Odpovídá na Silvinios
coells:

LZW obecně nedává příliš dobré výsledky, protože adaptace slovníku je pomalá. Některé varianty se to snaží upravovat, ať už více nebo méně úspěšně.

Různé varianty LZ77 se objevují asi ve všech lepších kompresorech (včetně 7-zip) z důvodů vysokého kompresního poměru. Nevýhodou je časová náročnost.

Jinak se používá aritmetické kódování kvůli rychlosti a kvalitní kompresi. Dnešní digitální obrázky a videa by ho už měla mít integrovaný, kdy se nahradil původní huffmanův strom a LZ.

 
Nahoru Odpovědět 14.11.2013 13:39
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Luboš Běhounek (Satik)
David Čápka:

Konečně jsem se znovu dostal k Satikovu výtvoru s použitím RLE, nyní již se zkompilovanou podobou. BMPčko mi zapakoval krásně, lorem impsum mu moc nešlo, ale co zabalil vždy i úspěšně rozbalil. Luboš Běhounek (Satik) tedy získává další placku, publikuj prosím aplikaci a napiš Míše jakou chceš :)

Nahoru Odpovědět 15.11.2013 16:09
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 30 zpráv z 30.