Was ist der beste Komprimierungsalgorithmus für kleine 4 KB-Dateien?

Question

Ich versuche, TCP-Pakete jeder von etwa 4   KB Größe zu komprimieren. Die Pakete können ein beliebiges Byte (von 0 bis 255) enthalten. Alle Benchmarks auf Kompressionsalgorithmen, die ich fand, basierten auf größeren Dateien. Ich habe nichts gefunden, was die Kompressionsrate verschiedener Algorithmen auf kleinen Dateien vergleicht, was ich brauche. Ich brauche es Open Source, damit es in C++ implementiert werden kann, also zum Beispiel kein RAR. Welcher Algorithmus kann für kleine Dateien von etwa 4 Kilobyte Größe empfohlen werden? LZMA? HACC? ZIP? gzip? bzip2?

Answer 1

Wählen Sie den Algorithmus, der am schnellsten ist, da Sie wahrscheinlich in Echtzeit daran interessiert sind. Im Allgemeinen komprimieren die Algorithmen für kleinere Datenblöcke ungefähr dasselbe (geben oder nehmen einige Bytes), hauptsächlich weil die Algorithmen das Wörterbuch oder die Huffman-Bäume zusätzlich zu den Nutzdaten übertragen müssen.

Ich empfehle Deflate (verwendet von zlib und Zip) aus einer Reihe von Gründen. Der Algorithmus ist ziemlich schnell, gut getestet, BSD-lizenziert und ist die einzige Komprimierung, die von Zip unterstützt werden muss (wie im Infozip Appnote). Abgesehen von den Grundlagen, wenn festgestellt wird, dass die Komprimierung größer ist als die dekomprimierte Größe, gibt es einen STORE-Modus, der nur 5 Bytes für jeden Datenblock hinzufügt (max Block ist 64k Bytes). Neben dem STORE-Modus unterstützt Deflate zwei verschiedene Arten von Huffman-Tabellen (oder Wörterbüchern): dynamisch und fest. Eine dynamische Tabelle bedeutet, dass der Huffman-Baum als Teil der komprimierten Daten übertragen wird und am flexibelsten ist (für verschiedene Arten von nicht-zufälligen Daten). Der Vorteil einer festen Tabelle besteht darin, dass die Tabelle allen Dekodern bekannt ist und somit nicht im komprimierten Datenstrom enthalten sein muss. Der Dekomprimierungs- (oder Aufblasen-) Code ist relativ einfach. Ich habe sowohl Java- als auch Javascript-Versionen geschrieben, die direkt auf zlib basieren, und sie funktionieren ziemlich gut.

Die anderen genannten Komprimierungsalgorithmen haben ihre Vorzüge. Ich bevorzuge Deflate wegen seiner Laufzeitleistung sowohl im Kompressionsschritt als auch besonders im Dekompressionsschritt.

Ein Punkt der Klarstellung: Zip ist kein Komprimierungstyp, es ist ein Container. Für die Paketkomprimierung würde ich Zip umgehen und einfach die von der zlib bereitgestellten Deflate/Inflation-APIs verwenden.

Answer 2

All diese Algorithmen sind zumutbar. Wie Sie sagen, sind sie nicht für kleine Dateien optimiert, aber der nächste Schritt besteht darin, sie einfach auszuprobieren. Es wird wahrscheinlich nur 10 Minuten dauern, um einige typische Pakete zu testen und zu sehen, welche Größen sich ergeben. (Probieren Sie auch verschiedene Compress-Flags aus). Aus den resultierenden Dateien können Sie wahrscheinlich herausfinden, welches Werkzeug am besten funktioniert.

Die Kandidaten, die Sie aufgelistet haben, sind alle gute erste Versuche. Sie könnten auch bzip2 ausprobieren.

Manchmal ist das einfache "probier sie alle" eine gute Lösung, wenn die Tests einfach zu machen sind. Zu viel denken, manchmal verlangsamen.

Answer 3

Ich glaube nicht, dass die Dateigröße zählt - wenn ich mich richtig erinnere, setzt das LZW in GIF sein Wörterbuch alle 4K zurück.

Answer 4

ZLIB sollte in Ordnung sein. Es wird in MCCP verwendet.

