Quels sont les usages courants des bitarrays?

Question

J'ai fait un exemple en utilisant bitarrays d'un manuel de débutant. Je veux savoir à quoi ils peuvent être utilisés et quelles sont leurs structures de données communes (en supposant que "array" est une terminologie assez lâche.)

Merci.

Answer 1

Il y a plusieurs énumérés dans la section Applications du Bit array article de Wikipédia:

En raison de leur compacité, les tableaux de bits ont un certain nombre d'applications dans des domaines où l'espace ou d'efficacité à une prime. 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 de priorité, où le bit à l'index k est défini 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 fortement d'une opération find-first-zero 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 disque, etc. Dans ce cas, le terme bitmap peut être utilisé. Cependant, ce terme est fréquemment utilisé pour désigner des images tramées, qui peuvent utiliser plusieurs bits par pixel.

Une autre application des matrices de bits est le filtre Bloom, une structure de données d'ensemble probabiliste qui peut 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 des faux positifs ou des faux négatifs.

Les tableaux de bits et les opérations sur eux sont également importants pour la construction de structures de données succinctes, qui utilisent près de l'espace possible minimum. Dans ce contexte, les opérations telles que trouver le nième bit 1 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 qui occupent des parties d'octets ou ne sont pas alignés sur les octets. Par exemple, la représentation codée Huffman compressée d'un seul caractère de 8 bits peut être comprise entre 1 et 255 bits.

Dans la recherche d'information, les tableaux de bits sont une bonne représentation pour les listes d'affichage de termes très fréquents. Si nous calculons les intervalles entre des 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 aussi 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) ≤ 1, ou approximativement le terme apparaît dans au moins 38% des documents.