Tiedon pakkaus

1.11. 1999
Harri Salonen, Mikko Rahikainen
Tietotekniikan osasto
Teknillinen Korkeakoulu
hsalonen@cc.hut.fi , mrahikai@cc.hut.fi

Tiivistelmä

Tässä dokumentissa käydään lyhesti läpi suurin osa nykyisin käytössä olevista pakkausmenetelmistä. Jokaisesta alalajista annetaan esimerkkialgoritmi, toimintaperiaatteittain esiteltynä.

Johdanto

Tiedon pakkaustapoja on pääasiassa kahdenlaisia:

Häviötön pakkaus
Häviöllinen pakkaus

Häviöttömässä pakkauksessa tieto puristetaan erilaisilla algoritmeilla mahdollisimman pieneen tilaan niin, että alkuperäinen tieto saadaan täysin samanlaisena takaisin. Häviötön pakkaus soveltuu erinomaisesti esim. asiakirjoihin, kuten tähän dokumenttiin, tietokoneohjelmiin, joissa ei saa olla pienintäkään bittivirhettä.

Häviöllinen pakkaus hävittää osan tiedosta, mutta pyrkii mahdollisimman aidonnäköiseen lopputulokseen. Esim. tv-kuvassa pienet virheet, eivät haittaa, eikä nykyisillä pakkausmenetelmillä ihmissilmä havaitse niitä kovin helposti staattisista kuvistakaan.

Pakkausmenetelmät luokitellaan yleensä algoritmin nopeuden ja pakkaustiheyden mukaan. Pakkaustiheyden testaamista varten on erillinen tiedostokirjasto [1]. Nopeus on kaikilla esitetyille algoritmeilla ainakin kohtuullinen. Tähän on otettu mukaan yleisesti hyväksytyt ja käytössä olevat algoritmit.

Häviötön pakkaus

Kiinteän pituiset koodit

Kiinteän pituisilla koodeilla pakkaaminen on yksi yksinkertaisimmista pakkausmetelmistä. Tiettyä merkkiä vastaa tietty bitti-koodi. Tämä bitti-koodi on suhteutettu merkin esiintymistaajuuteen, jolloin paljon käytetyillä merkeillä on suurin esiintymistarkkuus.

Esimerkkinä, Eliaksen gamma-koodi [2].

             Gamma koodi     Luku Bittejä
             --------------------------
             1                  1     1
             01x              2-3     3
             001xx            4-7     5
             0001xxx         8-15     7
             00001xxxx      16-31     9
             000001xxxxx    32-63    11
             0000001xxxxxx 64-127    13

Eli suurimman esiintymistaajuuden omaava luku koodataan vain yhdellä bitillä (1). Ja kaksi seuraavaksi käytetyintä kahdella bitillä (01x), jne.
Muita kiinteän koodin koodaustapoja ovat esim. Eliaksen delta-koodi, fibonancci-koodi, ym. Kiinnostuneet voivat lukeat lisää viitteestä [2].
Hyvinä puolina kiinteän pituisissa koodeissa on koodien helppo muodostaminen, ja algoritmin yksinkertaisuus. Huonona puolena mainittakoon, etteivät koodit suoraan riipu frekvensseistä, vaan olettavat, että pienempiä lukuja on enemmän.

Vaihtuvat pituiset koodit

Nämä koodit ovat suoraan suhteessa frekvenssiin. Frekvenssin suhteen kaikki luvut koodataan biteiksi.
Huffmanissa lasketaan ensin kaikkien lukujen frekvenssitaajuudet.
Sitten näistä taajuuksista muodostetaan puu.
Puu muodostetaan yhdistämällä aina pienimmät frekvenssit (tai solmut) uudeksi solmuksi. Tämän jälkeen lasketaan frekvenssit uudelleen ja kaksi yhdistettyä frekvenssiä korvataan solmulla.
Esim. [3]

"BAAAAAADBBABBBBBAAADABCD"
Frekvenssit: A (11) B (9) D (3) C (1)

        Yhdistys 1          Yhdistys 2          Yhdistys 3
        'A' 0.458           'A' 0.458           C2 0.542 0\ C3
        'B' 0.375           'B' 0.375 0\ C2     'A' 0.458 1/
        'D' 0.125 0\ C1     C1 0.167 1/
        'C' 0.042 1/

Koko puu näyttää nyt tältä:

                C3
             0 / \ 1
              /   'A'
             C2
          0 / \ 1
          'B'   \
                C1
             0 / \ 1
             'D' 'C'

Lähtemällä etenemään puuta juuresta, saadan merkin bitti-koodi (esim. 0 on vasen haara ja 1 oikea).
Ja esimerkkikoodit ovat luettuna:

'A' = 1 'B' = 00 'C' = 011 'D' = 010

Muita algoritmeja ovat esim. aritmeettinen koodaus.

