En rapport (très lointain) avec l'exercice "le mot le plus long" et son dictionnaire des mots français, j'ai pensé à proposer un exercice dérivé sur le codage de Huffman et sur la création d'un arbre binaire.
Je me suis aperçu après coup que ce sujet a été abordé dans les forums C et C++, mais  pas en Python ...et on ne resiste pas au plaisir d'utiliser la récursivité

Présentation :

Le codage de Huffman est une méthode de compression de données sans perte d'information.
Pour un texte,  le codage standard (ASCII ou UTF-8 par ex.) utilise un (au moins) ou plusieurs octets par caractère. On va remplacer ce codage  par un codage de longueur variable où les caractères les plus utilisés sont codés plus courts que les moins utilisés (ex. réel : 'e' = 010 - codé sur 3 bits, '~' = 1 0101 1011 1001 1101 0111 - codé sur 21 bits !).
En mode dit semi-adaptatif, la table de codage est calculée pour un fichier source. Le calcul se fait à partir des fréquences d'apparition des caractères dans ce fichier, donc le codage est optimal pour ce fichier.
L'algorithme est décrit dans http://fr.wikipedia.org/wiki/Codage_de_huffman (ou http://en.wikipedia.org/wiki/Huffman_coding , en anglais mais plus explicite) : il fait essentiellement appel à un arbre binaire à construire puis à parcourir.

EDIT : les explications de l'article Wikipedia.fr sont un peu rudes : j'ai ajouté un post détaillant le principe du codage à toutes fins utiles.

