Codage de Huffman

Cette technique fonctionne en créant un arbre binaire de nœuds. Ceux-ci peuvent être stockés dans un tableau régulier , dont la taille dépend du nombre de symboles.symbole lui-même, son poids (fréquence d'apparition) et, éventuellement, un lien vers un nœud parent . Ceci facilite la lecture du code (à l'envers) à partir d'une feuille. Les nœuds internes contiennent un poids , des liens vers deux enfants et, éventuellement, un lien vers un parent . Par convention, le bit « 0 » indique de suivre l'enfant gauche et le bit « 1 » indique de suivre l'enfant droit. Un arbre complet peut comporter jusqu'à

Le processus commence avec les nœuds feuilles contenant les probabilités du symbole qu'ils représentent. Ensuite, il sélectionne les deux nœuds ayant la plus faible probabilité et crée un nouveau nœud interne dont ces deux nœuds sont les enfants. Le poids de ce nouveau nœud est égal à la somme des poids de ses enfants. On applique ensuite le processus à nouveau, sur le nouveau nœud interne et sur les nœuds restants (c'est-à-dire en excluant les deux nœuds feuilles), et on répète ce processus jusqu'à ce qu'il ne reste qu'un seul nœud, qui est la racine de l'arbre de Huffman.

L'algorithme de construction le plus simple utilise une file de priorité où le nœud ayant la plus faible probabilité se voit attribuer la priorité la plus élevée :

1. Créez un nœud feuille pour chaque symbole et ajoutez-le à la file d'attente prioritaire.
2. Alors qu'il y a plus d'un nœud dans la file d'attente :
   1. Retirez de la file d'attente les deux nœuds de priorité la plus élevée (probabilité la plus faible).
   2. Créez un nouveau nœud interne avec ces deux nœuds comme enfants et avec une probabilité égale à la somme des probabilités des deux nœuds.
   3. Ajouter le nouveau nœud à la file d'attente.
3. Le nœud restant est le nœud racine et l'arbre est complet.

Étant donné que les structures de données de file de priorité efficaces nécessitent un temps O(log n ) par insertion, et qu'un arbre avec n feuilles a 2 n −1 nœuds, cet algorithme fonctionne en O( n log n ), où n est le nombre de symboles.

Si les symboles sont triés par probabilité, il existe une méthode linéaire (O( n )) pour créer un arbre de Huffman à l'aide de deux files d' attente : la première contient les poids initiaux (ainsi que des pointeurs vers les feuilles associées), et les poids combinés (ainsi que des pointeurs vers les arbres) sont placés à la fin de la seconde file d'attente. Ceci garantit que le poids le plus faible est toujours placé en tête de l'une des deux files d'attente :

1. Commencez avec autant de feuilles qu'il y a de symboles.
2. Enfilez tous les nœuds feuilles dans la première file d'attente (par ordre de probabilité croissant de sorte que l'élément le moins probable soit en tête de file d'attente).
3. Bien qu'il y ait plus d'un nœud dans les files d'attente :
   1. Retirez de la file les deux nœuds ayant le poids le plus faible en examinant les têtes des deux files d'attente.
   2. Créez un nouveau nœud interne, avec les deux nœuds qui viennent d'être supprimés comme enfants (chaque nœud peut être l'un ou l'autre enfant) et la somme de leurs poids comme nouveau poids.
   3. Insérer le nouveau nœud à la fin de la deuxième file d'attente.
4. Le nœud restant est le nœud racine ; l'arbre a maintenant été généré.

Une fois l'arbre de Huffman généré, on le parcourt pour générer un dictionnaire qui associe les symboles à des codes binaires comme suit :

1. Commencez par définir le nœud actuel comme racine.
2. Si le nœud n'est pas une feuille, étiquetez l'arête vers l'enfant gauche comme 0 et l'arête vers l'enfant droit comme 1. Répétez le processus pour l'enfant gauche et l'enfant droit.

L'encodage final de chaque symbole est alors lu par une concaténation des étiquettes sur les arêtes le long du chemin allant du nœud racine au symbole.

Dans de nombreux cas, la complexité temporelle n'est pas très importante dans le choix de l'algorithme, car n représente ici le nombre de symboles dans l'alphabet, qui est généralement un nombre très petit (comparé à la longueur du message à encoder) ; tandis que l'analyse de la complexité concerne le comportement lorsque n devient très grand.

Il est généralement avantageux de minimiser la variance de la longueur des mots de code. Par exemple, un tampon de communication recevant des données codées par Huffman peut nécessiter une taille plus importante pour gérer des symboles particulièrement longs si l'arbre est fortement déséquilibré. Pour minimiser la variance, il suffit de départager les files d'attente en choisissant l'élément de la première file. Cette modification préserve l'optimalité mathématique du codage de Huffman tout en minimisant la variance et la longueur du code du caractère le plus long.

