Kommentar: Fauler Kompressionszauber
Eine Patentschrift der Firma Zeosync, die ein lange angekündigtes, revolutionäres neues Kompressionsverfahren beschreibt, ist nun endlich veröffentlicht.
Die Quadratur des Kreises hat als Synonym für das Unmögliche längst Einzug in die Umgangssprache gehalten. Warum sie aber unmöglich ist, das wirklich zu begreifen, gelingt den meisten Mathematikstudenten erst nach einigen Semestern, manchen nie (Stichwort Algebra, Satz von Lindemann über die Transzendenz von Pi). Weil das Problem leicht zu verstehen ist, nicht aber der Beweis seiner Unlösbarkeit, versuchen sich immer wieder Leute daran, ebenso wie an anderen als unlösbar bewiesenen klassischen Problemen wie der Dreiteilung des Winkels mit Zirkel und Lineal.
Doch warum fallen immer noch so viele auf Hirngespinste herein, die so viel leichter zu durchschauen sind? Ein Kompressionsverfahren zum Beispiel, das jede erdenkliche Datei in eine kürzere überführt ... Man könnte es sogar mehrfach anwenden und so alle Informationen beliebig klein eindampfen. Schon diese Überlegung zeigt, dass da etwas nicht stimmen kann, zumindest, wenn man von verlustfreier Kompression ausgeht, der Inhalt der ursprünglichen Datei sich also unter allen Umständen exakt wiederherstellen lassen soll.
Noch einmal etwas präziser, frei nach einem Abschnitt aus der FAQ der Newsgroup comp.compression: Angenommen, ein Algorithmus könne jede n-Bit-Datei so komprimieren, dass sie höchstens n-1 Bit benötigt. Es gibt 2n Dateien, die exakt n Bit lang sind. Wie viele Dateien mit höchstens n-1 Bit gibt es aber? Eine der Länge null, zwei der Länge eins, 4, 8, 16 und so weiter, summa summarum 2n-1. Wenn man jeder der 2n unkomprimierten Dateien eine komprimierte zuordnen will, dann müssen mindestens zwei Dateien die gleiche komprimierte Repräsentation erhalten -- wenn ich 16 Dinge in 15 Schubladen stecke, enthält hinterher mindestens eine Schublade zwei Dinge. Aus zwei identischen komprimierten Dateien die verschiedenen Originale zu rekonstruieren, ist aber offensichtlich unmöglich.
Es geht also nicht. Oder doch? Im vergangenen Jahr versprach die Firma Zeosync den Durchbruch bei den Kompressionsverfahren. Multidimensional, mit Relational Differentiation Encoding und allerlei anderem Brimborium, auf einer schicken Website, wahlweise mit Flash oder ohne. Eine für alle praktischen Zwecke verlustfreie Kompression, mit einer klitzekleinen Nebenbedingung: Der mehrdimensionale Raum darf nicht supersaturiert sein (aha), was darauf hinausläuft, dass sich keine zwei verschiedenen Tauben am selben Ort befinden dürfen (logisch, siehe die letzten paar Zeilen unter Technology/Technical Process).
Nach langem Rätseln ist sie nun veröffentlicht, die Patentschrift, die Zeosync laut Dokumentation der World Intellecutal Property Organization (WIPO) eingereicht hat. Wie funktioniert es also nun, das Relational Differentiation Encoding? Um einen Zielwert zu kodieren, geben wir zunächst eine Zielmenge von Werten an, die den Zielwert enthält. Dann geben wir noch ein Kriterium an, das näher differenziert, welcher der Werte aus der Zielmenge es denn nun im Einzelnen ist. Beide Informationen zusammen spezifizieren exakt den Ursprungswert und belegen weniger Platz.
Ein Beispiel: Zunächst verrate ich, dass die kodierte Zahl eine ungerade Zahl ist. Dann gebe ich an, die wievielte Zahl in der Menge der ungeraden Zahlen ich meine, beispielsweise die dritte. Das wäre dann die 5. Die Zahl 3 braucht nur zwei Bit, während die Zahl 5 drei Bit lang ist. Ein Bit gespart? Nicht wirklich, denn das eine Bit brauche ich ja, um zu sagen, ob die Zielmenge die geraden oder die ungeraden Zahlen umfasst.
Also raffinierter, nämlich mit SMB und SMOB. Das Senior Most Bit SMB soll das höchste gesetzte Bit einer Zahl bezeichnen, SMOB steht für so many on/off bits, also die Anzahl der gesetzten Bits. Wenn SMB und SMOB bekannt sind (der SMB/SMOB-Record, SSR), haben wir schon eine Zielmenge, aus der wir das gemeinte Element nur noch näher spezifizieren müssen. Die Zielmenge differenziert sich in eine Kandidatenmenge und weiter in eine Menge vielversprechender Kandidaten, womöglich noch über wahrscheinliche Kandidaten bis hin zum Ziel -- je nach Implementierung. Doch warum sich durch SMB und SMOB, SSR und Armatures, differenzielle Paare von SSRs von Armatures und so weiter quälen, wenn man nur zwei bestimmte Zeilen liest: Seite 4, Zeile 12 verspricht uns die Kodierung without any loss, also verlustfrei, und Seite 5, Zeile 16: The target T is encoded so that a reduced number of bits are needed for transmission and storage, die Anzahl der benötigten Bits wird reduziert. Schön wärs.
Mag sein, dass Relational Differentiation Encoding zu irgendetwas zu gebrauchen ist, das versprochene Kompressionswunder kann es jedenfalls nicht vollbringen.
Ein paar Links zu verwandten Themen mögen wir den Lesern zum Schluss nicht vorenthalten: Das Perpetuum Mobile und der Funkwellenordner. (bo)