Wenn Sie jedoch wirklich eine gute Komprimierung benötigen, würde ich eine Analyse gängiger Muster durchführen und ein Wörterbuch davon in den Client einfügen, was zu noch höheren Komprimierungsraten führen kann.

Answer 5

Ich tat, was Arno Setagaya in seiner Antwort vorschlug: machte einige Beispieltests und verglich die Resultate.

Die Komprimierungstests wurden mit 5 Dateien durchgeführt, die jeweils 4096 Byte groß waren. Jedes Byte innerhalb dieser 5 Dateien wurde zufällig generiert.

WICHTIG: Im wirklichen Leben wären die Daten wahrscheinlich nicht zufällig, sondern würden eher ein paar sich wiederholende Bytes haben. Somit wäre die Komprimierung in der realen Anwendung tendenziell etwas besser als die folgenden Ergebnisse.

HINWEIS: Jede der 5 Dateien wurde von sich selbst komprimiert (d. H. Nicht zusammen mit den anderen 4 Dateien, was zu einer besseren Komprimierung führen würde). In den folgenden Ergebnissen verwende ich einfach die Summe der Größe der 5 Dateien zur Vereinfachung.

Ich habe RAR nur zu Vergleichszwecken aufgenommen, obwohl es nicht Open Source ist.

Ergebnisse: (vom besten zum schlechtesten)

lzop: 20775/20480 * 100 = 101,44% der Originalgröße

RAR: 20825/20480 * 100 = 101,68% der Originalgröße

LZMA: 20827/20480 * 100 = 101,69% der Originalgröße

PLZ: 21020/20480 * 100 = 102,64% der Originalgröße

BZIP: 22899/20480 * 100 = 111.81% der Originalgröße

Fazit: Zu meiner Überraschung produzierten ALLE getesteten Algorithmen eine größere Größe als die Originale !!! Ich schätze, sie eignen sich nur zum Komprimieren größerer Dateien oder Dateien, die viele sich wiederholende Bytes haben (keine zufälligen Daten wie oben). Daher werde ich keine Art von Komprimierung für meine TCP-Pakete verwenden. Vielleicht wird diese Information für andere hilfreich sein, die kleine Datenmengen komprimieren möchten.

EDIT: Ich vergaß zu erwähnen, dass ich Standardoptionen (Flags) für jeden der Algorithmen verwendet.

Answer 6

Ich hatte Glück, zlib-Komprimierungsbibliotheken direkt zu verwenden und keine Dateicontainer zu verwenden. ZIP, RAR, haben Overhead, um Dinge wie Dateinamen zu speichern. Ich habe gesehen, dass Komprimierung auf diese Weise positive Ergebnisse (Komprimierung kleiner als Originalgröße) für Pakete von bis zu 200 Bytes liefert.

Answer 7

Sie können versuchen delta compression. Die Komprimierung hängt von Ihren Daten ab. Wenn Sie eine Kapselung für die Payload haben, können Sie die Header komprimieren.

Answer 8

Wenn Sie "TCP-Pakete komprimieren" möchten, können Sie eine RFC-Standardtechnik in Erwägung ziehen.

• RFC1978 PPP Predictor Komprimierungsprotokoll
• RFC2394 IP Payload Compression Mit
• RFC2395 IP Payload-Kompression LZS
• RFC3173 IP Payload Compression Protocol (IPComp)
• RFC3051 IP Payload Compression DEFLATE ITU- Verwendung FERNSEHER.44 Packet Methode
• RFC5172 Verhandlung für IPv6-Datagram-Komprimierung IPv6 Control Protocol
• RFC5112 Die Präsenz Spezifische statische Wörterbuch Signaling Compression (SigComp)
• RFC3284 Die VCDIFF Generisches Differencing und Kompressions-Datenformat
• RFC2118 Microsoft-Point -To-Point Compression (MPPC) -Protokoll

Es gibt wahrscheinlich andere relevante RFCs, die ich übersehen habe.

Answer 9

Sie können bicom testen. Dieser Algorithmus ist zur kommerziellen Nutzung verboten. Wenn Sie es für professionelle oder kommerzielle Nutzung wollen, sehen Sie sich den "Range Coding Algorithm" an.