Huffman’s compressiealgoritme

In dit artikel gaan wij het hebben over datacompressie, en Huffman’s compressiealgoritme (ook wel Huffman codering genoemd) in het bijzonder. Na het lezen van dit artikel heeft u hopelijk meer inzicht in wat datacompressie inhoudt, en hoe dat in zijn werk gaat.

Compressie is een algemeen goed in de huidige computerwereld. Met behulp van compressie kan informatie compacter opgeslagen worden, en dat gebeurt op vele plaatsen. Om enkele voorbeelden te geven, de u wellicht wel bekende ‘zip’-archieven, ‘mp3’ muziekbestanden, ‘jpeg’ fotobestanden, en zelfs webpagina’s worden veelal gecomprimeerd verzonden, ten doeleinde schijfruimte en verzendingstijd te besparen.

Huffman codering is inmiddels al een behoorlijk oude techniek. Ten tijde van de ontwikkeling van zijn compressiealgoritme was David Huffman een 27-jarige student aan het Amerikaanse MIT (Massachusetts Institute of Technology). We hebben het hier over 1952, meer dan 50 jaar geleden dus. Huffman is in 1999 overleden.

Ondanks de leeftijd van de Huffman codering wordt het nog steeds regelmatig gebruikt in vele moderne informaticatoepassingen. Alle bovengenoemde bestandstypen maken er bijvoorbeeld gebruik van, weliswaar in combinatie met andere compressiealgoritmes.

We zullen nu wat dieper ingaan op de verschillende compressietechnieken, en waar Huffman is gepositioneerd.

Bij compressie kan men over het algemeen twee hoofdcategorieën onderscheiden: lossy en lossless compressie. Bij lossy compressie wordt er informatie weggegooid, en is het dus niet meer mogelijk om de oorspronkelijke gegevens volledig te herstellen. Dit lijkt vrij nutteloos, maar de informatie die weggegooid wordt bestaat uit dingen die voor het menselijk oog of oor niet of nauwelijks waarneembaar zijn, en op die manier kan een flinke verkleining worden gerealiseerd zonder al te veel aan kwaliteit in te boeten. Een verkleining van 90% is doorgaans haalbaar. Voorbeelden van lossy compressie zijn ‘mp3’ muziekbestanden en ‘jpeg’ plaatjes.

Lossy compressie is echter niet altijd bruikbaar. In het geval van een tekstbestand bijvoorbeeld, zou het behoorlijk vervelend zijn als er plotseling letters of leestekens zouden verdwijnen. Voor die gevallen is er lossless compressie. Deze werkt op basis van substitutie, en behaalt over het algemeen behoorlijke resultaten, maar niet zo goed als die van lossy compressie. Over het algemeen kan men spreken van verkleiningspercentages van rond de 50%. Lossless compressie word voornamelijk gebruikt voor archivering van data en uitvoerbare bestanden in bijvoorbeeld ‘zip’-archieven, en ook voor hoge kwaliteit beeld en geluid in het ‘png’ beeldformaat en het ‘flac’ audioformaat.

Huffman codering valt in de categorie van lossless compressiealgoritmes. Het heeft daar de grootste concurrentie van het eveneens populaire Lempel-Ziv algoritme. Vergeleken met Lempel-Ziv kiest Huffman voor een andere benadering, maar beiden hebben hun voordelen. In de praktijk wordt Huffman dan ook in combinatie met Lempel-Ziv gebruikt. Dezelfde praktijk zie je ook bij de lossy compressieformaten zoals ‘jpeg’. Huffman wordt dan gebruikt als extra laag bovenop de lossy algoritmes, om nog wat extra ruimtewinst eruit te persen.

Laten we in wat meer detail kijken naar hoe de Huffman compressie werkt. Zoals al eerder vermeld, werken lossless compressieformaten op basis van substitutie, dat wil zeggen, ze vervangen een vaak voorkomend patroon door een korter patroon, dat vervolgens in een ‘woordenboek’ opgeslagen wordt zodat bij het decoderen de oorspronkelijke informatie weer hersteld kan worden.

Om een voorbeeld ter illustratie te geven, stel dat je een regel tekst hebt waarin vier tekens voorkomen, de letters: a, b, c en d. De computer slaat deze tekst in binair formaat op, waarbij hij elk teken laat bestaan uit een vast aantal enen en nullen (bits), bijvoorbeeld: a=00, b=01, c=10 en d=11. Op die manier zal de regel ‘aabc’ als ‘00 00 01 10’ worden opgeslagen.

Stel echter dat als wij naar de waarschijnlijkheid van deze tekens kijken, we zien dat de letter a veel vaker voorkomt dan de rest en een waarschijnlijkheid heeft van 70%, terwijl de letter b 20% kans heeft, en de letters c en d een kans van 5%.

Wat de Huffman codering vervolgens doet, is op basis van deze kansen de bits voor elk teken herverdelen. Dit ziet er als volgt uit: a=0, b=10, c=110 en d=111. Zoals je ziet heeft het teken dat het meest voorkomt nu een veel kortere representatie dan de weinig gebruikte tekens.

Wanneer je dit wat verder uitwerkt blijkt dat het voor een dergelijk kleine set van tekens niet zo heel veel uitmaakt. Maar bij een groter tekstbestand met het volledige alfabet kan er een behoorlijke winst behaald worden door bijvoorbeeld de letter ‘a’ minder ruimte in te laten nemen ten koste van de letters ‘q’ en ‘ô’, of bepaalde weinig gebruikte leestekens.

Huffman is een eenvoudig algoritme dat enkel simpele bewerkingen doet, en zodoende efficiënt is met zijn tijd. De meest tijdrovende stappen in het Huffman coderen zijn het samenstellen van de waarschijnlijkheidstabel, waarbij je het volledige te coderen bestand moet doorlopen en de voorkomens van elk teken moet tellen, en het daadwerkelijk coderen van het bestand, waarbij je nogmaals het volledige te coderen bestand moet doorlopen om de tekens naar hun nieuwe representatie om te zetten.

En daar valt ook nog wat op te beknibbelen. Het bouwen van een waarschijnlijkheidstabel is namelijk niet altijd noodzakelijk. Weet je bijvoorbeeld dat het betreffende bestand een Engelse tekst bevat, dan is het ook mogelijk om een van tevoren samengestelde waarschijnlijkheidstabel op basis van statistische voorkomensfrequenties van letters in Engels schrift te gebruiken.

In de praktijk blijkt dat dit soort compressie goed werkt voor veel soorten data, en zelfs bovenop andere compressiealgoritmes. Huffman herverdeelt de bits naar hun gebruik, doet dat optimaal, kan dat ook snel, en in het ergste geval blijft het bestand even groot. Daardoor is het algoritme, zelfs 50 jaar nadat het bedacht is, nog steeds actueel. En dat gebeurt niet vaak in de Informatica.

Grauw