Mit Google fortfahren
Wenn in einer langen Reihe immer wieder dasselbe Zeichen steht, musst du nicht jedes einzeln notieren. Du kannst zählen, wie oft es direkt hintereinander vorkommt. Das ist zum Beispiel bei einfachen Grafiken praktisch.
Was du lernen wirst
- Du erklärst die Idee der Lauflängenkodierung.
- Du wandelst Zeichenfolgen in eine Kurzform um.
- Du entschlüsselst eine kodierte Folge wieder.
- Du erkennst, wann das Verfahren Speicherplatz spart.
Die Grundidee
Die Lauflängenkodierung ist ein Verfahren, das gleiche Zeichen zusammenfasst, wenn sie direkt nebeneinander stehen. Sie kann Daten dadurch kürzer speichern.
Eine Gruppe gleicher Zeichen ohne Unterbrechung heißt Lauf. Für jeden Lauf notierst du seine Anzahl und sein Zeichen.
Die Folge lautet:
HHHHHAA
Sie hat zwei Läufe: fünf H und zwei A.
Eine mögliche Kurzform ist:
5H2A
Ein anderer Buchstabe beendet den bisherigen Lauf und beginnt einen neuen.
Interaktiver Lückentext wird geladen ...
So kodierst du eine Folge
Die Kodierung bedeutet, eine ursprüngliche Folge in eine vereinbarte Kurzform umzuwandeln. Du gehst von links nach rechts, zählst gleiche Zeichen und schreibst dann Anzahl und Zeichen auf.
Ausgangsfolge:
AAAABCCCCC
- A kommt viermal vor.
- B kommt einmal vor.
- C kommt fünfmal vor.
Die Kodierung lautet:
4A1B5C
Manche Vereinbarungen schreiben zuerst das Zeichen, zum Beispiel A4B1C5. Entscheidend ist: Kodierung und Dekodierung müssen dieselbe Reihenfolge verwenden.
Interaktive Quizfrage wird geladen ...
So entschlüsselst du die Kurzform
Die Dekodierung ist das Zurückwandeln der Kurzform in die ursprüngliche Folge. Du liest die Anzahl und schreibst das zugehörige Zeichen genau so oft auf.
Kodierte Folge:
2R4T3E
Entschlüsselung:
RRTTTTEEE
Beim Dekodieren wird nichts geraten: Jede Zahl sagt genau, wie oft das folgende Zeichen erscheint.
Interaktiver Lückentext wird geladen ...
Wann spart die Kodierung Speicherplatz?
Lange Läufe sind günstig für die Lauflängenkodierung. In einer einfachen Schwarz-Weiß-Grafik gibt es oft viele gleiche Bildpunkte. Ein Bildpunkt ist ein einzelner Punkt eines digitalen Bildes.
WWWWWWWWWWWW enthält zwölf W.
Die Kurzform 12W beschreibt dieselbe Folge viel kürzer.
Bei ABABABAB gibt es dagegen nur Läufe der Länge eins.
Die Kurzform 1A1B1A1B1A1B1A1B ist länger als die Ausgangsfolge.
Die Lauflängenkodierung ist verlustfrei. Das bedeutet: Nach dem Dekodieren sind die Daten genau gleich wie vor der Kodierung.
Interaktive Quizfrage wird geladen ...
Zahlen und Bits
Ein Bit ist die kleinste Informationseinheit im Computer. Es kann nur den Wert 0 oder 1 haben. Bei einer Bitfolge können daher die Längen der Läufe reichen, wenn der erste Wert bekannt ist.
Bitfolge:
00011111
Die Folge beginnt mit 0.
- drei Nullen
- fünf Einsen
Die Laufzahlen sind:
3 5
Bei Bitfolgen muss feststehen, ob der erste Lauf aus Nullen oder Einsen besteht. Sonst sind die Laufzahlen nicht eindeutig.
Interaktive Quizfrage wird geladen ...
Zusammenfassung
Die Lauflängenkodierung fasst gleiche Zeichen zusammen, die direkt nebeneinander stehen. Jeder Lauf wird mit seiner Länge und seinem Zeichen beschrieben.
Beim Dekodieren wiederholst du jedes Zeichen so oft, wie es die Zahl vorgibt. Lange Wiederholungen sparen oft Speicherplatz. Bei vielen kurzen Läufen kann die Kurzform dagegen länger werden.