Verlustfreie Komprimierung

Verlustfreie Datenkomprimierungsalgorithmen können keine Komprimierung für alle Eingabedatensätze garantieren. Mit anderen Worten: Für jeden verlustfreien Datenkomprimierungsalgorithmus wird es einen Eingabedatensatz geben, der nicht kleiner wird, wenn er von dem Algorithmus verarbeitet wird, und für jeden verlustfreien Datenkomprimierungsalgorithmus, der mindestens eine Datei kleiner macht, wird es mindestens eine Datei geben, die er größer macht. Dies lässt sich leicht mit elementarer Mathematik unter Verwendung eines Zählarguments wie folgt beweisen:

• Angenommen, jede Datei wird als eine Bitfolge beliebiger Länge dargestellt.
• Angenommen, es gibt einen Kompressionsalgorithmus, der jede Datei in eine Ausgabedatei umwandelt, die nicht länger ist als die Originaldatei, und dass mindestens eine Datei in eine Ausgabedatei komprimiert wird, die kürzer ist als die Originaldatei.
• M sei die kleinste Zahl, bei der es eine Datei F mit der Länge M Bits gibt, die zu etwas Kürzeren komprimiert wird. Sei N die Länge (in Bits) der komprimierten Version von F.
• Da N<M ist, behält jede Datei der Länge N bei der Komprimierung ihre Größe. Es sind 2N solcher Dateien möglich. Zusammen mit F ergibt das 2N+1 Dateien, die alle in eine der 2N Dateien der Länge N komprimiert werden.
• Aber 2N ist kleiner als 2N+1, also muss es nach dem Schubladenprinzip eine Datei der Länge N geben, die gleichzeitig die Ausgabe der Kompressionsfunktion auf zwei verschiedenen Eingaben ist. Diese Datei kann nicht zuverlässig dekomprimiert werden (welches der beiden Originale sollte das Ergebnis sein?), was der Annahme widerspricht, dass der Algorithmus verlustfrei war.
• Wir müssen daher zu dem Schluss kommen, dass unsere ursprüngliche Hypothese (dass die Kompressionsfunktion keine Datei länger macht) notwendigerweise unwahr ist.

Jeder verlustfreie Kompressionsalgorithmus, der einige Dateien kürzer macht, muss notwendigerweise einige Dateien länger machen, aber es ist nicht notwendig, dass diese Dateien sehr viel länger werden. Die meisten praktischen Kompressionsalgorithmen bieten eine „Escape“-Funktion, mit der die normale Kodierung für Dateien, die durch die Kodierung länger werden würden, ausgeschaltet werden kann. Theoretisch ist nur ein einziges zusätzliches Bit erforderlich, um dem Decoder mitzuteilen, dass die normale Kodierung für die gesamte Eingabe ausgeschaltet wurde; die meisten Kodierungsalgorithmen verwenden jedoch mindestens ein ganzes Byte (und in der Regel mehr als eins) für diesen Zweck. Beispielsweise müssen deflate-komprimierte Dateien nie um mehr als 5 Byte pro 65.535 Byte Eingabe wachsen.

Wenn wir Dateien der Länge N betrachten und alle Dateien gleich wahrscheinlich wären, dann muss bei jeder verlustfreien Komprimierung, die die Größe einer Datei reduziert, die erwartete Länge einer komprimierten Datei (gemittelt über alle möglichen Dateien der Länge N) notwendigerweise größer als N sein. Wenn wir also nichts über die Eigenschaften der Daten wissen, die wir komprimieren, können wir sie genauso gut gar nicht komprimieren. Ein verlustfreier Komprimierungsalgorithmus ist nur dann sinnvoll, wenn es wahrscheinlicher ist, dass wir bestimmte Dateitypen komprimieren als andere; dann könnte der Algorithmus so entwickelt werden, dass er diese Datentypen besser komprimiert.

