Quelles sont les alternatives à un tableau de bits ?

Question

J'ai une application de récupération d'informations qui crée des tableaux de bits de l'ordre de dizaines de millions de bits.Le nombre de bits « définis » dans le tableau varie considérablement, de tous clairs à tous définis.Actuellement, j'utilise un tableau de bits simple (java.util.BitSet), donc chacun de mes tableaux de bits prend plusieurs mégaoctets.

Mon plan est de regarder la cardinalité du premier N bits, puis décidez quelle structure de données utiliser pour le reste.De toute évidence, certaines structures de données sont meilleures pour les tableaux de bits très clairsemés, et d'autres lorsqu'environ la moitié des bits sont définis (lorsque la plupart des bits sont définis, je peux utiliser la négation pour la traiter comme un ensemble clairsemé de zéros).

• Quelles structures pourraient être bonnes à chaque extrême ?
• Y en a-t-il au milieu ?

Voici quelques contraintes ou conseils :

1. Les bits ne sont définis qu'une seule fois et dans l'ordre d'index.
2. J'ai besoin d'une précision de 100 %, donc quelque chose comme un filtre Bloom n'est pas suffisant.
3. Une fois l’ensemble construit, je dois être capable de parcourir efficacement les bits « ensemble ».
4. Les bits sont distribués de manière aléatoire, de sorte que les algorithmes de codage par longueur ne seront probablement pas bien meilleurs qu'une simple liste d'index de bits.
5. J'essaie d'optimiser l'utilisation de la mémoire, mais la vitesse est toujours au rendez-vous quelques poids.

Quelque chose avec une implémentation Java open source est utile, mais pas strictement nécessaire.Je suis plus intéressé par les fondamentaux.

Answer 1

Sauf si les données sont vraiment aléatoires et a une distribution symétrique 1/0, cela devient alors simplement un problème de compression de données sans perte et est très analogue à la compression CCITT Groupe 3 utilisée pour le noir et blanc (c'est-à-dire :Binaire) Images de fax.Le groupe 3 du CCITT utilise un schéma de codage de Huffman.Dans le cas du FAX, ils utilisent un ensemble fixe de codes Huffman, mais pour un ensemble de données donné, vous pouvez générer un ensemble spécifique de codes pour chaque ensemble de données afin d'améliorer le taux de compression obtenu.Tant que vous n'avez besoin d'accéder aux bits que de manière séquentielle, comme vous l'avez laissé entendre, ce sera une approche assez efficace.L'accès aléatoire créerait des défis supplémentaires, mais vous pourriez probablement générer un index d'arbre de recherche binaire vers divers points de décalage du tableau, ce qui vous permettrait de vous rapprocher de l'emplacement souhaité, puis d'y entrer.

Note:Le schéma de Huffman fonctionne toujours bien même si les données sont aléatoires, tant que la distribution 1/0 n'est pas parfaitement égale.Autrement dit, moins la répartition est uniforme, meilleur est le taux de compression.

Enfin, si les bits sont vraiment aléatoires avec une distribution égale, alors, d'après M.Claude Shannon, vous ne pourrez pas le compresser de manière significative en utilisant n'importe quel schéma.

Answer 2

J'envisagerais fortement d'utiliser le codage par plage à la place du codage de Huffman.En général, le codage par plage peut exploiter l'asymétrie plus efficacement que le codage de Huffman, mais cela est particulièrement vrai lorsque la taille de l'alphabet est si petite.En fait, lorsque "l'alphabet natif" est simplement composé de 0 et de 1, la seule façon pour Huffman d'obtenir une compression est de combiner ces symboles - ce qui est exactement ce que fera l'encodage par plage, plus efficacement.

Answer 3

Peut-être trop tard pour vous, mais il existe une bibliothèque très rapide et efficace en mémoire pour les tableaux de bits clairsemés (sans perte) et d'autres types de données basés sur des essais.Regarder tableaux Judy

Answer 4

Merci pour les réponses.C'est ce que je vais essayer pour choisir dynamiquement la bonne méthode :

Je vais récupérer tous les premiers N frappe dans un tableau de bits conventionnel et choisissez l'une des trois méthodes, en fonction de la symétrie de cet échantillon.

• Si l'échantillon est hautement asymétrique, je vais simplement stocker les index sur les bits définis (ou peut-être la distance au bit suivant) dans une liste.
• Si l'échantillon est très symétrique, je continuerai à utiliser un tableau de bits conventionnel.
• Si l'échantillon est modérément symétrique, j'utiliserai une méthode de compression sans perte comme le codage de Huffman suggéré par Inscitekjeff.

Les limites entre les régions asymétriques, modérées et symétriques dépendront du temps requis par les différents algorithmes, équilibrés par rapport à l'espace dont ils ont besoin, où la valeur relative du temps par rapport à l'espace serait un paramètre réglable.L'espace nécessaire pour le codage de Huffman est fonction de la symétrie, et je vais le profiler avec des tests.De plus, je testerai les trois méthodes pour déterminer les délais de ma mise en œuvre.

Il est possible (et en fait j'espère) que la méthode de compression intermédiaire soit toujours meilleure que la liste ou le tableau de bits ou les deux.Peut-être que je peux encourager cela en choisissant un ensemble de codes de Huffman adaptés à une symétrie supérieure ou inférieure.Ensuite, je peux simplifier le système et utiliser simplement deux méthodes.

Answer 5

Une autre pensée sur la compression :

Si le tableau de bits n'est pas très long, vous pouvez essayer d'appliquer le Transformation de Burrows-Wheeler avant d'utiliser un codage de répétition, tel que Huffman.Une implémentation naïve prendrait O(n^2) de mémoire pendant la (dé)compression et O(n^2 log n) de temps pour décompresser - il existe presque certainement également des raccourcis.Mais s'il existe une structure séquentielle dans vos données, cela devrait vraiment aider le codage de Huffman.

Vous pouvez également appliquer cette idée à un bloc à la fois pour que l'utilisation du temps et de la mémoire soit plus pratique.L'utilisation d'un bloc à la fois pourrait vous permettre de toujours conserver la majeure partie de la structure de données compressée si vous lisez/écrivez de manière séquentielle.

Answer 6

La compression simple et sans perte est la voie à suivre.Pour le rendre consultable, vous devrez compresser des blocs relativement petits et créer un index dans un tableau de blocs.Cet index peut contenir le décalage du bit de départ dans chaque bloc.

Answer 7

Preuve combinatoire rapide que vous ne pouvez pas vraiment économiser beaucoup d'espace :

Supposons que vous ayez un sous-ensemble arbitraire de n/2 bits défini sur 1 sur n bits au total.Vous avez (n choisissez n/2) possibilités.En utilisant La formule de Stirling, c'est environ 2^n / sqrt(n) * sqrt(2/pi).Si chaque possibilité est également probable, alors il n'y a aucun moyen de donner des représentations plus courtes à des choix plus probables.Nous avons donc besoin de log_2 (n choisissez n/2) bits, ce qui représente environ n - (1/2)log(n) bits.

Ce n'est pas une très bonne économie de mémoire.Par exemple, si vous travaillez avec n=2^20 (1 Mo), vous ne pouvez enregistrer qu'environ 10 bits.Cela n'en vaut tout simplement pas la peine.

Cela dit, il semble également très peu probable que des données réellement utiles soient véritablement aléatoires.Si vos données sont plus structurées, il existe probablement une réponse plus optimiste.