Welches Potenzial steckt in der Kompression mit neuronalen Netzen?
Zur Beantwortung dieser Frage habe ich den Unterordner "Ide" des aktuellen Lazarus-Quelltextes mit verschiedenen Verfahren komprimiert. Das Ergebnis:
Code: Alles auswählen
Unkomprimierte Größe: 9 639 656 Bytes
Programm: Größe komprimiert
Zip 2 119 173 Bytes
gz 2 003 085 Bytes
7z -mx 1 228 846 Bytes
ZPAQ -m3 1 172 436 Bytes
ZPAQ -m4 964 877 Bytes
ZPAQ -m5 877 480 Bytes
PAQ8PX_v188 -7 618 778 Bytes
PAQ8PX_v199 -11l 582.494 Bytes
Vor diesem Hintergrund, dass 7z die Dateien bereits sehr stark komprimiert finde ich es noch einmal ungeheuer beeindruckend, dass es PAQ8PX schafft, die komprimierte Größe noch einmal zu halbieren. Wie macht PAQ das?
Kompression durch neuronale Netze
Das Geheimnis nennt sich Context Mixing (CM). Das Verfahren geht auf das in der 80er Jahren entwickelte Verfahren PPM (prediction by partial match) zurück und wurde um die Jahrtausendwende maßgeblich durch Matt Mahoney weiterentwickelt. Die Funtionsweise wird, neben anderen gängigen Algorithmen, durch Mahoney selbst auf folgender überaus lesenswerten Seite gut verständlich und anhand von Beispielen erklärt:
http://mattmahoney.net/dc/dce.html
Wo finde ich Context Mixing nutzende Kompressionsprogramme?
Die Forschung hin zur sehr dichten Datenkompression dauert bis in die Gegenwart an. Die derzeit hinsichtlich der Kompressionsdichte besten Programme sind Folgende: (beide GPL)
Das von Bryan Knoll entwickelte CMix: https://www.byronknoll.com/cmix.html
Das auf Mahoney's Arbeit aufbauende PAQ8PX: https://github.com/hxim/paq8px
Beide Programme liefern sich in den aktuellen Benchmarks ein dichtes Kopf-an-Kopf-Rennen. Selbst als inkompressibel geltende MP3-und JPG-Dateien werden 20%-30% komprimiert.
Beide Programme sind experimentell und ohne Rücksicht auf Arbeitsspeicherbedarf oder Laufzeit auf die Kompressionsdichte getrimmt. Für alle Experimentierfreudigen unter Euch empfehle ich PAQ8PX, da CMix auf Anhieb ca. 21 GB Arbeitsspeicher benötigt. PAQ8PX hat offenbar auch derzeit die Nase knapp vorn (vgl. https://encode.su/attachment.php?attach ... 1594623573).
CMix und PAQ8PX benötigen für ihre Kompression allerdings extrem viel Zeit. Dadurch sind sie zwar als experimentelles "Forschungs"programm hoch interessant. Für den Alltag erscheinen sie aufgrund der hohen Rechenzeit allerdings unbrauchbar.
Gibt es eine Implementierung von Context Mixing, die alltagstauglich ist und eine hohe Kompressionsdichte mit einer relativ kurzen Kompressionsdauer verbindet?
- Ja, die gibt es!
ZPAQ - hohe Kompressionsdichte UND hohe Geschwindigkeit: Ein Programm für den Alltag
Matt Mahoney hat als eines seiner letzteren größeren Projekte versucht, die Datenkompression durch Context Mixing einer größeren Allgemeinheit zugänglich zu machen und eine Referenzimplementierung geschrieben, die mehere Kompressionsmethoden in sich vereint: (public domain)
http://mattmahoney.net/dc/zpaq.html
ZPAQ beherrscht folgende Kompressionsmethoden:
Code: Alles auswählen
Methode Algorithmus
------- ---------
-m1 LZ77
-m2 LZ77
-m3 LZ77+CM or BWT
-m4 LZ77+CM, BWT or CM
-m5 CM
ZPAQ arbeitet bei vergleichbarer Kompressionsdichte schneller als die gängigen Programme:
Mit der Methode -m3 komprimiert ZPAQ den Ordner auf 1 172 436 Bytes - immer noch besser als 7-zip. Dafür benötigt ZPAQ nur 6,25 Sekunden anstelle von 7-zip mit 8,24 Sekunden.
(Nicht wundern: Gemessen auf meinem 12 Jahre altem Laptop, Ihr kommt bei Euch sicher auf kürzere Zeiten).
Zusammenfassung
Die verlustfreie Datenkompression unter Einbezug des Context Mixing hat in meinen Augen ein enormes Potenzial. Auf der einen Seite werden in experimentellen Programmen die derzeit höchsten Kompressionsdichten mit dem auf neuronalen Netzen beruhenden Verfahren erzielt. Auf der anderen Seite gibt es mit ZPAQ eine starke Implementierung, die nicht nur bei vergleichbarer Kompressionsdichte schneller ist als viele alternative Kompressionsprogramme, sondern die bei Bedarf eine sehr starke Kompressionsmethode zur Verfügung stellt, welche Daten in beeindruckender Dichte komprimiert.