¿Cómo puedo estimar la compresibilidad de un archivo sin comprimirlo?

Question

estoy usando un servidor basado en bucle de eventos en Python trenzado que almacena archivos, y me gustaría ser capaz de clasificar los archivos según su compresibilidad.

Si la probabilidad de que habían benefician de compresión es alta, que iría a un directorio con compresión btrfs encendido, de lo contrario irían a otra parte.

No necesito estar seguro - 80% de precisión sería un montón, y se ahorraría una gran cantidad de espacio en disco. Pero dado que también existe el problema de rendimiento de CPU y fs, no puedo simplemente guardar todo comprimido.

Los archivos están en los bajos megabytes. No puedo comprimirlos sin usar una gran cantidad de CPU y demorar indebidamente el ciclo de eventos o refactorizar un algoritmo de compresión para que encaje en el ciclo de eventos.

¿Hay mejores prácticas para dar una estimación rápida de la compresibilidad? Lo que se me ocurre es extraer un pequeño fragmento (pocos kB) de datos del comienzo del archivo, comprimirlo (con un retraso presumiblemente tolerable) y basar mi decisión en eso.

¿Alguna sugerencia? ¿Sugerencias? ¿Defectos en mi razonamiento y/o problema?

Answer 1

Sólo 1K desde el medio del archivo hará el truco. No desea el comienzo ni el final, ya que pueden contener información de encabezado o de avance que no es representativa del resto del archivo. 1K es suficiente para obtener cierta cantidad de compresión con cualquier algoritmo típico. Eso predecirá una cantidad relativa de compresión para todo el archivo, en la medida en que ese 1K medio sea representativo. La relación absoluta que obtenga no será la misma que para todo el archivo, pero la cantidad que difiere de la no compresión le permitirá establecer un umbral. Simplemente experimente con muchos archivos para ver dónde establecer el umbral.

Como se indicó, puede ahorrar tiempo al no hacer nada para los archivos que obviamente ya están comprimidos, p. .png. .jpg., .mov, .pdf, .zip, etc.

La medición de entropía no es necesariamente un buen indicador, ya que solo proporciona la estimación de compresibilidad de orden cero. Si la entropía indica que es suficientemente compresible, entonces es correcto. Si la entropía indica que no es suficientemente compresible, puede o no ser correcto. Su compresor real es un estimador de compresibilidad mucho mejor. Ejecutarlo en 1K no tomará mucho tiempo.

Answer 2

Creo que lo que busca es How to calculate the entropy of a file?

Esta pregunta contiene todo tipo de métodos para calcular la entropía del archivo (y por que se puede obtener la 'compresión' de un archivo). He aquí una cita a partir del resumen del artículo this (relación entre la entropía y de datos de prueba de compresión Kedarnath J. Balakrishnan, miembro de la IEEE, y Nur A. Touba, Senior Member, IEEE):

La entropía de un conjunto de datos es una medida de la cantidad de información contenida en él. Los cálculos de entropía para datos completamente especificados se han utilizado para obtener un límite teórico sobre la cantidad de datos que se pueden comprimir. Este documento amplía el concepto de entropía para datos de prueba incompletamente especificados (es decir, que tiene bits no especificados o no importa) y explora el uso de entropía para mostrar cómo se pueden calcular los límites en la cantidad máxima de compresión para una partición de símbolo particular. Se estudia el impacto de las diferentes formas de partición de los datos de prueba en símbolos de entropía. Para una clase de particiones que usan símbolos de longitud fija, se describe un algoritmo codicioso para especificar el no importa para reducir la entropía. Se muestra que es equivalente al problema de cobertura de conjunto de entropía mínimo y, por lo tanto, está dentro de un error constante aditivo con respecto a la entropía mínima posible entre todas las formas de especificar el no importa. Se describe un algoritmo de tiempo polinomial que se puede usar para aproximar el cálculo de la entropía. Se analizan diferentes técnicas de compresión de datos de prueba propuestas en la literatura con respecto a los límites de entropía. Las limitaciones y ventajas de ciertos tipos de estrategias de datos de prueba de codificación se estudió usando la teoría de entropía

Y para ser más constructivo, la caja this sitio para la aplicación de pitón de los cálculos de entropía de fragmentos de datos

Answer 3

archivos comprimidos suelen don se comprime bien Esto significa que casi cualquier archivo de medios no se comprimirá muy bien, ya que la mayoría de los formatos de medios ya incluyen compresión. Está claro que hay excepciones a esto, como BMP y TIFF, pero es probable que puedan construir una lista blanca de tipos de archivos con una buena compresión (PNG, MPEG, y aventurarse fuera de los medios visuales - gzip, bzip2, etc) para saltar y luego asumen la el resto de los archivos que encuentres se comprimirán bien.

Si le apetece ser elegante, puede generar retroalimentación en el sistema (observe los resultados de cualquier compresión que haga y asocie la relación resultante con el tipo de archivo). Si te encuentras con un tipo de archivo que tiene compresión deficiente, podrías agregarlo a la lista blanca.

Estas ideas dependen de la capacidad de identificar el tipo de archivo, pero hay utilidades estándar que hacen un trabajo bastante bueno (generalmente mucho mejor que el 80%) - file (1), /etc/mime.types, etc.