7.1.1  Begreper
Ordet komprimere (eng: compress) betyr å gjøre noe mindre, tettere eller mer kompakt og da på en slik måte at det opprinnelige innholdet kan gjenskapes enten eksakt eller tilnærmet. Ordet dekomprimere (eng: decompress) står for det motsatte.

Vi kjenner mange eksempler på «komprimering» fra dagliglivet. Hvis vi får i oppdrag å lage en utredning, er det vanlig, når den skal presenteres, å ha et sammendrag. Det kan kalles en komprimert versjon av utredningen. Men det er selvfølgelig umulig å gjenskape en hel utredningen kun ved hjelp av et (kort) sammendrag. Dette er derfor komprimering med (vesentlig) tap (eng: lossy compression).

De fleste vil nok etter hvert få en DAB-radio. Lyd digitaliseres, komprimeres og sendes ut i «eteren». Signalene fanges opp av DAB-radioens antenne og blir så dekomprimert til noe som våre ører kan bearbeide. Digitalisert lyd kan komprimeres ganske mye uten at det går vesentlig ut over lydkvaliteten. Men hvis vi hadde hatt tilgang til den originale lyden og sammenlignet den med det som kommer ut av en DAB-radio, vil nok de fleste høre at det er forskjell. Den originale lyden oppfattes ofte som å være mer fyldig og ha flere nyanser. Men når vi kun har lyden fra radioen, vil det for det meste høres ok ut. Dette er også et eksempel på komprimering med tap, men der tapet ikke er vesentlig.

I databehandling har vi to hovedtyper av komprimering:

• Komprimering med tap (eng: lossy compression)
• Komprimering uten tap (eng: lossless compression)

Disse to begrepene inngår f.eks. i de vanlige bilde- og grafikkformatene på web. Der er GIF og PNG eksempler på komprimering uten tap, mens JPG er komprimering med tap. Her er et eksempel der det samme bildet er konvertert til alle de tre formatene:

Vi skal kun se på teknikker for komprimering uten tap. Der kan vi bruke mange av de idéene, algoritmene og datastrukturene som vi har vært gjennom.

Komprimeringsgrad  I komprimering uten tap er komprimeringsgraden (eng: compression ratio) viktig. La gammel være størrelsen (f.eks. i antall byter) på den opprinnelige og ny på den komprimerte «meldingen». Da er komprimeringsgraden (i prosent) gitt ved:

En komprimeringsgrad på 0% betyr at den opprinnelig og den komprimerte meldingen bruker like stor plass, dvs. at gammel = ny. Hvis den er på 100%, må ny være 0. Det er selvfølgelig umulig. Hvordan skulle man i så fall dekomprimere? Fra ingenting? Det er heller ikke slik at graden, selv med den aller beste algoritmen, alltid vil være større enn 0%. Hvis det var tilfellet, kunne vi komme til ny = 0 ved gjentatt komprimering. Det normale, ved gjentatt komprimering, er faktisk at komprimeringsgraden blir negativ. Det betyr at den komprimerte meldingen bruker større plass enn den opprinnelige.

Komprimeringsgraden er avhengig av hvilken algoritme vi bruker og av hvordan meldingen ser ut. Alle algoritmer ser etter «mønster». Det kan f.eks. være frekvensen av tegn eller av «ord». Jo mer mønster og struktur, jo høyere komprimeringsgrad. Omvendt vil en melding som er «kaotisk», få en liten eller en negativ komprimeringsgrad.

Andre begreper: Statiske kontra adaptive algoritmer. Statisk analyse kontra dynamisk.