Réorganiser les données (ensemble de chaînes) pour optimiser la compression?

12

Existe-t-il des algorithmes de réorganisation des données à optimiser pour la compression? Je comprends que cela est spécifique aux données et à l'algorithme de compression, mais y a-t-il un mot pour ce sujet? Où puis-je trouver des recherches dans ce domaine?

Plus précisément, j'ai une liste json de 1,5 million de chaînes, et je veux réorganiser les chaînes afin que la compression gzip (pour HTTP) soit optimisée. Le tri des chaînes fonctionne plutôt bien, mais je ne sais pas vraiment si c'est optimal.

optimization permutations Jayen
la source
1
Réorganiser de manière optimale les chaînes pour la compression gzip (LZ77 avec une petite fenêtre coulissante) ressemble à un problème NP-difficile. Vous pouvez probablement trouver une réduction par rapport au problème de super chaîne le plus court.
Jouni Sirén
@ JouniSirén Je pense que la plus longue sous-chaîne commune est une meilleure approche car la plus courte chaîne commune me limite à avoir la partie commune dos à dos, non? Cela ne me dérange pas NP-hard tant qu'il est tractable (comme cela prend un jour pour fonctionner sur une machine moderne).
Jayen

Réponses:

6

Ceci est un ajout à la réponse de Navin Goyal.

Puisqu'un fichier JSON peut être considéré comme une structure de données d'arbre, vous pouvez utiliser la transformation XBW pour les arbres, qui est une extension de la transformation Burrows-Wheeler pour les chaînes.

Hiroki Yanagisawa
la source
1
Merci pour ça. Je n'ai qu'une liste / tableau JSON, pas d'objets JSON, donc je ne vois pas comment cela peut être considéré comme un arbre. Je pourrais convertir les chaînes en trie, mais je ne vois pas comment cela se rapporte à la transformation XBW.
Jayen
4

Burrows - Wheeler transform est un algorithme de compression bien connu qui fonctionne en réordonnant les caractères de la chaîne à compresser.

Navin Goyal
la source
1
Merci pour cela, mais je ne sais pas comment utiliser ces informations. Je veux réorganiser les chaînes de la liste pour qu'elles soient compressées, mais je m'en fiche si je peux récupérer l'ordre d'origine.
Jayen
1

Pour améliorer la compression gzip, vous souhaitez que les chaînes "similaires" soient fermées dans la liste. Il existe plusieurs façons de définir une telle similitude; permettez-moi d'en décrire une raisonnable qui fonctionne bien dans la pratique. Rappelons que la taille de bloc de gzip est de 64 Ko. Ainsi, vos données seront divisées en blocs de 64 Ko et chaque bloc sera compressé indépendamment. Pour optimiser la compression, il faudrait minimiser le nombre de k-mers distincts (sous-chaînes de taille k) dans chaque bloc. La motivation est que toutes ces sous-chaînes seront remplacées par un identifiant.

Alors que le problème ci-dessus est difficile en théorie (c'est une variante du partitionnement hypergraphique), il existe des algorithmes pratiques rapides. Je recommanderais un clustering de type LSH qui peut être implémenté en un seul passage sur vos données. Notez que le tri (alphabétique) est une autre façon de "regrouper" des chaînes similaires. Cependant, les algorithmes de clustering spécialisés peuvent mieux fonctionner.

Une alternative consiste à utiliser zstd , qui est (i) plus rapide, (ii) obtient des taux de compression plus élevés et (iii) n'a pas de limites sur la taille du bloc (et donc, comprime les chaînes également bien quel que soit l'ordre d'entrée).

Sergey Pupyrev
la source
0

J'ai vu un algorithme il y a quelque temps qui peut peut-être être utile. Il utilise un algorithme d'édition de distance pour calculer la distance entre chaque mot. Ainsi, il construit un graphique dont chaque poids de bord est cette distance. Enfin, il obtient un ordre en choisissant un chemin qui a la somme de poids la plus faible. Peut-être que cela peut améliorer gzip.

Rafael Ribeiro
la source
cela ne semble pas traitable, mais si quelqu'un l'essaie, veuillez poster un commentaire avec vos résultats
Jayen
Je vais essayer de le tester. Je suis curieux de ce problème. En plus de cela, pourquoi pensez-vous que ce n'est pas traitable?
Rafael Ribeiro
pour autant que je sache, la distance d'édition est O (nm), où n et m sont le nombre de lettres dans la paire de chaînes et vous devez le faire pour chaque paire de chaînes O (s ^ 2), donc si n = m, c'est O (s ^ 2 * n ^ 2) qui me semble intraitable pour 1,5 million de cordes.
Jayen
Oh, je ne me préoccupais pas beaucoup de la complexité parce que je pensais que votre problème était de réduire uniquement la taille binaire. Donc, cette opération se produira plus souvent, non?
Rafael Ribeiro
Je cherchais ici et peut-être que le coût de la modification de la distance peut être réduit en utilisant les automates levenshtein
Rafael Ribeiro