Comment trouver un bon/optimal dictionnaire pour zlib 'setDictionary' lors du traitement d'un ensemble donné de données?

Question

J'ai un (énorme) jeu de fichiers de données similaires. L'ensemble est en croissance constante. La taille d'un fichier unique est d'environ 10K. Chaque fichier doit être compressé seul. La compression est effectuée avec la bibliothèque zlib, utilisée par la classe java.util.zip.Deflater. En passant un dictionnaire à l'algorithme Deflate en utilisant setDictionary, je peux améliorer le taux de compression.

Existe-t-il un moyen (algorithme) pour trouver le dictionnaire "optimal", c'est-à-dire un dictionnaire avec le taux de compression optimal global?

Voir zlib manual

Answer 1

John Reiser explained on comp.compression:

Pour le dictionnaire: faire un histogramme de sous-chaînes courtes, trier par gain (nombre d'occurrences multiplié par le nombre de bits enregistré lorsque compressé) et mis les sous-chaînes les plus rentables dans le dictionnaire. Par exemple, si k est la longueur de la sous-chaîne la plus courte pouvant être compressée (habituellement 3 == k ou 2 == k), alors faites un histogramme de toutes les sous-chaînes de longueurs k, 1 + k, 2 + k et 3 + k. Bien sûr, il est un art de placer ces sous-chaînes dans le dictionnaire, en profitant de sous-chaînes, qui se chevauchent, les chaînes courtes près de l'extrémité haute adresse, etc.

Le noyau Linux utilise une technique similaire pour compresser les noms de les symboles utilisés pour l'impression des backtraces de la pile des appels de sous-programmes. Voir les scripts de fichiers/kallsyms.c. Par exemple, https://code.woboq.org/linux/linux/scripts/kallsyms.c.html

Le zlib manual recommends pour placer ocurrences les plus communes à la fin du dictionnaire. Le dictionnaire devrait être constitué de chaînes (séquences d'octets) susceptibles d'être rencontrées plus tard dans les données à compresser, les chaînes les plus couramment utilisées étant de préférence placées vers la fin du dictionnaire. L'utilisation d'un dictionnaire est plus utile lorsque les données à compresser sont courtes et peuvent être prédites avec une bonne précision; les données peuvent alors être mieux compressées qu'avec le dictionnaire vide par défaut. C'est parce que LZ77 a un algorithme de fenêtre glissante, de sorte que les sous-chaînes plus tard seront accessibles plus loin sur votre flux de données que les premiers.

Je jouerais avec la génération du dictionnaire avec un langage de niveau supérieur avec un bon support des chaînes. Un exemple JavaScript brut:

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 

Alors dict est une chaîne de 70 caractères avec:

rdsusedusefulwhencanismostofstringscompresseddatatowithdictionarybethe 

Vous pouvez essayer de copier-coller terme here (ajouter: "print (dict)")

C'est juste des mots entiers, pas des sous-chaînes. Il existe également des moyens de superposer des sous-chaînes courantes pour économiser de l'espace sur le dictionnaire.