Kompression

Lucas: Hallo und herzlich Willkommen zu einer neuen Ausgabe des INNOQ Podcasts. Heute habe ich Stefan Bodewig eingeladen. Hallo Stefan!

Stefan: Hallo Lucas!

Lucas: Wir haben uns heute zusammengefunden, um ein bisschen über Kompression zu sprechen und das ist ein Follow up zu unserer Folge 92. Da hatte ich im Kontext vom Web gesagt, dass es für mich nicht optional ist, wenn man seine Webseite vernünftig betreiben will, da Kompression einzuschalten, zum Beispiel mit gzip oder Brotli. Und wesentlich mehr hatte ich dann zur Kompression nicht gesagt. Und dann habe ich mir gedacht: Da lade ich doch noch mal den Stefan Bodewig ein, weil der kennt sich sehr gut aus mit Kompression und wir diskutieren einfach noch mal: Was ist das eigentlich? Was soll das überhaupt? Und an welchen Stellen benutzen wir eigentlich überall Kompression? Weil das ist erstaunlich, an wie vielen Orten wir komprimieren. Und wir wollen und ein bisschen auf verlustfreie Kompression konzentrieren. Nicht nur ein bisschen, sondern wir konzentrieren uns auf verlustfreie Kompression. Und deswegen müssen wir erst mal vielleicht diskutieren: Was ist eigentlich Kompression und was ist insbesondere verlustfreie Kompression, Stefan?

Stefan: Das können wir machen. Kompression ist ganz naiv gedacht: Ich habe irgendwo einen Sack von Daten und ich versuche mit weniger Datenvolumen die gleiche Information zu transportieren. Ich möchte also, dass meine Daten, die ich habe, in kürzerer Zeit übers Netz übertragen werden können, in schnellerer Zeit von der Platte geladen werden können oder einfach weniger Platz wegnehmen. Das waren vor allen Dingen in der Vergangenheit wichtige Gründe, weniger Platz auf der Festplatte zu haben. Das ist heute sicherlich nicht mehr ganz so dramatisch, weil Festplatten immer günstiger werden. Aber gerade in dem Kontext von Web, wie du es ansprichst, geht es natürlich auch darum, dass ich die Dinge in kürzerer Zeit über das Netz transportieren kann. Ich mache sie klein auf der Server Seite und dann packe ich sie aus und nach Möglichkeit kommt beim Auspacken das gleiche raus, was ich vorher eingepackt habe. Das wäre meine Definition von verlustfrei. Dass ich genau die Information, die ursprünglich da gewesen ist, auf der anderen Seite, nachdem ich die Kompression wieder rückgängig gemacht habe, auch wiederherstellen kann.

Lucas: Und wir komprimieren alle möglichen Arten von Daten. Wie komprimieren Text, Bilder, wir komprimieren aber auch Audio und Video. An allen möglichen Stellen benutzen wir Kompression, weil wenn man sich vorstellt, ein Kinofilm unkomprimiert, der verbraucht dann schon wirklich viel Platz auf der Platte, selbst nach heutigen Standards, wenn es dann die entsprechenden Auflösungen hat. Wir haben uns ein bisschen auf Text in dieser Folge konzentriert, aber wir reden auch immer ein bisschen über Bilder, weil es interessanterweise so ist, dass die Algorithmen, die dahinterstecken, tatsächlich die gleichen sind oder zumindest ähnliche sind. Da wollte ich jetzt einfach mal als Beispiel sagen, wie das in der Bildwelt ist. Wir haben zum Beispiel so Formate wie PNG, das ist ein verlustfreies Kompressionsformat, das ist jetzt schon eine ganze Weile gibt, und das benutzt die gleichen Algorithmen, über die wir heute in dieser Folge sprechen werden. Es gibt auch neuere Standards wie WebP, AVIF und JPEG XL, die alle auch verlustfreie Varianten anbieten. Und das ist, um das mal kurz abzugrenzen, der Unterschied zu verlustbehafteten Kompression und das kann man ganz gut bei Bildern erklären. Wenn wir uns zum Beispiel JPEG als Format anschauen, das ist eben ein verlustbehaftetes Format und das bedeutet jetzt nicht, dass JPEGs unbedingt optisch schlechter aussehen als das äquivalente PNG, aber es gehen bestimmte Informationen verloren. Das ist bei JPEG beispielsweise so, dass eben Pixel, die nah aneinander sind, vielleicht in dieselbe Farbe umgefärbt werden, um dieses Bild besser komprimieren zu können. Und das ist etwas, was so was wie PNG nicht macht. Bei PNG kann ich aus dem PNG Bild immer wieder das Originalbild zurückbekommen. Das ist das, was Stefan auch gerade gesagt hat. Das ist der Unterschied zwischen dieser verlustbehafteten Kompression. Und eine ganz spezielle Art von verlustbehafteter Kompression ist noch das, was man auch als Minification bezeichnet. So was wie UglifyJS oder TerserJS, die JavaScript nehmen und das kleiner machen. Das ist auch erst mal eine Art von Kompression und die würden wir als verlustbehaftet bezeichnen, weil wir bestimmte Informationen nicht mehr zurückbekommen können. Beispielsweise, wenn wir jetzt eine JavaScript Datei nehmen und allen Whitespace, alle Spaces, alle Tabs, die wir nicht brauchen – semantisch – aus der Datei rausnehmen, funktioniert die Datei immer noch so wie vorher. Sie ist immer noch semantisch äquivalent. Aber sie ist viel kleiner und wir können es aber nicht wiederherstellen, weil wir wissen nicht, an welchen Stellen vorher Spaces waren. Und genauso gibt es Verfahren, die die Variablennamen kürzen, bei TerserJS beispielsweise. Und auch die können wir nicht ohne Weiteres wiederherstellen. Und deswegen würden wir die als verlustbehaftete Kompression betrachten. Und das ist deswegen auch interessant, da kommen wir vielleicht dann später nochmal darauf zurück, weil ein gutes Kompressionsformat, was verlustfrei ist, teilweise Minification überflüssig macht. Das können wir vielleicht später noch mal diskutieren. Das erstmal so zur Abgrenzung und eine Frage, die einem doch häufiger mal begegnet ist. Man hat irgendwie Dateien und man sagt jetzt: Hey, mach doch mal gzip daraus und nachher ist die Datei gar nicht kleiner geworden oder ist vielleicht sogar größer geworden. Wie kann denn so was sein, Stefan?

Stefan: Ganz grundsätzlich, ohne dass wir jetzt tief in die Mathematik einsteigen, ist es so, dass bestimmte Inhalte sich überhaupt nicht eignen, komprimiert zu werden. Wenn wir uns vorstellen würden, das wäre andersrum. Ich würde tatsächlich die Datei mit GZIP komprimieren und sie wird danach kleiner, hätte ich wieder eine neue Datei, die könnte ich dann noch mal GZIP komprimieren, wenn die Annahme wäre, dass ich jede Datei beliebig verkleinern könnte. Das mache ich dann einfach so lange hintereinander, bis nur noch ein Byte oder ein Bit übrig bleibt. Es kann nicht funktionieren. Ganz offensichtlich muss es in gewisser Art und Weise Grenzen geben. Und es gibt immer eine gewisse Obergrenze oder eine Untergrenze von Datenvolumen. Unter da werde ich nicht drunter kommen. Das wird mir nicht gelingen, Daten unter ein bestimmtes Volumen zu komprimieren, weil ich ansonsten anfangen müsste, Informationen zu verlieren. Mit verlustfreien komme ich nicht drunter. Mit verlustbehafteten Kompressionsalgorithmen könnte ich dann vielleicht noch auf irgendwelche Informationen verzichten und könnte noch weiter komprimieren. Aber solange ich Daten nicht verlieren möchte, habe ich keine Chance. Dann gibt es bestimmte Dateien, die eignen sich nicht komprimiert zu werden und die eignen sich im Zweifel auch nicht durch irgendeinen der verschiedenen Kompressionsalgorithmen, die es gibt, komprimiert zu werden. Sonst könnte ich zwischen Algorithmen wechseln und dann immer noch versuchen, immer kleiner zu werden. Es gibt einfach Dateien, bei denen klappt nichts, was wir heute kennen.

