Datacompressie

Datacompressie is het representeren van digitale gegevens met minder bits dan de oorspronkelijke representatie. Dit artikel zou bijvoorbeeld minder ruimte innemen als we overal het woord 'comp' in plaats van 'compressie' kunnen schrijven. Daardoor zou het bijvoorbeeld sneller over een netwerk verstuurd kunnen worden.

Het comprimeren van gegevens is nuttig, omdat het helpt om bronnen te verkleinen en daardoor een hogere opslagcapaciteit of transmissiecapaciteit geeft. Dezelfde hoeveelheid gegevens kunnen namelijk in minder bytes worden verzonden en opgeslagen. Gecomprimeerde gegevens moeten eerst worden uitgepakt, hiervoor is tijd en rekenkracht nodig. Dit vergt een afweging tussen ruimtebesparing of tijdsbesparing.

Er zijn twee vormen van datacompressie; hardwarematig en softwarematig. Hardwarematige compressie wordt uitgevoerd door gespecialiseerde apparatuur, zoals een speciale videokaart. Dit versnelt de compressie aanzienlijk. Softwarematige compressie wordt gedaan door een computerprogramma, deze oplossing is goedkoper en universeler.

Typen datacompressie 
Er zijn verschillende typen datacompressie:
 exact omkeerbaar (Engels: lossless, zonder kwaliteitsverlies)
 niet-exact omkeerbaar (Engels: lossy, met kwaliteitsverlies)

Exact omkeerbare compressie
Bij exact omkeerbare compressie is het gedecomprimeerde (uitgepakte) bestand een exacte kopie van het oorspronkelijke bestand. Dat is essentieel voor bijvoorbeeld tekstdocumenten, spreadsheets en databasebestanden. De mate van compressie (de afname van het aantal bytes in het gecomprimeerde bestand vergeleken met het oorspronkelijke bestand) ligt in de praktijk tussen de 30% en de 70%.

Tekstbestanden 
Bij tekstbestanden komen bijvoorbeeld sommige letters veel vaker voor dan andere (vergelijk e en q in het Nederlands). Een compressiemethode is daarom om unieke lettercoderingen van verschillende bitlengte te kiezen, waarbij de meest voorkomende letters de kortste codes krijgen toebedeeld. Dit is de basis van de Huffmancodering, een algoritme dat voor deze methodiek de optimale code genereert op basis van de frequentietabel van de tekens in het bestand. Ook in de morsecode wordt dit principe, dat de frequentste letters de kortste codes hebben, gehanteerd, al was de theorie op het moment dat de morsecode werd uitgevonden nog niet zo formeel uitgewerkt.
Op tekstbestanden zijn echter door gebruik van andere algoritmen veel kleinere compressieratio's te behalen. (De compressieratio is de verhouding tussen de grootte van het bestand na en voor compressie: een compressieratio van 0,8 betekent dat het gecomprimeerde bestand 80% van de grootte van het oorspronkelijk bestand heeft.)

Gewone Nederlandse tekst is met optimale technieken exact omkeerbaar te comprimeren tot ca. 25 à 30 procent van de oorspronkelijke grootte. Vaak moet er een optimum worden gevonden tussen de theoretisch mogelijke graad van compressie en de daarvoor benodigde tijd of hoeveelheid geheugenruimte, waarbij ten behoeve van de snelheid met een iets minder goede compressie wordt volstaan.

Bij veel tekst kunnen (lange) woorden en zinsdelen vervangen worden door een kortere code. Als dat wordt toegepast wordt de compressie beter naarmate er meer tekst is. Ook kan gebruikgemaakt worden van een standaardbibliotheek met woorden, waardoor enkel de speciale code nog ruimte inneemt.

Exact omkeerbare compressie zal sommige bestanden langer maken 
Exact omkeerbare compressie kan niet alle mogelijke bestanden daadwerkelijk comprimeren. Er zullen ook bestanden zijn die door de gehanteerde compressiemethode in omvang gelijk blijven of toenemen. Anders gezegd, elk (exact omkeerbaar) compressiealgoritme moet noodzakelijkerwijs bij bepaalde invoerbestanden een uitvoerbestand genereren dat langer is dan het invoerbestand.

Het bovenstaande is eenvoudig te bewijzen met een telargument. Het aantal binaire bestanden van maximaal N bits is eindig. Het exact omkeerbare compressiealgoritme beeldt een-eenduidig dit eindige aantal bestanden op zichzelf af. Als er een bestand is dat in gecomprimeerde vorm geringer in omvang is, kunnen niet alle bestanden van die geringere omvang meer op zichzelf afgebeeld worden, en zal er dus minstens een zijn die door de compressie in omvang toeneemt.

Op een vergelijkbare manier heeft Claude Shannon in 1948 bewezen dat er een limiet is aan lossless compressie. Om die reden is de nooit gerealiseerde "uitvinding" van Jan Sloot, waarbij zestien willekeurige speelfilms lossless in 64 kilobyte zouden passen, theoretisch onmogelijk.

