Come trovare un dizionario valido/ottimale per zlib "setDictionary" durante l'elaborazione di un determinato set di dati?

Question

Ho un (enorme) set di file di dati simili. Il set è in costante crescita. La dimensione di un singolo file è di circa 10K. Ogni file deve essere compresso da solo. La compressione viene eseguita con la libreria zlib, che viene utilizzata dalla classe java.util.zip.Deflater. Quando si passa un dizionario all'algoritmo Deflate usando setDictionary, posso migliorare il rapporto di compressione.

C'è un modo (algoritmo) per trovare il dizionario 'ottimale', cioè un dizionario con il rapporto di compressione ottimale globale?

Vedi zlib manual

Answer 1

John Reiser explained on comp.compression:

per il dizionario: fare una istogramma di brevi stringhe, ordina per payoff (numero di occorrenze volte il numero di bit salvato quando compressi) e mettere le sottostringhe con il più alto profitto nel dizionario. Ad esempio, se k è la lunghezza della sottostringa più breve che può essere compressa (di solito 3 == k o 2 == k), quindi creare un istogramma di tutte le sottostringhe delle lunghezze k, 1 + k, 2 + k, e 3 + k. Naturalmente c'è una certa arte di porre quelle sottostringhe nel dizionario, sfruttando stringhe, si sovrappongono, brevi stringhe più vicino alla fascia alta-indirizzo, ecc

Il kernel Linux usa una tecnica simile per comprimere i nomi di simboli che vengono utilizzati per stampare i backtrace dello stack delle chiamate di subroutine. Vedi gli script di file/kallsyms.c. Per esempio, https://code.woboq.org/linux/linux/scripts/kallsyms.c.html

La zlib manual recommends per posizionare le occorrenze più comuni alla fine del dizionario.

Il dizionario deve essere composto da stringhe (sequenze di byte) che possono essere rilevate più avanti nei dati da comprimere, con le stringhe più comunemente utilizzate preferibilmente posizionate verso la fine del dizionario. L'utilizzo di un dizionario è molto utile quando i dati da comprimere sono brevi e possono essere previsti con una buona precisione; i dati possono quindi essere compressi meglio rispetto al dizionario vuoto predefinito.

Questo perché LZ77 ha un algoritmo a finestra scorrevole, quindi le sottostringhe successive saranno raggiungibili ulteriormente sul flusso di dati rispetto ai primi.

Mi piacerebbe giocare con la generazione del dizionario con un linguaggio di livello superiore con un buon supporto di stringhe. Un grezzo esempio 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 

Poi dict è una stringa di 70 caratteri con:

rdsusedusefulwhencanismostofstringscompresseddatatowithdictionarybethe 

si può provare copia-incolla-run here (aggiungere: "stampare (dict)")

Queste sono solo parole intere, non sottostringhe. Esistono anche modi per sovrapporre sottostringhe comuni per risparmiare spazio sul dizionario.