De manière générale, la décompression consiste simplement à traduire le flux de codes de préfixe en valeurs d'octets individuelles, généralement en parcourant l'arbre de Huffman nœud par nœud à mesure que chaque bit est lu dans le flux d'entrée (atteindre une feuille met fin à la recherche de cette valeur d'octet). Cependant, avant cela, l'arbre de Huffman doit être reconstruit. Dans le cas le plus simple, où les fréquences des caractères sont relativement prévisibles, l'arbre peut être préconstruit (et même ajusté statistiquement à chaque cycle de compression) et ainsi réutilisé, au prix d'une légère perte d'efficacité de compression. Sinon, les informations nécessaires à la reconstruction de l'arbre doivent être transmises a priori. Une approche naïve consisterait à ajouter le nombre d'occurrences de chaque caractère au début du flux de compression. Malheureusement, la surcharge dans ce cas pourrait atteindre plusieurs kilo-octets, ce qui rend cette méthode peu utile en pratique. Si les données sont compressées à l'aide d'un codage canonique , le modèle de compression peut être reconstruit avec précision.

L'algorithme original de Huffman est optimal pour un codage symbole par symbole avec une distribution de probabilité d'entrée connue, c'est-à-dire pour le codage séparé de symboles non liés dans un tel flux de données. Cependant, il n'est plus optimal lorsque la contrainte de codage symbole par symbole est levée, ou lorsque les fonctions de masse de probabilité sont inconnues. De plus, si les symboles ne sont ni indépendants ni identiquement distribués , un seul code peut s'avérer insuffisant pour une performance optimale. D'autres méthodes, telles que le codage arithmétique, offrent souvent une meilleure capacité de compression.

Bien que les deux méthodes susmentionnées puissent combiner un nombre arbitraire de symboles pour un codage plus efficace et s'adaptent généralement aux statistiques d'entrée réelles, le codage arithmétique le fait sans augmenter significativement sa complexité de calcul ou algorithmique (bien que sa version la plus simple soit plus lente et plus complexe que le codage de Huffman). Cette flexibilité est particulièrement utile lorsque les probabilités d'entrée sont imprécises ou varient considérablement au sein du flux. Cependant, le codage de Huffman est généralement plus rapide et le codage arithmétique a historiquement suscité des inquiétudes quant aux brevets . De ce fait, de nombreuses technologies ont historiquement privilégié le codage de Huffman et d'autres techniques de codage par préfixe, délaissant ainsi le codage arithmétique. À la mi-2010, les techniques les plus couramment utilisées pour cette alternative au codage de Huffman sont tombées dans le domaine public, les premiers brevets ayant expiré.

Pour un ensemble de symboles à distribution de probabilité uniforme et dont le nombre d'éléments est une puissance de deux , le codage de Huffman est équivalent à un codage binaire par blocs simple , tel que le codage ASCII . Ceci s'explique par le fait qu'aucune compression n'est possible avec de telles données d'entrée, quelle que soit la méthode employée ; autrement dit, ne rien modifier aux données est la solution optimale.

Le codage de Huffman est optimal parmi toutes les méthodes lorsque chaque position du flux d'entrée est une variable aléatoire indépendante et identiquement distribuée, de probabilité dyadique . Les codes préfixes, et donc le codage de Huffman en particulier, sont généralement inefficaces sur les petits alphabets, où les probabilités se situent souvent entre ces points optimaux (dyadiques). Le pire cas pour le codage de Huffman se produit lorsque la probabilité du symbole le plus probable dépasse largement 2^{1/2  − 1} = 0,5, rendant la limite supérieure de l'inefficacité infinie.

Deux approches connexes permettent de contourner cette inefficacité tout en utilisant le codage de Huffman. Le regroupement d'un nombre fixe de symboles (« blocage ») augmente généralement (et ne diminue jamais) la compression. Lorsque la taille du bloc tend vers l'infini, le codage de Huffman tend théoriquement vers la limite d'entropie, c'est-à-dire la compression optimale . Cependant, le blocage de groupes de symboles arbitrairement grands est impraticable, car la complexité d'un code de Huffman est linéaire par rapport au nombre de possibilités de codage, un nombre qui est exponentiel par rapport à la taille d'un bloc. Ceci limite le blocage effectué en pratique.

Une alternative pratique et largement répandue est le codage par plages . Cette technique ajoute une étape au codage entropique : le comptage (ou séquence) des symboles répétés, qui sont ensuite codés. Dans le cas simple des processus de Bernoulli , le codage de Golomb est optimal parmi les codes préfixes pour le codage par plages, un fait démontré par les techniques de codage de Huffman . Une approche similaire est utilisée par les télécopieurs, qui emploient un codage de Huffman modifié . Cependant, le codage par plages n'est pas aussi adaptable à un grand nombre de types d'entrées que d'autres technologies de compression.

