Keskustelu: Yleinen keskustelu: Miten Zip toimii?

Eli miten Zip ja Rar ohjelmat toimii?
Tietty ymmärrän, että ne pakkaa ohjelman, mutta miten ne sen periaatteessa tekee?
Ja miksi Rar on tehokkaampi kuin Zip, käyttääkö ne eri tekniikkaa?

Tässä tulee yksinkertainen esimerkki pakkauksesta.

Alkuperäinen tiedosto (15 merkkiä):

AAAAAAABBBCCCCC

Pakattu tiedosto (6 merkkiä):

7A3B5C

Eli jos samoja merkkejä on peräkkäin, merkitään tiedostoon koko merkkirivin asemesta vain tieto siitä, kuinka monta niitä on. Semmoiset tiedostot pakkautuvat parhaiten, joissa on paljon tällaisia saman merkin osuuksia. ZIP ja muut todelliset pakkausmuodot eivät tietenkään ole näin yksinkertaisia, mutta taustalla oleva periaate on sama.

Höh, olit nopeampi Antti. Kerrankin olisi jotain mitä minäkin olisin osannut (HTML:n lisäksi). Örrörrörr

Ai, en ois ite arvannu :P
Aika ovela veikko joka ton on keksiny.
Mutta miks Rar on tehokkaampi kuin Zip?

Pakkaustavat ovat erilaisia ja RAR varmaankin hoksaa tiedostosta enemmän osuuksia, jotka voidaan korvata lyhyemmällä merkinnällä.

Tein testiksi tuolla tavoin visual basic 5:lla ohjelman, joka pakkaa D:\pak.txt tiedoston (a kirjaimia sisältävä tiedosto), jossa on siis 16 a-kirjainta niin sen tiedoissa lukee:

Size: 46bytes
Size in disk: 4KB

sitten käynnistin sen ohjelman niin se teki D:\pak.pak tiedoston, jonka tiedoissa luki:

Size: 7bytes
Size in disk: 4KB

mutta jostain syystä, kun käski sen ohjelman sitten purkaa sen niin sen tekemä tiedosto oli isompi kuin alkuperäinen ja sekin vain, koska visual basic halusi ihan välttämättä tehdä yhden tyhjän rivin perään (olisikohan tuohon mitään korjausta?).

Mutta oikeastihan tuo ei ole silti ihan noin helppoa, koska sen ohjelman varmaankin pitäisi osata sijoittaa ne eri kirjaimet ja merkit oikeille paikoille tai se pakattu tiedosto ei sitten toimi enään oikein, kun sen purkaa ja ainakin, kun notepadilla katselee noita tiedostoja niin ne sisältävät sadoittain todellakin erikoisia merkkejä ja myös ihan kunnollistakin tekstiä siellä täällä.

Katsele mielummin heksaeditorilla. VB ei taida olla ihan tätä varten. Yleensä tiedostosta kannattaa lukea ennemmin tavuja kuin merkkejä (vähän hassusti sanottu :), jolloin vältytään turhilta rivinvaihdoilta.

ja entäs jos pitäisi pakata "5aa"? Taas algoritmi monimutkaistuu..

Zip käyttää erästä LZ77 algoritmin viritystä (käsittääkseni LZSS), jonka perusidea on varsin yksinkertainen. Algoritmissa yritettään etsiä seuraavia merkkejä aiemmin läpikäydyistä merkeistä. Algoritmissa koodataan (n, m, c) kolmikoita, joista n kertoo kuinka montamerkkia sitten oli samanlaisia merkkejä ja m kertoo kuinka pitkä toisto löydettiin. LZ77 algoritmissa c:hen lisättiin ensimmäinen merkki, ei täsmännyt aikaisemman toiston kanssa. LZSS:ssä päästiin pienellä virityksellä eroon c:stä.

ABBABCABBBBC
koodataan
(0,0,A)  //A
(0,0,B)  //B
(1,1,A)  //BA
(3,1,C)  //BC
(3,2,B)  //ABB
(2,2,C)  //BBC

(a,n,c) kolmikko tietenkin koodataan mahdollisimman lyhyesti valiten a:lle ja n:lle jotkin kiinteät (pienet) bittimäärät. a:n koko käytännössä rajoittaa algoritmin etsimään toistoja vain tietynkokoisesta liikkuvasta ikkunasta (esim 9k edellistä merkkiä).

Rar-algoritmistä en entuudestaan paljon tiedä eikä googlekaan nopealla etsinnällä kertonut sen käyttävän mitään perusalgoritmia.