Lucas: Und bevor wir jetzt in die Algorithmen einsteigen, ein Thema, was einem, wenn man sich mit diesem Thema beschäftigt, auch immer wieder begegnet, sind Patente. Da gibt es auch irgendwie Probleme mit manchen Algorithmen, dass die irgendwie patentbehaftet sind. Kannst du dazu noch was sagen?

Stefan: Das was möglicherweise heute das bekanntere von den Patentstreitigkeiten ist, da hat es durchaus mehrere gegeben in der Vergangenheit, ist das CompuServe und ich glaube auch noch ein paar andere Patente rund um das Grafik Format GIF gehalten hat. Das war irgendwann Ende der 80er, Anfang der 90er glaube ich, dass sie dieses Patent gewonnen haben. Und das ist dann ein bisschen höher gekocht in den 90ern, und das ist so in der Entstehungszeit von PNG. PNG ist ein stückweit sogar als Reaktion auf diese Patentstreitigkeiten, die da waren, entstanden. Es gibt aber auch, wir werden gleich noch ein bisschen über einige von den Algorithmen sprechen. Aber arithmetic encoding, arithmetische Codierung, hatte mehrere Patente, die dann in der Geschichte beispielsweise dazu geführt haben, das bzip2 Format, das der ein oder andere vielleicht kennt, sich gegen Arithmethic Encoding und für Huffman Encoding an einer Stelle, wo man sich zwischen zwei verschiedenen Algorithmen entscheiden konnte, entschieden hat, um solchen vielleicht auch nur gefühlten Patentschwierigkeiten aus dem Weg zu gehen.

Lucas: Manchmal ist es auch einfach nur die Angst davor, dass man eventuell Patentschwierigkeiten bekommen könnte, die einen dann davon abhalten. Okay, dann lasst uns doch direkt mal in die grundlegenden Algorithmen eintauchen. Ich hatte schon eben gesagt, dass wir bestimmte Sachen sowohl im Text als auch in Bildformaten wiederfinden. Bevor wir jetzt über die verschiedenen Familien von Algorithmen sprechen. Kannst du noch etwas dazu sagen, wie das mit Streams und Blöcken in der Kompression ist?

Stefan: Die Algorithmen, wie sie benutzt werden, die meisten davon nehmen sich einfach Daten und lesen die von vorne und komprimieren die Daten, während sie sie lesen. Und am Ende habe ich ein fertig komprimiertes Ergebnis. Das wäre das Streaming Verfahren. Das heißt, während ich die Daten lese, kann ich sie on the fly komprimieren und hinten kommen komprimierte Daten raus. Und genauso kann ich beim Empfang der Daten sie eigentlich schon wieder dekomprimieren, während ich die Daten empfange, während ich die Daten lese. Das heißt, ich habe den großen Vorteil, dass ich nicht warten muss, bis ich ein bestimmtes Datenvolumen zusammen habe und einfach schon loslegen kann. Aber ich erkaufe mir das durchaus durch Nachteile. Ein Nachteil ist, dass wenn ich vielleicht die Daten auf der Festplatte als Ganzes liegen hätte und sie gut in Blöcke aufteilen könnte und ich meinen Algorithmus immer nur auf einen Block anwende, dann kann ich das parallel machen. Wenn ich also mehrere Prozessoren habe, könnte ich jeweils einen Block von Daten, einen der CPUs in die Hand geben und die CPU komprimiert dann die Daten dieses Blocks, bin ich viel schneller fertig mit dem Komprimieren und das gilt genauso für das Dekomprimieren, wenn ich die Daten vollständig habe. Man hat bei Verschlüsselung die durchaus Verwandtschaft zu Kompression an manchen Stellen hat, ähnliche Dinge, dass man da auch abwägt zwischen Block- und Strom-Verschlüsselungsverfahren. Da kann man sehr kleine Blöcke wählen und ein bisschen die Vorteile von Blöcken bekommen, ohne die größeren Nachteile, dass ich eben warten muss, auf mich zu nehmen. Das klappt bei Kompression nicht ganz so gut, weil bei Kompression, wir werden es später, wenn wir auf die Algorithmen schauen, noch ein bisschen stärker sehen. Da hilft es, wenn die Blöcke groß sind. Wenn ich also möglichst viel Kontext habe, möglichst viel von den Daten kenne, die ich da komprimieren möchte, um ein möglichst gutes Ergebnis zu erzielen.

Lucas: Okay, dann lasst uns doch mal in die Algorithmen einsteigen. Ich glaube, zumindest von meinem Wissen, die älteste Idee, die bis heute immer noch super relevant in dem Codierungs-Bereich ist, ist von David Huffman erfunden worden. Diese Huffman Codierung oder Huffman Coding. Die ist von 1952. Also gibt es die schon eine ganze Weile. Kannst du erklären, was ist Huffman Coding und warum kann ich damit Daten komprimieren?

Stefan: Ich bin nicht sicher, wie einfach oder schwierig das werden wird, Algorithmen ohne Whiteboard und Malen zu erklären, aber wir können es zumindest versuchen. Die Kernidee von Huffman ist, dass man feststellt, dass nicht alle Symbole, wenn wir jetzt erst mal über Text sprechen, nicht alle Buchstaben in einem Text gleich häufig auftauchen, wir aber in der Art und Weise, wie wir Text repräsentieren – ASCII-Zeichensatz, wenn wir über englische Texte reden – da brauchen wir 1 Byte pro Buchstaben. Das heißt, egal wie häufig so ein Buchstabe vorkommt, auch für ein X brauche ich genau so viel Information, um das X zu übertragen wie ich brauche, um ein E zu kodieren. In der englischen Sprache wie auch in der deutschen ist E deutlich häufiger als ein X. Das ist eigentlich vielleicht nicht ideal. Und unter Umständen gewinnen wir was, wenn wir sagen: Ich benutze weniger Datenlänge und vielleicht nur 3 Bits oder so was in der Art für besonders häufige Symbole und erkaufe mir das dadurch, dass ich viel mehr, 20 Bits für besonders seltene Symbole verwende. Und dann gehe ich mit Statistik ran und schaue mir die Datei an, die ich da habe und stelle fest: In welcher Häufigkeit tauchen welche Symbole auf? Und überlege mir, wie ich diese Symbole möglichst gleich nach ihren Wahrscheinlichkeiten verteilt oder ihren Häufigkeiten verteilt, oft Kürzeres abbilden kann. Und bei Huffmann finden wir da so einen binären Baum, auf den das Ganze abgebildet wird. Das heißt, jedes Symbol besteht aus so einer Bit-Sequenz, auf die ich abbilden kann. Und dabei muss ich dafür sorgen, dass ich, wenn ich von vorne anfange zu lesen, nicht immer ganz eindeutig weiß, welches Symbol ich habe. Wir können mal ein fiktives Beispiel nehmen, dass wir sagen, wir haben in unserem Text überhaupt nur As, Bs und Cs auftauchen. Die Hälfte davon sind As und jeweils 1/4 sind Bs und Cs. Dann könnte ich, wenn ich Huffmann durchdenke, sagen: Meine As benutze ich nur das eine Bit 0, wenn bei meinen Bs 10 als zwei Bit-Sequenz, meine Cs 11 zwei Bit-Sequenzen. Wenn ich also von vorne lese und ich sehe als erstes eine 0, weiß ich, dass es ein A sein muss. Wenn ich eine 1 finde, schaue ich dahinter auf das nächste Bit und weiß, ob es ein B oder C gewesen ist. Und wenn ich mir eine Datei anschaue, die nach so einer Verteilung dagewesen ist, wenn ich vorher 100 As und jeweils 50 Bs und Cs gehabt habe, dann sind es 200 Zeichen und die komprimiere ich, wenn ich es stattdessen mit 100 mal 1 Bit für die As und 50 mal 2 Bits für die Bs und Cs, komme ich auf 200 Bit statt auf 200 Zeichen, die wir ursprünglich gehabt haben. Das ist schon eine relativ starke Kompression und das unabhängig davon, wie genau in der Datei sich eigentlich die As, Bs und Cs verteilen, sondern ich habe damit die Möglichkeit, einfach nur indem ich mir kürzere Symbole ausgedacht habe, für meine Zeichen deutlich kleiner zu werden.

