Kjør lengdekoding

Den RLK- koding ( engelsk RLK-koding , RLE for kort ), også den fortløpende koding , er en enkel tapsfri komprimeringsalgoritme , og tilhører gruppen av entropi-kodere . Den er egnet for komprimering av lengre repetisjoner av symboler.

idé

Den grunnleggende ideen til algoritmen er å erstatte hver sekvens av identiske symboler med deres nummer og, om nødvendig, symbolet. Dette betyr at bare stedene der symbolet endres i meldingen er merket. Siden lengdespesifikasjonen bare vokser logaritmisk sammenlignet med lengden på sekvensen , sparer du betydelig lagringsplass, spesielt med lange repeterende sekvenser . Motsatt, jo kortere repetisjoner, jo lavere er besparelsene.

Kjørelengdekoding brukes i dag som et forhåndskodningstrinn (f.eks. I bildekomprimering , for eksempel JPEG ) for å spare innsats i det følgende kodingstrinnet. (F.eks. Sparer Huffman-koding å se på lengre symboler, siden disse allerede er redusert.)

Eksempel:

I stedet for en sekvens med fem repetisjoner av karakteren 0 og tre ganger 1

0000 0111

du bare sparer

5 3

Startsymbolet må derfor være kjent eller kodet i tillegg.

Jo lenger en enkelt episode er, jo større er besparelsene, fordi

  • for 10 repetisjoner trenger du to desimaler,
  • for 100 repetisjoner trenger du tre desimaler,
  • for 1000 repetisjoner trenger du fire desimaler osv.

Det samme gjelder andre nummersystemer .

Fremgangsmåte

Bitstrenger

Det er bare to alternativer for koding av bitsekvenser: en sekvens av nuller eller en sekvens av en. Hver sekvens av nuller blir garantert fulgt av minst en - og omvendt også. Det eneste unntaket er når slutten på meldingen er nådd.

Koderen er nå enig med dekoderen hvilken bit til å begynne med. Dette kan enten være ved konvensjon eller for eksempel med en ekstra bit i begynnelsen. Lengdene på null og én sekvens overføres deretter vekselvis. Dekoderen trenger da ikke å gjøre noe annet enn å sende ut et tilsvarende antall null eller en bit for hver mottatt verdi.

Eksempel:

Startsekvensen er:

1111 1110 0000 1000 0001 1111

Den er kodet fra dette:

7 5 1 6 5

Minimum antall nødvendige binære sifre er tre, fordi dette dekker tallområdet fra 0 til 7. Den komprimerte sekvensen blir deretter binærkodet

111 101 001 110 101

De opprinnelige 24 bitene kunne reduseres til 15 bits.

Flerverdisymbolsekvenser

Når du komprimerer symbolsekvenser som består av et alfabet med mer enn to symboler, er det ikke lenger klart hvilket symbol som følger etter (f.eks. Byte har et alfabet med 256 mulige tegn). I tillegg til antall repetisjoner, må også symbolet som utgjør sekvensen sendes.

En spesiell funksjon her er at den komprimerte meldingen til og med kan bli større hvis lagringsplassen for antall repetisjoner er større enn selve sekvensen.

Eksempel:

Startsekvensen er:

AAAA ABBB BBBB CDDD EE

Den er kodet fra dette:

{A, 5}, {B, 7}, {C, 1}, {D, 3}, {E, 2}

I prinsippet kan et symbol bestå av to bokstaver i stedet for bare en:

{AA, 2}, {AB, 1}, {BB, 3}, {CD, 1}, {DD, 1}, {EE, 1}

I verste fall (ingen repetisjoner) ville den "komprimerte" meldingen være større enn originalen. Fra episoden

ABCD

ville

A1B1C1D1.

gjennomføring

Den grunnleggende algoritmen (uten optimaliseringer) er enkel å implementere: 

#include <stdio.h>

