NOVINKA - Online rekvalifikační kurz Java programátor. Oblíbená a studenty ověřená rekvalifikace - nyní i online.
IT rekvalifikace s podporou uplatnění. Seniorní programátoři vydělávají až 160 000 Kč/měsíc a rekvalifikace je prvním krokem. Zjisti, jak na to!

Diskuze: Machr na algoritmy - Komprese

V předchozím kvízu, Online test znalostí Java, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity
Avatar
David Hartinger
Vlastník
Avatar
David Hartinger:5.11.2013 9:48

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
5.11.2013 9:48
New kid back on the block with a R.I.P
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá na David Hartinger
Luboš Běhounek Satik:5.11.2013 10:45

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
5.11.2013 10:45
https://www.facebook.com/peasantsandcastles/
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Luboš Běhounek Satik
David Hartinger:5.11.2013 10:55

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

Nahoru Odpovědět
5.11.2013 10:55
New kid back on the block with a R.I.P
Avatar
Jakub Lásko[Saarix]
Tvůrce
Avatar
Odpovídá na David Hartinger
Jakub Lásko[Saarix]:5.11.2013 14:37

Takže GZip v C# je zakázán? :(

Nahoru Odpovědět
5.11.2013 14:37
Časem je vše možné.
Avatar
Kit
Tvůrce
Avatar
Odpovídá na Jakub Lásko[Saarix]
Kit:5.11.2013 15:45

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
5.11.2013 15:45
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Jakub Lásko[Saarix]
Tvůrce
Avatar
Odpovídá na Kit
Jakub Lásko[Saarix]:5.11.2013 16:06

Pravda no budu se muset zamyslet.

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

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
5.11.2013 16:53
https://www.facebook.com/peasantsandcastles/
Avatar
Silvinios
Tvůrce
Avatar
Odpovídá na Kit
Silvinios:5.11.2013 18:54

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 Hartinger
Vlastník
Avatar
Odpovídá na Silvinios
David Hartinger:5.11.2013 18:59

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

Nahoru Odpovědět
5.11.2013 18:59
New kid back on the block with a R.I.P
Avatar
adas
Tvůrce
Avatar
adas:5.11.2013 19:16

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

 
Nahoru Odpovědět
5.11.2013 19:16
Avatar
Michael Olšavský
Tvůrce
Avatar
Odpovídá na adas
Michael Olšavský:5.11.2013 19:39

A nespletl se třeba jen zase? :-D

 
Nahoru Odpovědět
5.11.2013 19:39
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Michael Olšavský
David Hartinger:5.11.2013 19:42

Ne, je to v pondělí :)

Nahoru Odpovědět
5.11.2013 19:42
New kid back on the block with a R.I.P
Avatar
Neaktivní uživatel
Člen
Avatar
Neaktivní uživatel:5.11.2013 19:43

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

Nahoru Odpovědět
5.11.2013 19:43
Neaktivní uživatelský účet
Avatar
Kit
Tvůrce
Avatar
Odpovídá na David Hartinger
Kit:5.11.2013 21:06

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

Nahoru Odpovědět
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
Tvůrce
Avatar
Luboš Běhounek Satik:11.11.2013 14:27

budete se nekdo ucastnit? :)

Nahoru Odpovědět
11.11.2013 14:27
https://www.facebook.com/peasantsandcastles/
Avatar
Michael Olšavský
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Michael Olšavský:11.11.2013 16:26

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
Tvůrce
Avatar
Luboš Běhounek Satik:11.11.2013 17:51

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
https://www.facebook.com/peasantsandcastles/
Avatar
martinsakra
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
martinsakra:11.11.2013 18:06

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 Hartinger
Vlastník
Avatar
Odpovídá na Luboš Běhounek Satik
David Hartinger:11.11.2013 18:21

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

Nahoru Odpovědět
11.11.2013 18:21
New kid back on the block with a R.I.P
Avatar
David Hartinger
Vlastník
Avatar
David Hartinger:11.11.2013 18:34

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
New kid back on the block with a R.I.P
Avatar
martinsakra
Tvůrce
Avatar
Odpovídá na David Hartinger
martinsakra:11.11.2013 18:52

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
Tvůrce
Avatar
Odpovídá na David Hartinger
Silvinios:11.11.2013 19:01

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
Tvůrce
Avatar
Odpovídá na Silvinios
martinsakra:11.11.2013 19:24

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
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá na David Hartinger
Luboš Běhounek Satik:11.11.2013 19:33

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
https://www.facebook.com/peasantsandcastles/
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Luboš Běhounek Satik
David Hartinger:12.11.2013 11:10

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
New kid back on the block with a R.I.P
Avatar
Silvinios
Tvůrce
Avatar
Odpovídá na David Hartinger
Silvinios:12.11.2013 20:04

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
Tvůrce
Avatar
coells:13.11.2013 19:42

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
13.11.2013 19:42
Avatar
Silvinios
Tvůrce
Avatar
Odpovídá na coells
Silvinios:14.11.2013 7:22

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
Tvůrce
Avatar
Odpovídá na Silvinios
coells:14.11.2013 13:39

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 Hartinger
Vlastník
Avatar
Odpovídá na Luboš Běhounek Satik
David Hartinger:15.11.2013 16:09

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
New kid back on the block with a R.I.P
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.