Sisällön pakkaajat

Lempel-Ziv-77 on tunnetuin esimerkki pakkaajasta, joka ottaa tekstin sisällön huomioon. Algoritmi periaatteessa etsii tekstistä merkkijonoja, jotka toistuvat. Jos esimerkiksi havaitsemme merkkijonon "jotka", korvaamme sen vain viittellä, esim. -60, 5 - joka tarkoittaa, että merkkijono löytyi 60 merkkiä sitten ja sen pituus oli 5.
Tämä varsin yksinkertainen menetelmä on yllättävän tehokas ja käytössä monissa nykyajan ohjelmissa, kuten esim. PKZip [4].

Yksinkertaisin esimerkki on RLE, run length encoding, jota käytetään mm. joissain Micrsoftin kuvatiedostoissa. Se pakkaa dataa yksinkertaisesti siten, että toistuvat merkit koodataan merkillä ja toiston pituudella, esim. aaaabbb -> 4a 3b.

Toinen kiintoisa esimerkki on Burrows-Wheeler transformaatio. Merkkijonosta luodaan n * n -taulukko, jossa n on merkkijonon pituus. Tämän taulukon vaakarivit järjestetään ensimmäisen kirjaimen mukaan, ja taulukosta tallennetaan viimeinen pystyrivi, ja alkuindeksi. Tämä itseasiassa kasvattaa tiedoston kokoa. Ideani koko algoritmissa onkin, että sen jälkeen ulostulo ohjataan jollekin muulle pakkajaalle - sisältöä ei siis ole pakattu, vaan se on muutettu luonteeltaan paremmin pakkautuvaksi. Lähteen [5] mukaan BW-RLE/aritmeettinen -yhdistelmä pakkaa paremmin kuin PKZip [4].

Muita mainitsemisen arvoisia esimerkkejä ovat mm. LZ-78 ja LZW.

Hybridit

Mikään algoritmi ei ole täydellinen, ja algoritmien toiminta on paljolti erilaista. Sisällön pakkaajat eivät suoraan laske frekvenssejä, eivätkä koodaus-menetelmät välttämättä ymmärrä sisältöä. Yhdistelemällä näitä menetelmiä on saatu parempia tuloksia, kuin algoritmit sinällään tuottaisivat. Esim. PKZip[4] käyttää ensin LZ-77 -pakkausta ja koodaa sitten ulostulon lähes Huffman-tyyppisellä pakkauksella.

Häviölliset menetelmät

JPEG

Käytetään kuvien pakkauksessa. Esimerkissä oletamme, että meillä on x*y pikselin kokoinen rgb (red, green, blue) -kuva.

Ensin väriavaruus muunnetaan YUV-muotoon. Tässä muodossa meillä on yksi komponentti kirkkautta varten (kuvittele vastaavaa harmaasävy-arvoa), ja kaksi muuta täsmentävät värin. Tärkein ihmissilmälle on kirkkauskomponentti, joten kahden muun arvosta voidaan tinkiä.

Toiseksi kuva jaetaan 8x8 matriiseihin. UV-komponentit pienennetään 4x4-kokoiseen, yksinkertaisesti laskemalla keskiarvo. Ero ei ole suoraan havaittavissa, koska Y-komponenttia ei kutisteta, ja silmä reagoi kirkkauden muutoksin radikaalimmin, kuin värimuutoksiin.

Sitten kuvalle tehdään DCT (discrete cosine transform), jolloin saadaan jokaisen tilataajuuden spektraalikomponentit. Nämä komponentit ovat voimakkaita origon läheisyydessä, mutta pienenevät mentäessä kauemmaksi. Itse asiassa, ne ovat suurimmaksi osaksi nollaa kaukauna origosta.

Seuraavaksi nämä komponentit pistetään taulukkoon, josta vielä karsitaan heikoimmat taajuudet pois jakamalla taulukko seuraavalla taulukolla:

1 1 2 4 8 16 32 64

1 1 2 4 8 16 32 64

2 2 2 4 8 16 32 64

4 4 4 4 8 16 32 64

8 8 8 8 8 16 32 64

16 16 16 16 16 16 32 64

32 32 32 32 32 32 32 64

64 64 64 64 64 64 64 64

Tässä kadotetaan taas tietoa, mutta pienimpien taajuuksien poisto vaikuttaa vain hyvin vähän. Yleensä jatkuvissa kuvissa kaikki tieto on ensimmäisissä spektraalikomponenteissa. Jos kuva taas on epätasainen (esim. tämä teksti ei ole jatkuvaa, vaan rosoista), voi pieniä häiriöitä ilmestyä kuvan sisälle.
Tämän jälkeen taulukko käydään läpi allaolevalla järjestyksellä.

1 2 6 7 15 16 28 29

3 5 8 14 17 27 30 43