Lucas: Und dabei ist es irrelevant, ob jetzt drei Cs hintereinander kommen oder ein C, dann ein B und dann wieder ein A? Das ist für Huffmann Encoding irrelevant. Die Reihenfolgen spielen keine Rolle.

Stefan: Zumindest wenn wir das in dieser Form, wie ich es gerade beschrieben habe, auf den einzelnen Buchstaben herunterbrechen. Man könnte sich natürlich vorstellen, dass man statt eines Buchstaben, sich Dinge nach ihrer Verteilung anschaut, gleich auf längere Dinge geht. Dass man Worte in so einen Baum einbaut. Im Endeffekt baue ich aber eine Art Dictionary auf, ein Verzeichnis, bei dem ich Symbole auf kürzere Symbole abbilde und das in beiden Richtungen eindeutig hinbekommen kann. Und diesen Baum muss ich dann natürlich auch auf der anderen Seite, die dekomprimieren soll, in irgendeiner Art und Weise mitteilen. Ich muss also zusätzlich zu den As, Bs Cs und wie ich gerade gesagt habe, muss ich dem Programm, dass das Ganze wieder dekomprimieren soll, sagen: Und im übrigen, meine Null ist das A, 10 ist das B und 11 ist das C. Das muss irgendwie auf der anderen Seite ankommen. Das müssen wir also irgendwo getrennt in irgendeiner Art und Weise übertragen. Und wenn wir da auf kompliziertere Dinge als einen Buchstaben gehen, wenn wir da ganze Worte haben können, dann kann man sich vorstellen, dass der Baum sehr groß wird. Dann verliere ich möglicherweise auch gleich wieder eine ganze Menge von dem, was ich gewonnen habe, wenn ich das mit übertragen muss.

Lucas: Und es wäre auch eine Option, sich bei einer Kompression auf einen bestimmten Baum vorab zu einigen, den quasi alle vorher schon haben, dann müsste ich ihn nicht übertragen, richtig?

Stefan: Genau das passiert durchaus auch. In einigen der Algorithmen, über die wir sprechen werden, gibt es dann das Standard Dictionary, das man verwendet und als Option, dass man ein anderes Dictionary einsetzt, wenn man es gerade für die Daten, die man sich anschaut, vielleicht besser weiß als der Standard.

Lucas: Und eingeschoben kurz noch, weil das erste Mal, als mir Huffman Coding begegnet ist, ist tatsächlich, als ich mir Perl damals angeschaut habe, weil Larry Wall, der Erfinder von Perl, hat auch das als Prinzip angewandt auf seine Programmiersprache, dass die Methoden oder die Funktionen, die man häufig aufruft, möglichst kurze Namen haben sollen und die, die man selten braucht, längere Namen haben sollen. Da hat er quasi dieselbe Idee benutzt, ob das jetzt zum Vorteil oder zum Nachteil der Sprache ist, das lasse ich die Hörerinnen und Hörern selbst überlegen. Eine Alternative oder eine andere Idee zu Huffman ist noch die arithmetische Kodierung. Was sind da die Ähnlichkeiten? Was sind die Unterschiede?

Stefan: Beide zusammen findet man relativ häufig als Entropy Encoding. Eigentlich versuchen wir gerade auszunutzen, dass wir bestimmte statistische Information über die Daten haben und Entropie, ich würde jetzt zu tief gehen, wenn wir hier über den informationstheorischen Bereich und Entropie, was das eigentlich sein soll, sprechen wollen. Im Endeffekt ist das so ein Maß dafür, wie gleich verteilt oder wie chaotisch eigentlich meine Daten sind. Das mal beiseite schiebend. Bei Huffman Encoding, ich habe das gerade schon beschrieben. Wenn wir da As, Bs und Cs haben und die treten mit bestimmten Häufigkeiten auf, dann komme ich auf ein Bit und das passte gerade auch super. Und das Beispiel, das ich genannt habe, habe ich ganz bewusst so gewählt, dass ich 50%, 25%, 25% an Verteilung habe. Wenn ich mir vorstellen würde, das A tritt aber in 99% aller Zeichen auf und ich habe nur As und Bs, dann muss ich trotzdem für A und B jeweils ein Bit benutzen. Und ich habe eigentlich gar nichts mehr davon, dass ich dieses sehr starke Ungleichgewicht an Verteilung habe. Ich komme bei Huffman Encoding nicht unter ein Bit drunter, wenn man so möchte. Und Arithmetic Encoding ist eine Idee, die sagt: Lass uns doch versuchen, den kompletten Satz an Daten, den ich komprimieren möchte, durch eine Zahl auszudrücken. Da gibt es verschiedene Ansätze. Einen, den ich vielleicht versuchen kann, halbwegs plausibel zu erklären, ist, dass man sich vorstellt: Wit suchen eine Fließkommazahl irgendwas zwischen 0 und 1, in dem wir uns den Zahlenraum zwischen 0 und 1 als ein Intervall vorstellen, und wir teilen dieses Intervall auf. In dem Beispiel von drei Symbolen mit 50%, 25%, 25% würden wir sagen, von 0 bis 0,5, hätten wir ein Intervall, das für das Zeichen A steht. Von 0,5 bis 0,75 steht das für das Zeichen B und von 0,75 bis 1 steht das Ganze für das Zeichen C. Dann schauen wir uns das erste Zeichen an und wissen dann danach, wenn es ein A gewesen ist. Unsere Zahl, die wir am Ende rausgeben, muss irgendwo zwischen null und 0,5 sein. Und dann teilen wir dieses Intervall wieder genau nach dieser Wahrscheinlichkeitsverteilung auf und kommen auf immer kleinere Intervalle und kommen am Ende auf eine Fließkommazahl aus, die genau mir, wenn ich wieder zurückgehe, das Intervall geben kann. Ich liege in einem bestimmten Intervall und kann zurückrechnen, wie denn die Datei ursprünglich ausgesehen hat, wenn ich diese Zahl bekomme. Ich kann es hier sicherlich so nicht erklären und nicht nachweisen, aber ich komme auf diese Art und Weise, wenn ich das so einbaue, auf potenziell deutlich unter 1 Bit an Information, die ich übertragen muss, um zu sagen: Ganz viele A’s waren da. Mein A braucht weniger als ein Bit am Ende.

Lucas: Okay, interessant. Das klingt auf jeden Fall nach einem komplizierteren Algorithmus als der von Huffman. Aber es gibt noch eine weitere Art, damit umzugehen. Das ist das Run-length encoding?