Antti Laaksonen kirjoitti:

Tässä tulee yksinkertainen esimerkki pakkauksesta.

Alkuperäinen tiedosto (15 merkkiä):

AAAAAAABBBCCCCC

Pakattu tiedosto (6 merkkiä):

7A3B5C

Yksinkertainen on kaunista, mutta se ei aina suoraan toimi. Kuten msdos464 huomasikin ei tuolla tavalla voi koodata merkkijonoa "5aa" koska se sisältää jo numeroita. Eräs yksinkertainen tapa toteuttaa RLE (Run length encoding, eli juuri tämä algoritmi) on sellainen, jossa aina kaksi (tai useampi) sama merkki tarkoittaa toiston alkua ja tälläisen parin perään merkitään vielä lisäksi tulevien merkkien määrä.

AAAAAAABBBCCCCC
olisi
AA5BB1CC3

ja
5AA
olisi
5AA0

Toistojen määrät tietenkin oikeasti merkittäisiin merkillä numero n (esim 5) eikä kyseisellä ascii merkillä ('5').

Yritin kerran tallentaa exe tai minkä tahansa tiedoston toiseen tiedostoon (binäärinä) johon tuli muutakin tietoa. sitten yritin lukea vain itse tiedosto datan jättäen sen muun tiedon lukematta. Mutta sen jälkeen siitä muodostunut tiedosto ei toiminut. Ilman tuota muuta tietoa se kyllä toimisi. Yritin tehdä asennus ohjelmaa. Että mitenkä saisi sitten pakattua monta tiedostoa yhteen? Mutta voi olla että tein jossain muuallakin virheen.

Itsekin tein kerran jonkinmoisen pakkauksen, joka etsi toistuvia tekstinpätkiä, kirjoitti tiedoston alkuun tekstinpätkän kerran, ja sitä vastaavan merkin. Sitten se korvasi tekstistä jokaisen usein toistuvan pätkän tuolla merkillä ja purkaja muutti merkit taas tekstiksi. (Siis teoriassa näin, käytännössä se ei ollut niin yksinkertaista) Juju on kai siinä, että pakkausohjelma tajuaa, kuinka pitkä pätkä tekstiä kannattaa ottaa. Esim.

PÄIVÄÄPÄIVÄÄ
PÄIVÄÄPÄIVÄÄPÄIVÄÄ

voisi pakata:

*=PÄIVÄÄ
**
***

mutta pakkajan pitää "tajuta" se noin, ettei se pakkaa esim.

*=PÄIVÄÄPÄIVÄÄ
*
*PÄIVÄÄ

Millainen maailma olisikaan ilman pakkausalgoritmeja:

1024x16384 Kokoinen kuva jossa on tasan 16777216 väriä:
Pakkaamaton BMP: 50331674 tavua
PNG-formaatissa: 84803 tavua
Eka pakkaus kerta: 1007 tavua
Toka pakkaus kerta: 855 tavua

855 tavua pienemmäksi ei mennyt.

Sinänsä hämmästyttävää, mutta kun tarkastelee pakkaamattoman PNG-tiedoston sisältöä, näkee siellä yllättävän paljon toistoa, jonka voi vielä pakata helposti.

Jokatapauksessa, hämmästyttävää että noinkin iso kuva menee alle kilotavun...

Toteutin kuvan pakkaamisen PHP:llä, käyttäen gzcompress() funktiota.
Kuvana käytin: AllColors_php.png

Osoitteesta www.wotsit.org löytyy tietoa zipeistä ja rareista ja monesta muustakin formaatista.

T.M. kirjoitti:

Jokatapauksessa, hämmästyttävää että noinkin iso kuva menee alle kilotavun...

No eipä oikeastaan. Kyseessähän on täysin keinotekoinen ja hyvien pakkausalgoritmien odottama kuvio. Kaikki mikä on säännöllistä tai ennalta arvattavaa on myös helposti pakattavissa. Toi 855 tavua ei ole vielä kovin hyvä pakkaus tuolle kuvalle. Veikkaisin, että hyvä assembler koodari tuottaa alle 50 tavun ohjelman, joka luo tuollaisen bmp-kuvan. Datan tuottava ohjelma on myös eräs pakkaustapa.

Sellainen ohjelma vaan on vähän vaikea tehdä, että kun antaa
sille syötteenä jonkin valokuvan, niin se tekee 10 kt ohjelman joka
piirtää sen :)

tuollainen pakkaus toimii lähinnä silloin kun etukäteen tiedetään
että minkälainen kuva on..