Hoe werkt lossless datacompressie

Ook al is breedband internet tegenwoordig gemeengoed, het blijft interessant om bestanden van zo min mogelijke grootte door de pijplijnen te sturen. Vandaar dat muziekbestanden als mp3 worden verzonden, video als mpeg, software als zip-bestand, enzovoort. Maar hoe werken die compressietechnieken eigenlijk? In dit artikel komen de runlenght-, delta-, Huffman- en LZW-compressie aan bod.

Lossless

De strategieën die kunnen worden gebruikt om informatie te comprimeren, laten zich indelen in compressietechnieken die niets van de originele informatie verloren laten gaan (‘lossless’) en methoden die slechts in staat zijn het origineel te benaderen (‘lossy’). Er zijn met andere woorden methoden die perfect werken en er zijn slordige methoden. De lossless methoden moeten worden toegepast op informatie waarvan helemaal niets verloren mag gaan, zoals de programmeercode in software en in tekstverwerkingsbestanden. Programma’s als ZipIt en StuffIt maken daarom gebruik van compressietechnieken die een bestand zodanig verkleinen dat het later weer volledig identiek kan worden ‘uitgepakt’. We hebben tenslotte niets aan Photoshop of Microsoft Word die na het uitpakken ‘bij benadering’ doen waarvoor ze ooit zijn gemaakt…

Lossy

Lossy-compressie mag worden toegepast bij bestanden waarvan het iets minder erg is als er enige informatie verloren gaat, zoals gescande afbeeldingen. Alles draait hier om wat de gebruiker acceptabel vindt. Zolang een afbeelding er voor ons mensen mooi uitziet, kan een lossy compressie wegkomen met het feit dat de foto niet helemaal meer dezelfde kwaliteit heeft als het origineel. Groot voordeel van de lossy technieken is dat ze veel effectiever zijn dan de lossless methoden: ze kunnen bestanden wel vijftig keer zo klein maken. Echter, hoe groter de compressie, des te meer onvolkomenheden (ruis) er in het gecomprimeerde bestand terechtkomen, tot het punt waarop het menselijk oog ze gaat waarnemen. Kijk bijvoorbeeld maar eens goed naar jpeg’s op internet. Wie goed kijkt (soms is dit niet eens nodig) ziet vaak ‘blokvorming’ rond de details van een afbeelding.

Runlength

De verschillende strategieën bij datacompressie zijn het best uit te leggen aan de hand van twee relatief eenvoudige methoden. Bestanden bevatten bijna zonder uitzondering gedeelten waar een bepaald karakter zichzelf een aantal maal achtereen herhaalt. Denk hierbij aan een afbeelding van een strakblauwe hemel, of de vele spaties in witregels van tekstbestanden. Het is in zo’n geval handiger om te omschrijven dat een serie identieke karakters begint en hoeveel daarvan er achter elkaar staan, dan om al die karakters één voor één te beschrijven. Dit is precies de strategie die runlength volgt om bestanden te comprimeren. Een serie van acht nullen bijvoorbeeld wordt gecomprimeerd door één nul weg te schrijven die wordt gevolgd door het cijfer acht. Deze compressietechniek beperkt zich niet tot nullen of één ander specifiek karakter, maar kan worden toegepast op alle karakters in een bestand. Zo comprimeert PackBits, een toepassing van de runlenght-techniek, de serie 21, 21, 21, 21, 21 door hiervoor 21, -4 te noteren, de serie 5,5,5 door 5, -2 te noteren, enzovoort. Wordt een getal dus gevolgd door een getal met een minteken ervoor, dan betekent dit een serie van dit cijfer, die bestaat uit het absolute getal van het tweede cijfer, plus één.

verliesvrije_datacompressie_01
Afbeelding 1
Deltacompressie

Deltacompressie is van een vergelijkbare eenvoud. Deze methode neemt slechts het eerste getal uit een reeks onveranderd over en noteert van alle daarop volgende getallen het verschil (de deltawaarde) met het voorgaande. Deze methode leidt alleen tot echt kleinere bestanden als de verschillen tussen de opeenvolgende getallen niet te groot zijn, zoals bij geluidssignalen veelal het geval is. Tekst en software laten zich daarentegen slecht comprimeren door deze methode. Een voordeel van deze methode is weer dat nieuwe reeksen van opeenvolgende nullen kunnen ontstaan wanneer het signaal over een bepaalde periode hetzelfde blijft. Het bestand kan dan nog verder worden gecomprimeerd door er runlength compressie op los te laten. Deze combinaties van technieken worden overigens wel vaker toegepast om bestanden te verkleinen. Zo wordt runlength in de eindfase toegepast in onder andere jpeg- en mp3-compressie.

