Compression Huffman en c.

Version imprimable

10/08/2009, 13h37
fred61

Compression Huffman en c.

Bonjour,

Je suis en train d'étudier la compression Huffman et comment l'adapter en C et il y a un point que je ne comprend pas.

Mon problème est de savoir comment je vais écrire dans mon fichier compressé après avoir fait mon arbre, en effet en c il n'est possible d'écrire dans un fichier binaire que 8 bits par 8 bits, et pas bits par bits, alors comment faire pour inscrire un 'e' (qui ne sera composé seulement de 3 bits 101) dans mon fichier compressé ?

J'espère que j'ai été assez clair.

Si vous pouvez m'éclairer ?
Merci.

Dans ce cas, effectivement, tu ne peux pas écrire les 3 bits.

Donc tu les gardes quelques part et tu traites le caractères suivants en ajoutant les bits du caractère suivant à ces 3 bits. Dès que tu as 8 bits, tu les écris, tu supprimes les 8 bits écrit de ta mémoire et tu continues.

Bien sûr, il faut gérer les cas un peu plus spéciaux
Code:

1 2 3 4 caractère ==> 3 bits ==> 0 + 3 = 3 bits en attente caractère ==> 9 bits ==> 3 + 9 = 12 bits en attente ==> ecrire 8 bits, reste 4 bits caractère ==> 5 bits ==> 4 + 5 = 9 bits en attente ==> ecrire 8 bits, reste 1 bits ...

10/08/2009, 14h20
fred61

Et le mieux pour stocker les bits en attentes, c'est d'utiliser un champs de bits ? ou il y a une meilleur solution ?
10/08/2009, 17h21
wadabush

Champ de bits ou bien tu peux t'amuser avec les decalages et les |. Je pense que niveau performance, ca doit s'equivaloir (ca se dit ca? :? )
10/08/2009, 17h53
ram-0000

Citation:

Envoyé par wadabush

Champ de bits ou bien tu peux t'amuser avec les decalages et les |.

Je jouerai plutôt avec les opérateurs de décalage (<<, >>) et les opérateurs logiques (&, |). J'ai peut que tu te prennes la tête pour rien avec les champs de bits.

Citation:

Envoyé par wadabush

... ca doit s'equivaloir (ca se dit ca? :?

PS, je viens de vérifier, le verbe equivaloir existe bien dans le Larousse
11/08/2009, 03h27
Mac LAK

L'idéal est quand même d'avoir, au minimum, un buffer de 8 bits (un char) en sortie, dans lequel tu "pousses" les bits un par un par décalages successifs et masquage. Quand l'octet-buffer est plein, tu l'écris sur le disque (ou vers un autre buffer plus gros, si les performances sont un souci), et tu recommences à zéro.
Les champs de bits, c'est vraiment pas une bonne idée pour faire ce genre d'opération, par contre, je te le déconseille.

Solution déjà testée et validée en Ada, langage infiniment plus restrictif que le C, et qui n'a pas bronché d'un poil face à cette méthode... ;)
11/08/2009, 07h57
plxpy

Pour info, vous opposez une méthode utilisant un buffer de n char (n*8 bits) avec décalages à droite, à gauche et utilisation des masques et une autre utilisant des "champs de bits".

Si je vois parfaitement à quoi correspond la première méthode, celle que j'aurais utilisée "naturellement", je ne vois pas à quoi fait référence la deuxième. Qu'entendez-vous par "champs de bits" ?

Citation:

Envoyé par plxpy

Qu'entendez-vous par "champs de bits" ?

Ça :

Code:

1
2
3
4
5
6
7
8
9
10
typedef struct {
    char bit0 : 1 ;
    char bit1 : 1 ;
    char bit2 : 1 ;
    char bit3 : 1 ;
    char bit4 : 1 ;
    char bit5 : 1 ;
    char bit6 : 1 ;
    char bit7 : 1 ;
} char_bitfield ;

11/08/2009, 08h23
plxpy

Ok, merci. J'avais pris le terme "champs" de façon générale, et pas comme "champs d'une structure".
11/08/2009, 09h31
Mac LAK

Citation:

Envoyé par plxpy

Ok, merci. J'avais pris le terme "champs" de façon générale, et pas comme "champs d'une structure".

C'est le terme consacré en C : "bitfields" en anglais, "champs de bits" en français. Quand tu verras ces termes dans une discussion C/C++, c'est très rarement autre chose que les structures dans le genre de l'exemple ci-dessus... Et quand c'est autre chose, c'est en général précisé explicitement.
11/08/2009, 09h54
plxpy

