java - sistemas - sistema de recomendacion tesis

Cómo predecir eficientemente si los datos son compresibles.

Question

Quiero escribir un backend de almacenamiento para almacenar grandes porciones de datos. Los datos pueden ser cualquier cosa, pero se trata principalmente de archivos binarios (imágenes, archivos PDF, archivos jar) o archivos de texto (xml, jsp, js, html, java ...). Encontré que la mayoría de los datos ya están comprimidos. Si todo está comprimido, se puede guardar alrededor del 15% del espacio en disco.

Estoy buscando el algoritmo más eficiente que pueda predecir con alta probabilidad que una parte de los datos (digamos 128 KB) se pueda comprimir o no (compresión sin pérdida), sin tener que mirar todos los datos si es posible.

El algoritmo de compresión será LZF, Deflate o algo similar (tal vez Google Snappy). Por lo tanto, predecir si los datos son comprimibles debería ser mucho más rápido que comprimir los datos en sí y usar menos memoria.

Algoritmos que ya conozco:

• Intente comprimir un subconjunto de los datos, digamos 128 bytes (esto es un poco lento)

• Calcule la suma de 128 bytes, y si está dentro de un cierto rango, es probable que no sea comprimible (dentro del 10% de 128 * 127) (esto es rápido y relativamente bueno, pero estoy buscando algo más confiable, porque el algoritmo realmente solo mira los bits más altos para cada byte)

• Mire los encabezados de los archivos (relativamente confiable, pero se siente como hacer trampa)

Supongo que la idea general es que necesito un algoritmo que pueda calcular rápidamente si la probabilidad de cada bit en una lista de bytes es aproximadamente 0.5.

Actualizar

He implementado ''comprobación ASCII'', ''cálculo de entropía'' y ''compresión simplificada'', y todos dan buenos resultados. Quiero refinar los algoritmos, y ahora mi idea es no solo predecir si los datos se pueden comprimir, sino también cuánto se pueden comprimir. Posiblemente utilizando una combinación de algoritmos. Ahora, si solo pudiera aceptar respuestas múltiples ... aceptaré la respuesta que dio los mejores resultados.

¡Las respuestas adicionales (nuevas ideas) todavía son bienvenidas! Si es posible, con código fuente o enlaces :-)

Actualización 2

Un método similar ahora se implementa en Linux .

Answer 1

Calcular la entropy de los datos. Si tiene una alta entropía (~ 1.0), probablemente no se comprimirá más. Si tiene una entropía baja (~ 0.0), eso significa que no hay mucha "información" en ella y se puede comprimir aún más.

Proporciona una medida teórica de cómo se puede comprimir una pieza de datos.

Answer 2

Desde mi experiencia, casi todos los formatos que pueden comprimirse efectivamente no son binarios. Entonces, verificar si alrededor del 70-80% de los caracteres están dentro de la rabia [0-127] debería hacer el truco.

Si quiere hacerlo "correctamente" (aunque realmente no puedo ver una razón para hacerlo), tiene que ejecutar (parte de) su algoritmo de compresión en los datos o calcular la entropía, como tskuzzy ya ha propuesto.

Answer 3

Dice en tu perfil que eres el autor de H2 Database Engine, una base de datos escrita en Java.

Si estoy adivinando correctamente, está buscando diseñar este motor de base de datos para comprimir automáticamente los datos BLOB, si es posible.

Pero (supongo) se ha dado cuenta de que no todo se comprimirá y la velocidad es importante, por lo que no desea perder un microsegundo más de lo necesario para determinar si debe comprimir los datos ...

Mi pregunta es ingeniería en la naturaleza, ¿por qué hacer todo esto? Básicamente, ¿no se trata de adivinar la intención del usuario de la base de datos / desarrollador de aplicaciones, a expensas de la velocidad?

¿No pensaría que un desarrollador de aplicaciones (que está escribiendo datos en los campos de blob en primer lugar) sería la mejor persona para tomar la decisión si los datos deben comprimirse o no, y si es así, para elegir la compresión adecuada? ¿método?

El único lugar posible en el que puedo ver la compresión automática de la base de datos que posiblemente agregue algún valor es en los campos de texto / varchar, y solo si están más allá de cierta longitud, pero aun así, esa opción podría ser mejor decidida por el desarrollador de la aplicación. Incluso podría ir tan lejos como para permitirle al desarrollador de la aplicación un complemento de compresión, si es así ... De esa manera pueden tomar sus propias decisiones para sus propios datos ...

Si mis suposiciones sobre lo que estás tratando de hacer estaban mal, entonces me disculpo humildemente por decir lo que dije ... (Es solo la opinión de un usuario insignificante).

Answer 4

Este problema es interesante solo porque, por ejemplo, con zlib la compresión de datos no comprimibles lleva mucho más tiempo que la compresión de datos comprimibles. Por lo tanto, hacer una compresión sin éxito es especialmente costoso (para más detalles, consulte los enlaces). Un buen trabajo reciente en esta área ha sido realizado por Harnik et al. de IBM.

