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 Codage de Hu ?man Marc Lorenzi décembre In import math import heapq Voici trois cha? nes de caractères que nous utiliserons dans tout le notebook La cha? ne abra est très courte et a des propriétés intéressantes La cha? ne ovide est un peu plus lo

Codage de Hu ?man Marc Lorenzi décembre In import math import heapq Voici trois cha? nes de caractères que nous utiliserons dans tout le notebook La cha? ne abra est très courte et a des propriétés intéressantes La cha? ne ovide est un peu plus longue In abra 'abracadabra' ovide 'Ante mare et terras et quod tegit omnis caelum unus erat toto nat Notion de code Alphabets lettres mots Un alphabet A est un ensemble ?ni d'objets Les éléments d'un alphabet sont appelés des lettres Jusque là tout le monde me suit L'alphabet auquel nous pensons tous est évidemment A a b ? z auquel nous pourrions rajouter les lettres majuscules les chi ?res les symboles de ponctuation etc Mais n'importe quel ensemble ?ni fera l'a ?aire Un mot sur l'alphabet A est une suite ?nie éventuellement vide de lettres Notation On note A ? l'ensemble des mots sur l'alphabet A Un mot de longueur ou taille n ? u a ? an ?? est noté plus simplement u a a ? an ?? par la juxtaposition de ses lettres Le mot vide l'unique mot de longueur qui n'a pas de lettre est noté si besoin Nous noterons u la longueur du mot u Nous disposons donc de la fonction ? A ? ? dé ?nie par u u Convention Nous identi ?erons un mot de longueur avec son unique lettre Avec cette convention A ? A ? Dans toute la suite A désigne un alphabet Lorsque nous écrivons u a ? an ?? et que u est un mot les ai sont les lettres de u et n est sa longueur Le mot vide ne sera pas systématiquement traité comme il conviendrait à son rang le lecteur est censé s'assurer que ce que nous raconterons s'applique aussi dans ce cas Produit de mots CL'ensemble A ? est muni de l'opération de concaténation ou produit des mots que nous noterons multiplicativement Dé ?nition Soient u a a ? am ?? et v b b ? bm ?? deux mots non vides Le produit de u et v est le mot uv a a ? am ?? b b ? bn ?? Si u est le mot vide on pose uv v Si v est le mot vide on pose uv u Propriété A ? muni du produit des mots est un mono? de en général non commutatif Précisément Pour tous u v w ?? A ? uv w u vw Pour tout u ?? A ? u u u L'opération de concaténation est non commutative dès que A possède au moins lettres Démonstration Sans di ?culté particulière Noter que si a et b sont deux lettres di ?érentes de l'alphabet A alors a b ?? b a Le produit n'est donc pas commutatif si A possède au moins deux lettres Propriété Tout mot est le produit de ses lettres Propriété Pour tous mots u v ?? A ? uv u v La fonction ? est donc un morphisme de mono?