verliesvrije_datacompressie_02
Afbeelding 2
Huffman

Een geheel andere strategie bedacht A.D. Huffman in de jaren vijftig. Hij maakte gebruik van het algemeen geldende principe dat in een bestand een klein gedeelte van alle mogelijke karakters het overgrote deel van het totaal aantal karakters vormt. Zo bestaat 96% van een tekstbestand uit slechts 31 van de 128 mogelijke karakters uit de ASCII-tabel die tekstverwerkers gebruiken. Dit zijn de onderkasten (kleine letters) uit het alfabet, de komma, spatie en punt en de return. In de computer worden alle 128 karakters uit de ASCII-tabel weergegeven door één byte, die weer uit acht bits bestaat. Eén bit informatie bestaat uit twee toestanden: 0 (uit) of 1 (aan). Acht bit aan informatie bestaat uit 2 tot de macht 8 is 256 mogelijke toestanden. Dit is dus meer informatie, maar het kost ook meer ruimte om het op te slaan. Huffman kreeg daarom het idee om karakters die veel voorkomen uit minder bits te laten bestaan en de zeldzamere karakters uit meer bits. Immers, als 96% van een bestand uit minder bits bestaat dan normaal, móet het wel kleiner zijn dan het origineel, redeneerde hij.

verliesvrije_datacompressie_03
Afbeelding 3
Waarschijnlijkheid

De compressiemethode die Huffman vervolgens bedacht, is gebaseerd op de waarschijnlijkheid dat karakters voorkomen. Stel dat in de gemiddelde tekst de ‘a’ het meest voorkomt, gevolgd door de ‘e’, de ‘b’, enzovoort. De ‘a’ krijgt dan één bit (1) toegewezen, de ‘e’ twee bits (01), de ‘b’ vier bits (0010), enzovoort. Deze codes bestaan altijd uit een serie nullen, gevolgd door 1 en eventueel een nul of één. Zo ontstaat een tabel van karakters en de unieke serie bits waaruit ze zijn opgebouwd. Deze tabel wordt bij het comprimeren en decompressie (uitpakken) gebruikt om de karakters van het originele bestand om te zetten in nieuwe codes en vice versa. De lengte van deze codes is zoals gezegd variabel, terwijl de computer slechts kan omgaan met bytes van acht bits. De codes van de individuele karakters worden daarom samengevoegd tot bytes van acht bits en achter elkaar gezet. Decompressie bestaat uit het zoeken van een unieke code in de reeks, deze op basis van de tabel omzetten in een karakter, verder zoeken naar de volgende unieke code, enzovoort. Ook de Huffman-compressie wordt veel toegepast voor het verliesvrij verkleinen van beeld en geluid. Zo past Kodak het toe bij PhotoCD’s.

LZW

Deze compressiemethode ontleent zijn naam aan A. Lempel en J. Ziv, die de originele techniek ontwikkelden, en T. Welch, die later enkele verfijningen aanbracht. Het is een veelgebruikte methode om tekst, programmeercode, signalen, afbeeldingen en vergelijkbare bestanden te comprimeren. LZW maakt, net als de Huffman-compressie, gebruik van een tabel om data te comprimeren en weer uit te pakken. LZW gebruikt een tabel met 4096 codenummers, waarvan de eerste 256 enkele bytes representeren en de rest een serie bytes. Het codenummer 0000 staat dus voor de byte 0, 0001 voor de byte 1, 0255 voor de waarde 255, en 0256 voor bijvoorbeeld de serie bytes 145, 201 en 4, enzovoort. De inhoud van de tabel is variabel en krijgt pas gestalte op het moment dat de compressie plaatsvindt. LZW bekijkt het bestand en begint de tabel te vullen met series van bytes die het daarin tegenkomt.

Het gaat hier te ver om de algoritmen die dit voor elkaar krijgen precies te beschrijven. Het komt er ongeveer op neer dat LZW aan het begin van het bestand de tabel begint te vullen met karakters, vervolgens bij ieder daarop volgend karakter kijkt of deze al in de tabel staat, de volgordes van karakters bijhoudt, series formuleert en controleert of een bepaalde serie zich herhaalt, totdat het bestand volledig is doorlopen. Als de tabel klaar is, kunnen de series van bytes in het originele bestand worden omgezet in kleinere codenummers, en het resultaat is een gecomprimeerd bestand. Het uitpakken komt neer op het vertalen van de enkele bytes naar de serie bytes uit de tabel zoals die aan het begin van het comprimeren werd samengesteld.

verliesvrije_datacompressie_04
Afbeelding 4
Scroll Up

Pin It on Pinterest