Dans le cadre des bits, je ne suis pas tout à fait d'accord.

"A bit field is a common idiom used in computer programming to store a set of Boolean datatype flags compactly, as a series of bits. The bit field is stored in an integral type of known, fixed bit-width." (wikipedia)

Autant le terme "champ", dans tout autre contexte, m'aurait, évidemment, fait penser à un champ d'une structure, autant là ça pouvait porter à confusion. Mais c'est du détail.
11/08/2009, 10h11
Mac LAK

Citation:

Envoyé par plxpy

"A bit field is a common idiom used in computer programming to store a set of Boolean datatype flags compactly, as a series of bits. The bit field is stored in an integral type of known, fixed bit-width." (wikipedia)

Ce qui est exactement ce dont on parle : les données sont bien une série de bits compacts (pas d'espace entre les divers bits), et c'est stocké dans un type intégral connu de taille fixe (un "char" dans l'exemple ci-dessus)... ;)

J'aurais une question concernant ces bits fields.

Citation:

Ce qui est exactement ce dont on parle : les données sont bien une série de bits compacts (pas d'espace entre les divers bits), et c'est stocké dans un type intégral connu de taille fixe (un "char" dans l'exemple ci-dessus)...

Est-ce que la chose suivante est tout le temps vraie?
Code:

1 2 3 4 5 6 7 8 9 10 11 typedef struct { char bit0 : 1 ; char bit1 : 1 ; char bit2 : 1 ; char bit3 : 1 ; char bit4 : 1 ; char bit5 : 1 ; char bit6 : 1 ; char bit7 : 1 ; } char_bitfield ;
Si je caste le premier element de mon champ de bits en char, je retrouve la valeur du char correspondant a mon champ de bit?

Pour moi la reponse est non, et depend tres serieusement du compilo. Des commentaires?

11/08/2009, 10h50
Mac LAK

Citation:

Envoyé par wadabush

Si je caste le premier element de mon champ de bits en char, je retrouve la valeur du char correspondant a mon champ de bit?

Non : si tu castes le champ lui-même (struct.bit0), tu n'obtiendras que la valeur 0 ou 1, étendue au nombre de bits correspondant au type destination (ex : 32 classiquement avec un cast (int)). Tu ne retrouverais la valeur du char que si tu castes la structure elle-même, ou que tu la couples avec un char dans une union bien sûr.

Citation:

Envoyé par wadabush

Pour moi la reponse est non, et depend tres serieusement du compilo. Des commentaires?

En fonction du compilateur et de l'endianness de la cible, le premier bit déclaré n'est pas forcément le même bit dans l'octet. Il y a des inversions entre GCC / Big-endian et Visual / Little-endian, par exemple, j'ai déjà eu la farce... Ce qui rend l'écriture de telles structures hautement dépendant de la plate-forme et du compilateur, et donc en général fortement déconseillé en dehors des couches très bas niveau.
Pour être honnête, en dehors des bouts de code tapant dans des registres / ports I/O et des protocoles réseau, je n'ai jamais vu de nécessité impérative d'utiliser les bitfields... Or, justement, ces deux types de code sont inextricablement liés à la machine et/ou au compilateur / OS...

Par contre, l'insertion des bits par des décalages / masques, elle, est toujours portable sans restriction tant que tu ne sérialises pas (à ce moment, l'endianness peut jouer si tu travailles sur plus de 8 bits). Mais en restant sur un flux d'octet, même l'endianness n'a plus aucun impact.

Toutefois, en théorie, l'accès par un bitfield est plus rapide que par des décalages / masques manuels, car le compilateur peut utiliser des trucs assez immondes pour optimiser l'accès (ex : décalage bourrin de la valeur et test direct du flag Carry), tout particulièrement en lecture. Comme souvent, tu dois donc trancher entre performances maximales et portabilité...
De plus, dans ce cas particulier du codage de Huffman, je trouve le code avec les décalages plus agréable à lire que celui via les bitfields, car ce dernier ne permet pas l'accès via des boucles et impose des séries hideuses de "switch" assez moches ou l'utilisation de macros encore plus moches...
11/08/2009, 14h05
wadabush

Ok merci de l'eclaircicement.

Je n'ai en effet vu l'emploi de ces bit fields seulement dans des couches plateformes dependant, ce qui confirme ce que tu viens de dire! :ccool: