Keskustelu: Ohjelmointiputka: Putkaposti 41: Huono pakkaus

Syksy tuo tullessaan uuden putkapostin:

https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=hupa

Kiva tehtävä. Nykyinen ratkaisu taitaa kuitenkin olla jo paras mahdollinen, nimittäin jos zip havaitsee, että "pakkaamisesta" ei ole apua, se tallentaa tiedoston pakkaamattomana.

Nykyiset tuloksethan ovat kaikki tod.näk. satunnaisdataa jota saadaan kätevästi esim. *nixien /dev/(u)randomista. Nuo 158 tavua ovat zipin headereita. Itse sain paisutettua tiedoston peräti 4056 tavuun yksinkertaisesti nimeämällä tiedoston mahdollisimman pitkästi (zip säilyttää tiedostonimet headerissa), mutta putkan tulokseen tällä ei ollut vaikutusta ilmeisestikin uploadin vaihtaessa nimen.

Kray kirjoitti:

Nykyiset tuloksethan ovat kaikki tod.näk. satunnaisdataa

Itse ainakin ratkaisin tehtävän ihan yksinkertaisella logiikalla. Tämä tietenkin vaatii perustietoja käytettävän pakkausalgoritmin periaatteista.

Kray kirjoitti:

Nykyiset tuloksethan ovat kaikki tod.näk. satunnaisdataa jota saadaan kätevästi esim. *nixien /dev/(u)randomista. Nuo 58 tavua ovat zipin headereita.

Tarkoittanet 158 tavua?

Kray kirjoitti:

mutta putkan tulokseen tällä ei ollut vaikutusta ilmeisestikin uploadin vaihtaessa nimen.

Niin, tehtävänannossa sanotaan, että:

lainaus:

se muutetaan ZIP-paketiksi seuraavalla Unix-komennolla:

zip suuri.zip suuri.dat

Eli ilmeisesti tiedoston nimi on aina suuri.dat

Vähän yli puoli tuntia ehti kulua uuden tehtävän ilmoittamisesta, ennen kuin periaate vastauksen tuottamiseen kerrottiin. En oikein hahmota nopean spoilaamisen ideaa, mutta ehkä olen ainoa.

Joudun pyörtämään puheeni: isommalla datamäärällä (64 kilotavua) sain zip-ohjelman luomaan pakkauksen kanssa hieman isomman tiedoston kuin ilman pakkausta. Ehkä siis tähänkin tehtävään on jokin syöte, jolla ohjelmaa saa huijattua. Tämän selvittämiseksi pitäisi varmaankin tutustua ohjelman lähdekoodiin.

vai olisiko headerissa sitten informaatio tiedoston koosta ilmoitettu sellaisessa formaatissa, joka kasvattaa tiedoston kokoa? isompi luku vaatii varmasti enemmän tilaa.

Huono implementaatio.

Putkaposti kirjoitti:

jos menetelmä pienentää jonkin tiedoston kokoa, se vastaavasti suurentaa jonkin tiedoston kokoa

US Patent 5,533,051 väittää että siinä esitelty menetelmä pienentää minkä tahansa ja että kertaalleen pienennettyä voi aina pienentää lisää samalla menetelmällä ..

Grez kirjoitti:

US Patent 5,533,051 väittää että siinä esitelty menetelmä pienentää minkä tahansa ja että kertaalleen pienennettyä voi aina pienentää lisää samalla menetelmällä ..

Oliko tuo vitsi? Eihän moinen ole edes teoriassa mahdollista. Siis, että voisi muka aina pakata mitä tahansa dataa pienemmäksi.

Mistä lähtien amerikkalaisilla patenteilla on ollu mitään tekemistä todellisuuden kans?

Grez kirjoitti:

US Patent 5,533,051 väittää että siinä esitelty menetelmä pienentää minkä tahansa ja että kertaalleen pienennettyä voi aina pienentää lisää samalla menetelmällä ..

Tässä on oma vastaava menetelmäni: Pakatun tiedoston alussa on aina muutaman tavun mittainen otsikkotieto, joka sisältää olennaisesti datan pituuden ja valitun dataformaatin numeron (0..255). Tätä seuraa pakattu data, joka on aina täsmälleen yhden tavun lyhyempi kuin alkuperäinen. Kätevää, eikö? Ja paras on vielä edessä: varsinainen pakkausalgoritmi toimii vakioajassa syötteen pituudesta riippumatta! (Toki datan siirtely muistissa yhä vie aikansa.)

Joo, asiasta tietämättömiä on helppo huijata, kunhan esittää väitteensä tarpeeksi tyylikkäästi.

aaämdee kirjoitti:

Oliko tuo vitsi?

Mua ainakin pikemminkin itkettä kuin naurattaa.

Eikö tähän kannattaisi vaihtaa sellainen pakkausohjelma, joka ei jätä leikkiä kesken hankalan tiedoston kanssa. Vai onko se toiminnallisuus sidottu formaattiin?

Zip-paketti kannattaisi vaihtaa johonkin tiettyyn algoritmiin tai tarpeeksi tyhmään pakkausformaattiin. Nyt /dev/urandom:inkin tuottama satunnaisdata saa täydet pisteet.

ZIP-menetelmä on kaikkien tuntema pakkausmenetelmä, minkä vuoksi se on luonteva valinta tehtävään. Moni on saanut tuloksen 1158, mutta onko joku varma siitä, että se on paras mahdollinen tulos?

Antti Laaksonen kirjoitti:

Moni on saanut tuloksen 1158, mutta onko joku varma siitä, että se on paras mahdollinen tulos?

Se että zip kertoo pakkauksen olevan 0 ja se että pakattu tiedosto on pakkauksen sisällä sellaisenaan kertonee jotain. Ja koska tiedoston nimi ja pakkauskomentokin ovat fiksattuja, niin ei headerin pituuteenkaan ole käsittääkseni mahdollista vaikuttaa.

Tämä on totta, mutta ohjelma saattaa "pakata" tiedoston, vaikka pakattu tiedosto olisi suurempi kuin alkuperäinen tiedosto.

Ohjelman tuloste, kun 1000 tavun tiedosto lisätään sellaisenaan:

  adding: suuri1.dat    (in=1000) (out=1000) (stored 0%)
total bytes=1000, compressed=1000 -> 0% savings

Ohjelman tuloste, kun 65536 tavun tiedosto lisätään "pakattuna":

  adding: suuri2.dat    (in=65536) (out=65546) (deflated 0%)
total bytes=65536, compressed=65546 -> 0% savings

Jälkimmäisessä tapauksessa "pakattu" tiedosto vie siis 10 tavua enemmän tilaa kuin alkuperäinen tiedosto. Voisiko sopivasti valittu 1000 tavun tiedosto aiheuttaa vastaavaa?

Minkäköhän kokoisissa palasissa ZIP pakkaa (tämä kilpailussa käytetty ZIP implementaatiot oletusasetuksillaan). Meinaan jos se saa osaa paloista pakattua vähän ja osaa ei, niin se saattaa harhautua laittamaan näitä paloja talteen vaikka koko tiedoston tallettaminen pakkaamattomana saattaisi viedä vähemmän tilaa. Tietenkin jos lohkon koko on yli 1000, niin tuossa kilpailutehtävän tapauksessa peli on menetetty vaikka 64k tiedostolla kokoa pystyisikin kasvattamaan.

Antti Laaksonen kirjoitti:

Tämä on totta, mutta ohjelma saattaa "pakata" tiedoston, vaikka pakattu tiedosto olisi suurempi kuin alkuperäinen tiedosto.

Ohjelman tuloste, kun 1000 tavun tiedosto lisätään sellaisenaan:

  adding: suuri1.dat    (in=1000) (out=1000) (stored 0%)