Stefan: Eigentlich ist Run-length encoding, da muss man ein Stück zurückgehen. Das, was wir gerade besprochen haben. Huffman, wie auch Arithmetic encoding sagt, ich habe irgendwelche Daten, über die kenne ich die statistische Verteilung, und deshalb rechne ich mir ein bestimmtes Verfahren aus, wie ich das besser kodieren kann, damit ich möglichst wenig Daten für das angeben muss. Wenn wir uns meine fiktive Datei mit 100 As und 50 Bs und Cs anschauen, dann habe ich gesagt, dann brauche ich dafür 200 Bit in Huffman Encoding. Und völlig egal, wie die As, Bs und Cs verteilt sind. Wenn wir uns aber jetzt vorstellen, dass diese Datei die 100 As hintereinanderstehen hat und danach 50 Bs hintereinander und 50 Cs hintereinander, dann brauche ich im Huffman Encoding immer noch meine 200 Bit um das darstellen zu können. Aber man könnte sich was viel naiveres vorstellen und ich glaube Run-length encoding ist am Ende sogar älter von der Idee her als Huffman, weil sie so naheliegend ist, dass ich nicht sage, ich kodiere da irgendwas anderes, sondern ich sage: Jetzt kommt 100 Mal das Zeichen A, indem ich erstmal 1 Byte brauche, indem ich sage: Das nächste Zeichen wird hundertmal wiederholt, und dann schreibe ich das Zeichen A und dann sagt das nächste Byte: Das nächste Zeichen wird 50 mal wiederholt und schreibe das Zeichen B und für C mache ich das Gleiche und dann komme ich runter auf ganze sechs Bytes, die ich habe. Und das ist natürlich viel kürzer auch noch als die 200 Bit, die ich hatte, wenn ich dann auf 48 Bit runter komme anstatt 200 Bit. Ich habe es also noch viel stärker komprimiert und das ohne, dass ich irgendwelches statistisches Wissen benutzt habe. Die Idee, die ich da gerade gegeben habe, ist natürlich der Idealfall. Im schlimmsten Fall habe ich überhaupt keine Wiederholungen von Zeichen. Dann blase ich damit meine Daten eher auf, indem ich vor jedem Zeichen sagen würde: Das nächste Zeichen gibt es genau einmal, habe damit eine Verdopplung meines ursprünglichen Datenvolumens. Aber das sind so andere Ideen. Das worum es eigentlich eher geht ist zu sagen: Wir haben mit Huffman und Arithmetic encoding eine Möglichkeit für willkürlich statistische Verteilungen von Daten. Aber wir können die Statistik besiegen, unter Umständen, indem wir eben solche Dinge finden, in denen zwar Statistik über die komplette Datei betrachtet, uns zu bestimmten Dingen zwingt. Aber wenn wir lokale Statistiken betrachten, kriegen wir vielleicht doch noch ein bisschen mehr herausgeholt, indem wir uns auf solche Wiederholungen beispielsweise stürzen.

Lucas: Aber was die alle gemeinsam haben, ist, dass ich das perfekte „Wörterbuch“ nur dann ermitteln kann, wenn ich die gesamten Daten kenne, richtig?

Stefan: Ich brauche die statistische Verteilung. Bei Run-length encoding nicht. Da schaue ich einfach in die Datei rein. Und sehe einfach: Das A wiederholt sich und wenn es sich nicht mehr wiederholt, dann kann ich irgendwie ausgeben: Habe jetzt zwölf Wiederholungen des As gesehen, da muss ich das vorher nicht wissen. Das gehört schon in eine andere Kategorie von Dingen. Aber bei Huffman und Arithmetic Encoding brauche ich ein statistisches Modell und eine Möglichkeit, das statistische Modell zu gewinnen ist, ich schaue mir die Datei vorher an und mache eine exakte Statistik. Andere Ansätze, die wir später vielleicht noch mal besprechen werden, gehen eher den Weg. Eine andere Möglichkeit wäre die, die du schon angesprochen hast. Wir können uns einfach irgendein Standard Dictionary ausdenken. Ob das jetzt perfekt passt auf die Datei oder nicht, ist relativ egal. Wenn es gut genug ist, könnte ein Huffman Dictionary für englische Texte beispielsweise machen. Und wenn ich weiß, dass ich eine englische Textdatei habe, die ich komprimieren möchte, dann wird das Modell gut genug sein in den meisten Fällen.

Lucas: Das kann man sich ganz gut vorstellen. Das ist auch bekannt, dass bestimmte Buchstaben einfach häufiger vorkommen als andere in einer bestimmten Sprache. Auf Englisch Es und Is kommen häufiger vor als Zs beispielsweise.

Stefan: Genau. Und das, was man in neueren Algorithmen tatsächlich sieht, ist, dass man versucht, diese statistischen Zahlen nicht exakt zu haben, sondern sich anschaut: Was habe ich bisher gesehen und auf Basis verschiedenster Ideen, die aus Wahrscheinlichkeitsrechnung und anderen Richtungen kommen, vorherzusagen, wie denn die statistische Verteilung sein wird und dass man mit diesen vorhergesagten statistischen Verteilungen dann Huffman Encoding oder Arithmetic Encoding macht.

Lucas: Das heißt also, wir haben jetzt die ersten drei Ideen kennengelernt. Eine weitere wichtige Familie von Ideen kommt von Lempel und Ziv. Und das erste ist LZ77, ist das richtig?

Stefan: Ja, genau. Lempel und Ziv haben Ende der 70er Jahre offenbar eine sehr fruchtbare Phase gehabt und sich gleich zwei Algorithmen von Weltruhm, die bis heute benutzt werden, ausgedacht. Und den einen im Jahr 1977, den anderen im Jahr 1978, deshalb heißen die dann LZ77 und LZ78, wenn man drüber spricht. Und LZ77 ist glaube ich der Algorithmus, der am meisten Einfluss gehabt auf das, was in späteren Dingen entstanden ist, hat. Das ist eigentlich die Grundlage der meisten Kompressionsverfahren, die heute eingesetzt werden. Die Idee ist gar nicht so ganz anders als die bei Run-length Encoding. Ich suche nach Dingen, die sich wiederholen. Nur da, wo ich bei Run-Length Encoding vielleicht auf ein einzelnes Byte geschaut habe, ist die Idee bei LZ77, ich habe schon mal Daten gehabt. Ich bin also jetzt irgendwo in der Mitte meines Datenbestandes und stelle fest, das, was ich hier jetzt gerade vor mir liegen habe, dieses Zeichen und die nächsten X Zeichen, die ich mir anschaue, habe ich eigentlich vorher schon mal gesehen. Und dann schreibe ich nicht meine Daten, die ich habe, sondern ich schreibe stattdessen in meine Datei: Hier, füge jetzt bitte ein, die nächsten 20 Byte und du findest die, indem du 50 Bytes vorher schaust, was du da gehabt hast. Dass ich also solche Rückverweise einbaue, und das kann man relativ clever machen. Und das, was bei LZ77, eigentlich von vornherein überraschend war, ist, dass man diese Idee vielleicht sogar noch ein Stück weitertreibt, indem man sagt: Ich schaue nicht nur nach rückwärts, indem ich sage: Schaue 50 Zeichen zurück, sondern ich schaue auf das, was dabei, wenn ich das anwende, entsteht. Das klingt jetzt ein bisschen komisch, aber wenn ich mir vorstelle: Ich habe diese 100 As, von denen ich gesprochen habe, dann muss ich nicht erst mal zwei, drei As gesehen haben und dann sagen: Und jetzt bitte gehe drei Stück zurück und kopiere wieder drei As hierhin. Sondern was ich tun kann, ist, dass ich das erste A rausgeben muss, da habe ich noch keine Vergangenheit. Das nennt sich in dem Kontext dann ein Literal, dass ich also sage: Hier habe ich Daten, wofür ich keinen Rücksprung habe. Ich gebe also erst mal Daten in einem Literal aus. Ich könnte ein einzelnes A ausgeben. Und beim zweiten Buchstaben könnte ich sagen: Und jetzt gehe bitte ein Zeichen zurück und kopiere von da an die Daten für die nächsten 99 Zeichen. Also nicht genau zufällig, falls das einer A ist, immer wieder das gleiche A zu wiederholen, sondern eigentlich das, was aus diesem Kopieren und Wiederholen entsteht, dass ich das nach vorne fortsetze, das ist gerade ohne Papier furchtbar schwierig zu erklären. Aber der Trick besteht tatsächlich darin, dass ich vielleicht sogar in auch nach vorneguckend Daten mitkopiere, anstatt nur komplett aus dem zu nehmen, was hinter mir liegt.

