Wie kann ich die Komprimierbarkeit einer Datei schätzen, ohne sie zu komprimieren?

Question

Ich verwende einen Event-Loop-basierten Server in Twisted Python, der Dateien speichert, und ich würde in der Lage sein, die Dateien entsprechend ihrer Komprimierbarkeit zu klassifizieren.

Wenn die Wahrscheinlichkeit, dass sie von der Komprimierung profitieren, hoch ist, würden sie in ein Verzeichnis mit aktivierter btrfs-Komprimierung gehen, andernfalls würden sie woanders hingehen.

Ich muss nicht sicher sein - 80% Genauigkeit wäre reichlich, und würde eine Menge Speicherplatz sparen. Aber da es auch das CPU- und fs-Leistungsproblem gibt, kann ich nicht einfach alles komprimieren.

Die Dateien befinden sich in den niedrigen Megabyte. Ich kann sie nicht testen, ohne einen großen Prozessorblock zu verwenden und die Ereignisschleife übermäßig zu verzögern oder einen Komprimierungsalgorithmus zu refaktorieren, der in die Ereignisschleife passt.

Gibt es eine Best Practice, um eine schnelle Schätzung der Kompressibilität zu geben? Ich habe einen kleinen Brocken (wenige kB) Daten vom Anfang der Datei genommen, ihn komprimiert (mit einer vermutlich tolerierbaren Verzögerung) und meine Entscheidung darauf gestützt.

Irgendwelche Vorschläge? Hinweise? Mängel in meiner Argumentation und/oder Problem?

Answer 1

Nur 1K von der Mitte der Datei wird den Trick tun. Sie möchten nicht den Anfang oder das Ende, da sie Header- oder Trailerinformationen enthalten können, die für den Rest der Datei nicht repräsentativ sind. 1K reicht aus, um mit einem typischen Algorithmus eine gewisse Kompression zu erzielen. Das wird eine relative Komprimierungsmenge für die gesamte Datei vorhersagen, in dem Maße, dass diese mittlere 1K repräsentativ ist. Das absolute Verhältnis, das Sie erhalten, ist nicht dasselbe wie für die gesamte Datei, aber die Menge, die es von keiner Komprimierung unterscheidet, erlaubt es Ihnen, einen Schwellenwert festzulegen. Experimentieren Sie einfach mit vielen Dateien, um zu sehen, wo Sie den Schwellenwert festlegen können.

Wie bereits erwähnt, können Sie Zeit sparen, indem Sie nichts für Dateien tun, die offensichtlich bereits komprimiert sind, z. .png. .jpg., .mov, .pdf, .zip usw.

Die Messung der Entropie ist nicht notwendigerweise ein guter Indikator, da sie nur die Schätzung der Kompressibilität nullter Ordnung angibt. Wenn die Entropie anzeigt, dass es komprimierbar genug ist, dann ist es richtig. Wenn die Entropie anzeigt, dass sie nicht genug komprimierbar ist, dann mag es stimmen oder auch nicht. Ihr tatsächlicher Kompressor ist ein viel besserer Schätzer der Kompressibilität. Es auf 1K laufen zu lassen dauert nicht lange.

Answer 2

Ich denke, was Sie suchen ist How to calculate the entropy of a file?

Diese Fragen alle Arten von Methoden enthält die Entropie der Datei (und damit können Sie die ‚Kompressibilität‘ einer Datei erhalten) zu berechnen. Hier ist ein Zitat aus der Zusammenfassung von this Artikel (Beziehung zwischen Entropy und Test Data Compression Kedarnath J. Balakrishnan, Mitglied, IEEE, und Nur A. Touba, Senior Member, IEEE):

Die Entropie einer Datenmenge ist ein Maß für die Menge der darin enthaltenen Informationen. Entropieberechnungen für vollständig spezifizierte Daten wurden verwendet, um eine theoretische Grenze dafür zu erhalten, wie stark diese Daten komprimiert werden können. Dieses Papier erweitert das Konzept der Entropie auf unvollständig spezifizierte Testdaten (d. H. Die nicht spezifizierten oder nicht interessierenden Bits) und untersucht die Verwendung von Entropie, um zu zeigen, wie Grenzen für die maximale Kompression für eine bestimmte Symbolpartitionierung berechnet werden können. Der Einfluss verschiedener Arten der Partitionierung der Testdaten in Symbole auf Entropie wird untersucht. Für eine Klasse von Partitionen, die Symbole fester Länge verwenden, wird ein Greedy-Algorithmus zum Spezifizieren der Nicht-Entropie-Verringerung beschrieben. Es wird gezeigt, dass es äquivalent zu dem Minimum-Entropie-Set-Cover-Problem ist und somit innerhalb eines additiven konstanten Fehlers in Bezug auf die minimale Entropie ist, die unter allen Arten des Spezifizierens von Nicht-Interessieren möglich ist. Ein Polynomialzeitalgorithmus, der verwendet werden kann, um die Berechnung der Entropie zu approximieren, wird beschrieben. Verschiedene in der Literatur vorgeschlagene Testdatenkompressionstechniken werden hinsichtlich der Entropiegrenzen analysiert. Die Einschränkungen und Vorteile bestimmter Arten von Testdaten-Codierungsstrategien Entropie Theorie studierten mit

und konstruktiver zu sein, Kasse this Website für Python-Implementierung von Entropie Berechnungen von Datenblöcken

Answer 3

Komprimierte Dateien in der Regel don nicht gut komprimieren. Dies bedeutet, dass fast jede Mediendatei nicht sehr gut komprimiert werden kann, da die meisten Medienformate bereits eine Komprimierung beinhalten. Natürlich gibt es Ausnahmen wie BMP- und TIFF-Bilder, aber Sie können wahrscheinlich eine Whitelist von gut komprimierten Dateitypen (PNGs, MPEGs und weg von visuellen Medien - gzip, bzip2, usw.) erstellen, um zu überspringen und dann davon auszugehen Der Rest der Dateien, die Sie finden, wird gut komprimiert.

Wenn Sie Lust haben, sich etwas einfallen zu lassen, können Sie Feedback in das System einbauen (beobachten Sie die Ergebnisse der Komprimierung, die Sie tun, und ordnen Sie das resultierende Verhältnis dem Dateityp zu). Wenn Sie auf einen Dateityp stoßen, der dauerhaft schlecht komprimiert ist, können Sie ihn der Whitelist hinzufügen.

Diese Ideen hängen davon ab, in der Lage zu sein, den Typ einer Datei zu identifizieren, aber es gibt Standard-Dienstprogramme, die ziemlich gut funktionieren (im Allgemeinen viel besser als 80%) - Datei (1), /etc/mime.types, usw.