¿Cómo encontrar un diccionario bueno/óptimo para zlib 'setDictionary' al procesar un conjunto dado de datos?

Question

Tengo un (enorme) conjunto de archivos de datos similares. El conjunto está en constante crecimiento. El tamaño de un solo archivo es de aproximadamente 10K. Cada archivo debe comprimirse por sí mismo. La compresión se realiza con la biblioteca zlib, que es utilizada por la clase java.util.zip.Deflater. Al pasar un diccionario al algoritmo Deflate usando setDictionary, puedo mejorar la relación de compresión.

¿Hay alguna manera (algoritmo) para encontrar el diccionario 'óptimo', es decir, un diccionario con la relación de compresión óptima global?

Ver zlib manual

Answer 1

John Reiser explained on comp.compression:

Para el diccionario: crea un histograma de subcadenas cortos, ordenar por pago (número de ocurrencias veces el número de bits salvó cuando se comprime) y poner las subcadenas de mayor rentabilidad en el diccionario. Por ejemplo, si k es la longitud de la subcadena más corta que se puede comprimir (generalmente 3 == k o 2 == k), entonces haga un histograma de todas las subcadenas de longitud k, 1 + k, 2 + k, y 3 + k. Por supuesto, hay un poco de arte a la colocación de esos subcadenas en el diccionario, aprovechando subcadenas,, cadenas cortas que se solapan más cerca del extremo de alta dirección, etc.

El núcleo de Linux utiliza una técnica similar para comprimir nombres de símbolos que se utilizan para imprimir trazas inversas de la pila de llamadas de subrutina. Ver los scripts de archivo/kallsyms.c. Por ejemplo, https://code.woboq.org/linux/linux/scripts/kallsyms.c.html

El zlib manual recommends para colocar las ocurrencias más comunes al final del diccionario.

El diccionario debe consistir en cadenas (secuencias de bytes) que es probable encontrar más adelante en los datos que se van a comprimir, con las cadenas más comúnmente utilizadas, preferiblemente, colocadas hacia el final del diccionario. El uso de un diccionario es más útil cuando los datos que se van a comprimir son cortos y pueden predecirse con buena precisión; los datos pueden comprimirse mejor que con el diccionario vacío predeterminado.

Esto se debe a que LZ77 tiene un algoritmo de ventana deslizante, por lo que las últimas subcadenas serán accesibles más allá de su flujo de datos que las primeras.

Jugaría a generar el diccionario con un lenguaje de nivel superior con un buen soporte de cadenas. Un crudo ejemplo de JavaScript:

var str = "The dictionary should consist of strings (byte sequences) that" 
    + " are likely to be encountered later in the data to be compressed," 
    + " with the most commonly used strings preferably put towards the " 
    + "end of the dictionary. Using a dictionary is most useful when the" 
    + " data to be compressed is short and can be predicted with good" 
    + " accuracy; the data can then be compressed better than with the " 
    + "default empty dictionary."; 
// Extract words, remove punctuation (extra: replace(/\s/g, " ")) 
var words = str.replace(/[,\;.:\(\)]/g, "").split(" ").sort(); 
var wcnt = [], w = "", cnt = 0; // pairs, current word, current word count 
for (var i = 0, cnt = 0, w = ""; i < words.length; i++) { 
    if (words[i] === w) { 
     cnt++; // another match 
    } else { 
     if (w !== "") 
      wcnt.push([cnt, w]); // Push a pair (count, word) 
     cnt = 1; // Start counting for this word 
     w = words[i]; // Start counting again 
    } 
} 
if (w !== "") 
    wcnt.push([cnt, w]); // Push last word 
wcnt.sort(); // Greater matches at the end 
for (var i in wcnt) 
    wcnt[i] = wcnt[i][1]; // Just take the words 
var dict = wcnt.join("").slice(-70); // Join the words, take last 70 chars 

Entonces dict es una cadena de 70 caracteres con:

rdsusedusefulwhencanismostofstringscompresseddatatowithdictionarybethe 

Puede probar que copiar y pegar a ejecutar here (añadir: "impresión (dict)")

Eso es solo palabras completas, no subcadenas. También hay formas de superponer subcadenas comunes para ahorrar espacio en el diccionario.