Lucas: Aber das bedeutet, dass dieses Verfahren besonders dann interessant ist, wenn ich viele Wiederholungen in meinem zu komprimierenden Datensatz. Ist das richtig?

Stefan: Genau. Und so ein Stück weit muss es sich auch lohnen, auf die Wiederholung zurückzuverweisen. Ich muss im Zweifel auch Daten schreiben, um zu sagen: Gehe jetzt 50 Byte zurück und kopiere von da 20 Byte. Irgendwie muss ich auch diese Information schreiben, das kostet im Zweifel auch irgendwas. Da werde ich dann schon ein paar Byte für benötigen, um das hinschreiben zu können. Also muss das, was ich aus der Vergangenheit hole, auch lang genug sein, damit sich das lohnt. Wenn ich am Ende mehr brauche, um zu sagen: Geh dahinten hin zurück, als die eigentliche Datenmenge gewesen ist, die ich da wiederholen möchte, dann lohnt sich das auch nicht mehr. Aber in real existierenden Dateien finden wir das relativ häufig, dass wir Wiederholungen haben. Und bei Bildern kann man sich das relativ leicht vorstellen, wenn die naiv codiert sind, schwarz-weiß Bitmaps, die vielleicht nur aus Nullen und Einsen bestehen. Da wären dann große weiße Flächen vielleicht ganz viele Einsen und große schwarze Flächen ganz viele Nullen. Dann hätte ich ganz starke Wiederholungen, die da drin sind. Und in Texten haben wir sicherlich Worte, die immer wieder auftauchen oder Silben, die immer wieder auftauchen, auf die ich zurückverweisen kann. Wenn ich mir XML Dokumente, HTML Dokumente anschaue, die Tags, die darin auftauchen – <div – das sind dann vier Zeichen, die ich wahrscheinlich ziemlich häufig in einer HTML Seite finde, auf die ich zurückverweisen kann. Das ist schon sehr effizient, was ich da finde.

Lucas: Genau. Und das ist auch einer der Gründe, warum vielleicht eine Minifizierung mit diesem Verfahren, die man auch in JavaScript häufig benutzt, vielleicht manchmal gar nicht so viel hilft, weil man die Variablennamen auch wieder wiederholende Daten sind. Wenn ich immer wieder ein 30 Zeichen langen Identifier benutze und den wieder benutze und wieder benutze, dann kann ich ihn in so einem Lempel-Ziv Komprimierung sehr kurz ausdrücken und einfach nur sagen: Bitte füge jetzt hier wieder den Variablennamen ein, anstatt den jetzt irgendwie zur „Compilezeit“ in ein Ein-Buchstaben-Identifier zu ersetzen. Das ist eine der Gründe, warum oftmals das gar nicht so interessant ist, die Variablennamen zu kürzen, wenn man danach sowieso so was wie GZIP oder so was benutzt.

Stefan: Richtig. Das gleiche gilt für White Space einsparen, weil sieben Spaces hintereinander oder so was in der Form vielleicht sowieso häufig genug auftauchen, dass ich die nachher auch zu kurz codieren kann.

Lucas: Genau. Ich vermute, die meisten Kompressionsverfahren haben ein sehr kurzes Zeichen für Leerzeichen, vermute ich jetzt mal, weil das doch ein sehr häufiges Zeichen ist. Ein Verfahren, was auch ein bisschen in diesem Bereich mitspielt ist das Snappy Verfahren, was ich irgendwie aus dem Datenbankkontext kenne. Kannst du dazu kurz was sagen?

Stefan: Bei LZ77 habe ich versucht zu erklären, es ist mir nicht wirklich gut gelungen. Der Algorithmus soll als solcher funktionieren. Ich habe irgendwo abwechselnd, nicht immer streng abwechselnd, aber ich habe immer wieder Blöcke von Daten, für die ich vorher noch nichts gesehen habe. Damit habe ich auch an, was die Literale sind. Und dann habe ich solche Rücksprünge, bei denen ich sage: Jetzt kopiere bitte was aus der Vergangenheit. Das ist aber erst mal nur der Algorithmus. Wie das aussieht, das muss ich in irgendeiner Art und Weise konkret kodieren. Snappy ist ein Format, das nichts anderes als das macht. Das ist eine spezielle Form, um zu sagen: Ich habe Blöcke, die Literale sind. Ich habe Blöcke, die solche Wiederholungen von irgendwas sind, was in der Vergangenheit stattgefunden hat. Und ich habe eine bestimmte Art und Weise, wie ich das codiere. Das machen ganz viele andere Algorithmen oder andere Formate auch, die dann möglicherweise noch zusätzlich etwas mehr hinzu. Bei Snappy hat man sich ganz bewusst ausschließlich auf genau dieses Anwenden von LZ77… Wir reden jetzt nur über Lempel und Ziv. Tatsächlich haben ein paar andere Leute noch das ganze Verfahren erweitert, das dann aus LZ77 häufig eher formal richtiger wäre es als LZSS, weil ein Herr Storer und ein Herr Schimanski noch Weiterentwicklungen beigetragen haben. Aber die beschränken sich ins Snappy eben genau auf diesen puren Algorithmus mit einer bestimmten Kodierung und machen nicht mehr als das, verzichten dadurch möglicherweise ein stückweit auf Kompression. Es könnte vielleicht noch weniger Daten brauchen, wenn man hinten drauf noch ein bisschen mehr machen würde als das. Dafür geht es aber sehr schnell und das sowohl beim Komprimieren jetzt verhältnismäßig schnell als auch beim Dekomprimieren. Und was Snappy noch macht ist, dass es die Daten ganz bewusst in Blöcke segmentiert. Das ist ein Framed Snappy, dass man um den eigentlichen Snappy Algorithmus sagt: Ich zerlege meine Daten in Blöcke, die ich dann parallel komprimieren kann und das macht es zum Beispiel interessant. Snappy ist auch ein Hadoop Dateisystem beispielsweise drin, dass man das genau auf den Knoten verteilt. Jeder Knoten kann seine Daten für sich separat komprimieren und dekomprimieren ohne die Daten kennen zu müssen, die auf anderen Knoten in einem verteilten Dateisystem, das auf mehreren Rechnerknoten sitzt, auslesen oder schreiben zu können. Das ist so ein Schritt, der bewusst gegangen worden ist um in die gleiche Familie von Kompressionsalgorithmen oder Formaten gehört, LZ4. Das ist ein bisschen schneller als Snappy noch von der Idee her und ist vielleicht sogar zumindest in der C-Implementierung ein bisschen besser in der Kompression, aber es ist eigentlich die gleiche Kategorie. Wir machen nur LZ77 und nicht noch irgendwas obendrauf.

Lucas: Und Snappy wird in ganz vielen Datenbanken benutzt, wie zum Beispiel MongoDB, Cassandra, Hadoop. Die benutzen das alle, um ihre Daten auf die Festplatte oder die SSD zu schreiben, um das platzsparender zu machen. Aber da ist, wie Stefan schon sagt, einfach die Geschwindigkeit wirklich essenziell wichtig. Und da ist es dann nicht ganz so wichtig, ob es vielleicht das Allerkleinste ist, was man da schreibt. Das ist anders, als, wenn man die Daten übertragen möchte. Aber du hast eben schon angesprochen, Lempel und Ziv haben sich 1977 nicht in den Ruhestand begeben, sondern haben dann 1978 ihr zweites rausgebracht. LZ78. Was ist denn da die Veränderung zu der LZ77? Oder ist es ein ganz anderer Algorithmus, der gar nichts damit zu tun hat?

