Bonjour à tous!
 
Voilà je suis nouveau sur ce forum très intéressant, et je commence avec un post... modeste (ou pas)  
 
J'ai un petit soucis concernant les bits  
 
Il faudrait que je passe d'un identifiant, un entier en l'occurrence, par exemple

et le passer en bits (ici

pour ensuite l'écrire dans un fichier...
Pour écrire dans un fichier en bits, pas de problème, j'ai implémenté une bibliothèque, et ça marche, mais pour le passage de l'entier à bit je ne vois pas comment faire...
 
Merci d'avance pour votre aide.
 
PS: Vous allez me dire que c'est simple, j'ai qu'à écrire directement le int dans mon fichier... Oui mais non, parce que si un int est codable sur seulement 3 bits, j'aimerais n'écrire que ces trois bits là, donc mon problème reste le même

Certes, mais pour un int codable en 3 bits (donc dans [4,8[), ça va prendre 3 caractères, donc 24 bits, pour un int codable en 4 bits (donc dans [8,16[), ca va prendre 4 caractères, donc 32 bits soit le taille d'un entier (sur les machines les plus courantes) donc on ne gagne rien, et au delà, on est perdant en espace occupé dans le fichier...
Edit: Ah, vous écrivez directement en bits. Mais vous êtes conscient que en C, la plus petite unité d'écriture dans un fichier, c'est le char, et donc que même pour un entier de 3 bits, vous allez en occuper 8. Vos suites de bits vont occuper 8, 16, 24 ou 32 bits selon l'entier à écrire.
Et pour le relire, vous allez faire comment pour délimiter vos entier, vu qu'ils sont de taille variable maintenant? Il va vous falloir un caractère délimiteur, qui mange 8 bits lui aussi, ce qui va impliquer que votre représentation va occuper 16, 24, 32 ou 40 bits. Pas sur que vous y gagnez grand chose par rapport a une représentation binaire de taille fixe (qui n'a donc pas besoin de caractère délimiteur).
A+,

Hum ce que je compte faire c'est remplacer des mots par des identifiants, puis écrire ces identifiants directement en bits.
 
Par exemple, avec ce texte :

, j'obtiens la liste de mots suivante :

 
Puis j'associe à chaque mot différent un identifiant (un entier)

 
Le chiffre max est 5, codable ainsi en bit : 101 donc avec 3 bits, je peux coder n'importe lequel des identifiants. Ce qui donne :

 
Et ainsi mon texte devient

que je peut alors écrire grâce à ma bibliothèque de manipulation des bits avec seulement 6 octets au lieu de 33. Bon, bien sûr il faut que je note le codage quelque part, et sur un petit fichier c'est pas efficace, mais sur des plus gros c'est bon.

fais un tableau de char et des fonctions pour écrire tes bits dedans à un index donné en paramètre ...
 

 
ca semble plutôt pratique, comme API, et tu ne devrais pas avoir trop de mal à l'implémenter.
 
Edit : et tu malloc la struct avec un malloc( sizeof( BitField ) + nbCharAStocker );

Ah!
J'ai pigé ce que vous voulez faire.
Il va néanmoins falloir  
1) stocker un dictionnaire ordonné des mots quelque part
2) stocker la longueur B du nombre de bits d'encodage quelque part
3) réserver une valeur (de préférence 000...0 avec B zéros) comme marqueur de fin de chaîne de bits (car comme on ne peux écrire que des octets, si ça ne tombe pas juste à la fin, il faut savoir ou on s’arrête).
 
Pour le passage d'un entier a une suite de bits, il y a plusieurs possibilités.
La plus efficace me semble être de ne travailler qu'avec des entiers non-signés, et de tester la valeur des B premiers bits (puisque vous savez que les autres sont a 0) avec un masque:
unsigned int maskarray[32] ;
maskarray[0] = 1;
int i = 0;
while (i++ < 32) {maskarray[i] = 2*maskarray[i-1];}
 
et vous testez individuellement chaque bit du nombre k que vous voulez écrire dans un buffer de bits:
for (i = B-1; i >= 0; --i) {
    bit_write(bitbuffer, k & maskarray[i]);
}
ou bitbuffer est un bitarray, et bit_write une operation qui écrit un bit dans ce buffer. Je suppose que vous employez déja une librairie de manipulation de bitarray en C, puisque c'est un prérequis à pouvoir écrire un bitarray dans un fichier, comme vous le faites par la suite.
 
On pourrait essayer de faire plus optimisé, regarder la représentation (intrinsèque) binaire du nombre comme un bitarray, et n'écrire dans un buffer (de bits) que ce qui nous intéresse d'un coup, avec une fonction d'une brairie de manipulation de bitarray ad-hoc, mais si ça colle pour un petit entier (qui tient dans un char), si on a des entiers relativement grand, la représentation intrinsèque n'est plus nécessairement linéaire et peut dépendre de l'architecture machine (endianness...), c'est un nid à problèmes.
 
Note: pour une librairie de manipulation de bitarray, voir en fin de page ici http://michael.dipperstein.com/bitlibs/ et adapter à son problème le cas échéant.
A+,

C'est grosso modo l'algo de Huffman ça.

 
Non.  Huffman tient compte des frequences, ici pas du tout.  Ca ressemble plus a un algo a dictionnaire avec un dictionnaire defini statiquement, d'habitude on le decouvre dynamiquement (et on utilise Huffmann derriere pour gagner un peu plus, ou du codage arithmetique si on veut aller plus loin).

Ah oui, j'avais oublié, il y a des raisons particulières pour que ce soit codé en C?
Il me semble que C++ a un peu plus de support pour les bitarray: http://www.sgi.com/tech/stl/bitset.html et http://www.boost.org/doc/libs/1_46 [...] itset.html
 
A+,

Non, ce n'est pas l'algo de Huffman, que j'ai à implémenter après, mais c'est une autre histoire.
 
Il faut que ça soit en C car c'est le langage étudié en ce moment en cours, il est donc préférable de faire avec.
 
Ce qui m'intéresse c'est surtout de savoir comment en prenant l'identifiant le plus grand et qui prendra le plus de bits en place, on peut savoir le nombre de bits à réserver...
Dans mon exemple, il fait 16 bits, mais comment fait-on pour savoir quand s'arrêter à la lecture des bits? Il doit y avoir une formule à base de Log, mais je ne vois pas comment je pourrai mettre ça en place...
 
Merci en tout cas pour votre réactivité à tous =)

Il va suffire de compter le nombre de fois que sa division par 2 est non nulle (et sans doute ajouter 1) pour connaitre la taille fixe que vous utilisez pour représenter un entier.
A+,

http://graphics.stanford.edu/~sean [...] LogObvious

J'ai rien dit d'autre, j'ai juste pas précisé comment diviser par 2
A+,

Merci à tous pour vos réponses, je vous tiens au courant sur l'avancement de mon travail. De toutes façons, demain soir il faut que ça soit fini, j'ai d'autres projets à coder pour ce week-end, et je suis mal parti ^^'