Quelles sont les utilisations les plus courantes des bitarrays?

Question

J'ai utilisé un exemple en utilisant bitarrays à partir d'un manuel de débutant. Je veux savoir à quoi ils peuvent servir et à quoi servent certaines structures de données communes (en supposant que "tableau" est une terminologie assez vague.)

Merci.

Answer 1

Plusieurs Applications de la section Tableau de bits Article dans Wikipedia:

  

En raison de leur compacité, les matrices de bits ont de nombreuses applications dans des domaines où l’espace ou l’efficacité sont primordiaux. Le plus souvent, ils sont utilisés pour représenter un simple groupe de drapeaux booléens ou une séquence ordonnée de valeurs booléennes.

     

Nous avons mentionné ci-dessus que les tableaux de bits sont utilisés pour les files d'attente prioritaires, où le bit d'indice k est activé si et seulement si k est dans la file d'attente; Cette structure de données est utilisée, par exemple, par le noyau Linux et bénéficie grandement d’une opération de recherche du premier zéro dans le matériel.

     

Les tableaux de bits peuvent être utilisés pour l'allocation de pages de mémoire, d'inodes, de secteurs de disques, etc. Dans ce cas, le terme bitmap peut être utilisé. Cependant, ce terme est fréquemment utilisé pour désigner des images raster, qui peuvent utiliser plusieurs bits par pixel.

     

Une autre application des tableaux de bits est le filtre de Bloom, une structure de données d’ensembles probabiliste pouvant stocker de grands ensembles dans un petit espace en échange d’une faible probabilité d’erreur. Il est également possible de construire des tables de hachage probabilistes basées sur des tableaux de bits acceptant les faux positifs ou les faux négatifs.

     

Les tableaux de bits et leurs opérations sont également importants pour la construction de structures de données succinctes, qui utilisent un espace proche du minimum possible. Dans ce contexte, les opérations telles que trouver le nième 1 bit ou compter le nombre de 1 bits jusqu'à une certaine position deviennent importantes.

     

Les tableaux de bits sont également une abstraction utile pour examiner les flux de données compressées, qui contiennent souvent des éléments occupant des portions d’octets ou non alignés. Par exemple, la représentation de codage de Huffman compressée d’un seul caractère de 8 bits peut aller de 1 à 255 bits.

     

Dans la recherche d’informations, les tableaux de bits sont une bonne représentation des listes d’affichage de termes très fréquents. Si nous calculons les espaces entre les valeurs adjacentes dans une liste d’entiers strictement croissants et les codons en utilisant un codage unaire, le résultat est un tableau de bits avec un bit à la nième position si et seulement si n est dans la liste. La probabilité implicite d'un écart de n est 1 / 2n. C'est également le cas particulier du codage de Golomb où le paramètre M est 1; ce paramètre n'est normalement sélectionné que lorsque -log (2-p) / log (1-p) & # 8804; 1, ou approximativement, le terme est utilisé dans au moins 38% des documents.