Datenkompression: Huffman-Codierung und Run-Length Encoding erklärt

Huffman-Codierung

Die Huffman-Codierung ist ein allgemeines Verfahren zur Codierung und Komprimierung, das entwickelt wurde, um die durchschnittliche Anzahl der benötigten Bits zur Übertragung eines Symbols zu minimieren, wenn mehrere unabhängige und statistisch gleichwertige Kopien des Symbols übergeben werden müssen. Diese Methode bestimmt, wie die verschiedenen Werte des Symbols als binäre Strings dargestellt werden können. Nehmen wir an, dass wir mit dem Symbol X Werte (x₁, ..., x_n) mit den Wahrscheinlichkeiten (p₁, ..., p_n) senden können. Die Idee ist, den häufigsten Werten von X kurze Codewörter zuzuweisen. Diese Methode funktioniert nicht, wenn die Benutzung eines Trennzeichens zwischen den Werten erforderlich ist.

Beispiel:

• x (0,5)
• 1 x (0,3)
• 2 x (0,15)
• 3 x (0,05)
• 4

Bei Verwendung von 00, 01, 10 und 11 müssen immer 2 Bits für den Wert von X verwendet werden. Wenn die Codewörter 0, 10, 110 und 111 verwendet werden, werden im Durchschnitt nur 1,7 Bits benötigt (weniger als 2).

Algorithmus der Huffman-Codierung

1. Wählen Sie die beiden Symbole mit der kleinsten Wahrscheinlichkeit (Xi, Xi).
2. Fassen Sie diese zu einem neuen Symbol zusammen (Yi = Y0 Y1).
3. Entfernen Sie die ursprünglichen Symbole aus der Liste und fügen Sie das neue Symbol mit der kombinierten Wahrscheinlichkeit hinzu.
4. Wiederholen Sie die Schritte 1 bis 3, bis nur noch ein Symbol übrig ist.

Run-Length Encoding (RLE)

Run-Length Encoding (RLE) ist eine Methode zur Komprimierung von Signalen, um die Übertragung von FAXen einfacher und effizienter zu gestalten. Ein Faxgerät durchsucht eine Seite Zeile für Zeile, indem es die Lichtintensität von weit entfernten Punkten jeder Zeile misst. Das Ergebnis ist eine Folge von Bits, die angeben, ob Punkte auf den Linien weiß (1) oder schwarz (0) sind. Wenn die Maschine 200 Zeilen pro Zoll scannt und 200 Punkte pro Zoll misst, wird eine Seite der Größe 8,5 x 11 Zoll mit 200 * 200 * 8,5 * 11 = 3,73 * 10⁶ Bits dargestellt. Mit einem 9600-bps-Modem würde dies 6,5 Minuten dauern. Wenn die Anzahl der Bits um das 20-fache reduziert würde, würde die Übertragung nur 20 Sekunden dauern.

Um diesen Kompressionsfaktor zu erreichen, überträgt die Maschine die Anzahl der aufeinanderfolgenden Nullen zwischen zwei Einsen anstelle einer langen Reihe von Nullen. Zum Beispiel wird die Zeichenfolge 1000...01 (mit 600 Nullen) durch die Darstellung der Anzahl der Nullen (i) kodiert. Wenn i = 600, dann ist die binäre Darstellung von 600 1001011000. Diese 10 Bits ersetzen die 600 Nullen.