Stefan: Das, was die Gemeinsamkeit ist, ist, dass wir wieder ausnutzen, dass sich Dinge wiederholen. Aber da hört es eigentlich auch schon auf mit den Gemeinsamkeiten. LZ77 schaut nach hinten und LZ78 schaut nach vorne. Die Idee ist: Ich überlege mir, dass ich ein Wörterbuch brauche für meine Daten. Und es ist ein komplett Wörterbuch-basiertes Verfahren, bei dem ich das Wörterbuch, während ich die Daten komprimiere, erst anfange aufzubauen. Die einfachste Idee ist zu sagen: Ich benutze für jedes Symbol, bleiben wir bei Texten, die in einem 8 Bit Zeichensatz sind, ASCII oder so etwas. Und ich benutze 9 Bit pro Symbol und ich starte mein Wörterbuch, indem ich das schon mal initialisiere, damit die 8 Bit meines ASCII-Zeichensatz sind genau die ersten 256 Zeichen, die in meinem Wörterbuch drinstehen, das aber durch ein Bit mehr doppelt so viele Daten aufnehmen könnte. Wenn ich dann anfange zu kodieren, dann sage ich: Ich sehe hier ein A, dann schreibe ich jetzt auf den Strom 9 Bit, die sagen: Das A ist da gewesen, dann schaue ich mir das nächste Zeichen an und schaue: Habe ich diese Sequenz von A und folgendem A eigentlich schon mal gesehen? Habe ich dafür schon einen Eintrag in meinem Wörterbuch? Es ist in den 9 noch nicht drin. Ich bin gerade erst beim zweiten Zeichen angekommen, dann schreibe ich dieses A auch raus. Aber ich merke mir dann im ersten freien Slot meines Wörterbuchs die Sequenz AA und die kriegt jetzt ein neues Symbol. Und so treibe ich das weiter. Und beim Dekomprimieren macht die Software, die dekomprimiert ganz genauso. Die sieht das erste A und sieht das zweite A und weiß: Okay, jetzt habe ich also die Sequenz von AA. Das ist der zweite Eintrag in meinem Wörterbuch. Und baut während der Dekompression genau das gleiche Wörterbuch auf, das beim Komprimieren aufgebaut worden ist. Und so treibe ich das weiter, und je länger ich das mache, desto mehr sammle ich dann möglicherweise Sequenzen ein, die länger sind und wo es sich dann gelohnt hat, die tatsächlich in das Wörterbuch abzulegen. Aber da wird erst mal ohne irgendeine Statistik, ohne irgendwas vorher zu wissen, das Wörterbuch einfach dynamisch zur Laufzeit aufgebaut. Wenn ich jetzt gesagt habe, mit 9 Bit kann man das Ganze machen, wird man irgendwann feststellen: Das Wörterbuch ist voll. Was tun wir jetzt an der Stelle? Und da unterscheiden sich dann verschiedene konkrete Implementierungen, wie diese Idee von LZ78 weitergetrieben wird. Manchmal lässt man ab der Stelle das Wörterbuch wachsen und sagt: Okay, sowohl der komprimierende als auch der dekomprimierende Algorithmus weiß: Jetzt ist das Wörterbuch mit seinen 9 Bit voll. Jetzt benutzen wir ab jetzt 10 Bit auf beiden Seiten. Oder ich fange einfach von vorne an und sage: Okay, setzen wir zurück und fangen einfach neu an zu kodieren. Was bei einigen von den konkreten Fällen, wo LZ78 oder in der Weiterentwicklung von Herrn Welsch, der noch dazugekommen ist, dann LZW ist, wo man dann vielleicht feststellt: Das Wörterbuch, das wir da haben, ist eigentlich gar nicht mehr so toll. Das hat am Anfang gut gepasst, aber inzwischen hat sich irgendwas in den Daten verändert und so richtig passt das Ganze nicht mehr ineinander. Wir finden eigentlich gar nicht mehr die Hits oder wenn wir was finden, dann brauchen wir dafür viel zu viele Bit. Das sieht gar nicht so toll aus. Fangen wir doch noch mal von vorne an. Also das ist durchaus in den konkreten Implementierungen dieser Idee dann mit eingebaut, dass man feststellt zwischendrin, wenn wir noch mal von vorne anfangen würden, bekommen wir ab hier eine bessere Kompression. Bis hierhin haben wir irgendwas, was auch schon komprimiert übertragen worden ist, aber ab hier können wir vielleicht noch mal was gewinnen, indem wir von vorne anfangen mit einem neuen Dictionary. Das gibt dann extra Symbole, die vorher verabredet worden sind. In das Dictionary gleich Symbole einbaut für: Wir wollen noch mal von vorne anfangen.

Lucas: Ja, verstehe.

Stefan: Genutzt wird LZ78 in GIFs. Deshalb ist das auch so ein bisschen in dieser Falle von Patent belasteten Algorithmen geraten und hat glaube ich danach weniger Beachtung gefunden als LZ77. Alleine schon deshalb, weil man eben immer diese Patent Problematik im Hinterkopf hatte.

Lucas: Ja. Kann man denn sagen, dass LZ78 weniger oder mehr komprimiert als LZ77 ist? Oder lässt sich das allgemein gar nicht beantworten?

Stefan: Tatsächlich muss man sich anschauen, was man denn tatsächlich zu komprimierende Daten hat. Ich glaube, es gibt nicht den einen Algorithmus, der optimal und ideal für alle Daten ist, die man hat. Aber wenn man statistische Mittel anschaut, scheint es schon so zu sein, dass die LZ77 basierten Algorithmen heute die besseren Ergebnisse liefern. Kombiniert allerdings durchaus mit Entropie Encoding, Huffman oder Arithmetic Encoding, das hinten drauf noch angewendet wird.

Lucas: Okay. Wir haben jetzt glaube ich die wichtigsten Algorithmen Familien durchgesprochen, also Huffman, arithmetische Kodierung, LZ77 und LZ78. Aber es gibt noch so ein paar, die vielleicht ein bisschen ungewöhnlicher sind, die man auch nicht ganz so häufig begegnet. Kannst du die auch noch mal vielleicht beispielhaft vorstellen?

