Encodage de huffman

Question

J'essaie d'implémenter l'algorithme de Huffman pour la compression, ce qui nécessite d'écrire des bits de longueur variable dans un fichier. Est-il possible en C++ d'écrire des données de longueur variable avec une granularité de 1 bit dans un fichier?

Answer 1

Non, la plus petite quantité de données que vous pouvez écrire dans un fichier est un octet.

Vous pouvez utiliser un bitset pour faciliter la manipulation de bits, puis utiliser un ofstream pour écrire dans un fichier. Si vous ne voulez pas utiliser de bitset, vous pouvez utiliser le bitwise operators pour manipuler vos données avant de les sauvegarder.

Answer 2

Le plus petit nombre de bits accessibles et sauvegardés est 8 = 1 octet. Vous pouvez accéder aux bits en octets à l'aide des opérateurs de bits^& |.

Vous pouvez mettre le bit à 1 en utilisant n'th:

my_byte = my_byte | (1 << n); 

où n est 0 à 7.

Vous pouvez mettre le bit à 0 en utilisant n'th:

my_byte = my_byte & ((~1) << n); 

Vous pouvez activer ou désactiver bit n'th en utilisant:

my_byte = my_byte^(1 << n); 

Plus de détails here.

Answer 3

La réponse de klew est probablement celle que vous voulez, mais juste pour ajouter quelque chose à ce que Bill a dit, les bibliothèques Boost ont un dynamic_bitset que j'ai trouvé utile dans une situation similaire.

Answer 4

Non. Vous devrez empaqueter des octets. En conséquence, vous aurez besoin d'un en-tête dans votre fichier qui spécifie combien d'éléments sont dans votre fichier, car vous aurez probablement des bits de fin inutilisés.

Answer 5

Toutes les informations dont vous avez besoin sur le bit bidouilles est ici:
How do you set, clear, and toggle a single bit?

Mais l'objet le plus petit que vous pouvez mettre dans un fichier est un octet.
Je voudrais utiliser dynamic_bitset et chaque fois que la taille est supérieure à 8, extraire les 8 bits inférieurs dans un char et écrire cela dans un fichier, puis décaler les bits restants vers le bas de 8 places (répéter).