Sí, el método de prefijo y la entropía de orden 0 de bytes (llamada entropía en las otras publicaciones) son buenos indicadores. Otras buenas maneras de adivinar si un archivo es comprimible o no son (del papel):

• Tamaño del conjunto principal: el conjunto de caracteres que compone la mayoría de los datos
• Indicador de distribución de pares de símbolos

Aquí está el paper RÁPIDO y las slides .

Answer 5

Implementé algunos métodos para probar si los datos son compresibles.

Compresion simplificada

Básicamente esto verifica pares de bytes duplicados:

static boolean isCompressible(byte[] data, int len) {
    int result = 0;
    // check in blocks of 256 bytes, 
    // and sum up how compressible each block is
    for (int start = 0; start < len; start += 256) {
        result += matches(data, start, Math.min(start + 255, len));
    }
    // the result is proportional to the number of 
    // bytes that can be saved
    // if we can save many bytes, then it is compressible
    return ((len - result) * 777) < len * 100;
}

static int matches(byte[] data, int i, int end) {
    // bitArray is a bloom filter of seen byte pairs
    // match counts duplicate byte pairs
    // last is the last seen byte
    int bitArray = 0, match = 0, last = 0;
    if (i < 0 || end > data.length) {
        // this check may allow the JVM to avoid
        // array bound checks in the following loop
        throw new ArrayIndexOutOfBoundsException();
    }
    for (; i < end; i++) {
        int x = data[i];
        // the bloom filter bit to set
        int bit = 1 << ((last ^ x) & 31);
        // if it was already set, increment match
        // (without using a branch, as branches are slow)
        match -= (-(bitArray & bit)) >> 31;
        bitArray |= bit;
        last = x;
    }
    return match;
}

En mi (limitado) conjunto de datos de prueba, este algoritmo es bastante preciso. Es 5 veces más rápido que comprimirlo si los datos no son compresibles. Para datos triviales (todos ceros), sin embargo, es aproximadamente la mitad de rápido.

Entropía parcial

Este algoritmo estima la entropía de los mordiscos altos. Quería evitar usar demasiados cubos, ya que tienen que ser puestos a cero cada vez (lo cual es lento si los bloques a revisar son pequeños). 63 - numberOfLeadingZeros es el logaritmo (quería evitar el uso de números de punto flotante). Dependiendo de los datos, es más rápido o más lento que el algoritmo anterior (no estoy seguro de por qué). El resultado no es tan preciso como el algoritmo anterior, posiblemente debido al uso de solo 16 depósitos, y solo a la aritmética de enteros.

static boolean isCompressible(byte[] data, int len) {
    // the number of bytes with 
    // high nibble 0, 1,.., 15
    int[] sum = new int[16];
    for (int i = 0; i < len; i++) {
        int x = (data[i] & 255) >> 4;
        sum[x]++;
    }
    // see wikipedia to understand this formula :-)
    int r = 0;
    for (int x : sum) {
        long v = ((long) x << 32) / len;
        r += 63 - Long.numberOfLeadingZeros(v + 1);
    }
    return len * r < 438 * len;
}

Answer 6

Supongo que no hay forma de comprobar qué tan compresible es algo hasta que no intentes comprimirlo. Puede buscar patrones (más patrones, quizás más compresibles), pero luego un algoritmo de compresión particular puede no usar los patrones que usted verificó, y puede hacerlo mejor de lo que espera. Otro truco puede ser tomar los primeros 128000 bytes de datos, pasarlos a través de la compresión Desinflar / Java y ver si es menor que el tamaño original. Si es así, lo más probable es que valga la pena comprimir todo el lote.

Answer 7

También - ¿Por qué no probar lzop? Personalmente puedo responder por el hecho de que es más rápido, mucho más rápido (compresión y descompresión) que bzip, gzip, zip, rar ...

http://www.lzop.org

Al utilizarlo para la compresión de la imagen del disco, el proceso del disco-IO está vinculado. El uso de cualquiera de los otros compresores hace que el proceso esté ligado a la CPU (es decir, los otros compresores usan toda la CPU disponible, lzop (en una CPU razonable) puede manejar datos a la misma velocidad que un disco duro de 7200 RPM puede repartirlos ... )

Apuesto a que si lo probaste con los primeros X bytes de una cadena de ''compresión de prueba'', sería mucho más rápido que la mayoría de los otros métodos ...

Answer 8

Un compresor rápido como el LZ4 ya tiene comprobaciones integradas para la compresibilidad de datos. Rápidamente saltan los segmentos malos para concentrarse en los más interesantes. Para dar un ejemplo adecuado, LZ4 en datos no comprimibles funciona a casi el límite de velocidad de RAM (2GB / s en mi computadora portátil). Así que hay poco espacio para que un detector sea aún más rápido. Puede probarlo usted mismo: http://code.google.com/p/lz4/