Stefan: Ja, gerne. Kurz zum Hintergrund: Ich habe mit Kompressions Algorithmen vor allen Dingen zu tun über Apache Commons Compress. Das ist eine Java Bibliothek für Archivierung und Kompressionsformate und da gibt es einen Algorithmus: Bzip2. Der gerade vor allem in den Neunzigern sehr beliebt gewesen ist, weil er deutlich besser komprimiert als Gzip, zumindest oft deutlich besser komprimiert. Und für den gibt es in dieser Bibliothek auch eine Implementierung, aber die hat irgendjemand beigesteuert und ist anschließend nicht mehr Teil des Projekts gewesen. Und dann gab es einen Bug in einem Teil davon und dann musste man erst mal anfangen zu verstehen, wie dieses Ding eigentlich funktioniert. Und dann mehrere verschiedene Ideen zusätzlich zu Huffman Encoding und Runlength Encoding, was eigentlich so der Kern von Bzip2 ist, hinzugefügt. Und die Idee, die diese Dinge, die da eingebaut worden sind, haben, ist sie sorgen einfach dafür, dass wir Wiederholungen bekommen. Wir versuchen die Daten so umzustrukturieren, dass wir sie reversibel umstrukturieren, wir das also wieder zurückbekommen, was wir da eigentlich haben. Aber wir hoffen dabei möglichst viele Wiederholungen in die Daten zu bekommen. Und eine Idee, die man beispielsweise haben könnte, ist, dass man nicht den Wert, der irgendwo steht, über eine Messfolge, eine Messreihe beispielsweise schauen würden, nicht den konkreten Messwert nehmen, sondern ich auftrage, wie die Veränderung des Messwerts zum vorherigen Messwert gewesen ist. Das nennt sich dann Delta Encoding. Das ist nicht in Bzip2 drinnen, aber das ist das Ding, was man einfacher erklären kann. Wenn ich mir vorstelle, ich habe einen Messwert, der linear immer größer wird, dann habe ich da vielleicht nicht die Folge 23456 drinstehen, sondern ich habe da drinstehen 211111 und dann habe ich eben diese Abfolge von Einsen, die ich besser komprimieren kann, weil es immer wieder die gleiche ist. Und ich kann das Delta Encoding anschließend rückgängig machen, relativ einfach, indem ich eben wieder aufaddiere. Exotischer und von der Idee her etwas wilder ist die Burrows Wheeler Transformation. Das ist das, was das B von Bzip2 eigentlich ausmacht. Die Idee ist: Ich nehme mir meine Daten, die ich komprimieren möchte und betrachte die praktisch als Zeile, nehme das wirklich als Text. Also ich habe eine Textzeile, die heißt A, B, C, machen wir es möglichst kurz, dann bekommen wir das besser erklärt. Die schreibe ich darunter noch mal, aber ich rotiere die einmal nach links. Also ich schreibe mir dann eine Matrix hin, die aus drei mal drei besteht, in dem ich das jeweils wiederholt habe. Ich habe in der ersten Zeile A, B, C stehen, in der zweiten habe ich dann B, C, A stehen und in der dritten habe ich C, A, B stehen. Jetzt habe ich blöderweise keine Wiederholung drinnen, so dass das nicht viel nützt. Sagen wir, ich nehme A, B, A, in der zweiten Zeile habe ich dann B, A, A und in der dritten habe ich A, A, B stehen, wenn ich das so durchdenke. Und die sortiere ich alphabetisch diese Zeilen, die ich habe. Bekomme dann A, A, B in der ersten Zeile, A, B, A in der zweiten und B, A, A in der dritten Zeile. Und ich merke mir, die zweite war die, die ich ursprünglich gehabt habe und dann schmeiße ich alles weg aus der letzten Spalte. Und in der letzten Spalte stehen nach dem, was ich gerade erzählt habe, irgendwie B, A, A zufällig. Aber das, was man tatsächlich feststellt, ist, wenn man diesen Algorithmus auf echte englische Texte beispielsweise anwendet. Wenn wir uns vorstellen, wir haben einen langen englischen Text, den ich eben so mir vorstelle, dann habe ich nach dem alphabetischen Sortieren alle THIS untereinander stehen, also T, H, I, S, die irgendwo da sind. Weil ich alle Substrings, die irgendwo drinnen sind, in dem Text untereinander stehen habe, habe ich alle diese bestimmten Artikel untereinander stehen. Ich habe aber auch alle HIs, deren T in der letzten Spalte gelandet ist, untereinander stehen. Wenn ich das also auf einen englischen Text anwende, dann hat diese letzte Spalte tatsächlich sehr viele Wiederholungen, die im Originaltext in der Form nicht drin gewesen sind. Tatsächlich kann man, wenn man sich nur die letzte Spalte merkt und weiß, welche davon war denn die ursprüngliche Zeile, das kann man mit rein kodieren oder sich out of Band merken, kann man nur mit der letzten Stelle, die eigentlich nur in der letzten Spalte die eine Umsortierung des Originaltextes ist, den Originaltext wiederherstellen und bekommt aber sehr viele Wiederholungen. Das ist die Idee hinter der Burrows Wheeler Transformation. Wie man das jetzt genau macht, kann ich wirklich ohne Papier, glaube ich, nicht vernünftig erklären, wie das funktioniert. Aber das ist ganz spannend. Und genau in diesem Punkt war damals die Schwäche in unserer Bzip2 Implementierung, weil das Sortieren in dieser Burrows Wheeler Transformation da gibt es einen ganz furchtbar schlauen Algorithmus, der auch in der Original C Implementierung genutzt wird, wie man Substrings besonders effizient sortieren kann. Der großartiges Best Case und auch Average Case Verhalten hat und dann wirklich sehr schnell ist. Aber wenn er ganz bestimmte Inhalte bekommt, dann war der furchtbar langsam. Und damit konnte man bei unserer Implementierung, wenn man dem Code besonders präparierten Input gegeben hat, dafür sorgen, dass eine CPU praktisch stundenlang beschäftigt war, bis die Datei endlich fertig komprimiert war. Und da war es dann erst mal rauszufinden, wie das Ding funktioniert. Das war kompliziert.

Lucas: Und das bedeutet, dass konnte man dann tatsächlich für einen Denial of Service Angriff benutzen, indem man einfach bestimmte Einträge im Kommentarfeld oder sowas reinschreibt.

Stefan: Richtig. Bei Commons Compress ist es eben durchaus so, dass die Implementierung vielleicht auch in Build Tools gelandet ist. Und wenn ich dann das schaffe, zu einem Build Server – Hosted Jenkins oder sonst irgendwas – mit einer Datei zu beschäftigen, die ich präparieren konnte, weil ich sie eingecheckt habe in irgendein Repository, dann habe ich damit vielleicht diesen Build Server echt in Bedrängnis kriegen können.

Lucas: Ja, wirklich interessant.

Stefan: Das was in Bzip2 auch noch drinsteckt, ist Move to Front. Da werden eben Dinge auch versucht, noch mal anders zu sortieren. Aber ich glaube, das geht jetzt viel zu weit, wenn ich da auch noch versuche zu erklären, wie das im Detail funktioniert. Die Idee ist aber tatsächlich die, dass man sich überlegt: Wie schaffe ich es, meine Redundanzen in meinen Daten künstlich herzustellen, die vielleicht ursprünglich gar nicht da gewesen sind, um den anderen Algorithmen eine bessere Chance zu geben?

Lucas: Also quasi ein Vorbereitungs Algorithmus. Okay, gut. Wir haben jetzt über ganz viele verschiedene Algorithmen gesprochen. Wir haben zwischendurch auch schon so Sachen wie Bzip und Snappy erwähnt. Aber ich vermute, dass die meisten, die uns gerade zuhören, sagen: Ich habe noch nie irgendwie Rechtsklick „Archivier bitte als LZ77“ gemacht. Sondern man kennt andere Sachen wie Gzip oder Brotli oder sonst irgendwas. Und das sind ja irgendwie darauf aufbauende Algorithmen. Manchmal sind es wirklich darauf aufbauende Algorithmen, manchmal sind es wirklich nur diese Algorithmen und haben ein bestimmtes Format, wie sie ihre Informationen ablegen. Und über die wollen wir als nächstes sprechen. Und da fangen wir vielleicht einfach mal mit den Sachen an, die in jedem Browser eingebaut sind. Da ist, glaube ich, jetzt als erstes zu erwähnen, als so ein bisschen als historische Note der Compress Algorithmus. Was ist das? Das hast du, glaube ich, eben schon erwähnt.

Stefan: Ich bin gar nicht sicher, ob ich es erwähnt habe. Compress kennen alte Unix Veteran:innen möglicherweise als Kommandozeilen Tool. Das dann Compress auch tatsächlich heißt. Und die Dateien haben dann üblicherweise so ein großes Z als Endung gehabt, wenn man damit komprimiert hat. Das ist ein sehr altes Unix Tool. So alt kann es nicht sein, weil es LZ78 können muss. Also zumindest ist es dann von Ende der 70er oder Anfang der 80er. Im Endeffekt Compress benutzt LZW, also das LZ78 mit kleinen Einsprengseln am Rande mit einigen Ideen, wie ich wachse mit meinem Dictionary zur Laufzeit, wenn es notwendig ist.

