Login
Newsletter
Werbung

Mi, 23. September 2015, 12:01

Software::Entwicklung

Google stellt neuen Kompressionsalgorithmus Brotli vor

Entwickler von Google haben den Brotli-Algorithmus, der bereits im Web-Font-Format WOFF2 zum Einsatz kommt, unter der Apache 2.0-Lizenz veröffentlicht. Brotli ist eine der besten bekannten Kompressionsmethoden und beim Dekomprimieren schneller als Deflate/GZip.

Mirko Lindner

Ein Algorithmus, der stärker komprimieren kann als LZMA, aber bei der Dekompression schneller als LZMA und auch GZip ist: Das ist Brotli, ein neues Kompressionsverfahren, das Google entwickelt und jetzt vorgestellt hat.

Ziel von Google war es demnach, einen Ersatz für die Deflate-Kompression zu finden, die in Zip und GZip verwendet wird. Diese Kompression ist bereits recht fortgeschritten und erreicht gute Kompressionsraten bei akzeptablen Geschwindigkeiten. Zudem ist der Algorithmus simpel. Doch Google suchte fürs Web nach einem Algorithmus, der stärker komprimiert und dabei mindestens genauso schnell dekomprimiert.

Ein erster Ansatz dazu war Googles Zopfli-Algorithmus, der Deflate-kompatible Dateien erzeugt, die stärker komprimiert sind, aber trotzdem von den Standard-Programmen wie GZip verarbeitet werden können. Effektiv ist Zopfli wie Gzip mit einer noch höheren Kompressionsstufe - GZip bietet die Stufen 1 bis 9 an, wobei 1 am geringsten und 9 am stärksten komprimiert. Doch die benötigte Zeit erhöht sich auf den höheren Stufen drastisch, somit ist Zopfli extrem langsam.

Brotli hingegen verwendet ein eigenes neues Dateiformat. Damit haben die Entwickler eine 20 bis 26 Prozent höhere Kompression als Zopfli erreicht. Brotli ist ein eigenständiges Programm mit Optionen ähnlich wie gzip oder bzip2. Seine Kompressionsstufen reichen allerdings von 1 bis 11. Das in C++ geschriebene Programm steht unter der Apache-Lizenz 2.0.

Ein Fachartikel der Google-Entwickler vergleicht die Leistung von Brotli mit diversen anderen Algorithmen, die von Google in Erwägung gezogen wurden: zlib (Deflate), Zopfli, LZMA, LZHAM und bzip2. Dabei konnte Brotli in den Disziplinen Kompressionsrate, Kompressionsgeschwindigkeit und Dekompressionsgeschwindigkeit Bestwerte auf, allerdings jeweils mit unterschiedlichen Einstellungen - alles zugleich zu optimieren, ist nicht möglich. Die Messungen beziehen sich auf den »Canterbury-Korpus«, eine genau für solche Tests zusammengestellte Sammlung von Text- und Binärdateien.

Auf Stufe 1 komprimiert Brotli mit 98,3 MB/s schneller als Deflate, wobei immer noch eine bessere Kompression erreicht wird. Auch bei der Dekompression kann Brotli Deflate mit bis zu 354,5 MB/s knapp schlagen. Auf der höchsten Kompressionsstufe 11, die einen Faktor von 4,347 und damit den besten Wert aller Programme erreicht, ist die Dekompression etwas langsamer. Die hohe Kompression hat allerdings ihren Preis. Mit 0,5 MB/s ist sie um fast das 200-fache langsamer als Stufe 1. Die anderen Algorithmen sind allerdings auch nicht schneller, und Zopfli schafft nur 0,2 MB/s.

Wie die Autoren schreiben, wurden die Tests mit einem festen Rückwärtsreferenz-Fenster von 22 Bit durchgeführt. Manche Algorithmen könnten mit größeren Werden bessere Leistung zeigen und Brotli die Krone wieder entreißen. Allerdings würden die Zeiten für Kompression und Dekompression sowie der Speicherbedarf bei der Dekompression weiter steigen, was nicht Googles Zielen entspreche. Die Idee von Brotli, ein statisches Wörterbuch für die Kompression von kleinen Dateien einzusetzen, könnte auf einfache Weise auch in die anderen Algorithmen eingebracht werden und diese verbessern.

In der Summe stellt Brotli eine verbesserte Alternative zu Deflate dar und sollte daher bald Unterstützung in den Webbrowsern und eventuell den Webservern finden. Mozilla hat bereits angekündigt, dass Brotli in Firefox 44 erscheinen wird. An anderer Stelle wird Brotli bereits jetzt verwendet: In der Kompression von Web-Fonts im WOFF2-Format.

Werbung
Kommentare (Insgesamt: 4 || Alle anzeigen )
"these go to eleven" (N.T., Mi, 23. September 2015)
Re[2]: Und der Nächste? (CRB, Mi, 23. September 2015)
Re: Und der Nächste? (oder, Mi, 23. September 2015)
Und der Nächste? (Momo, Mi, 23. September 2015)
Pro-Linux
Pro-Linux @Facebook
Neue Nachrichten
Werbung