En-tête de HUFFMAN
Cahls
-
l'o.g.m. (Organisme à grosses mains) -
l'o.g.m. (Organisme à grosses mains) -
Bonjour,
Je dois programmer la méthode de compression de HUFFMAN, et je bute sur un problème de choix.
Pour coder l'en-tête d'HUFFMAN afin de l'utiliser lors de la décompression, est-il plus préférable de transmettre la table de codage des couples (caractères, chemin de code) (1), ou est-il plus préférable de transmettre l'arbre directement en faisant un tableau (2) ?
(1) : je coderais un caractère et son code sous 4 octets max : 1 octet pour le caractère, 1 octet pour le nombre de bits utiles, et les suivants pour le code. Ainsi, le nombre d'octets total utilisé pour coder un caractère et son code est variable.
D'ailleurs, quel est le nombre de bits maximum que l'on puisse avoir pour coder le chemin de code dans l'arbre ?
(2) un tableau dont le n° de case est le n° du noeud, puis à l'intérieur du tableau, des cases pour : n° de noeud donnant FD, n° du noeud donnant FG, caractère. Au pire, on a 511 noeuds (2*256-1), donc 511 lignes de tableau. Chaque n° de noeud (1case du tableau) étant codé sur un entier de type "short int" ferait économiser de la place (2 octets), ce qui ferait donc 5 octets, constants, par ligne (1 caractère = 1 octet).
Merci de m'aider à résoudre ce problème !
Je dois programmer la méthode de compression de HUFFMAN, et je bute sur un problème de choix.
Pour coder l'en-tête d'HUFFMAN afin de l'utiliser lors de la décompression, est-il plus préférable de transmettre la table de codage des couples (caractères, chemin de code) (1), ou est-il plus préférable de transmettre l'arbre directement en faisant un tableau (2) ?
(1) : je coderais un caractère et son code sous 4 octets max : 1 octet pour le caractère, 1 octet pour le nombre de bits utiles, et les suivants pour le code. Ainsi, le nombre d'octets total utilisé pour coder un caractère et son code est variable.
D'ailleurs, quel est le nombre de bits maximum que l'on puisse avoir pour coder le chemin de code dans l'arbre ?
(2) un tableau dont le n° de case est le n° du noeud, puis à l'intérieur du tableau, des cases pour : n° de noeud donnant FD, n° du noeud donnant FG, caractère. Au pire, on a 511 noeuds (2*256-1), donc 511 lignes de tableau. Chaque n° de noeud (1case du tableau) étant codé sur un entier de type "short int" ferait économiser de la place (2 octets), ce qui ferait donc 5 octets, constants, par ligne (1 caractère = 1 octet).
Merci de m'aider à résoudre ce problème !
A voir également:
- En-tête de HUFFMAN
- Un mot est caché dans l’en-tête du document. pour le trouver, modifiez sa couleur. - Forum Word
- Impossible de supprimer en-tête word ✓ - Forum Word
- Un mot est caché dans l'en-tête du document. pour le trouver, modifiez sa couleur. ✓ - Forum Word
- Nettoyer tete d'impression hp deskjet 2700 - Forum Imprimante
- Supprimer en tete excel ✓ - Forum Excel
1 réponse
Bonjour,
Personnellement, je transmettrais la table de cardinalités, avec des longueurs variables...
Exemple :
Un premier octet donnant le nombre de bits utiles pour coder l'occurrence de chaque caractère (1-> 0 ou 1 fois ; 2 -> 2 à 3 fois ; 3 -> 4 à 7 fois... n -> 2^(n-1) à 2^n-1 fois... )
Ensuite, triés par ordre ASCII, EBCDIC, autre, les caractères suivis des n bits donnant leur cardinalité dans le fichier d'origine (en se préservant de mettre ceux dont la cardinalité est 0)... Un caractère NULL (zéro binaire) vient clore la liste, à moins que le dernier caractère présent ait le code 255 ;o)
L'agorithme de détermination du codage doit donc être exécuté dans le programme de décompression, de la même manière que dans le programme de compression, mais il me semble que c'est une solution qui permet de gagner pas mal de place, surtout pour les fichiers textes qui n'utilisent qu'une faible partie des caractères.
Bien cordialement,
F.
Personnellement, je transmettrais la table de cardinalités, avec des longueurs variables...
Exemple :
Un premier octet donnant le nombre de bits utiles pour coder l'occurrence de chaque caractère (1-> 0 ou 1 fois ; 2 -> 2 à 3 fois ; 3 -> 4 à 7 fois... n -> 2^(n-1) à 2^n-1 fois... )
Ensuite, triés par ordre ASCII, EBCDIC, autre, les caractères suivis des n bits donnant leur cardinalité dans le fichier d'origine (en se préservant de mettre ceux dont la cardinalité est 0)... Un caractère NULL (zéro binaire) vient clore la liste, à moins que le dernier caractère présent ait le code 255 ;o)
L'agorithme de détermination du codage doit donc être exécuté dans le programme de décompression, de la même manière que dans le programme de compression, mais il me semble que c'est une solution qui permet de gagner pas mal de place, surtout pour les fichiers textes qui n'utilisent qu'une faible partie des caractères.
Bien cordialement,
F.