Lucas: Genau. Und das ist tatsächlich auch die gleiche Idee, die in GIF und TIFF steckt. Und das ist tatsächlich das hatte ich gar nicht mehr auf dem Schirm in allen Browsern immer noch unterstützt als Format, obwohl man das in der Praxis glaube ich heute nicht mehr benutzt. Also ich begegne dem auf jeden Fall in der Praxis nicht mehr. Was man aber schon häufiger sieht, ist tatsächlich ja Deflate. Was ist denn Deflate? Und wo finde ich denn das?

Stefan: Deflate kommt eigentlich ursprünglich aus dem Zip Archiv Format. Phil Katz, der Zip in den Achtzigern erfunden hat – PKZIP für Katz‘ ZIP – war da irgendwie auch das Programm, mit dem man diese Archive hergestellt hat. Der hat den Deflate Algorithmus für eine der neueren Versionen damals des Zip Programms neu erfunden. Und im Wesentlichen besteht Deflate darin, dass ich erst LZ77 mache – oder LZSS – und mir dann eine möglichst gute Idee ausgedacht habe, wie ich dann die Literale und die Rücksprünge, die ich habe, vielleicht noch kleiner bekommen kann. Und das, was er sich ausgedacht hat ist, dass er für die Literale, die übrig bleiben Huffman Encoding anwendet und dass er auch für die Rücksprünge, die eben auch gar nicht so Redundanz frei sind, sondern ich habe vielleicht sehr häufig eine Sequenz von “gehe 50 Zeichen zurück und dann 20 Zeichen nach vorne”, dass ich auch diese in einen eigenen Huffman Dictionary hinein packe und sie dann getrennt komprimiere.

Lucas: Okay. Das heißt also, das kombiniert schon zwei Ideen, die wir schon kennen und wir sehen, das sowohl in Gzip als auch in PNG wird dieser Algorithmus benutzt. Also daran sieht man eben, dass das zumindest mal eine Idee ist, die auch heute noch weitverbreitet ist, obwohl die Ideen ja von 77 und 52 sind. Es ist eben heute immer noch sehr praktisch relevant. Interessant finde ich auch den Zopfli als Beispiel für eine Implementierung von Deflate, die eben kleinere Ergebnisse erzeugt. Also Zopfli ist von Google und Google hat einen Algorithmus geschrieben, der mit Deflate kompatibel ist. Das heißt, wir können etwas mit Zopfli komprimieren und mit Deflate dekomprimieren beispielsweise. Und dabei erreichen sie fünf Prozent kleinere Dateigrößen, aber für eine 80 fache Kompressionszeit, also sind jetzt natürlich beides irgendwie Durchschnittswerte. Jetzt keine absoluten Werte. Und daran erkennt man ja auch, dass man tatsächlich innerhalb von diesen Algorithmen oder zumindest innerhalb von diesen Formaten doch noch ein bisschen Spielraum hat, den Algorithmus entweder leistungsstärker zu machen, indem man besser komprimiert oder vielleicht schneller zu machen. Also da hat man auch noch so ein bisschen Einfluss darauf. Und bei vielen Kompressions Programmen kann man ja tatsächlich auch den Kompressions Faktor konfigurieren und damit die Laufzeit beeinflussen.

Stefan: Genau das, was man dabei auch relativ stark sieht, ist, dass man bei solchen Kompressions Algorithmen häufig ein sehr starkes Ungleichgewicht zwischen dem Aufwand, den man in die Kompression steckt und dem Aufwand, den man für die Dekompression braucht, hat. In ganz furchtbar vielen Algorithmen ist es der Fall, dass die Kompression erheblich mehr Zeit benötigt, erheblich mehr Ressourcen benötigt als die Dekompression. Im Fall von Zopfli ist es ja sogar so, dass der Prozess, der dekomprimiert, gar nicht mal weiß, dass am anderen Ende Zopfli beteiligt gewesen ist. Für den Prozess sieht es aus wie ein Deflate Stream.

Lucas: Ja, genau und das ist finde ich auch etwas, was man für die Praxis mitnehmen kann. Also neben diesem ganzen Thema Wiederholungen sind nicht so schlimm, wie man vielleicht erstmal denkt, weil sie sind eigentlich für Kompression sogar gut. Ich finde da auch wichtig mitzunehmen ist, dass man bei bestimmten Sachen überlegen muss: Ist es vielleicht sinnvoll, ein bestimmtes File, was man sehr oft ausliefert, vorab zu komprimieren, damit man die Komprimierung eben nur einmal durchführt, weil das eben CPU aufwendig ist, diese Komprimierung durchzuführen, aber dass dekomprimieren nachher sehr schnell funktioniert. Also so was kann man dann durchaus abwägen, ob man vielleicht für etwas, wo man vorher nicht weiß, was man eben nicht vorab berechnen kann, beispielsweise die HTML Antwort, die man generiert aus einer Anwendung, dass man da vielleicht keinen Zopfli benutzt, sondern ein ganz klassisches Deflate, weil man das eben zur Laufzeit macht. Aber wenn man es eben zur Compile Zeit macht, weil man zum Beispiel sein CSS oder sein JavaScript vorab in Deflate codieren möchte, kann man dafür durchaus Zopfli benutzen. Und das ist finde ich, eine wichtige Sache, die man einfach im Hinterkopf behalten sollte, wenn man über solche Algorithmen spricht. Aber die Idee von Zopfli wurde tatsächlich auch noch weiterentwickelt zu Brotli. Die Namen ähneln sich auch so ein bisschen. Kannst du ein bisschen was zu Brotli erzählen?

Stefan: Ja, ich glaube, das war so ungefähr das gleiche Team Leute von Google aus der Schweiz, die da die Formate nach Gebäck benannt haben. Genau anders als bei Zopfli benutzt Brotli nicht direkt Deflate. Die nutzt ähnliche Zutaten, verwendet auch LZ77 für Rückreferenzen und für Verweise. Und Huffman Encoding für die Länge der Rücksprünge oder für die Literale selber. Aber mischt die Dinge ein bisschen anders zusammen und benutzt einige der Tricks, die man bei Zopfli gelernt hat, auch um im Brotli etwas besser komprimieren zu können. Das, was aber entscheidend hinzu kommt noch ist, dass bei der Definition des Brotli Formats ein statisches Wörterbuch, ein Dictionary hinzugefügt wird, das sowohl die Software, die die Daten komprimiert, als auch die Software, die die Daten dekomprimiert kennt, dass man also nicht extra übertragen muss. Das wird einmal vorher festgelegt und innerhalb dieses Wörterbuchs befinden sich Worte aus verbreiteten Sprachen, vielleicht sogar auch nur Silben aus verbreiteten Sprachen. Und Sprachen ist nicht unbedingt auf natürliche Sprachen beschränkt, sondern durchaus auch Dinge, die in HTML oder in JavaScript vorkommen. Und wenn ich dann die Daten komprimiere, kann ich eben nicht nur Rückverweise auf Daten machen, die schon vorher enthalten waren in meinem Datenstrom, sondern ich kann auch verweisen auf dieses statische Wörterbuch und kann damit Daten komprimieren als Verweis auf das Wörterbuch, ohne dass ich sie einmal zumindest als Literal in den Strom geschrieben haben muss, wie ich das bei Deflate tun müsste.

Lucas: Ja. Und es ist tatsächlich bei Brotli so, dass sie sich so spezialisiert haben, auch auf Web, dass da eben so Sachen drinstehen wie