Artikel: PAQ - über das Potenzial von neuronalen Netzen bei der Datenkompression

Für sonstige Unterhaltungen, welche nicht direkt mit Lazarus zu tun haben
Antworten
Euklid
Lazarusforum e. V.
Beiträge: 2808
Registriert: Fr 22. Sep 2006, 10:38
OS, Lazarus, FPC: Lazarus v2.0.10, FPC 3.2.0
Wohnort: Hessen
Kontaktdaten:

Artikel: PAQ - über das Potenzial von neuronalen Netzen bei der Datenkompression

Beitrag von Euklid »

PAQ ist die Bezeichnung einer Reihe von Kompressionsprogrammen, die mithilfe neuronaler Netze eine starke verlustfreie Datenkompression erreichen.

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
7zip kenne ich als Kompressionsprogramm, das die Daten deutlich besser komprimiert, als herkömmliche Programme, wie z.B. Zip oder gz. Diese Einschätzung wird in diesem Benchmark bestätigt: Die 7z-Datei ist nur etwa halb so groß, wie die von Zip komprimierte Datei.

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
Mit der stärksten Methode -m5 benötigt ZPAQ nur etwa 850 MB RAM und auf modernen Rechnern eine Kompressionszeit von einigen Sekunden. Den "Ide"-Ordner von Lazarus komprimiert ZPAQ dabei auf 877 480 Bytes, was immer noch verdammt gut ist.

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.
Zuletzt geändert von Euklid am So 24. Jan 2021, 14:14, insgesamt 3-mal geändert.

Mathias
Beiträge: 6163
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Artikel: PAQ - über das Potenzial von neuronalen Netzen bei der Datenkompression

Beitrag von Mathias »

Krass, das man über 3x besser komprimieren kann als zip. :shock:
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Euklid
Lazarusforum e. V.
Beiträge: 2808
Registriert: Fr 22. Sep 2006, 10:38
OS, Lazarus, FPC: Lazarus v2.0.10, FPC 3.2.0
Wohnort: Hessen
Kontaktdaten:

Re: Artikel: PAQ - über das Potenzial von neuronalen Netzen bei der Datenkompression

Beitrag von Euklid »

Hallo zusammen,

gerade habe ich einen neuen Benchmark gemacht. Diesmal die Sicherung meiner privaten Dateien von 2009 auf meiner externen Festplatte...

Code: Alles auswählen

Unkomprimierte Größe: 942 987 712 Bytes

Programm:             Größe komprimiert
Zip                   692 328 122 Bytes
ZPAQ -m1              619 091 768 Bytes
7z -mx                605 538 294 Bytes
ZPAQ -m2              578 987 378 Bytes
ZPAQ -m3              562 693 055 Bytes
ZPAQ -m4              555 815 934 Bytes
ZPAQ -m5              544 166 564 Bytes
Mit stärkster Komprimierung erspart ZPAQ im Vergleich zu ZIP also nochmal rund 150 MiB an Speicherplatz.
Die Komprimierung mit -m3 dauerte auf meinem 12 Jahre alten Rechner nur knapp 5 Minuten und bringt im Vergleich zu ZIP dennoch 130 MB zusätzliche Ersparnis.

Meine Externe Festplatte platzt aus allen Nähten. Durch die -m3 Komprimierung kann ich also in vertretbarer Zeit den belegten Speicherplatz etwa halbieren und die Festplatte weitere Jahre mir meinen Sicherungskopien füllen <3

Soweit der zweite Benchmark. Wenn Ihr Lust habt, könnt Ihr weitere Benchmarks machen. Am Besten komprimiert der hier nicht getestete PAQ8PX, der dafür allerdings auch eine halbe Ewigkeit rechnet. (Siehe Tabelle im ersten Beitrag)

Liebe Grüße, Euklid

EDIT: -m2 und -m4 hinzugefügt.

Mathias
Beiträge: 6163
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Artikel: PAQ - über das Potenzial von neuronalen Netzen bei der Datenkompression

Beitrag von Mathias »

Cooler Packer, aber das grösste Problem wird sein, das sie nicht kompatibel zu den Standard Packern ist.

Ich mag mich noch an DOS Zeiten erinnern, da gab es lha, der kompriemierte dazumal schon viel besser als zip.
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Euklid
Lazarusforum e. V.
Beiträge: 2808
Registriert: Fr 22. Sep 2006, 10:38
OS, Lazarus, FPC: Lazarus v2.0.10, FPC 3.2.0
Wohnort: Hessen
Kontaktdaten:

Re: Artikel: PAQ - über das Potenzial von neuronalen Netzen bei der Datenkompression

Beitrag von Euklid »

Hallo Mathias,

da stimme ich Dir zu, das ist so ein bisschen das Henne-Ei-Problem:
--> Ein wenig verbreitetes Format wird von den Standard-Packprogrammen nicht unterstützt
--> Ein Format bleibt wenig verbreitet, wenn es von den Standard-Packprogrammen nicht unterstützt wird.

Das ist ein grundsätzliches Problem. Es gibt aber auch Positivbeispiele:
7zip hat es z.B. gepackt, da es einfach überzeugt: Das Format hat derart gut komprimiert und war derart leicht zu bedienen, dass es sich nach und nach in jedes gute Archivierungsprogramm eingeschlichen hat. Ähnlich auch bei dem proprietären *.rar-Format.

ZPAQ hat folgendes Problem, das ein Ausschlusskriterium für eine weitere Verbreitung ist:
Es gibt derzeit keine gut funktionierende grafische Benutzeroberfläche - d.h. man kann es nur über die Konsole vernünftig nutzen...
... und daran ändern wir jetzt was :D

Die Version 0.9.3 von ZPAQ's Face funktioniert schon in den grundlegenden Dingen. Meine Hoffnung ist so ein bisschen, dass ich dem Mangel an funktionierender Benutzeroberfläche dadurch Abhilfe schaffen kann.
Sobald ZPAQ's Face fortgeschritten entwickelt ist, können wir überlegen, es einer größeren Allgemeinheit zur Verfügung zu stellen und dann sehen wir einfach mal, was passiert :D

Liebe Grüße und einen schönen Abend noch!
- Alexander alias Euklid

Antworten