Codes Huffman: exemples, applications

Pour le moment, peu de gens pensent au fait,comment fonctionne la compression. Comparé au passé, l'utilisation d'un ordinateur personnel est devenue beaucoup plus facile. Et pratiquement chaque personne travaillant avec le système de fichiers utilise des archives. Mais peu de gens pensent à leur fonctionnement et sur quel principe est la compression des fichiers. La toute première version de ce processus était les codes Huffman, et ils sont encore utilisés dans divers archivers populaires. Beaucoup d'utilisateurs ne pensent même pas combien il est facile de compresser le fichier et selon quel schéma cela fonctionne. Dans cet article, nous verrons comment la compression fonctionne, quelles nuances aident à accélérer et à simplifier le processus d'encodage, et nous comprendrons également le principe de construction d'un arbre de codage.

Histoire de l'algorithme

Le tout premier algorithme pour une efficacitéle codage de l'information électronique était le code proposé par Huffman au milieu du XXe siècle, à savoir en 1952. C'est actuellement l'élément de base principal de la plupart des programmes créés pour compresser l'information. À l'heure actuelle, l'une des sources les plus populaires utilisant ce code sont les archives ZIP, ARJ, RAR et bien d'autres.

Cet algorithme de Huffman est également utilisé pourcompression d'images JPEG et d'autres objets graphiques. Eh bien, tous les télécopieurs modernes utilisent également le codage, inventé en 1952. Malgré le fait que depuis la création du code tant de temps a passé, à ce jour il est utilisé dans les nouveaux obus et sur l'équipement des types anciens et modernes.

Le principe du codage efficace

La base de l'algorithme de Huffman est un schéma,Il permet de remplacer les symboles les plus probables, les plus fréquemment rencontrés par les codes d'un système binaire. Et ceux qui sont moins communs sont remplacés par des codes plus longs. La transition vers les codes Huffman longs se produit uniquement lorsque le système utilise toutes les valeurs minimales. Cette technique vous permet de minimiser la longueur du code pour chaque caractère du message original dans son ensemble.

Un point important est que, au débutl'encodage de la probabilité d'occurrence des lettres devrait déjà être connu. C'est à partir de ceux-ci que le message final sera compilé. Sur la base de ces données, l'arbre de code Huffman est construit, sur la base duquel le processus d'encodage des lettres dans l'archive sera effectué.

Le code de Huffman, exemple

Pour illustrer l'algorithme, prenonsune version graphique de la construction d'un arbre de code. Pour utiliser cette méthode a été efficace, il est utile de clarifier la définition de certaines valeurs nécessaires pour le concept de cette méthode. L'ensemble des arcs et des nœuds qui sont dirigés de nœud à nœud est généralement appelé un graphique. L'arbre lui-même est un graphique avec un ensemble de certaines propriétés:

• dans chaque nœud ne peut pas entrer plus d'un des arcs;
• l'un des nœuds doit être la racine de l'arbre, c'est-à-dire qu'aucun arc ne doit l'entrer du tout;
• Si à partir de la racine pour commencer à se déplacer le long des arcs, ce processus devrait permettre d'entrer complètement dans l'un des nœuds.

Il y a aussi un tel concept, qui est inclus dans les codesHuffman, comme une feuille d'arbre. C'est un nœud à partir duquel aucun arc ne devrait s'échapper. Si deux nœuds sont connectés par un arc, alors l'un d'entre eux est le parent, l'autre enfant, selon le nœud dont provient l'arc et celui dans lequel il se trouve. Si deux nœuds ont le même nœud parent, ils sont généralement appelés nœuds fraternels. Si, en plus des feuilles, il y a plusieurs arcs dans les nœuds, cet arbre est appelé binaire. C'est exactement l'arbre de Huffman. La particularité des nœuds de cette construction est que le poids de chaque parent est égal à la somme du poids de tous ses enfants nodaux.

Algorithme pour construire un arbre selon Huffman

La construction du code Huffman est faite à partir de lettresde l'alphabet d'entrée. Une liste de ces nœuds qui sont libres dans le futur arbre de code est créée. Le poids de chaque noeud dans la liste doit être la même que la probabilité d'occurrence des postes de lettres correspondant à ce noeud. Dans ce cas, parmi les quelques noeuds libres du futur arbre est choisi celui qui pèse le moins. Dans le même temps, si les indicateurs minimum sont observés dans plusieurs nœuds, il est alors possible de choisir librement l'une des paires.

Ensuite, la création du parentnœud, qui devrait peser autant que la somme de cette paire de nœuds pèse. Après cela, le parent est envoyé à la liste avec des nœuds libres, et les enfants sont supprimés. En même temps, les arcs reçoivent les indices correspondants, les uns et les zéros. Ce processus est répété exactement aussi longtemps que nécessaire pour ne laisser qu'un seul noeud. Après cela, les nombres binaires sont écrits de haut en bas.

Améliorer l'efficacité de la compression

Pour augmenter l'efficacité de compression, il est nécessaire dele temps de construire un arbre de code pour utiliser toutes les données concernant la probabilité de lettres apparaissant dans un fichier particulier attaché à un arbre, et de ne pas les laisser disperser sur un grand nombre de documents texte. Si vous parcourez d'abord ce fichier, vous pouvez immédiatement calculer les statistiques sur la fréquence à laquelle les lettres d'un objet à compresser sont rencontrées.

L'accélération du processus de compression

Pour accélérer l'algorithme, la définition des lettresIl est nécessaire d'effectuer non sur les indices de la probabilité de l'apparition de telle ou telle lettre, et sur la fréquence de son apparition. Grâce à cela, l'algorithme devient plus simple, et le travail avec celui-ci est grandement accéléré. Cela évite également les opérations associées aux virgules flottantes et à la division.

De plus, travaillant dans ce mode, dynamiqueLe code de Huffman, ou plutôt l'algorithme lui-même, n'est soumis à aucun changement. Ceci est principalement dû au fait que les probabilités sont directement proportionnelles aux fréquences. Il convient de porter une attention particulière au fait que le poids final du fichier ou du nœud racine sera égal à la somme du nombre de lettres dans l'objet à traiter.

Conclusion

Les codes de Huffman - simples et établis de longue datealgorithme, qui est encore utilisé par de nombreux programmes et entreprises bien connus. Sa simplicité et sa clarté permettent d'obtenir des résultats de compression efficaces pour les fichiers de toute taille et de réduire considérablement l'espace qu'ils occupent sur le disque de stockage. En d'autres termes, l'algorithme de Huffman est un schéma longuement étudié et bien conçu, dont la pertinence ne diminue pas à ce jour.

Et grâce à la possibilité de réduire la taille des fichiers,leur transmission à travers le réseau ou par d'autres moyens devient plus simple, rapide et pratique. En travaillant avec l'algorithme, vous pouvez compresser absolument n'importe quelle information sans nuire à sa structure et à sa qualité, mais avec l'effet maximum de réduire le poids du fichier. En d'autres termes, le codage de code de Huffman était et reste la méthode la plus populaire et la plus courante de compression de taille de fichier.