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.