RLEcompressie

RLEcompressie, of run-length encoding, is een eenvoudige verliesvrije compressietechniek die opeenvolgende identieke symbolen vervangt door een korte representatie van het aantal herhalingen gevolgd door het symbool zelf. Het idee is om lange reeksen gelijke elementen compact weer te geven, waardoor de grootte van de data afneemt als er lange runs voorkomen.

In de basisvorm scan je de data van begin tot eind. Als je een reeks dezelfde elementen ziet, sla je een paar op met het aantal herhalingen en het symbool. De meeste implementaties gebruiken één byte voor de lengte, waardoor een run van maximaal 255 herhalingen past. Voor data met veel variatie worden vaak ook “literal runs” gebruikt, waarin ongecodeerde blokken van tekens worden weggeschreven wanneer er geen lange runs zijn; dit voorkomt onnodige overhead bij zeer afwisselende data.

Toepassingen en varianten: RLE wordt veel toegepast bij eenvoudige grafische bestanden en bitmapbeelden, vooral als er grote gebieden met dezelfde kleur zijn. Het komt veel voor in oudere bestandsformaten en communicatiekanalen, zoals PackBits in TIFF en in sommige PCX- en faxgerelateerde systemen. Hoewel er geen generieke standaard is voor alle varianten, draait het vrijwel altijd om het zoeken naar opeenvolgende identieke symbolen en het coderen daarvan.

Voordelen en nadelen: RLE is eenvoudig te implementeren en snelle compressie/decompressie vereist weinig rekenkracht. Het is verliesvrij en effectief bij data met lange runs, maar kan de grootte vergroten bij data met veel variatie. De efficiëntie hangt sterk af van de karakteristiek van de input.

Voorbeeld: de reeks A A A B B C C C C D wordt gecodeerd als (3,A)(2,B)(4,C)(1,D), wat vaak wordt weergegeven als 3A 2B 4C 1D. De methode werkt lineair in de hoeveelheid data.