Codes Huffman: exemples, applications

Pour le moment, peu de gens pensent àComment fonctionne la compression de fichier? Par rapport au passé, utiliser un ordinateur personnel est devenu beaucoup plus facile. Et presque toutes les personnes travaillant avec le système de fichiers utilisent des archives. Mais peu de gens pensent à leur fonctionnement et au principe de la compression de fichier. Les codes de Huffman constituaient la toute première version de ce processus. Ils sont toujours utilisés par divers archiveurs populaires. De nombreux utilisateurs ne pensent même pas à quel point il est facile de compresser un fichier et en fonction de quel schéma cela fonctionne. Dans cet article, nous verrons comment la compression se produit, quelles nuances aident à accélérer et simplifier le processus de codage, ainsi que le principe de la construction d'un arbre de codage.

Histoire de l'algorithme

Le tout premier algorithme à conduire efficacementLe codage des informations électroniques est devenu le code proposé par Huffman dès le milieu du XXe siècle, à savoir en 1952. Qu'il est actuellement le principal élément de base de la plupart des programmes conçus pour compresser des informations. Actuellement, l’une des sources les plus populaires utilisant ce code est ZIP, ARJ, RAR et de nombreuses autres archives.

En outre, cet algorithme de Huffman est utilisé pourCompressez les images JPEG et autres objets graphiques. Tous les télécopieurs modernes utilisent également le codage inventé en 1952. Bien que beaucoup de temps ait passé depuis la création du code, il est encore utilisé aujourd'hui dans les coquilles les plus récentes et dans l'équipement des types anciens et modernes.

Le principe du codage efficace

L'algorithme de Huffman est basé sur un schémavous permet de remplacer les codes de caractères les plus probables et les plus courants du système binaire. Et ceux qui sont moins communs sont remplacés par des codes plus longs. La transition vers les codes de Huffman longs se produit uniquement après que le système a utilisé toutes les valeurs minimales. Cette technique vous permet de réduire la longueur du code pour chaque caractère du message d'origine dans son ensemble.

Le point important est qu'au débutLes probabilités de codage de l'apparition des lettres doivent déjà être connues. C'est à partir d'eux que le message final sera composé. Sur la base de ces données, l’arborescence de codes de Huffman est en cours de construction, sur la base de laquelle le processus de codage des lettres dans les archives est effectué.

Exemple de code Huffman

Pour illustrer l’algorithme, prenonsversion graphique de la construction de l'arbre de code. Pour utiliser efficacement cette méthode, il convient de préciser la définition de certaines valeurs nécessaires au concept de cette méthode. L'ensemble d'arcs et de nœuds dirigés d'un nœud à l'autre s'appelle un graphe. L'arbre lui-même est un graphe avec un ensemble de propriétés spécifiques:

• chaque nœud ne peut contenir 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 y entrer du tout;
• Si vous commencez à vous déplacer depuis la racine le long d'arcs, ce processus devrait vous permettre de tomber complètement dans l'un des nœuds.

Il y a aussi une telle chose incluse dans les codesHuffman comme une feuille d'arbre. C'est un nœud à partir duquel aucun arc ne doit s'étendre. Si deux nœuds sont connectés par un arc, l'un d'eux est un parent, l'autre enfant, en fonction du nœud auquel l'arc entre et dans lequel il entre. Si deux nœuds ont le même nœud parent, ils sont appelés nœuds fraternels. Si, à part les feuilles, les nœuds apparaissent en plusieurs arcs, alors cet arbre est appelé binaire. Tel est l'arbre de Huffman. Une caractéristique des nœuds de cette construction est que le poids de chaque parent est égal à la somme du poids de tous ses enfants clés.

Algorithme de construction d'arbre de Huffman

Construire un code de Huffman se compose de lettresalphabet d'entrée. Une liste des nœuds libres dans la future arborescence de codes est formée. Le poids de chaque nœud de cette liste doit être identique à la probabilité d'occurrence de la lettre du message correspondant à ce nœud. Dans ce cas, parmi les quelques nœuds libres du futur arbre, celui qui pèse le moins est sélectionné. De plus, si les indicateurs minimum sont observés sur plusieurs nœuds, vous pouvez choisir librement l’une des paires.

Après cela, la création du parentun nœud qui devrait peser autant que la somme de cette paire de nœuds. Après cela, le parent est envoyé à la liste avec des nœuds libres et les enfants sont supprimés. Dans ce cas, les arcs reçoivent les indicateurs correspondants, des uns et des zéros. Ce processus est répété exactement le temps nécessaire pour ne laisser qu'un seul nœud. Ensuite, les chiffres binaires sont écrits dans la direction du haut vers le bas.

Amélioration de l'efficacité de la compression

Pour améliorer l'efficacité de la compression, vous devezIl est temps de créer un arbre de code afin d’utiliser toutes les données relatives à la probabilité que des lettres d’un fichier particulier soient jointes à un arbre, et d’empêcher qu’elles ne soient dispersées dans un grand nombre de documents texte. Si vous parcourez d'abord ce fichier, vous pouvez calculer immédiatement les statistiques sur la fréquence de recherche des lettres de l'objet à compresser.

Accélérer le processus de compression

Pour accélérer l’algorithme, la définition des lettresdoit être effectuée non pas en fonction de la probabilité d'apparition d'une lettre particulière, mais en fonction de sa fréquence De ce fait, l'algorithme devient plus facile et le travail avec celui-ci est grandement accéléré. Cela évite également les opérations liées aux virgules flottantes et aux divisions.

De plus, travaillant dans ce mode, dynamiqueLe code de Huffman, ou plutôt l'algorithme lui-même, n'est sujet à aucune modification. Cela 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 dit racine sera égal à la somme du nombre de lettres de l'objet à traiter.

Conclusion

Codes de Huffman - simples et établis depuis longtempsUn algorithme qui est encore utilisé par de nombreux programmes et entreprises bien connus. Sa simplicité et sa clarté permettent d’obtenir des résultats efficaces en compressant des fichiers de toutes tailles et réduisent considérablement l’espace disque qu’ils occupent. En d’autres termes, l’algorithme de Huffman est un schéma bien étudié et développé depuis longtemps, dont la pertinence ne diminue pas à ce jour.

Et grâce à la possibilité de réduire la taille des fichiers,leur transmission via le réseau ou par d'autres moyens devient plus facile, plus rapide et plus pratique. En utilisant l'algorithme, il est possible de compresser absolument n'importe quelle information sans nuire à sa structure et à sa qualité, mais avec le maximum d'effet de réduire le poids du fichier. En d’autres termes, le codage de Huffman a été et reste la méthode la plus courante et la plus courante pour la compression de la taille de fichier.