Die wichtigste Lehre aus diesem Argument ist also nicht, dass man große Verluste riskiert, sondern lediglich, dass man nicht immer gewinnen kann. Die Wahl eines Algorithmus bedeutet immer, dass man eine Teilmenge aller Dateien auswählt, die sinnvollerweise kürzer wird. Dies ist der theoretische Grund, warum wir verschiedene Kompressionsalgorithmen für verschiedene Arten von Dateien brauchen: Es kann keinen Algorithmus geben, der für alle Arten von Daten gut ist.

Der „Trick“, der es verlustfreien Komprimierungsalgorithmen ermöglicht, bei der Anwendung auf die Art von Daten, für die sie entwickelt wurden, solche Dateien durchgängig auf eine kürzere Form zu komprimieren, besteht darin, dass die Dateien, für die die Algorithmen entwickelt wurden, alle irgendeine Form von leicht modellierbarer Redundanz aufweisen, die der Algorithmus beseitigen soll, und somit zu der Teilmenge von Dateien gehören, die der Algorithmus kürzer machen kann, während andere Dateien nicht komprimiert oder sogar größer werden würden. Algorithmen sind in der Regel sehr spezifisch auf einen bestimmten Dateityp abgestimmt: So funktionieren beispielsweise verlustfreie Audiokomprimierungsprogramme nicht gut bei Textdateien und umgekehrt.

Insbesondere können Dateien mit Zufallsdaten von keinem denkbaren verlustfreien Datenkomprimierungsalgorithmus konsistent komprimiert werden: Dieses Ergebnis wird in der Tat verwendet, um das Konzept der Zufälligkeit in der algorithmischen Komplexitätstheorie zu definieren.

Es ist nachweislich unmöglich, einen Algorithmus zu erstellen, der beliebige Daten verlustfrei komprimieren kann. Zwar gab es im Laufe der Jahre viele Behauptungen von Unternehmen, die eine „perfekte Komprimierung“ erreicht haben, bei der eine beliebige Anzahl N zufälliger Bits immer auf N – 1 Bits komprimiert werden kann, aber diese Art von Behauptungen kann man getrost verwerfen, ohne sich weitere Details des angeblichen Komprimierungsverfahrens anzusehen. Ein solcher Algorithmus widerspricht grundlegenden Gesetzen der Mathematik, denn wenn es ihn gäbe, könnte er wiederholt angewandt werden, um jede beliebige Datei verlustfrei auf die Länge 0 zu reduzieren. Angeblich „perfekte“ Kompressionsalgorithmen werden aus diesem Grund oft spöttisch als „magische“ Kompressionsalgorithmen bezeichnet.

Andererseits ist auch bewiesen, dass es keinen Algorithmus gibt, mit dem sich feststellen lässt, ob eine Datei im Sinne der Kolmogorov-Komplexität inkompressibel ist. Daher ist es möglich, dass eine bestimmte Datei, auch wenn sie zufällig erscheint, erheblich komprimiert sein kann, sogar unter Berücksichtigung der Größe des Dekomprimierers. Ein Beispiel sind die Ziffern der mathematischen Konstante Pi, die zufällig erscheinen, aber von einem sehr kleinen Programm generiert werden können. Auch wenn nicht festgestellt werden kann, ob eine bestimmte Datei inkompressibel ist, zeigt ein einfaches Theorem über inkompressible Zeichenketten, dass über 99 % der Dateien beliebiger Länge nicht um mehr als ein Byte (einschließlich der Größe des Dekomprimierers) komprimiert werden können.

Mathematischer HintergrundBearbeiten

Abstrakt betrachtet kann ein Komprimierungsalgorithmus als eine Funktion auf Sequenzen (normalerweise aus Oktetten) angesehen werden. Die Komprimierung ist erfolgreich, wenn die resultierende Sequenz kürzer ist als die ursprüngliche Sequenz (und die Anweisungen für die Dekomprimierungskarte). Damit ein Kompressionsalgorithmus verlustfrei ist, muss die Kompressionsabbildung eine Injektion von „reinen“ zu „komprimierten“ Bitsequenzen bilden.

