Naar inhoud springen

Run-length encoding

Uit Wikipedia, de vrije encyclopedie

Run-length encoding, kortweg RLE, is het vervangen van herhalende patronen in data door het aantal herhalingen plus wat herhaald moest worden. Een voorbeeld: stel dat we de volgende tekenreeks in het alfabet [a-z]* willen comprimeren:

dghakaaaaaaaaaaaaaabbbbaaakhffff

We kunnen dan ons alfabet uitbreiden met de tekens [0-9] om herhalingen aan te geven, en zouden dan de tekst als volgt kunnen comprimeren:

dghak14a4b3akh4f

Er zijn vele varianten van het RLE-algoritme. Sommige bijvoorbeeld kunnen alleen tekens herhalen, andere kunnen ook "blokken" met tekens herhalen.

Over het algemeen is RLE-compressie weinig effectief, en in veel gevallen zal de lengte van een reeks gegevens zelfs iets toenemen. RLE blijkt in de praktijk alleen geschikt bij grote hoeveelheden herhalende data.

Een geval waarin RLE uitermate effectief is, is het comprimeren van grafische afbeeldingen zoals logo's en animaties. In deze beelden bevinden zich vaak grote gedeelten met pixels van dezelfde kleur. In sommige gevallen kan de bestandsgroote van een afbeelding of animatie door RLE tientallen keren worden verkleind. Voorbeelden van grafische compressieschema's die gebruikmaken van RLE zijn TIFF en de Quicktime(c) Animation-codec. In beide gevallen is de compressie lossless, in tegenstelling tot compressieschema's als JPG waarbij naast RLE ook informatie wordt verwijderd ten gunste van de bestandsgrootte.

In animaties kan RLE worden gebruikt om te comprimeren binnen een frame, en bovendien om te comprimeren tussen frames onderling. Dan wordt er gebruikgemaakt van keyframes waarin gedeelten van het beeld worden vastgelegd die in de opvolgende frames gelijkblijven.