4 9 13 18 26 31 42 44

10 12 19 25 32 41 45 54

11 20 24 33 40 46 53 55

21 23 34 39 47 52 56 61

22 35 38 48 51 57 60 62

36 37 49 50 58 59 63 64

Kuten selvästi huomaa, korkeimmat taajuudet käydään ensin ja lopussa olevat heikot taajuudet viimeiseksi.
Koska loppu on yleensä pelkkää nollaa, sovelletaan jonoon RLE-algoritmia.

Lopuksi saadut tiedot ajetaan vielä huffman-algoritmin läpi.

MPEG

Yleistä

Tällä hetkellä on kolme vallitsevaa MPEG-standardia. MPEG-1 oli ensimmäinen, joka pyrki määrittelemään videon toistoa 1,2 Mbps-nopeudella. MPEG-2 standardia tarkennettiin, ja bittinopeutta nostettiin. MPEG-4 on MIT:issä kehitetty laajennus, joka lähinnä määrittelee tilatoiston (ts. spatiaalisen äänen).
MPEG-3 standardia ei ole olemassa ja sitä ei kannata sekoittaa MP3:een.

MPEG-koodaus jakautuu kolmeen osaan, videoon, audioon ja systeemiin, joista video ja audio koodataan erikseen. Systeemi tarjoaa sitten 90 kHz kellon videon ja audion synkronointiin..

MPEG Audio

MPEG-2 standardiin mennessä oli määritelty kolme audiokerrosta.
Jokainen toimii tietyillä bittinopeuksilla (bitrate), jotka kertovat, kuinka paljon informaatiota on saatu mahtumaan audio-osuuteen (kilobittiä/sekunti).

Layer 1

Tämä on kaikkein perusmallisin audioalgoritmi. Perustuu DCC:hen ja äänenlaatu on suhteessa kaikkein surkein. Eli bittinopeuden on oltava lähellä alkuperäistä, jotta ääni kuulostaisi hyvältä. Suositeltu bittinopeus on 192kbps-448kbps.

Layer 2

Tilanvarausta on parannettu ja lisätty DAB (Digital Audio Broadcasting)-komponentit tulevaa käyttöä varten. Yleisesti, tämä on laskenut tarvittavaa bittinopeutta, jolla ääni kuulostaa hyvältä ja siksi suositeltu nopeus onkin 128kbps-384kbps.

Layer 3

Yleisesti tunnettu nimellä MP3. Äänen vaatima tila on saatu erittäin pieneen tilaan, käyttämällä esim. erilaisia filttereitä, huffman-koodausta, ym.. Tämän seurauksena Layer 3 -koodattuja äänitiedostoja on saanut sinällään (ilman video-osuutta) Internetistä jo pitkään ja ne aiheuttavat musiikkiteollisuudelle huomattavaa päänvaivaa.
Suositeltu bittinopeus on 64kbps-320kbps. Jo bittinopeudella 128kbps ei eroa CD-tasoiseen äänen huomaa ja tieto on pakkautunut noin kymmenesosaan alkuperäisestä.

MPEG video

Videokuvissa voidaan yksittäiset kuvat (tästä lähin: framet) koodata erikseen JPEG-pakkauksella. MPEG-standardi yleensä ottaa myös huomioon toistuvat sekvenssit. Esimerkiksi paikaltaan kuvatussa mäkihyppääjäfilmissä liikkuu ainoastaan mäkihyppääjä.

Kuvat koodataan siis kuten JPEG-standardissa, mutta toistuvat matriisit, ts. matriisit, jotka eivät paljon eroa edellisestä tai tulevasta framesta, koodataan vain laittamalla viite edelliseen/seuraavaan frameen. Kirkkaus on 16*16 matriisi ja värikomponentit taas puolet kummassakin suunnassa, eli 8*8.

MPEG-1 määrittelee neljä perustilaa [6]:

Kuvat on koodattu JPEG-muodossa ilman ennustusta.
Kuvien matriisien eroja etsitään edellisestä framesta.
Kuvien matriisien eroja etsitään edellisestä ja seuraavasta framesta.
Keskiarvoja matriiseista käytettäväksi pikakelaukseen

JPEG-pakkausmenetelmä hävittää tietoa. Tästä syystä väliin laitetaan aina perusframeja, eli JPEG-koodattu frame, jotta kuvan häviöllinen pakkaus ei heikentäisi kuvan laatua liikaa, ja jotta katselu pystyttäisiin aloittamaan vapaavalintaisesta kohdasta (ts. jos kaikki riippuisivat edellisestä, käyttäjä joutuisi katsomaan koko videon uusiksi).

MPEG-2 poistaa tilan 4, lisää lisää DCT:n tarkkuutta 10x10-matriisiin, ja lisää eri tiloja kuvan laatuun. Mukana on pari perustilaa ja HDTV-tilat, jotka ovat huomattavasti tarkkuudeltaan muita parempia.
'
Esim. digitaalinen TV pohjautuu MPEG-2 -standardiin [7].

