Ich verwende einen auf Ereignisschleifen basierenden Server in Twisted Python, auf dem Dateien gespeichert sind, und möchte die Dateien nach ihrer Komprimierbarkeit klassifizieren können.

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

Ich muss nicht sicher sein - eine Genauigkeit von 80% wäre ausreichend und würde viel Speicherplatz sparen. Da es aber auch Probleme mit der CPU und der fs-Leistung gibt, kann ich nicht einfach alles komprimiert speichern.

Die Dateien sind in den niedrigen Megabyte. Ich kann sie nicht testen, ohne einen großen Teil der CPU zu verwenden und die Ereignisschleife übermäßig zu verzögern oder einen Komprimierungsalgorithmus so umzugestalten, dass er in die Ereignisschleife passt.

Gibt es eine bewährte Methode, um eine schnelle Schätzung der Kompressibilität vorzunehmen? Was ich mir ausgedacht habe, ist, einen kleinen Teil (wenige kB) Daten vom Anfang der Datei zu nehmen, sie zu testen (mit einer vermutlich tolerierbaren Verzögerung) und meine Entscheidung darauf zu stützen.

Irgendwelche Vorschläge? Hinweise? Fehler in meiner Argumentation und / oder meinem Problem?

9
elpollodiablo 7 Okt. 2012 im 19:04

3 Antworten

Beste Antwort

Nur 10 KB von der Mitte der Datei reichen aus. Sie möchten weder den Anfang noch das Ende, da sie möglicherweise Header- oder Trailer-Informationen enthalten, die nicht für den Rest der Datei repräsentativ sind. 10K reichen aus, um mit einem typischen Algorithmus eine gewisse Komprimierung zu erzielen. Dadurch wird ein relativer Komprimierungsgrad für die gesamte Datei vorhergesagt, sofern diese mittleren 10 KB repräsentativ sind. Das absolute Verhältnis, das Sie erhalten, ist nicht das gleiche wie für die gesamte Datei, aber der Betrag, der sich von keiner Komprimierung unterscheidet, ermöglicht es Ihnen, einen Schwellenwert festzulegen. Experimentieren Sie einfach mit vielen Dateien, um festzustellen, wo der Schwellenwert festgelegt werden soll.

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 unbedingt ein guter Indikator, da sie nur die Schätzung der Kompressibilität nullter Ordnung liefert. Wenn die Entropie anzeigt, dass sie komprimierbar genug ist, ist sie richtig. Wenn die Entropie anzeigt, dass sie nicht komprimierbar genug ist, kann sie richtig sein oder auch nicht. Ihr tatsächlicher Kompressor ist ein viel besserer Schätzer für die Kompressibilität. Das Ausführen auf 1K dauert nicht lange.

12
Mark Adler 29 Nov. 2018 im 22:03

Komprimierte Dateien werden normalerweise nicht gut komprimiert. Dies bedeutet, dass nahezu jede Mediendatei nicht sehr gut komprimiert werden kann, da die meisten Medienformate bereits eine Komprimierung enthalten. Natürlich gibt es Ausnahmen wie BMP- und TIFF-Bilder, aber Sie können wahrscheinlich eine Whitelist mit gut komprimierten Dateitypen (PNGs, MPEGs und weg von visuellen Medien - gzip, bzip2 usw.) erstellen, um das zu überspringen und dann anzunehmen Der Rest der Dateien, auf die Sie stoßen, wird gut komprimiert.

Wenn Sie Lust haben, können Sie Feedback in das System einbauen (beobachten Sie die Ergebnisse Ihrer Komprimierung und ordnen Sie das resultierende Verhältnis dem Dateityp zu). Wenn Sie auf einen Dateityp stoßen, der eine durchweg schlechte Komprimierung aufweist, können Sie ihn der Whitelist hinzufügen.

Diese Ideen hängen davon ab, ob Sie den Dateityp identifizieren können, aber es gibt Standarddienstprogramme, die dies ziemlich gut machen (im Allgemeinen viel besser als 80%) - Datei (1), /etc/mime.types usw.

5
Jean-Paul Calderone 7 Okt. 2012 im 15:27

Ich denke, was Sie suchen, ist Wie berechnet man die Entropie einer Datei? ?

Diese Frage enthält alle Arten von Methoden zur Berechnung der Entropie der Datei (und auf diese Weise können Sie die Komprimierbarkeit einer Datei ermitteln). Hier ist ein Zitat aus der Zusammenfassung von diesem Artikel () Beziehung zwischen Entropie und Testdatenkomprimierung Kedarnath J. Balakrishnan, Mitglied, IEEE, und Nur A. Touba, Senior Member, IEEE):

Die Entropie eines Datensatzes ist ein Maß für die darin enthaltene Informationsmenge. 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. In diesem Artikel wird das Konzept der Entropie für unvollständig spezifizierte Testdaten (d. H. Nicht spezifizierte oder nicht interessierende Bits) erweitert und die Verwendung von Entropie untersucht, um zu zeigen, wie Grenzen des maximalen Komprimierungsbetrags für eine bestimmte Symbolpartitionierung berechnet werden können. Der Einfluss verschiedener Arten der Aufteilung der Testdaten in Symbole auf die Entropie wird untersucht. Für eine Klasse von Partitionen, die Symbole fester Länge verwenden, wird ein gieriger Algorithmus zum Festlegen der Entropie beschrieben, bei dem es nicht darum geht, die Entropie zu reduzieren. Es wird gezeigt, dass es dem Problem der Abdeckung durch minimale Entropiesätze äquivalent ist und somit innerhalb eines additiven konstanten Fehlers in Bezug auf die minimale Entropie liegt, die unter allen Arten der Spezifizierung des Nicht-Interessierens möglich ist. Ein Polynomzeitalgorithmus, der zur Annäherung der Entropieberechnung verwendet werden kann, wird beschrieben. Verschiedene in der Literatur vorgeschlagene Testdatenkomprimierungstechniken werden in Bezug auf die Entropiegrenzen analysiert. Die Einschränkungen und Vorteile bestimmter Arten von Testdatencodierungsstrategien werden unter Verwendung der Entropietheorie untersucht

Um konstruktiver zu sein, lesen Sie this Site für die Python-Implementierung von Entropieberechnungen von Datenblöcken

6
Community 23 Mai 2017 im 10:29