java - servidor - ¿Cómo encontrar un diccionario bueno/óptimo para zlib ''setDictionary'' al procesar un conjunto de datos determinado?
cliente servidor java socket hilos (1)
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 ser comprimido por su cuenta. 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 de setDictionary usando setDictionary , puedo mejorar la relación de compresión.
¿Hay alguna forma (algoritmo) para encontrar el diccionario ''óptimo'', es decir, un diccionario con la relación de compresión óptima global?
Ver manual de zlib
John Reiser explicó en comp.compression :
Para el diccionario: haga un histograma de subcadenas cortas , ordene por recompensa (número de veces que ocurre la cantidad de bits guardados cuando se comprime) y coloque las subcadenas de mayor recompensa 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), haga un histograma de todas las subcadenas de longitudes k, 1 + k, 2 + k, y 3 + k. Por supuesto, hay algo de arte para colocar esas subcadenas en el diccionario, aprovechando las subcadenas, las superposiciones, las cadenas cortas más cerca del extremo de la dirección alta , etc.
El kernel de Linux utiliza una técnica similar para comprimir los nombres de los símbolos que se usan para imprimir los backtraces de la pila de llamadas de subrutinas. Ver el archivo scripts / kallsyms.c. Por ejemplo, https://code.woboq.org/linux/linux/scripts/kallsyms.c.html
El manual de zlib recomienda colocar las incidencias más comunes al final del diccionario.
El diccionario debe consistir en cadenas (secuencias de bytes) que probablemente se encuentren más adelante en los datos que se comprimirán, con las cadenas más comúnmente utilizadas ubicadas preferiblemente hacia el final del diccionario. El uso de un diccionario es más útil cuando los datos a comprimir son cortos y se pueden predecir con buena precisión; los datos se pueden comprimir mejor que con el diccionario vacío predeterminado.
Esto se debe a que LZ77 tiene un algoritmo de ventana deslizante, por lo que las subcadenas posteriores serán más accesibles en su flujo de datos que las primeras.
Jugaría con la generación del diccionario con un lenguaje de nivel superior con un buen soporte de cadenas. Un ejemplo crudo 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 probarlo copiando, pegando y ejecutando here (agregue: "print (dict)")
Eso es sólo palabras completas, no subcadenas. También hay formas de superponer subcadenas comunes para ahorrar espacio en el diccionario.