Exercice proposé :
A partir du fichier source (http://documents.epfl.ch/users/m/ms/mschalle/www/liste_finale.txt) dico des mots français, calculer le gain (en taille du fichier) qui serait obtenu sur ce fichier en lui appliquant le codage de Huffman.

Principe :
- calculer les fréquences d'apparition des caractères dans le fichier source
- calculer et afficher la table de codage de Huffman correspondant à ce fichier (table : caractère <=> code binaire) - c'est le coeur de l'exercice, évidemment !
- calculer le gain potentiel sur ce fichier par rapport à un codage fixe sur 8 bits (type ASCII ou EBCDIC)

- (facultatif) : écrire les fonctions huffman_encode ( texte => bit stream ) et huffman_decode ( bit stream => texte) correspondantes.

Pour l'exercice, on pourra se contenter de traiter les chaînes de bits comme des chaînes (type str) de caractères '0' et '1'  et non comme des vrais paquets de bits : ex. 01010 codé '01010' et non 0b01010

Nota : le fichier dictionnaire proposé est assez gros (> 350.000 mots) mais simplifié : il ne contient que les 26 lettres minuscules sans accents ni cédilles, plus des tirets '-' et les sauts de ligne après chaque mot (ça facilite le debugging éventuel ).

Niveau Python estimé : intermédiaire (la complexité est plutôt sur l'algorithmique)
Connaissances : strings, listes, dictionnaires, fichier texte ...

-
Edité par Rozo2 21 août 2014 à 12:12:38

Voici une soluce pas forcement très bonne mais elle marche ...

Tous les caractères du fichier d'entrée sont traités y compris le saut de ligne.

# calcul du codage de Huffman sur le fichier dico.txt
#  des mots français (sans cédilles, ni accents, mais avec des tirets)
#
# structures utilisées :
#   occurs : dictionnaire clé = caractère ; valeur = nb d'occurrences dans le fich.
#   a_traiter : liste ordonnée (classe PriorityQueue) de 2-tuples
#     des feuilles ou noeuds non traités. Tuple :
#       - numéro du noeud ou caractère (feuille)
#       - nb d'occurrences du caract. ou cumulées pour le sous-arbre d'un noeud 
#   arbre = BinaryTree (géré en dictionnaire) - mémorise l'arborescence binaire
#       - clé (string) = caractère (feuille) ou numéro de noeud (format #999)
#       - valeur : 2-tuple
#             lchild = nom du noeud fils gauche
#             rchild = nom du noeud fils droit
#   codes = liste résultat du codage : tuples
#       - caractère
#       - code de Huffman correspondant (string de '0' et '1')
from math import ceil, log2
 
VERBOSE = 2     # impressions : 0 = aucune
                # 1 = table de codage seule
                # 2 = table + résultats intermédiaires
                 
file_name = "c:/python34/dico.txt"     # path du fichier d'entrée
 
class PriorityQueue(list):
    """ liste de 2-tuples ordonnée sur tuple[1] croissant """
    def __init__(self):                 # la PQ est initialisée vide
        self = list.__init__(self)
        return self
     
    def push(self, info, value) :
        """ ajoute un élément (info, value) à la Priority Queue
              (maintient la liste ordonnée décroissante sur value)
        """
        for i, elt in enumerate(self) :
            if value < elt[1] : continue
            self.insert(i, (info, value))
            break
        else :                 # PQ vide ou value < tous elts existants
            self.append((info, value))   #  ajouter à la fin de PQ
        return
 
    def pull(self) :
        """ retourne l'élément fin de liste (value la + faible) et le supprime
             - léve une exception PQEmpty si PQ vide
        """
        try :
            return self.pop()
        except IndexError :
            raise PQEmpty
 
class PQEmpty(Exception) :
    """ levée quand pull(pop) sur PQ vide """
    pass
 
class BinaryTree(dict) :
    """ arbre binaire géré en dictionnaire """
    def __init__(self,*args):
        self.dernier_noeud = 0
        self = dict.__init__(self, *args)
        return self
     
    def name_node(self):
        """ retourne un nom standardisé pour le dernier noeud créé """
        return "#" + str(self.dernier_noeud)
     
    @staticmethod
    def is_leaf(node) :
        """ retourne True si node est une feuille, False si c'est un noeud """
        return (len(node) <= 1)
 
    def make_node(self, c1, n1, c2, n2):
        """ créer un noeud au dessus des elts (c1, n1) et (c2, n2)
             - retourne (c, n) avec n = n1 + n2 et c = nom du noeud créé
        """
        self.dernier_noeud += 1
        c = self.name_node()
        self[c] = (c1, c2)
        return c, n1 + n2
 
    def parcourir(self, node, inherited_code):
        """ si node est une feuille, la traiter et retour,
              sinon parcourir les branches du noeud de façon récursive
              en propageant le code binaire
        """
    #    global codes
        if self.is_leaf(node) :
            # on a une feuille : maj liste 'codes' pour ce caractère et retour
            codes.append((node, inherited_code))
            return
        # pour un noeud : parcourir les deux branches filles
        left, right = self[node]
        self.parcourir(left, inherited_code + "0")
        self.parcourir(right, inherited_code + "1")
 
# utilitaire :
def print_gain(base):
    """ imprime le gain estimé sur codage fixe à 'base' bits """
#    global nb_tot, nb_bits_huff
    nb_base = nb_tot * base
    if nb_base :
        delta = nb_base - nb_bits_huff
        print("*** gain du codage Huffman / codage {} bits  : {:10.3f} koctets soit {:6.2%} ***"
              .format(base, delta/8000, delta/nb_base))
 
#            __main__   
# calcul des fréquences des lettres (plus '-' et le EOL) dans le fichier dico.txt des mots français
#  résultat dans le dictionnaire 'occurs': clé = caractère, valeur = nombre d'occurrences
 
occurs = {}
nb_tot = 0
with open(file_name) as dico :
    while True :
        buffer = dico.read(10000)
        if buffer == "" : break
        nb_tot += len(buffer)
        for c in buffer :
            occurs[c] = occurs.get(c,0) + 1
 
if VERBOSE >= 2 :   # afficher les tables des fréquences des caractères
    freqs = []
    for c, n in occurs.items() :
        freqs.append((c,n/nb_tot))
    freqs.sort()
    print("Fréquence des caractères dans le fichier source")
    for c, f in freqs :
        print("{} : {:10.6%}".format(c, f))
    print("Classement par fréq. croissante")
    freqs = sorted(freqs, key = lambda tuple : tuple[1])
    for c, f in freqs :
        print("{} : {:10.6%}".format(c, f))
 
#
# traitement de calcul du codage de Huffman :
 
# créer la Priority Queue des elts à traiter - init avec la table des occurrences
a_traiter = PriorityQueue()   
for c, n in occurs.items() :
    a_traiter.push(c, n)
 
# créer l'arbre et vider la PQ en créant les noeuds
arbre = BinaryTree()
while True :
    # créer un noeud avec les deux éléments tête de liste (sortis de la liste)
    try :
        cc, nn = a_traiter.pull()
        ccc, nnn = a_traiter.pull()
    except PQEmpty : break
    # créer le noeud dans l'arbre et l'insérer dans la PQ
    cnw, nnw = arbre.make_node(cc, nn, ccc, nnn)
    a_traiter.push(cnw, nnw)
 
# liste épuisée : root pointe le noeud racine de l'arbre (dernier créé)
root = arbre.name_node()
 
# parcourir l'arbre en descendant depuis root pour calculer les codes de Huffman
# - stocke dans la liste 'codes' les codes des feuilles rencontrées
 
codes = []
seed_code = ""
try :
    arbre.parcourir(root, seed_code)
    codes = sorted(codes)   
except KeyError :   # cas particulier : arbre vide (1 seul caract. dans fich. init)
    for c, n in occurs.items() :
        codes.append((c, '0'))
 
if VERBOSE >= 1 :
    print("Table de codage de Huffman \n  pour le fichier : ",file_name)
    for c, code in codes :
        print("'{}' = {}".format(c,code))
 
if VERBOSE >= 2 :
    nb_bits_huff = sum( len(code) * occurs[c] for c, code in codes) 
    # gain potentiel par rapport au codage 8 bits initial
    print_gain(8)
 
    # gain potentiel par rapport à codage de longueur fixe sur n bits
    base = ceil(log2(len(codes)))
    print_gain(base)

Bémol :avec mon choix d'implantation de l'arbre, je suis obligé de traiter en cas particulier un fichier d'entrée qui aurait un seul caractère (ex : "aaaaa" )

-
Edité par Rozo2 23 août 2014 à 16:36:07

Explications du principe par un exemple :

Soit un texte de 1000 caractères, contenant seulement des lettres minuscules de a à j, donnant la table des fréquences
suivante :
a = 103 , b= 57, c= 264 , d= 53 , e= 356 , f= 65 , g= 9 , h= 3 , i= 85 , j= 5
On aura noté qu'il ne s'agit pas vraiment des fréquences mais du nombre d'occurrences de chaque lettre dans le texte (il suffit de diviser par 1000 pour avoir les fréquences) ; on parlera de poids de la letttre par la suite.

Première étape, on crée une 'liste ordonnée' avec tous ces couples (lettre, poids). On appelle liste ordonnée (LO, ou Priority Queue en anglais) une liste maintenue triée ici selon le poids décroissant, qui retournera l'élément de poids le plus faible à chaque 'pop'.
La LO initiale pour notre ensemble de couples sera :

LO = [(e,356), (c,264), (a,103), (i,85), (f,65), (b,57), (d,53), (g,9), (j,5), (h,3) ]

(la notation est Python like mais ne préjuge pas de l'implémentation réelle ultérieure)

Nous allons maintenant créer l'arbre binaire en partant du bas (la racine est en haut !).

1er tour :
 - sortir de la LO les deux éléments de poids le plus faible: (h,3) et (j,5)
 - créer un noeud, le premier ! qu'on nommera N1 et pointant sur les feuilles h et j :
    arbre :

      N1
     /  \
    h    j

 - entrer dans la LO le noeud créé, avec un poids = poids des deux sous éléments (ici 8 = 3 + 5) :

LO = [(e,356), (c, 264), (a,103), (i,85), (f,65), (b,57), (d,53), (g,9), (N1,8) ]

2eme tour :
Si on a encore au moins deux éléments dans LO, on répète :
 - sortir de la LO les deux éléments de poids le plus faible: N1,8 et g,9
 - créer un noeud, le second, qu'on nommera N2 et pointant sur les éléments N1 et g :

    arbre :
        N2
       /  \
      N1   g
     /  \
    h    j

 - entrer dans la LO le noeud créé, avec un poids = 17 (8 plus 9) :
LO = [(e,356), (c, 264), (a,103), (i,85), (f,65), (b,57), (d,53), (N2,17) ]

3eme tour :  fusion de N2 et d pour donner N3 de poids 70 ; on notera dans la nouvelle LO que N3, qui pèse plus que b et f, est passé avant eux :
LO = [(e,356), (c, 264), (a,103), (i,85), (N3,70), (f,65), (b,57) ]

4eme tour :  fusion de b et f pour donner N4 de poids 122 :
LO = [(e,356), (c, 264), (N4,122), (a,103), (i,85), (N3,70) ]

5eme tour :  fusion de N3 et i pour donner N5 de poids 155 :
LO = [(e,356), (c, 264), (N5,155), (N4,122), (a,103) ]

6eme tour :  fusion de a et N4 pour donner N6 de poids 225 :
LO = [(e,356), (c, 264), (N6,225), (N5,155) ]

7eme tour :  fusion de N5 et N6 pour donner N7 de poids 380 :
LO = [(N7,380), (e,356), (c, 264) ]

8eme tour :  fusion de c et e pour donner N8 de poids 620 :
LO = [(N8,620), (N7,380) ]

9eme tour :  fusion de N7 et N8 pour donner N9 de poids 1000 :
LO = [(N9,1000) ]

 ... et c'est fini : on a créé l'arbre dont le noeud racine est N9.

 Deuxième phase : descendre l'arbre pour calculer les codes binaires des feuilles

Chaque noeud hérite d'un code binaire. Les descendants hériteront de ce code augmenté à droite d'un bit supplémentaire. Arbitrairement, j'ai choisi d'ajouter systématiquement un 0 pour le descendant de la branche de gauche, un 1 pour la branche de droite.

On part de la racine N9 avec un code initial vide. L'arbre est représenté ci-dessous avec le code binaire entre () au dessous des éléments :
                                              N9 
                                              ()       
                            0/----------   ------\1
                            N7                          N8   
                           (0)                          (1)
                    0/----  ----\1               0/  \1
                   N5              N6               c       e 
                  (00)            (01)           (10)  (11)
                0/     \1       0/     \1
                N3       i       a        N4  
             (000) (001)  (010)  (011)
           0/     \1                     0/  \1
          N2       d                     b     f 
       (0000)  (0001)      (0110) (0111)
     0/        \1
    N1          g 
  (00000)  (00001)
 0/         \1
 h             j 
(000000) (000001)

La table de codage, par ordre de longueur de code est donc :
c=10, e=11 , i=001, a=010, d=0001, b=0110, f=0111, g=00001, h=000000, j=000001

On voit que e et c, très fréquents, sont codés sur 2 bits, et on va jusqu'à 6 bits pour les rares h et j !

Ex de codage :
'ceci' = 101110001 (décomposé 10 11 10 001 )
'ebahi' = 110110010000000001 (décomposé 11 0110 010 000000 001 )

Si on reprend notre texte initial avec les occurrences de chaque lettre, le nombre total de bits pour coder le texte entier sera :
 N = 365*2 (pour a) + 264*2 (pour c) + 103*3 (pour i) ... + 3*6 (pour h) = 2597 bits
             soit 324 octets pleins plus 5 bits dans un dernier octet.
Avec un codage 'classique' sur 8 bits, il aurait fallu 1000 octets. Le gain est de 67,54 %  !!!

Je vous laisse découvrir comment dans l'autre sens décoder une chaîne de bits en chaîne de caractères (ex . 010110101010000001001 > 'ebahi') en utilisant l'arbre binaire construit pour le codage ...

-
Edité par Rozo2 25 août 2014 à 11:02:47

Voilà un lien qui peut vous aider 

http://python-prepa.github.io/information_theory.html

Bonsoir, voici un algorithme un peu moins long :

def divise(arbre):
    return arbre[0], arbre[1]


def parcours_branche(arbre,A):
    if (type(arbre) != list) and (type(arbre) !=  np.ndarray) :
        return [[arbre, A]]
    arbre1, arbre2 = divise(arbre)
    A1 = A + str(arbre1[1])
    A2 = A + str(arbre2[1])
    L1 = parcours_branche(arbre1[0],A1)
    L2 = parcours_branche(arbre2[0],A2)
    return L1 + L2


def Huffman(M): 
    L = []
    for E in M :
        for n in E :
            if not(n in L) :
                L.append(n)
    P = [[L[k],0] for k in range(len(L))]
    for E in M :
        for n in E :
            k = 0
            while L[k] != n :
                k = k+1
            P[k][1] = P[k][1] + 1
    while len(P)>1 :
        Min1 = P[0][1]
        indice1 = 0
        for i in range(len(P)):
            if Min1>P[i][1] :
                Min1 = P[i][1]
                indice1 = i
        indice2 = (indice1 + 1)%len(P)
        Min2 = P[indice2][1]
        for i in range(len(P)):
            if (Min2>=P[i][1]) and (i != indice1) :
                Min2 = P[i][1]
                indice2 = i
        a, b = min(indice1,indice2), max(indice1,indice2)
        A = P[0:a] + P[a+1: b] + P[b+1:]
        a = 1
        if Min1 == min(Min1, Min2) :
            a = 0
        P = A + [[[[P[indice1][0], a],[P[indice2][0],1-a]], Min1 + Min2]]
    P = P[0][0]
    E = parcours_branche(P,'0')
    for i in range(len(E)):
        E[i][1] = E[i][1][1:]
    return E