Datacompressie

Er zijn verschillende typen datacompressie:

1. exact omkeerbaar (Engels: lossless, zonder kwaliteitsverlies)
2. niet-exact omkeerbaar (Engels: lossy, met kwaliteitsverlies)

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%.

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 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.

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)

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.

Tegenwoordig wordt datacompressie voor verschillende toepassingen gebruikt, zoals:

• muziek
• beeld
• spraak
• computerdata, zoals tekstbestanden
• back-ups
• HTTP-compressie, voor websites
• Streaming media

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

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

• Beeldcompressie
• Codec
• Cryptografie
• Data-entropie

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