Nederlands
Menu

Wat is Run-length encoding?

Methode voor verliesvrije compressie die gegevens kleiner maakt door elk stuk met dezelfde opeenvolgende waarde (een run) te vervangen door het paar van die waarde en de lengte van de run. De reeks zwart-witte pixels 0000000011110000 kan bijvoorbeeld worden geschreven als „8 keer 0, 4 keer 1, 4 keer 0”. Ze werkt goed bij gegevens waarin dezelfde waarde lang aanhoudt, zoals tekeningen op een grotendeels witte achtergrond, faxbeelden en beelden met grote vlakken in één kleur. Bij gegevens waarvan de waarden snel wisselen, zijn de runs kort en kan het resultaat zelfs groter worden dan het origineel. Ook RLE genoemd.

Japanse benaming: ランレングス符号化

“Run-length encoding” komt voor in 2 oefenvragen uit 1 onderwerpen, bijv. Basis van informatietheorie en codering.

Vakgebied: Basis van informatietheorie en codering

Nu oefenen: vragen over Run-length encoding

De tekenreeks van 40 tekens AAAAAAAAAAAABBBBCCCCCCCCCCCCCCCCCCCCDDDD (12 keer A, 4 keer B, 20 keer C en 4 keer D) wordt gecomprimeerd met run-length encoding, die elke reeks van hetzelfde opeenvolgende teken weergeeft als een paar „teken (1 byte) en aantal (1 byte)”. De oorspronkelijke tekenreeks gebruikt 1 byte per teken. Als de compressieverhouding wordt gedefinieerd als „grootte na compressie ÷ grootte voor compressie”, wat is dan de compressieverhouding?

  1. A10%
  2. B20%
  3. C80%
Antwoord en toelichting tonen

Antwoord: B. 20%

Er zijn vier reeksen van hetzelfde teken (runs), voor A, B, C en D, dus de gecomprimeerde gegevens zijn 4 × 2 = 8 bytes. Het origineel is 40 bytes, dus de compressieverhouding is 8 ÷ 40 = 0,2, oftewel 20%. Run-length encoding maakt gegevens kleiner naarmate dezelfde waarde langer aanhoudt.

Welke gegevens worden met run-length encoding waarschijnlijk het kleinst?

  1. AEen tekening met zwarte lijnen op een witte achtergrond, weergegeven als een zwart-witbeeld met twee niveaus
  2. BEen beeld zoals een foto, waarin de waarden van naburige pixels fijn variëren
  3. CGegevens na versleuteling, waarin nullen en enen willekeurig gerangschikt lijken
Antwoord en toelichting tonen

Antwoord: A. Een tekening met zwarte lijnen op een witte achtergrond, weergegeven als een zwart-witbeeld met twee niveaus

Run-length encoding geeft de lengte van een reeks van dezelfde waarde (een run) weer als een getal, dus gegevens waarin dezelfde waarde lang aanhoudt, krimpen het meest. In een tekening met twee niveaus en een grotendeels witte achtergrond volgen witte pixels elkaar over lange stukken op, zodat het effect groot is; ook faxcodering gebruikt dit idee. Bij gegevens waarvan de waarden fijn variëren, zijn de runs kort en kan het resultaat zelfs groter worden dan het origineel.

“Run-length encoding” in de toelichting

Vragen met “Run-length encoding” (2)

  1. De tekenreeks van 40 tekens AAAAAAAAAAAABBBBCCCCCCCCCCCCCCCCCCCCDDDD (12 keer A, 4 keer B, 20 keer C en 4 keer D) wordt gecomprimeerd met run-length encoding, die elke reeks van hetzelfde opeenvolgende teken weergeeft als een paar „teken (1 byte) en aantal (1 byte)”. De oorspronkelijke tekenreeks gebruikt 1 byte per teken. Als de compressieverhouding wordt gedefinieerd als „grootte na compressie ÷ grootte voor compressie”, wat is dan de compressieverhouding?
  2. Welke gegevens worden met run-length encoding waarschijnlijk het kleinst?

Verwante termen

Binair symmetrisch kanaal Compressie met verlies Forward error correction (FEC) Gemiddelde codelengte Hamming-afstand Hamming-code Huffman-code Informatie-entropie Informatie-inhoud Ongelijkheid van Kraft

Naar de woordenlijst