Un petit coucou à Maître Georges en passant...
L'arbre de Huffman vous connaissez?
Est-ce un arbre de Nouvelle Zélande?
Est-ce une espèce rare et persistante qu'on trouve chez quelques pépiniéristes?
Un arbre de style T5 qui cache la forêt?
L'arbre généalogique de la famille Huffman?
Si vous avez répondu oui à l'une de ces questions vous avez tout faux car il ne prendra jamais racine ... sauf si vous jouez cette mystery.
Nous avons tous entendu parler des fichiers compressés, ceux qui permettent de gagner de la place sur votre smartphone ou votre disque dur.
Lorsque Windows vous envoie des mises à jours ses fichiers sont compressés....gain de place et gain de temps....
Ces fichiers s'appellent *.rar,*.war ou *.zip ......Ainsi un fichier compressé utlise des outils qu'on appelle des algorithmes et qui sont l'interaction de l'algorithme LZ77 ( remplacement des séquence s récurrentes par un code de position et de longueur) et le codage de David Albert Huffman sans perte de données présenté en 1951 par ce développeur américain.
Nous nous intéresserons ici au dernier.
(1925-1999)
Petit rappel informatique....
Les ordinateurs convertissent toutes les données en séries de bits (des 0 et des 1).
Ainsi le code Ascii de la lettre M se traduit en binaire 01001101 et la lettre R 01010010.
L'avantage du codage de Huffman est de réduire considérablement le nombre de bits nécessaires à cette traduction en rétribuant un code binaire plus court aux caractères les plus utilisés dans les fichiers qu'il doit compresser.
Il est bien entendu toujours d'actualité mais il ne s'agit pas de cryptographie.
Voici la méthode....avec le mot GEOCACHING
La fréquence d'apparition des lettres est comptée, c'est leur poids.
Pour cela on crée un arbre de Huffman (2 ramifications par noeud) en fonction de leur poids du plus léger( ligne 0) au plus lourd ( ligne 1) en descendant.
Pour obtenir le nouveau code d'un caractère on enregistre en descendant dans l'ordre les numéros des branches à atteindre (les fameux 1 et les 0).
Sur ce graphe les rectangles représentent les feuilles qui contiennent la lettre, son poids et son code compressé.
Les ellipses représentent les décomptes des lettres.
Sur le graphe de GEOCACHING, H devient 011, G devient 10.
On passe ainsi de 80 bits à 25 bits en compressé.
Efficace !!!!! Non ????...
Maintenant passons à la pratique....
Vous pouvez également vous aider par des vidéos et des informations qui circulent sur le Net, vous avez l'embarras du choix.
Voici l'arbre que vous devez résoudre.
Il cache une citation très connue.
Notez que les espaces (space) sont comptés et quelque soit l'ordre des lettre vous aurez toujours le même graphe.
Pour vous aider voici la même citation en latin.
Vous pouvez utiliser le solveur de Dcode
ICI
Ou ce générateur d'arbre d'Huffman pour planter vos propres arbres
ICI
Vous avez trouvé le nom de l'auteur de cette citation?
Alors checkez et rentrez votre réponse en majuscules.
Vous trouverez des instructions pour vous aventurer dans la forêt d' Huffman
et apprécier l'efficacité de la compression de données.
Plantez les arbres d'Huffman en toute saison.
Grâce à certitude. ils prendront racine...
N'attendez pas la Ste Catherine...
La cache se trouve aux coordonnées
N 47° 52.(X*8)+16 W 004° 02.(X*5)-5
Cette page est optimisée pour les smartphones