total bytes=1000, compressed=1000 -> 0% savings

Ohjelman tuloste, kun 65536 tavun tiedosto lisätään "pakattuna":

  adding: suuri2.dat    (in=65536) (out=65546) (deflated 0%)
total bytes=65536, compressed=65546 -> 0% savings

Jälkimmäisessä tapauksessa "pakattu" tiedosto vie siis 10 tavua enemmän tilaa kuin alkuperäinen tiedosto. Voisiko sopivasti valittu 1000 tavun tiedosto aiheuttaa vastaavaa?

Niin, mutta tuo negatiivinen pakkaus taitaa johtua käytetyn DEFLATE-formaatin "pakkaamattoman" 00-lohkon maksimipituudesta, joka on 65535 tavua.

Yleisestikin ottaen zip-standardin mukaisia pakkauksia pystyy tekemään parempia ja huonompia. Kun ei tiedä Antin käyttämää versiota, niin mielestäni aika turha alkaa tutkia tarkemmin.

Esim. omassa melkein Unixissa eli Linuxissa zip (Copyright (c) 1990-2006 Info-ZIP - Zip 2.32 (June 19th 2006)) tuottaa vain 1150 tavua pitkän tiedoston 1000 tavusta urandomia sisältävästä suuri.dat:sta, kun taas Antin käyttämä versio tuottaa 8 tavua enemmän.

Vastaavasti 7-zip tuottaa oletusastuksilla -tzip -flagilla (eli zip eikä 7z) 1116 tavun tiedoston, eli 42 tavua Antin zippiä pienemmän. Voi toki olla että Windowsissa tallennetaan vähemmän informaatiota tiedostosta. Päivämäärä ainakin näyttää tallentuvan, mutta oikeusflageista ei tietoa.

Käännän seuraavan kysymykseni rot13:sta.

Wbf bvxrva lzzäefva avva xälgäaaöffä rxnxfv ibvfva yhbqn fryynvfra .qng gvrqbfgba wbfgn ghyrr ghb 1000 gniha mvc-gvrqbfgb wbgn fvggra xälqäa .qng gvrqbfgban. Aävauäa mvc uhbznn rggä cnxxnhxfrfgn rv byr ulöglä xha fr ba wb xreena cnxnggh. Byraxb bvxrvyyn wäywvyyä?

Voi sen noinkin tehdä, mut helpomminki onnistuu.

Xreeb zvgra yhbg gvrqbfgba, wbxn mvcngghan ba gnfna 1000 gnihn.

jutti kirjoitti:

Xreeb zvgra yhbg gvrqbfgba, wbxn mvcngghan ba gnfna 1000 gnihn.

Yhbznyyn gvqbfgba, wbffn ba 1000 gnihn fnghaanvfgn qngnn wn mvccnnznyyn fr. Bznyyn xbarryynav aäva fnnqha mvcva xbxb byv 1138 gnihn. 1000-138=862 Alg ynvgrgnna gvrqbfgbba 862 gnihn enaqbz-qngnn wn mvcngnna fr, wbyybva mvcva xbba cvgävfv byyn 1000 gnihn.

-tossu-: Aika hyvä, mutta toisaalta jos keksii tuon, ei ehkä kaipaa enää sitä 1000 tavun zippiä. :)

tesmu: Ratkaisuideassasi on virhe: tiedoston otsikko on pakkaamatonta dataa, joten kun 1000 tavun zip-tiedosto pakataan, se menee alkuperäistä pienempään tilaan. (Toki lisäksi tulee uuden zip-tiedoston otsikko, jolloin yhteiskoko kasvaa.) Seuraava on zip-ohjelman tuloste koneellani, kun suuri.dat onkin 1000 tavun zip-tiedosto, joka on tehty, kuten -tossu- yllä ehdotti:

  adding: suuri.dat     (in=1000) (out=979) (deflated 2%)