L' algorithme de Huffman n -aire utilise un alphabet de taille n , généralement {0, 1, ..., n-1}, pour encoder les messages et construire un arbre n -aire. Cette approche a été envisagée par Huffman dans son article original. Le même algorithme s'applique qu'en binaire (n symboles les moins probables sont regroupés.

Notez que pour n > 2, tous les ensembles de mots sources ne peuvent pas former correctement un arbre n -aire complet pour le codage de Huffman. Dans ces cas, il peut être nécessaire d'ajouter des symboles de substitution supplémentaires de probabilité nulle. En effet, la structure de l'arbre doit relier de manière répétée n branches en une seule, ce que l'on appelle une combinaison « n à 1 ». Pour le codage binaire, il s'agit d'une combinaison « 2 à 1 », qui fonctionne quel que soit le nombre de symboles. Pour le codage n -aire, un arbre complet n'est possible que si le nombre total de symboles (réels + symboles de substitution) est égal à 1 lorsqu'il est divisé par (n-1).

Une variante appelée codage de Huffman adaptatif consiste à calculer dynamiquement les probabilités en fonction des fréquences réelles récentes dans la séquence des symboles sources, et à modifier la structure de l'arbre de codage pour correspondre aux estimations de probabilité mises à jour. Elle est rarement utilisée en pratique, car le coût de la mise à jour de l'arbre la rend plus lente que le codage arithmétique adaptatif optimisé , qui est plus flexible et offre une meilleure compression.

Le plus souvent, les poids utilisés dans les implémentations du codage de Huffman représentent des probabilités numériques, mais l'algorithme présenté ci-dessus ne l'exige pas ; il requiert seulement que les poids forment un monoïde commutatif totalement ordonné , c'est-à-dire une manière de les ordonner et de les additionner. L' algorithme de Huffman permet d'utiliser tout type de poids (coûts, fréquences, paires de poids, poids non numériques) et l'une des nombreuses méthodes de combinaison (et pas seulement l'addition). De tels algorithmes peuvent résoudre d'autres problèmes de minimisation, comme la minimisation de…

Le codage de Huffman à longueur limitée est une variante où l'objectif reste d'obtenir une longueur de chemin pondéré minimale, mais avec une contrainte supplémentaire : la longueur de chaque mot de code doit être inférieure à une constante donnée. L' algorithme de fusion de paquets résout ce problème par une approche gloutonne simple , très similaire à celle utilisée par l'algorithme de Huffman. Sa complexité temporelle est O (n²).

Dans le problème de codage de Huffman standard, on suppose que chaque symbole de l'ensemble à partir duquel les mots de code sont construits a un coût de transmission identique : un mot de code de longueur N chiffres aura toujours un coût de N , quel que soit le nombre de 0, de 1, etc. parmi ces chiffres. Sous cette hypothèse, minimiser le coût total du message et minimiser le nombre total de chiffres reviennent au même.

Le codage de Huffman avec coûts de lettres inégaux est une généralisation qui s'affranchit de cette hypothèse : les lettres de l'alphabet de codage peuvent avoir des longueurs non uniformes, du fait des caractéristiques du support de transmission. L'alphabet de codage du code Morse en est un exemple : un tiret est plus long à transmettre qu'un point, et son coût temporel est donc plus élevé. L'objectif reste de minimiser la longueur moyenne pondérée des mots de code, mais il ne suffit plus de minimiser uniquement le nombre de symboles utilisés par le message. Aucun algorithme connu ne résout ce problème de la même manière ni avec la même efficacité que le codage de Huffman classique, bien qu'il ait été résolu par Richard M. Karp , dont la solution a été affinée pour le cas des coûts entiers par Mordecai J. Golin

Dans le problème de codage de Huffman standard, on suppose que tout mot de code peut correspondre à n'importe quel symbole d'entrée. Dans la version alphabétique, l'ordre alphabétique des entrées et des sorties doit être identique. Ainsi, par exemple,de Hu-Tucker , d'après T.C. Hu et Alan Tucker , auteurs de l'article présentant la première solution. de ce problème d'arbre binaire alphabétique optimal présente certaines similarités avec l'algorithme de Huffman, sans toutefois en être une variante. Une méthode ultérieure, l' algorithme de Garsia-Wachs d' Adriano Garsia et Michelle L. Wachs (1977), utilise une logique plus simple pour effectuer les mêmes comparaisons dans le même laps de temps total. Ces arbres binaires alphabétiques optimaux sont souvent utilisés comme arbres de recherche binaire .