Wie verlustfreie Datenkomprimierung funktioniert | Quanta-Magazin

Da täglich mehr als 9 Milliarden Gigabyte an Informationen im Internet unterwegs sind, suchen Forscher ständig nach neuen Möglichkeiten, Daten in kleinere Pakete zu komprimieren. Modernste Techniken konzentrieren sich auf verlustbehaftete Ansätze, die eine Komprimierung durch den absichtlichen „Verlust“ von Informationen aus einer Übertragung erreichen. Google hat beispielsweise kürzlich eine verlustbehaftete Strategie vorgestellt, bei der der sendende Computer Details aus einem Bild löscht und der empfangende Computer mithilfe künstlicher Intelligenz die fehlenden Teile errät. Sogar Netflix verwendet einen verlustbehafteten Ansatz und verringert die Videoqualität, wenn das Unternehmen feststellt, dass ein Benutzer die Inhalte auf einem Gerät mit niedriger Auflösung ansieht.

Im Gegensatz dazu gibt es derzeit nur sehr wenig Forschung zu verlustfreien Strategien, bei denen die Übertragung kleiner gemacht wird, aber keine Substanz geopfert wird. Der Grund? Verlustfreie Ansätze sind bereits bemerkenswert effizient. Sie unterstützen alles, vom JPEG-Bildstandard bis zum allgegenwärtigen Software-Dienstprogramm PKZip. Und das alles wegen eines Doktoranden, der einfach nach einem Ausweg aus einer harten Abschlussprüfung suchte.

Vor siebzig Jahren stellte ein Professor des Massachusetts Institute of Technology namens Robert Fano den Studenten seines Informationstheoriekurses die Wahl: eine traditionelle Abschlussprüfung abzulegen oder einen führenden Algorithmus zur Datenkomprimierung zu verbessern. Fano hat seinen Schülern möglicherweise mitgeteilt, dass er der Autor dieses bestehenden Algorithmus war oder dass er seit Jahren nach einer Verbesserung suchte. Was wir wissen ist, dass Fano seinen Schülern die folgende Herausforderung stellte.

Stellen Sie sich eine Nachricht vor, die aus Buchstaben, Zahlen und Satzzeichen besteht. Eine einfache Möglichkeit, eine solche Nachricht zu kodieren, besteht darin, jedem Zeichen eine eindeutige Binärzahl zuzuweisen. Beispielsweise könnte ein Computer den Buchstaben A als 01000001 und ein Ausrufezeichen als 00100001 darstellen. Dies führt zu Codes, die leicht zu analysieren sind – alle acht Ziffern oder Bits entsprechen einem eindeutigen Zeichen –, aber furchtbar ineffizient, da es sich um dieselbe Zahl handelt Die Zahl der Binärziffern wird sowohl für allgemeine als auch für ungewöhnliche Einträge verwendet. Ein besserer Ansatz wäre so etwas wie Morsecode, bei dem der häufige Buchstabe E nur durch einen einzelnen Punkt dargestellt wird, während für das seltenere Q das längere und aufwändigere Strich-Strich-Punkt-Strich erforderlich ist.

Doch auch Morsecode ist ineffizient. Sicher, einige Codes sind kurz und andere lang. Da die Codelängen jedoch variieren, können Nachrichten im Morsecode nur dann verstanden werden, wenn zwischen den einzelnen Zeichenübertragungen kurze Pausen eingelegt werden. Tatsächlich hätten die Empfänger ohne diese kostspieligen Pausen keine Möglichkeit, die Morsebotschaft Strich Punkt-Strich-Punkt Punkt-Punkt Strich Punkt („trite“) von Strich Punkt-Strich-Punkt Punkt-Punkt-Strich Punkt („wahr“) zu unterscheiden. ).

Fano hatte diesen Teil des Problems gelöst. Er erkannte, dass er Codes unterschiedlicher Länge verwenden konnte, ohne kostspielige Leerzeichen zu benötigen, solange er niemals dasselbe Ziffernmuster sowohl für einen vollständigen Code als auch für den Anfang eines anderen Codes verwendete. Wenn zum Beispiel der Buchstabe S in einer bestimmten Nachricht so häufig vorkommt, dass Fano ihm den extrem kurzen Code 01 zuweist, dann würde kein anderer Buchstabe in dieser Nachricht mit irgendetwas codiert werden, das mit 01 beginnt; Codes wie 010, 011 oder 0101 wären alle verboten. Dadurch konnte die codierte Nachricht ohne Mehrdeutigkeit von links nach rechts gelesen werden. Wenn beispielsweise dem Buchstaben S 01, dem Buchstaben A 000, dem Buchstaben M 001 und dem Buchstaben L 1 zugewiesen ist, kann die Nachricht 0100100011 plötzlich sofort in das Wort „klein“ übersetzt werden, obwohl L durch eins dargestellt wird Ziffer, S durch zwei Ziffern und die anderen Buchstaben durch jeweils drei.

