Comment emballer des bits lors de la compression de Huffman?

Question

Je mets en œuvre un programme pour effectuer une compression / décompression de Huffman (dans le but d'apprendre / de s'amuser, donc je ne veux pas utiliser les bibliothèques / programmes existants).

J'ai réussi à construire la compression trois, j'ai donc une table avec tous les personnages et leur représentation comprimée respective en bits. Par exemple:

A = 0010 B = 01101 C = 0011 D = 1101 E = 101

Maintenant, mon idée est de stocker les bits dans un conteneur (par exemple, une variable char ou int), puis de les sortir dans un fichier.

Je sais comment emballer / déballer les bits dans un char ou INT en utilisant des opérations bitwise. Le problème auquel je suis confronté, cependant, est que le nombre de bits dans la version compressée ne corresponde pas au nombre de bits dont j'ai disponible.

Supposons que je souhaite compresser la chaîne "ABC" en utilisant le tableau ci-dessus. Je commencerais par comprimer «A», donc emballer 0010 dans une variable char. Ensuite, je compresserais «B», mais cela nécessite 5 bits, et il ne me reste que 4 bits sur ma variable de char. Je pourrais utiliser une autre variable, mais il deviendrait un gâchis pour suivre la variable utilise le nombre de bits.

L'utilisation d'INT me donnerait 32 bits avec qui travailler, mais le même problème se produirait une fois que je me rapprocherais de la limite.

Answer 1

Il n'y a aucun moyen de contourner. Tu ont Pour garder une trace des bits laissés dans votre structure de stockage.

Ce n'est pas vraiment un gâchis. C'est en fait relativement facile à essayer. Conservez simplement les bits supérieurs dans le stockage restant, puis stockez les inférieurs dans le nouveau stockage. À chaque étape, vous devez savoir combien de bits il reste.

Je suggère également d'utiliser des types UInt32 au lieu de char, en raison de leur capacité de stockage supérieure. Cela nécessitera moins de mélange et donc améliorer la vitesse.