Comment prédire efficacement si les données sont compressibles

D’après mon expérience, presque tous les formats pouvant être compressés sont non binarys. Donc, vérifier si environ 70-80% des caractères sont dans la rage [0-127] devrait faire l’affaire.

Si vous voulez le faire “correctement” (même si je ne vois vraiment pas de raison de le faire), vous devez exécuter (une partie de) votre algorithme de compression sur les données ou calculer l’entropie, comme le propose déjà tskuzzy.

J’ai implémenté quelques méthodes pour tester si les données sont compressibles.

Compression simplifiée

Cela vérifie essentiellement les paires d’octets en double:

static boolean isCompressible(byte[] data, int len) { int result = 0; // check in blocks of 256 bytes, // and sum up how compressible each block is for (int start = 0; start < len; start += 256) { result += matches(data, start, Math.min(start + 255, len)); } // the result is proportional to the number of // bytes that can be saved // if we can save many bytes, then it is compressible return ((len - result) * 777) < len * 100; } static int matches(byte[] data, int i, int end) { // bitArray is a bloom filter of seen byte pairs // match counts duplicate byte pairs // last is the last seen byte int bitArray = 0, match = 0, last = 0; if (i < 0 || end > data.length) { // this check may allow the JVM to avoid // array bound checks in the following loop throw new ArrayIndexOutOfBoundsException(); } for (; i < end; i++) { int x = data[i]; // the bloom filter bit to set int bit = 1 << ((last ^ x) & 31); // if it was already set, increment match // (without using a branch, as branches are slow) match -= (-(bitArray & bit)) >> 31; bitArray |= bit; last = x; } return match; } 

Sur mon ensemble (limité) de données de test, cet algorithme est assez précis. Il est environ 5 fois plus rapide que de se compresser si les données ne sont pas compressibles. Pour les données sortingviales (toutes les zéros), il est cependant environ deux fois plus rapide.

Entropie partielle

Cet algorithme estime l’entropie des gros octets. Je voulais éviter d’utiliser trop de seaux, car ils doivent être mis à zéro à chaque fois (ce qui est lent si les blocs à vérifier sont petits). 63 - numberOfLeadingZeros est le logarithme (je voulais éviter d’utiliser des nombres à virgule flottante). Selon les données, il est plus rapide ou plus lent que l’algorithme ci-dessus (pas sûr de savoir pourquoi). Le résultat n’est pas aussi précis que l’algorithme ci-dessus, probablement en raison de l’utilisation de 16 intervalles et de l’arithmétique entière.

 static boolean isCompressible(byte[] data, int len) { // the number of bytes with // high nibble 0, 1,.., 15 int[] sum = new int[16]; for (int i = 0; i < len; i++) { int x = (data[i] & 255) >> 4; sum[x]++; } // see wikipedia to understand this formula :-) int r = 0; for (int x : sum) { long v = ((long) x << 32) / len; r += 63 - Long.numberOfLeadingZeros(v + 1); } return len * r < 438 * len; } 

Calculez l’ entropie des données. S’il a une entropie élevée (~ 1.0), il ne sera probablement pas compressé davantage. S’il a une faible entropie (~ 0.0), cela signifie qu’il n’y a pas beaucoup d’informations et qu’il peut être compressé.

Il fournit une mesure théorique de la compression possible d’une donnée.

Ce problème est intéressant à lui seul car avec par exemple zlib, la compression de données non compressibles prend beaucoup plus de temps que la compression de données compressibles. Une compression infructueuse est donc particulièrement coûteuse (pour plus de détails, voir les liens). De beaux travaux récents dans ce domaine ont été effectués par Harnik et al. d’IBM.

Oui, la méthode du préfixe et l’entropie d’ordre des octets (appelé entropie dans les autres messages) sont de bons indicateurs. D’autres bonnes façons de deviner si un fichier est compressible ou non sont (du papier):

• Taille du jeu de base – Jeu de caractères constituant la plupart des données
• Indicateur de dissortingbution de paires de symboles

Voici le papier FAST et les diapositives .

Je pense qu’il est impossible de vérifier si quelque chose est compressible avant d’essayer de le compresser. Vous pouvez rechercher des motifs (plus de motifs, peut-être plus compressibles), mais un algorithme de compression particulier risque de ne pas utiliser les motifs que vous avez recherchés – et peut faire mieux que prévu. Une autre astuce peut être de prendre les 128 000 premiers octets de données, de les pousser à travers la compression Deflate / Java et de voir si leur taille est inférieure à la taille d’origine. Si c’est le cas – il y a de fortes chances que cela comprenne le tout.

Les compresseurs rapides tels que LZ4 ont déjà des contrôles intégrés pour la compressibilité des données. Ils sautent rapidement les mauvais segments pour se concentrer sur les plus intéressants. Pour donner un bon exemple, LZ4 sur des données non compressibles fonctionne presque à la vitesse de la RAM (2 Go / s sur mon ordinateur portable). Il y a donc peu de place pour qu’un détecteur soit encore plus rapide. Vous pouvez l’essayer vous-même: http://code.google.com/p/lz4/

Il indique sur votre profil que vous êtes l’auteur du H2 Database Engine, une firebase database écrite en Java.

Si je me trompe, vous envisagez de concevoir ce moteur de firebase database pour compresser automatiquement les données BLOB, si possible.

Mais – (je suppose) vous avez compris que tout ne compressera pas et que la vitesse est importante – vous ne voulez donc pas perdre une microseconde plus que nécessaire pour déterminer si vous devez compresser des données …

Ma question est de nature technique: pourquoi faire tout cela? Fondamentalement, n’est-il pas question de deviner l’intention de l’utilisateur de la firebase database / du développeur de l’application – au désortingment de la vitesse?

Ne pensez-vous pas qu’un développeur d’application (qui écrit des données dans les champs blob en premier lieu) serait la meilleure personne pour décider si les données doivent être compressées ou non et, le cas échéant, pour choisir la compression appropriée méthode?

Le seul endroit où je peux voir la compression automatique de la firebase database append éventuellement une valeur est dans les champs text / varchar – et uniquement s’ils dépassent une certaine longueur – mais même dans ce cas, cette option pourrait être mieux choisie par le développeur de l’application. Je pourrais même aller jusqu’à permettre au développeur d’applications un plug-in de compression, si c’est le cas … De cette façon, ils peuvent prendre leurs propres décisions pour leurs propres données …

Si mes hypothèses sur ce que vous essayez de faire étaient fausses – alors je m’excuse humblement d’avoir dit ce que j’ai dit … (C’est juste l’opinion d’un utilisateur insignifiant.)

Aussi – Pourquoi ne pas essayer lzop? Je peux personnellement garantir que c’est plus rapide, beaucoup plus rapide (compression et décompression) que bzip, gzip, zip, rar …

http://www.lzop.org

Son utilisation pour la compression d’image disque rend le processus lié à l’IO disque. Utiliser l’un des autres compresseurs rend le processus lié au processeur (les autres compresseurs utilisent tous les processeurs disponibles, lzop (sur un processeur raisonnable) peut gérer les données à la même vitesse qu’un disque dur de 7 200 tr / min peut …) )

Je parie que si vous le testiez avec les X premiers octets d’une chaîne de “compression de test”, ce serait beaucoup plus rapide que la plupart des autres méthodes …