Questions TD 2014

Question à propos de trie

question

Il s’agit de reproduire à l’aide de dictionnaires un trie. Voici le code que vous avez donné et qui effectivement fonctionne à merveille

def build_trie(mots) :
    trie = { }
    for m in mots :
        r = trie
        for c in m :
            if c not in r : r[c] = { }
            r = r[c]
    return trie

Cependant, je ne comprends pas très bien comment il fait pour tourner ! A quel moment est ce que l’on modifie le dictionnaire trie défini initialement comme {} ? Pour moi, pour chaque m dans mots, on ne fait que créer une copie nommée r de trie, c’est à dire au début {}, puis on réalise des opérations sur ce r que l’on modifie en cours de route, et à la fin de ces opérations, on passe au mot suivant en créant une nouvelle copie r de trie, à savoir toujours {} !

réponse

Il existe un bon moyen de visualiser l’exécution, c’est le site Python Tutor. En recopiant, l’exemple suivant, on peut suivre pas à pas l’exécution

def build_trie(mots) :
    trie = { }
    for m in mots :
        r = trie
        for c in m :
            if c not in r : r[c] = { }
            r = r[c]
    return trie
mots = [ "aaa", "aba", "aab", "baa", "bbb", "bba", "bab" ]
trie = build_trie(mots)
print(trie)

A chaque nouveau mot, les premiers caractères vont probablement faire déjà partie du trie, les derniers vont être ajoutés au bout d’une branche existante. La question est comment trouver cette branche. Cette branche peut avoir une longueur variable.

../_images/wiki_trie2.png

Pour trouver cette branche, le mécanisme qu’on utilise est très proche de celui qu’on uilise pour se déplacer dans une liste chaînée.

Dans une liste chaînée, il n’y a pas d’indice pour un élément. Chaque élément pointe sur le suivant (il est conseillé d’utiliser Python Tutor pour visualiser l’exécution)

class liste_chainee :

    def __init__ (self, value):
        self.value = value
        self.next = None

    def attache(self, element):
        self.next = element

    def atteindre_la_fin(self):
        position_courante = self
        if position_courante.next is not None:
            position_courante = position_courante.next
        return position_courante

e0 = liste_chainee (0)
e1 = liste_chainee (1)
e2 = liste_chainee (2)
e0.attache(e1)
e1.attache(e2)

fin = e0.atteindre_la_fin()
print(fin.value)

Cet exemple est plus simple car pour se déplacer du début à la fin, il n’y qu’une seule direction : soit on est à la fin, soit il faut continuer car il y a un élément suivant (next n’est pas None).

Toutefois, le programme précédent montre qu’il faut utiliser une variable position_courante qui mémorise la position à laquelle on se trouve lorsqu’on parcours la liste. Pour avancer, on exécute simplement

position_courante = position_courante.next

La position courante devient la suivante. Dans le cas du trie, cette instruction change car l’élément suivant dépend du caractère c

r = r[c]

Le premier code comprend deux éléments :

  • le fait de se promener le long d’un chemin

    r = trie  # initialisation
    r = r[c]  # on avance d'un cran
    
  • le fait d’ajouter un caractère au trie

    r[c] = { }
    

Le caractère c a été ajouté au trie en tant que clé d’un dictionnaire, lui-même valeur d’un dictionnaire associé à une clé égale au caractère précédent dans le mot qu’on est en train d’ajouter.

suite

Lorsque l’on crée un dictionnaire, appelons le « a », puis que l’on en crée une autre copie, que l’on appelle « b », et que l’on modifie b, alors a se retrouve modifié ! Le dictionnaire b est en fait plus qu’une copie, mais une deuxième entité qui code le même objet, et je crois que c’est ca que je n’avais pas compris.

Par ailleurs, ce qui est surprenant, c’est que ceci ne fonctionne qu’avec les dictionnaires ! Lorsque l’on execute ceci

a=[]
b=a
b = b+[2]
print(a)

Alors la sortie est []. Quand on execute ceci

a={}
b=a
b[1]=1
print(a)

La réponse est {1 : 1}.

réponse

Ceci est une propriété des listes et des dictionnaires qui sont des objets mutable en Python. Je renvoie à la page Qu’est-ce qu’un type immuable ou immutable ? pour comprendre ce que sont ces deux propriétés en particulier.

Les listes sont mutable. Donc si on écrit b = a, on crée un second identifiant pour accéder à la même liste. Voici pourquoi écrire a[0]=1 a le même effet que b[0]=1. Toutefois, dans le cas où b désigne une copie de la liste a, ces deux instructions n’auront pas les mêmes conséquences. Pour comprendre le résultat, il faut se demander dans quel cas, on ne fait de copie, dans quel autre une copie a été créée.

L’instruction b=a ne crée pas de copie. L’instuction b=b+[2] construit la concaténation de deux listes, c’est donc une nouvelle liste qu’on affecte à b. Dans l’exemple suivant, ce n’est plus le cas même si le code paraît équivalent

a=[]
b=a
b += [2]  # --> il n'y a plus de copie implicite
print(a)  # --> affiche [2]

Le même exemple pour être écrit avec des dictionnaires car ils sont aussi mutable.