Tous les exemples de codage de Huffman que j'ai vus utilisent des lettres (A, B, C) comme caractères à coder, dans lesquels ils calculent les fréquences de chacun pour générer l'arbre de Huffman. Que se passe-t-il lorsque les données à coder sont binaires ? J'ai vu des gens traiter chaque octet comme un caractère, mais pourquoi ? Il semble arbitraire d'utiliser 8 bits comme seuil pour un "caractère", pourquoi pas 16 ? Pourquoi pas 32 pour l'architecture 32 bits ?
Réponse
Trop de publicités?
David Cary
Points
1678
C'est très perspicace de votre part de vous rendre compte que Codage de Huffman peut travailler avec plus de 256 symboles. Quelques implémentations du codage de Huffman fonctionnent avec bien plus de 256 symboles, comme par exemple
- HuffWord, qui analyse un texte anglais en mots plus ou moins anglais (généralement des blocs de texte contenant environ 32 000 mots uniques) et génère un arbre de Huffman dans lequel chaque feuille représente un mot anglais, codé avec un code de Huffman unique.
- HuffSyllable, qui analyse le texte en syllabes et génère un arbre de Huffman dont chaque feuille représente (approximativement) une syllabe anglaise, codée avec un code de Huffman unique.
- DEFLATE qui remplace d'abord les chaînes répétées par des symboles (longueur, décalage), dispose de plusieurs tables de Huffman différentes, dont l'une est optimisée pour représenter les symboles les distances (offsets), et un autre avec 287 symboles où chaque feuille représente soit une longueur spécifique (partie du symbole (longueur, décalage)) ou un octet littéral.
- Certains des arbres de Huffman à longueur limitée utilisés dans la compression JPEG coder JPEG quantifié valeurs de luminosité (de -2047 à +2047 ?) avec une longueur de code maximale de 16 bits.
Sur un ordinateur à architecture 16 bits ou 32 bits, les fichiers texte ASCII et les fichiers texte UTF-8 et les photographies sont à peu près les mêmes que sur les ordinateurs 8 bits, il n'y a donc aucune raison de passer à une approche différente.
Sur une architecture 16 bits ou 32 bits, le code machine est généralement aligné sur 16 bits, de sorte que l'algorithme de Huffman statique avec des symboles de 16 bits peut s'avérer judicieux.
L'algorithme de Huffman statique implique la transmission d'informations sur les longueurs de bits pour chaque symbole, afin que le récepteur puisse reconstruire les mots de code nécessaires à la décompression. Les quelque 257 longueurs de bits de l'en-tête de la méthode Huffman statique à 8 bits sont déjà trop importantes pour la "compression de chaînes courtes". Comme l'a souligné sascha, l'utilisation de 16 bits pour un "caractère" nécessiterait une surcharge beaucoup plus importante (65 000 longueurs de bits environ), de sorte que le codage de Huffman statique avec des entrées de 16 bits n'aurait de sens que pour les longs fichiers où cette surcharge est moins importante.
