Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

huffman Classe de première SI Codage de Hu ?man Table des matièresLe principe L'Algorithme de compression de Hu ?man Convention de codage binaire Codage à taille ?xe à taille variable Le codage à taille variable L'algorithme de Hu ?man Les arbres binaires

Classe de première SI Codage de Hu ?man Table des matièresLe principe L'Algorithme de compression de Hu ?man Convention de codage binaire Codage à taille ?xe à taille variable Le codage à taille variable L'algorithme de Hu ?man Les arbres binaires Implémentation de l'algorithme de Hu ?man Exemple Code source Le codage de Hu ?man est une méthode de compression statistique de données qui permet de réduire la longueur du codage d'un alphabet Le code de Hu ?man est un code de longueur variable optimal c'est- à-dire tel que la longueur moyenne d'un texte codé soit minimale On observe ainsi des réductions de taille de l'ordre de à -hu ?man odt CClasse de première SI Le principe Le principe de l'algorithme de Hu ?man consiste à recoder les octets rencontrés dans un ensemble de données source avec des valeurs de longueur binaire variable L'unité de traitement est ramenée au bit Hu ?man propose de recoder les données qui ont une occurrence très faible sur une longueur binaire supérieure à la moyenne et recoder les données très fréquentes sur une longueur binaire très courte Ainsi pour les données rares nous perdons quelques bits regagnés pour les données répétitives Par exemple dans un ?chier ASCII le w apparaissant fois aura un code très long Ici la perte est de bits x bits car sans compression il serait codé sur bits au lieu de Par contre le caractère le plus fréquent comme le e avec apparitions sera codé par Le gain sera de bits x bits On comprend l'intérêt d'une telle méthode De plus le codage de Hu ?man a une propriété de pré ?xe une séquence binaire ne peut jamais être à la fois représentative d'un élément codé et constituer le début du code d'un autre élément Si un caractère est représenté par la combinaison binaire alors la combinaison ne peut être le code d'aucune autre information Dans ce cas l'algorithme de décodage interpréterait les bits comme une succession du caractère codé puis du caractère codé Cette caractéristique du codage de Hu ?man permet une codi ?cation à l'aide d'une structure d'arbre binaire L'Algorithme de compression de Hu ?man Cet algorithme est non- destructif c'est à dire qu'il compresse les données sans introduire de perte d'information de sorte que le ?chier décompressé est une copie conforme de l'original Le codage employé est dit entropique c'est à dire qu'il se base sur les statistiques d'apparition des di ?érents octets du ?chier et à taille variable c'est à dire que chaque octet est codé selon une suite de bits dont la taille di ?ère selon l'octet Pour comprendre en quoi un codage entropique peut nous permettre de compresser un ?chier nous commençons cette présentation par un rappel sur le principe du stockage d'informations en binaire Convention de codage binaire On code un nombre entier compris entre et par une séquence de chi ?res binaires binary digits ou bits en anglais valant ou encore appelée octet A priori il su ?t pour cela de se