Visual Basic - Technik, FAQ, Tricks, Beispiele

Home / Workshops / RLE / Grundlagen

Grundlagen und Beispiel

RLE steht für "Run Length Encoding", was auf deutsch etwa mit "Codierung nach der Lauflänge" übersetzt werden könnte. Dies ist ein komplizierter Name für einen im Grunde sehr einfachen Algorithmus...

Das Prinzip

In dem zu komprimierenden Text werden sich wiederholende Zeichen gesucht. Diese werden ersetzt durch eine bestimmte Markierung ("Achtung, hier kommt eine Wiederholung!"), der Anzahl der Wiederholungen sowie dem zu wiederholenden Zeichen. Statt das Zeichen x-Mal zu speichern, werden also nur noch 3 Zeichen benötigt.

Ein einfaches Beispiel

In dem 38 Zeichen langen Text
bla bla xxxxxxxxxx bla bla yyy bla bla
könnten alle fett markierten Stellen derart ersetzt werden. Aufgrund der Art der Komprimierung macht eine entsprechende Ersetzung allerdings erst bei mindestens 4 Wiederholungen Sinn. Daher wird der Beispieltext folgendermaßen durch RLE dargestellt:
bla bla [Markierung][10]x bla bla yyy bla bla

Es werden also nur noch 31 Zeichen benötigt.

Markierungs-Probleme

Das Markierungs-Zeichen wird für die Komprimierung verwendet. Wenn die Markierung selbst im zu komprimierenden Text vorkommt, muss sie ersetzt werden durch die Folge [Markierung][1][Markierung]. Ansonsten würde es beim DeKomprimieren zu Fehl-Interpretationen kommen. Daher sollte das Markierungs-Zeichen mit Bedacht gewählt werden. Denkbar sind u.a. folgende Alternativen:

  1. Es wird immer ein bestimmtes Zeichen (z.B. "x") verwendet. Vorteil: Sehr einfach; Nachteil: Eventuell wird gerade dieses Zeichen sehr häufig verwendet.
  2. Das sich wiederholende Zeichen selbst dient als Markierung. Vorteil: Unabhängigkeit von der Vorkommens-Anzahl; Nachteil: Einfache (also 2 Zeichen lange) Wiederholungen werden durch die Ersetzung auf drei Zeichen verlängert (kommt gerade in Text-Dokumenten sehr häufig vor).
  3. Es wird genau das Zeichen verwendet, welches am wenigsten vorkommt. Vorteil: Bestes Ergebnis; Nachteil: Minimum-Bestimmung kann u.U. aufwendig sein.
Alle diese Möglichkeiten sind bereits in RLE-Algorithmen eingesetzt worden. Das Ziel dieses Workshops wird erstmal die dritte Alternative sein.

Eine Lösung ohne extra Markierungsbyte wird daran anschließend vorgestellt.


...>>

© Jost Schwider, 21.01.2001-05.05.2005 - http://vb-tec.de/rle1.htm