Datacompressie

Van Wikipedia

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.

Inhoud

1 Typen datacompressie
2 Exact omkeerbare compressie zal sommige bestanden langer maken
3 Methodiek
- 3.1 Tekstbestanden
4 Algoritmen
5 Programma's
6 Zie ook
7 Externe links

[bewerk] Typen datacompressie

Er zijn verschillende typen datacompressie:

exact omkeerbaar (Engels: lossless)
niet-exact omkeerbaar (Engels: lossy)

In het eerste geval is het mogelijk het oorspronkelijke bestand exact bit-voor-bit weer terug te krijgen, wat bijvoorbeeld essentieel is voor tekstdocumenten; in het tweede geval niet. Lossy compression wordt bijv. in de elektronische beeldverwerking gebruikt en bij het comprimeren van geluidsbestanden. Door de eis van geen verlies van informatie te laten vallen is er bij plaatjes of geluidsbestanden een veel grotere mate van compressie mogelijk, zonder dat het de toeschouwer of luisteraar opvalt dat het origineel niet identiek is aan het weer gedecomprimeerde beeld. JPEG is een lossy algoritme voor beeldcompressie, MP3 voor digitale geluidsbestanden, MPEG-2 voor videobestanden (voor DVD of Digitale Televisie DVB).

[bewerk] 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 16 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 ernstige teleurstellingen het resultaat zijn.

Wanneer na compressie het output-bestand langer blijkt te zijn dan het input-bestand, kan compressie uiteraard beter achterwege worden gelaten. Het al of niet toegepast hebben van de compressie wordt doorgegeven aan de ontvanger. Dit kost tenminste een extra bit.

[bewerk] 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.

[bewerk] 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. Over het algemeen volgt dit soort algoritmen het vierstappenmodel. Op tekstbestanden zijn echter door gebruik van andere algoritmen veel grotere 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% 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.

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