Dus elk exact omkeerbare compressiealgoritme kan een bestand genereren dat langer is dan het oorspronkelijke bestand. Een goed compressiealgoritme moet dus toegesneden zijn op de eigenschappen, zoals statistiek etc., van de te comprimeren bestanden. Wanneer de werkelijkheid afwijkt van de veronderstellingen waarop de compressor is gebaseerd, kunnen grote teleurstellingen het resultaat zijn.

Wanneer na compressie het uitvoerbestand langer blijkt te zijn dan het invoerbestand, kan compressie uiteraard beter achterwege worden gelaten. Het al of niet toegepast hebben van de compressie wordt doorgegeven aan de ontvanger. Dit kost ten minste een extra bit.

Niet-exact omkeerbare compressie
Lossy compression wordt gebruikt voor digitale formaten die een weergave zijn van een analoog signaal, bijvoorbeeld beeld en geluid.

Omdat het digitale formaat een weergave is van een analoog signaal is het niet noodzakelijk om het oorspronkelijke digitale signaal te kunnen reconstrueren en kan men de eis dat er geen informatie verloren mag gaan laten vallen. Daardoor is er een veel grotere mate van compressie mogelijk zonder dat het de toeschouwer of luisteraar, die alleen het gereconstrueerde analoge signaal waarneemt, opvalt dat het origineel niet identiek is aan het weer gedecomprimeerde signaal. Bij niet-exact omkeerbare compressiealgoritmes zijn, afhankelijk van de te comprimeren gegevens, compressies van meer dan 99% mogelijk, het gecomprimeerde bestand heeft dan dus een grootte die minder dan 1% bedraagt van de grootte van het ongecomprimeerde bestand.

Veelgebruikte niet-omkeerbare compressiealgoritmes zijn:
 JPEG is een algoritme met verlies van kwaliteit voor beeldcompressie
 MP3 en AAC voor digitale geluidsbestanden
 MPEG-2 voor videobestanden (voor dvd of digitale televisie DVB)

Methodiek 

Datacompressie verwijdert de zogenaamde redundantie (lett: 'overbodigheid') van de informatie in bestanden. Bestanden met bijvoorbeeld meer nullen dan enen, of meer enen dan nullen, vertonen redundantie, die met compressie kan worden verwijderd. Een gecomprimeerd bestand zal, als de compressie goed geslaagd is, geen of weinig redundantie vertonen. Om die reden heeft het daarom vaak weinig zin om een compressiebewerking te herhalen met de verwachting dat het bestand nog verder gecomprimeerd wordt. Compressie van willekeurige gegevens (bijvoorbeeld getallen verkregen uit een ideale toevalsgenerator), en dus niet redundant, is niet mogelijk. Voor een goede keuze van het compressie-algoritme (codec) is het van groot belang de aard van de bestanden die ermee zullen worden gecomprimeerd te kennen, omdat we anders een goede kans hebben met een langer 'gecomprimeerd' bestand te eindigen.

Het succes van compressie is afhankelijk van de interne structuur van de informatie. Herhalende patronen laten zich over het algemeen beter comprimeren, terwijl bestanden waarin al een vorm van compressie is toegepast niet of nauwelijks verder te comprimeren zijn. Dat laatste is bijvoorbeeld het geval bij veel digitale media zoals MP3, JPEG en diverse videoformaten.

Sommige goede compressiemethoden mogen niet door iedereen worden gebruikt omdat er een octrooi op rust.

Toepassingen 
Tegenwoordig wordt datacompressie voor verschillende toepassingen gebruikt, zoals:
 muziek
 beeld
 spraak
 computerdata, zoals tekstbestanden
 back-ups
 HTTP-compressie, voor websites
 Streaming media

Algoritmen 
Er bestaan verschillende algoritmen voor datacompressie, bijvoorbeeld:
 aritmetische codering,
 Burrows-Wheelertransformatie
 Dynamische Markovcodering
 haal-naar-vorencodering (move-to-front coding)
 Huffmancodering
 Lempel Ziv Welch,
 run-length encoding

Programma's 

Veel mensen werken met datacompressie door middel van compressieprogramma's voor algemeen gebruik. Bekende voorbeelden daarvan zijn:
 7-Zip
 ARC
 ARJ
 Bzip2
 Compress
 Gzip
 LHarc
 PKZip van Phil Katz
 SQLar
 WinZip van NicoSoft
 WinRAR
 WinACE

Zie ook 
 Beeldcompressie
 Codec
 Cryptografie
 Data-entropie

Externe links 
  Vergelijkingssite van compressie-programma's
  Compressie algoritmen
 Het ACCM-algoritme, een bewerkte versie van Markov modellen
 Lijst van bestandsformaten voor datacompressie
 Achtergrond artikel compressie en informatietheorie
 Profielwerkstuk over datacompressie (in de vorm van een website)

Dataopslag
Algoritme