Komprimieren mit Lauflängen

1. Läufe

Eine Zeile eines Bildes aus wenigen Farben besteht meist aus langen Stücken derselben Farbe: links Hintergrund, dann ein Rand, dann eine Fläche. So ein Stück heißt Lauf, und statt »Weiß, Weiß, Weiß, Weiß, Weiß, Weiß« genügt »6 × Weiß«. Diese Lauflängencodierung (englisch Run-Length Encoding, RLE) ist das einfachste Verfahren zum Komprimieren, und sie ist verlustfrei: Aus den Läufen kommt genau die Zeile zurück.

Hier ist die Diskette aus dem GIF-Labor, 16 × 16 Pixel in 4 Farben. Neben jeder Zeile stehen ihre Läufe. Wähl eine Farbe und klick in das Bild, oder zieh mit gedrückter Maustaste: Die Läufe und die Größe ändern sich mit.

Jeder Lauf braucht zwei Bytes, eins für die Länge und eins für die Farbe. Die Diskette hat lange, ruhige Zeilen und wird viel kleiner. Mal ein Schachbrett hinein, und es wird größer als das Bild selbst: Jedes Pixel ist dann ein eigener Lauf und braucht zwei Bytes statt einem.

2. Einrichten

Lege im Terminal (StrgJ) einen Ordner an und öffne ihn mit StrgK StrgO:

mkdir /workspace/rle

# Lauflängen: statt »AAAA« steht »4A« da.

# Als Text: 'WWWWWWBBBWWWW' wird '6W3B4W'
def rle(text)
end

def unrle(code)
end

# Als Bytes: immer zwei Zahlen, die Länge (1 bis 255) und das Byte
def rle_bytes(data)
end

def unrle_bytes(bytes)
end

p rle('WWWWWWBBBWWWW')

# Lauflängen: statt »AAAA« steht »4A« da.


def rle(text):
    """Als Text: 'WWWWWWBBBWWWW' wird '6W3B4W'"""
    return ''


def unrle(code):
    return ''


def rle_bytes(data):
    """Als Bytes: immer zwei Zahlen, die Länge (1 bis 255) und das Byte"""
    return []


def unrle_bytes(numbers):
    return b''


print(rle('WWWWWWBBBWWWW'))

3. Als Text

Schreib rle. Es geht den Text Zeichen für Zeichen durch, zählt, wie oft dasselbe Zeichen hintereinander kommt, und schreibt für jeden Lauf die Zahl und das Zeichen hin.

Dann unrle, andersherum: aus '6W3B4W' wieder 'WWWWWWBBBWWWW'. Eine Zahl kann mehrere Ziffern haben, '12A' sind zwölf A.

4. Wenn Ziffern im Text stehen

Als Text geht es nur, solange der Text selbst keine Ziffern enthält: Sonst weiß niemand, welche Ziffern Längen sind und welche zum Text gehören. Echte Programme schreiben deshalb immer genau zwei Bytes für jeden Lauf, eins mit der Länge und eins mit dem Byte, das sich wiederholt. Dann ist klar, was was ist, egal was in der Datei steht. Weil ein Byte höchstens 255 sein kann, wird ein längerer Lauf geteilt: 300-mal A sind [255, 65, 45, 65].

5. Wie gut ist das?

Lade drei Dateien zum Ausprobieren in den Ordner: die Diskette, achtfach vergrößert, als rohe Pixel (128 × 128 Bytes, jedes die Nummer einer Farbe), die Spezifikation von GIF als Text, und ein Foto als JPEG.

wget https://workspace.hackschule.de/rle/diskette.raw
wget https://workspace.hackschule.de/lzw/spec-gif89a.txt
wget https://workspace.hackschule.de/jpeg/44-baseline.jpg

Lass dein Programm für jede ausgeben, wie groß sie ist und wie viele Zahlen rle_bytes daraus macht, und prüf dabei, ob unrle_bytes wieder genau die Datei ergibt.

In einem Text sind Läufe selten: Außer Leerzeichen und Linien aus - und = kommt kaum ein Zeichen zweimal hintereinander, und jedes einzelne kostet jetzt zwei Bytes. Im JPEG ist fast jedes Byte ein Lauf der Länge 1.

6. RLE in Fax und JPEG

Ein Faxgerät tastet eine Seite Zeile für Zeile ab, jede Zeile 1728 Pixel breit, und jedes Pixel ist weiß oder schwarz. Eine Zeile Text besteht dann aus langen weißen Läufen mit kurzen schwarzen dazwischen. Das Fax schickt nur die Längen der Läufe, abwechselnd weiß und schwarz, sodass es die Farbe gar nicht mitschicken muss, und codiert diese Längen mit festen Huffman-Codes: Häufige Längen bekommen kurze Codes.

JPEG macht etwas Ähnliches mit den Nullen. Nach der Quantisierung sind die meisten der 64 Zahlen eines Blocks 0. Jedes Symbol in der AC-Tabelle sagt deshalb zweierlei: wie viele Nullen vor der nächsten Zahl stehen, also einen Lauf, und wie viele Bits diese Zahl hat. Wie das genau aussieht, steht in Eine JPEG-Datei decodieren.

7. Weiter geht's

• PackBits: Damit Dateien ohne Läufe nicht doppelt so groß werden, kennt das Verfahren PackBits (von Apple, auch in TIFF) zwei Sorten von Stücken. Ein Byte n von 0 bis 127 heißt: Die nächsten n + 1 Bytes kommen so, wie sie sind. Ein Byte von 129 bis 255 heißt: Das nächste Byte kommt 257 − n-mal. Schreib packbits und unpackbits und vergleich mit rle_bytes.
• Spalten statt Zeilen: Lies diskette.raw spaltenweise statt zeilenweise. Wird es kleiner oder größer? Warum?
• Huffman für die Längen: Zähl, welche Längen in diskette.raw vorkommen, und überleg, wie viele Bits sie mit Huffman bräuchten.