int main()
{
   int n = 1; /* Anzahl der Wiederholungen */
   int ch = -1; /* Aktuelles Zeichen */
   int prev_ch = getchar(); /* Vorheriges Zeichen */

   do {
      ch = getchar();

      if ((ch != prev_ch) || (n == 255)) /* Symbol/Wiederholungen-Tupel ausgeben, falls ein anderes Symbol kommt oder die maximal darstellbare Anzahl erreicht. */
      {
         /* printf("%c%c", prev_ch, n); */ /* Binäre Ausgabe */
         printf("%c, %d\n", prev_ch, n); /* Lesbare Ausgabe als 2er-Tupel */

         n = 0; /* Beginn einer neuen Folge */
      }

      prev_ch = ch;
      ++n;
   } while (ch != EOF);

   return 0;
}

Modifikasjoner

Noen ganger er det veldig få repetisjoner i en melding. For å forhindre at hver enkelt forekomst i et flerverdig alfabet blir erstattet av en tuple med lengde 1 (f.eks.  ABC→ A1B1C1), blir bare sekvenser av en viss lengde (f.eks. Fire eller flere ) kodet.

Men da trenger du et spesialtegn ( escape-tegn ), som indikerer at en komprimert tuple følger. Ideelt sett vises ikke dette spesielle tegnet eller symbolet i meldingen ellers, ellers velger man et symbol som man antar at det sjelden forekommer. Det spesielle ved dette symbolet er at det må kodes som en tupel hver gang (selv om det bare forekommer en gang), ellers er det ikke mulig å skille mellom symbolet og tupelen.

Eksempel :

Den opprinnelige meldingen er:

Auus die Maaaaauuuuus (Lengde: 21 tegn)

Vi velger tegnet “s” som fluktkarakter (for klarhetens skyld). I tillegg koder vi bare sekvenser som inneholder minst tre repetisjoner:

Auuss1 die Msa5su5ss1 (Lengde: 21 tegn)

Hvis en bokstav gjentas mer enn tre ganger, eller hvis det er rømningstegnet , indikerer utgangen av rømningstegnet at en tupel med lengdespesifikasjon følger. Dette følges av antall repetisjoner og til slutt det tilsvarende symbolet.

Fluktkarakteren resulterer faktisk i ytterligere minnekrav, men i dette tilfellet kompenseres dette ved lagring i lengde 1-sekvenser. Meldingen ville være naivt kodet som følger:

1A2u1s_1d1i1e_1M5a5u1s (Lengde: 22 tegn)

Med PCX -filformatet brukes et annet escape-tegn avhengig av antall repetisjoner (disse utgjør en fjerdedel av tegnsettet i PCX), slik at escape- og lengdetegn sammenfaller og danner ett tegn.

applikasjoner

Kjørelengdekoding brukes i kombinasjon med en modifisert Huffman-koding for faksoverføring i henhold til ITU-T- anbefaling T.30 ("G3 faks"). Løpslengdekodingen oppnår gode resultater, spesielt når du overfører svarte og hvite sider, siden lange hvite områder veksler med kortere svarte områder.

Ved tapsfri komprimering av bilder blir kjørelengdekoding brukt på de enkelte koeffisientene etter transformasjonen til frekvensdomenet. Spesielt etter kvantiseringen er det vanligvis mange identiske verdier eller nuller som effektivt kan komprimeres med løpskoding. Deretter komprimeres disse "forhåndskomprimerte" dataene ytterligere med Huffman-kodingen .

Filformater

Kjente filformater som bruker kjørelengdekoding er noen eldre grafiske formater som Windows Bitmap , GEM Image , Targa eller PCX . Under Microsoft Windows brukes filtypen * .rle vanligvis til RLE-komprimerte bilder .

litteratur

  • David Salomon: Datakomprimering: Den komplette referansen . 4. utgave. Springer, 2007, ISBN 978-1-84628-602-5 .

Individuelle bevis

  1. 30 T.30: Prosedyrer for dokumentfaksoverføring i det generelle koblede telefonnettet. ITU-T, åpnet 15. august 2013 .