Um die Codes tatsächlich zu bestimmen, erstellte Fano Binärbäume und platzierte jeden erforderlichen Buchstaben am Ende eines visuellen Zweigs. Der Code jedes Buchstabens wurde dann durch den Pfad von oben nach unten definiert. Wenn der Pfad nach links abzweigt, fügt Fano eine 0 hinzu; Die rechten Zweige erhielten eine 1. Die Baumstruktur machte es Fano leicht, diese unerwünschten Überschneidungen zu vermeiden: Sobald Fano einen Buchstaben im Baum platzierte, endete dieser Zweig, was bedeutete, dass kein zukünftiger Code auf die gleiche Weise beginnen konnte.

Um zu entscheiden, welche Buchstaben wohin gehen würden, hätte Fano jedes mögliche Muster ausgiebig testen können, um maximale Effizienz zu erzielen, aber das wäre unpraktisch gewesen. Stattdessen entwickelte er eine Annäherung: Für jede Nachricht ordnete er die relevanten Buchstaben nach Häufigkeit und ordnete die Buchstaben dann den Zweigen zu, sodass die Buchstaben auf der linken Seite in einem bestimmten Zweigpaar in der Nachricht ungefähr genauso oft verwendet wurden wie die Buchstaben rechts. Auf diese Weise würden häufig verwendete Zeichen auf kürzeren, weniger dichten Zweigen landen. Eine kleine Anzahl von Buchstaben mit hoher Häufigkeit würde immer eine größere Anzahl von Buchstaben mit niedrigerer Häufigkeit ausgleichen.

Das Ergebnis war eine bemerkenswert effektive Kompression. Aber es war nur eine Annäherung; Es musste eine bessere Komprimierungsstrategie vorhanden sein. Also forderte Fano seine Schüler auf, es zu finden.

Fano hatte seine Bäume von oben nach unten gebaut und dabei so viel Symmetrie wie möglich zwischen den Zweigpaaren gewahrt. Sein Schüler David Huffman stellte den Prozess auf den Kopf und baute die gleichen Baumarten, jedoch von unten nach oben. Huffmans Erkenntnis war, dass in einem effizienten Code die beiden am wenigsten verbreiteten Zeichen, was auch immer passiert, die beiden längsten Codes haben sollten. Also identifizierte Huffman die beiden am wenigsten verbreiteten Zeichen, gruppierte sie zu einem verzweigten Paar und wiederholte dann den Vorgang, wobei er dieses Mal unter den verbleibenden Zeichen und dem Paar, das er gerade gebildet hatte, nach den beiden am wenigsten verbreiteten Einträgen suchte.

Stellen Sie sich eine Nachricht vor, bei der der Fano-Ansatz ins Stocken gerät. In „Schulzimmer“ erscheint O viermal und S/C/H/L/R/M jeweils einmal. Fanos ausgleichender Ansatz beginnt mit der Zuweisung des O und eines weiteren Buchstabens zum linken Zweig, wobei die insgesamt fünf Verwendungen dieser Buchstaben die fünf Vorkommen der übrigen Buchstaben ausgleichen. Die resultierende Nachricht benötigt 27 Bit.

Im Gegensatz dazu beginnt Huffman mit zwei der ungewöhnlichen Buchstaben – beispielsweise R und M – und gruppiert sie, wobei er das Paar wie einen einzelnen Buchstaben behandelt.

Sein aktualisiertes Häufigkeitsdiagramm bietet ihm dann vier Möglichkeiten: das O, das viermal vorkommt, den neuen kombinierten RM-Knoten, der funktional zweimal verwendet wird, und die einzelnen Buchstaben S, C, H und L. Huffman wählt erneut die beiden am wenigsten verbreiteten Optionen aus, nämlich Matching (sagen wir) H mit L.

Das Diagramm wird erneut aktualisiert: O hat weiterhin eine Gewichtung von 4, RM und HL haben jetzt jeweils eine Gewichtung von 2 und die Buchstaben S und C stehen allein. Von dort aus fährt Huffman fort, indem er in jedem Schritt die beiden am wenigsten häufigen Optionen gruppiert und dann sowohl den Baum als auch das Häufigkeitsdiagramm aktualisiert.

Letztlich wird „Schulzimmer“ zu 11101111110000110110000101, womit der Top-Down-Ansatz von Fano ein wenig abgesenkt wird.

Ein bisschen hört sich vielleicht nicht nach viel an, aber selbst kleine Einsparungen wachsen enorm, wenn sie auf Milliarden Gigabyte skaliert werden.

Tatsächlich hat sich Huffmans Ansatz als so wirkungsvoll erwiesen, dass heute fast jede verlustfreie Komprimierungsstrategie die Erkenntnisse von Huffman ganz oder teilweise nutzt. Benötigen Sie PKZip, um ein Word-Dokument zu komprimieren? Der erste Schritt beinhaltet eine weitere clevere Strategie zur Erkennung von Wiederholungen und dadurch zur Komprimierung der Nachrichtengröße. Der zweite Schritt besteht jedoch darin, die resultierende komprimierte Nachricht zu nehmen und sie durch den Huffman-Prozess laufen zu lassen. Ein Bild als JPEG speichern? Ihr Computer übersetzt das Bild zunächst in eine textbasierte Darstellung und verwendet dann erneut die Huffman-Kodierung, um diesen Text zu komprimieren.

Nicht schlecht für ein Projekt, das ursprünglich durch den Wunsch eines Doktoranden motiviert war, eine Abschlussprüfung zu überspringen.