Das Schubladenprinzip verbietet eine Bijektion zwischen der Sammlung von Sequenzen der Länge N und jeder Teilmenge der Sammlung von Sequenzen der Länge N-1. Daher ist es nicht möglich, einen verlustfreien Algorithmus zu entwickeln, der die Größe jeder möglichen Eingabesequenz reduziert.

Anwendungspunkte in der realen KompressionstheorieBearbeiten

Die Entwickler von realen Kompressionsalgorithmen akzeptieren, dass Datenströme mit hoher Informationsentropie nicht komprimiert werden können, und bieten dementsprechend Möglichkeiten zur Erkennung und Behandlung dieser Bedingung. Eine offensichtliche Möglichkeit der Erkennung besteht darin, einen rohen Kompressionsalgorithmus anzuwenden und zu prüfen, ob seine Ausgabe kleiner ist als seine Eingabe. Manchmal erfolgt die Erkennung durch Heuristiken; beispielsweise kann eine Komprimierungsanwendung Dateien, deren Namen auf „.zip“, „.arj“ oder „.lha“ enden, als nicht komprimierbar einstufen, ohne dass eine weitergehende Erkennung erfolgt. Eine gängige Methode, mit dieser Situation umzugehen, ist das Zitieren der Eingabe bzw. nicht komprimierbarer Teile der Eingabe in der Ausgabe, um den Komprimierungsaufwand zu minimieren. Das Zip-Datenformat gibt beispielsweise die „Kompressionsmethode“ „Gespeichert“ für Eingabedateien an, die wortwörtlich in das Archiv kopiert wurden.

Die Million Random Digit ChallengeEdit

Mark Nelson hat als Reaktion auf die Behauptungen über magische Kompressionsalgorithmen, die in comp.compression aufgetaucht sind, hat er eine 415.241 Byte große Binärdatei mit hochgradig entropischem Inhalt konstruiert und eine öffentliche Herausforderung in Höhe von 100 Dollar an jeden herausgegeben, der ein Programm schreiben kann, das zusammen mit seiner Eingabe kleiner ist als die von ihm bereitgestellten Binärdaten und dennoch in der Lage ist, diese fehlerfrei wiederherzustellen.

Die FAQ für die Newsgroup comp.compression enthält eine Herausforderung von Mike Goldman, der 5.000 Dollar für ein Programm anbietet, das Zufallsdaten komprimieren kann. Patrick Craig nahm die Herausforderung an, aber anstatt die Daten zu komprimieren, teilte er sie in separate Dateien auf, die alle mit der Zahl 5 endeten, die nicht als Teil der Datei gespeichert war. Durch das Weglassen dieses Zeichens waren die resultierenden Dateien (plus, gemäß den Regeln, die Größe des Programms, das sie wieder zusammensetzte) kleiner als die Originaldatei. Es fand jedoch keine tatsächliche Komprimierung statt, und die in den Dateinamen gespeicherten Informationen waren notwendig, um sie in der richtigen Reihenfolge in der Originaldatei wieder zusammenzusetzen, und diese Informationen wurden beim Vergleich der Dateigrößen nicht berücksichtigt. Die Dateien selbst reichen also nicht aus, um die Originaldatei wiederherzustellen; die Dateinamen sind ebenfalls erforderlich. Patrick Craig stimmte zu, dass keine sinnvolle Komprimierung stattgefunden hatte, argumentierte aber, dass der Wortlaut der Aufforderung dies eigentlich nicht erfordere. Ein ausführlicher Bericht über den Vorfall, einschließlich der Diskussion darüber, ob die Herausforderung technisch erfüllt wurde oder nicht, findet sich auf der Website von Patrick Craig.