Lähteet

[1] University of Canterbury, Canterbury Corpus, 1999
<http://corpus.canterbury.ac.nz/>
[2] Ojala Pasi, Compression Basics 1998
<http://www.cs.tut.fi/~albert/Dev/pucrunch/packing.html>
[3] Lelewer D.A. and Hirschberg D.S., "Data compression," Computing Surveys 19,3 (1987), 261-297. Reprinted in Japanese BIT Special issue in Computer Science (1989), 165-195.
<http://www.ics.uci.edu/~dan/pubs/DataCompression.html>
[4] PKWARE, inc., The Data Compression Experts!
<http://www.pkware.com>
[5] Nelson Mark, Data Compression with the Burrows-Wheeler Transform, Dr.Dobb's Journal, syyskuu 1996.
<http://www.dogma.net/markn/articles/bwt/bwt.htm>
[6] Tanenbaum, Andrews, Computer Networks, 3rd edition, Prentice-Hall International, 1996
[7] DVB, DVB Data Broadcasting, 13.7.1998
<http://www.dvb.org/dvb_standards/dvb_dvbd.htm>

Kiintoisaa luettavaa

Berkeley Multimedia Research Center, MPEG2 FAQ 1999
<http://bmrc.berkeley.edu/frame/research/mpeg/mpeg2faq.html>
Burrows M. & Wheeler D.J, A Block-sorting Lossless Data Compression Algorithm, SRC Research Report 10.5.1994
<ftp://ftp.digital.com/pub/DEC/SRC/research-reports/SRC-124.pdf>
comp.compression FAQ, 1999
<http://www.faqs.org/faqs/compression-faq/part2/>
Nelson Mark, Arithmetic Coding + Statistical Modeling = Data Compression, Part 1 - Arithmetic Coding, Dr.Dobb's Journal helmikuu 1991
<http://www.dogma.net/markn/articles/arith/part1.htm>
Tsutsui Kyoya et al., ATRAC: Adaptive Transform Acoustic Coding for MiniDisc, the 93rd Audio Engineering Society Convention in San Fransisco, 1992 October 1-4
<http://www.hip.atr.co.jp/~eaw/minidisc/aes_atrac.html>
Ziring Neal, TFTP Compression and Security Options, NSA INTERNET DRAFT 26.5.1999
<http://search.ietf.org/internet-drafts/draft-ziring-nsa-tftp-security-01.txt>
Unisys, License Information on GIF and Other LZW-based Technologies
<http://corp2.unisys.com/LeadStory/lzwfaq.html>
RealNetworks, The Home of Streaming Media
<http://www.real.com>
nullsoft, nullsoft SHOUTcast
<http://www.shoutcast.com>

Harri Salonen

1	1	2	4	8	16	32	64
1	1	2	4	8	16	32	64
2	2	2	4	8	16	32	64
4	4	4	4	8	16	32	64
8	8	8	8	8	16	32	64
16	16	16	16	16	16	32	64
32	32	32	32	32	32	32	64
64	64	64	64	64	64	64	64

1	2	6	7	15	16	28	29
3	5	8	14	17	27	30	43
4	9	13	18	26	31	42	44
10	12	19	25	32	41	45	54
11	20	24	33	40	46	53	55
21	23	34	39	47	52	56	61
22	35	38	48	51	57	60	62
36	37	49	50	58	59	63	64

1	1	2	4	8	16	32	64
1	1	2	4	8	16	32	64
2	2	2	4	8	16	32	64
4	4	4	4	8	16	32	64
8	8	8	8	8	16	32	64
16	16	16	16	16	16	32	64
32	32	32	32	32	32	32	64
64	64	64	64	64	64	64	64

1	2	6	7	15	16	28	29
3	5	8	14	17	27	30	43
4	9	13	18	26	31	42	44
10	12	19	25	32	41	45	54
11	20	24	33	40	46	53	55
21	23	34	39	47	52	56	61
22	35	38	48	51	57	60	62
36	37	49	50	58	59	63	64

1	1	2	4	8	16	32	64
1	1	2	4	8	16	32	64
2	2	2	4	8	16	32	64
4	4	4	4	8	16	32	64
8	8	8	8	8	16	32	64
16	16	16	16	16	16	32	64
32	32	32	32	32	32	32	64
64	64	64	64	64	64	64	64

1	2	6	7	15	16	28	29
3	5	8	14	17	27	30	43
4	9	13	18	26	31	42	44
10	12	19	25	32	41	45	54
11	20	24	33	40	46	53	55
21	23	34	39	47	52	56	61
22	35	38	48	51	57	60	62
36	37	49	50	58	59	63	64