Lektion
Die Theorie — Lauflängenkodierung (RLE)
Die Lauflängenkodierung ersetzt jeden maximalen Lauf gleicher Symbole durch ein einziges Paar (Symbol, Anzahl). In der Anzeige landet nicht der Text, sondern zwei Zahlen: N Zeichen und R Läufe. Jede weitere Größe auf der Seite ist der Quotient dieser beiden.
Was die einzelnen Symbole bedeuten
N- die Zahl der eingehenden Zeichen — die Länge des Getippten, mehr nicht.
R- die Zahl der Läufe, also maximaler Blöcke eines wiederholten Symbols. R steigt überall dort um eins, wo sich zwei Nachbarn unterscheiden; gezählt werden Grenzen, nicht Zeichen.
L̄N/R, die mittlere Lauflänge. Sie allein entscheidet über das Ergebnis.ratioN/2R, alsoL̄/2. Über 1 ist die Ausgabe kleiner als die Eingabe.
Woher die Formel kommt
- Zähle Läufe, nicht Zeichen. In
0010111100001111unterscheiden sich die Nachbarn an fünf Stellen, also gibt es sechs Läufe und die Zeile zeigtR=6. - Die kodierte Größe ist
2Rund sonst nichts. Woraus die Läufe bestehen, geht nie in die Rechnung ein — sechs Läufe kosten zwölf Einheiten, ob es Pixel, Buchstaben oder Ziffern sind. - Teile:
ratio = N/2R = L̄/2. Die Nulllinie liegt damit beiL̄ = 2, und sie ist exakt erreichbar — tippeAABB, und die Balken zeigen 4 Bytes hinein, 4 Bytes hinaus. - Die beiden Richtungen sind nicht symmetrisch. Nach oben gibt es keine Grenze: ein einzelner Lauf von einer Million Zeichen wird zu einem Paar. Nach unten liegt der Boden bei
0.50×und ist nicht zu unterbieten, denn schlimmer als ein eigener Lauf je Zeichen geht es nicht.
So liest du, was du siehst
Alle vier Beispiele sind genau sechzehn Zeichen lang — deshalb lohnt es sich, sie als Satz zu lesen. Bildzeile hat drei Läufe und ergibt 6 Bytes. Klassische Läufe hat vier und ergibt 8. Bitmaske hat sechs und ergibt 12. Schlechtester Fall hat sechzehn und ergibt 32. Gleiche Länge hinein, und heraus kommt zwischen 6 und 32 Bytes — Faktor fünf, allein durch R entschieden. Tippe dann hello world: elf Zeichen, zehn Läufe, 20 Bytes. Gewöhnlicher Fließtext liegt am unteren Ende dieser Spanne, und genau deshalb ist RLE ein Bauteil von Kompressoren und keiner für sich.
- Setzt voraus
- Dass ein Paar genau 2 Einheiten kostet, dass Symbol und Anzahl gleich breit sind und dass eine Anzahl beliebig groß sein darf. Echte Kodierer geben der Anzahl eine feste Breite — ein Byte, also 255 — und müssen längere Läufe in mehrere Paare zerlegen, was die Nulllinie etwas über 2 schiebt. Die Gleichbreiten-Annahme scheitert am deutlichsten genau dort, wo RLE am besten ist: in einem 1-Bit-Faxscan ist das Symbol ein Bit, die Anzahl nicht.
- Versagt, wenn
- Der Boden bei
0.50×ist kein Mangel, den man wegkonstruieren könnte. Ein verlustfreier Kodierer muss umkehrbar sein, verschiedene Eingaben also auf verschiedene Ausgaben abbilden; und es gibt weniger kurze Zeichenfolgen als lange, auf die abgebildet werden könnte. Jedes Verfahren, das auch nur eine Eingabe verkürzt, verlängert daher eine andere. Das ist eine Abzählaussage, keine Eigenschaft der Lauflängenkodierung. PackBits im dritten Einblick oben drückt seinen schlechtesten Fall auf ein Steuerbyte je 128 — unter 1% — und weiter kommt niemand, denn der Boden lässt sich beliebig senken, aber nie erreichen. RLE trägt diese Kosten nur außen, in einer Anzeige, der man beim Wandern zusehen kann.
Aufgabe vollständig gelöst
-
Lauflängenkodierung von AAAAAABBBCCDDDDD in vier Paare 5 Schritte
Die Lauflängenkodierung macht aus AAAAAABBBCCDDDDD vier Paare. Berechnen Sie die Kompression und anschließend die genaue Bedingung, unter der dieses Verfahren eine Datei größer macht.
-
Die Kodierung ist die offensichtliche: Jeder Lauf wird durch das Zeichen und seine Länge ersetzt. Sechzehn Zeichen schrumpfen zu vier Paaren.
-
Zwei Zahlen beschreiben jede Eingabe für dieses Verfahren — ihre Länge und ihre Anzahl an Läufen — und ihr Verhältnis ist die mittlere Lauflänge. Hier beträgt sie 4.
-
Nun zählen wir ehrlich nach. Jedes Paar kostet zwei Token, ein Zeichen und eine Anzahl, sodass die Ausgabe 2R gegenüber einer Eingabe von N beträgt. Nichts anderes an den Daten spielt eine Rolle.
-
Das Verfahren gewinnt also genau dann, wenn 2R < N gilt, was umgeformt eine mittlere Lauflänge von über 2 ergibt. Hier steht 8 gegen 16 — eine saubere Halbierung — und die Ergebniszeile auf dem Panel drückt mit einem einzigen Symbol dasselbe aus.
-
Unterhalb dieser Schwelle verliert es, und bei einer mittleren Lauflänge von 1 verliert es maximal: Jedes Zeichen wird zu einem Paar, was die Datei verdoppelt.
Antwort
Das Werkzeug gibt N = 16 und R = 4 aus, eine mittlere Lauflänge von 4 und eine 2× Ersparnis. Diese Bedingung gilt es festzuhalten: RLE komprimiert genau dann, wenn die Läufe im Schnitt mehr als zwei betragen, und es ist eines der wenigen Kompressionsverfahren, dessen Gewinnschwelle eine einzelne Zahl ist, die man auf einen Blick prüfen kann. Geben Sie ABCD in das Feld ein und beobachten Sie, wie es auf die doppelte Größe anwächst. Das ist kein Mangel — es ist der Grund, warum RLE nur dort überlebt, wo Läufe konstruktionsbedingt garantiert sind: Fax-Abtastzeilen, dünnbesetzte Bitmaps und die flachen Bereiche eines JPEG nach der Quantisierung, niemals bei allgemeinem Text.
-
Lernpfad
Kompression von Hand
Quellen (3)
- Insight block 3 — PackBits, and the control byte that bounds its worst case: Adobe Systems, TIFF Revision 6.0, section 9 (PackBits Compression), 1992 — the format where Apple's variant became a standard compression mode.
- The run lengths themselves as the thing to be coded: S. W. Golomb, "Run-length encodings (Corresp.)." IEEE Transactions on Information Theory 12(3), 399–401, 1966.
- And the earlier paper that measured how long runs in real pictures actually are: J. Capon, "A probabilistic model for run-length coding of pictures." IRE Transactions on Information Theory 5(4), 157–163, 1959.