Dictionnaires, Ensembles & Applications IA

§1 Rappel — le problème des listes

Dans les cours précédents, on a stocké les données dans des listes : une liste de notes, une liste de tailles, une matrice d'images. Les listes, c'est génial pour les séquences ordonnées. Mais pour chercher un élément par sa valeur, c'est lent : il faut parcourir toute la liste.

# Chercher "Bob" dans une liste de noms — O(n)
annuaire_liste = ["Alice", "Bob", "Charlie", "Dana"]
# Pour trouver le numéro de Bob, on parcourt... pas terrible

# Avec un dictionnaire — O(1) en moyenne
annuaire_dict = {"Alice": "0601020304",
                 "Bob":   "0605060708",
                 "Charlie": "0609101112"}
print(annuaire_dict["Bob"])  # Immédiat

§2 Les dictionnaires : des paires clé → valeur

Un dictionnaire associe des clés (keys) à des valeurs (values). Comme un vrai dictionnaire : on cherche un mot (clé), on trouve sa définition (valeur).

2.1 Création et accès

# Création avec accolades (comme un set, mais avec des ':' )
vide = {}
notes = {"Alice": 14, "Bob": 8, "Charlie": 16}

# Accès par clé
print(notes["Alice"])   # 14

# Ajouter / modifier
notes["Dana"] = 12      # Ajoute une nouvelle entrée
notes["Bob"] = 10       # Modifie la note de Bob

print(notes)

2.2 Parcourir un dictionnaire

# Parcours des clés
for nom in notes:
    print(nom, "a", notes[nom])

# Parcours des paires (clé, valeur)
for nom, note in notes.items():
    print(nom, ":", note)

# Avec une compréhension (comme pour les listes !)
adm = {nom: note for nom, note in notes.items() if note >= 10}
print(adm)  # {'Alice': 14, 'Charlie': 16, 'Dana': 12}

2.3 Table de hachage — la magie derrière le rideau

# Les clés doivent être « hashables » (immuables)
# → str, int, float, tuple OK
# → list, dict, set  PAS OK (mutables → hash non stable)

# Le hash d'une chaîne :
print(hash("Bob"))         # par exemple : 619161574
print(hash("Alice"))       # différent (normal)
print(hash((1, 2)))       # un tuple marche
# print(hash([1, 2]))  # TypeError ! Les listes ne sont pas hashables

§3 Applications IA avec les dictionnaires

3.1 Comptage de mots — la fréquence, en mieux

On reprend l'idée du cours 2 (compter des notes), mais avec des mots. Un dictionnaire est parfait : clé = mot, valeur = nombre d'occurrences.

def compte_mots(texte):
    """Compte les occurrences de chaque mot dans un texte.
    Retourne un dict {mot: compte}.
    """
    # On met tout en minuscules et on sépare les mots
    mots = texte.lower().split()
    frequences = {}
    
    for mot in mots:
        # Technique 1 : si le mot n'existe pas, l'initialiser à 1
        if mot in frequences:
            frequences[mot] = frequences[mot] + 1
        else:
            frequences[mot] = 1
    return frequences

# Technique 2 — plus élégante avec .get()
def compte_mots_v2(texte):
    mots = texte.lower().split()
    frequences = {}
    for mot in mots:
        frequences[mot] = frequences.get(mot, 0) + 1
    return frequences

# Technique 3 — avec collections.Counter (bonus)
from collections import Counter

texte = "python java python javascript python java python"
freq = compte_mots_v2(texte)
print(freq)
# {'python': 4, 'java': 2, 'javascript': 1}

3.2 One-Hot Encoding — mettre les mots en nombres

Pour qu'un algorithme d'IA comprenne des mots, il faut les numériser. Le one-hot encoding crée un vecteur de la taille du vocabulaire, avec un 1 à la position du mot et des 0 partout ailleurs.

def one_hot(vocabulaire):
    """Crée un dictionnaire {mot: vecteur_one_hot}.
    vocabulaire est une liste de mots uniques.
    """
    taille = len(vocabulaire)
    vecteurs = {}
    for i, mot in enumerate(vocabulaire):
        vecteur = [0] * taille
        vecteur[i] = 1
        vecteurs[mot] = vecteur
    return vecteurs

vocab = ["python", "java", "javascript"]
encodage = one_hot(vocab)

print("python", "→", encodage["python"])
print("java", "→", encodage["java"])
print("javascript", "→", encodage["javascript"])

3.3 Mémoïsation — accélérer la récursivité

Souvenez-vous du Fibonacci exponentiel du cours 1. On peut le rendre linéaire en mémorisant les résultats déjà calculés dans un dictionnaire (cache). C'est la mémoïsation.

def fib_memo(n, cache={0: 0, 1: 1}):
    """Fibonacci avec mémoïsation — O(n) au lieu de O(2ⁿ).
    
    Le paramètre cache={...} est évalué une fois à la définition
    et conservé entre les appels. C'est un « accumulateur magique ».
    """
    if n in cache:
        return cache[n]
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

print(fib_memo(10))    # 55
print(fib_memo(50))    # 12586269025 — instantané !
print(fib_memo(100))   # 354224848179261915075

3.4 Index inversé — le moteur de recherche du pauvre

Un index inversé associe chaque mot d'un corpus à la liste des documents qui le contiennent. C'est le cœur de tous les moteurs de recherche (Google, Elasticsearch, etc.).

def index_inverse(documents):
    """Construit un index inversé : {mot: [id_doc1, id_doc2, ...]}.
    documents est une liste de chaînes.
    """
    index = {}
    for doc_id, texte in enumerate(documents):
        mots = set(texte.lower().split())  # set = mots uniques
        for mot in mots:
            if mot not in index:
                index[mot] = []
            index[mot].append(doc_id)
    return index

docs = [
    "Python est génial pour l'IA",
    "Java est génial pour le web",
    "Python et l'IA sont géniaux"
]

idx = index_inverse(docs)
print(idx["python"])  # [0, 2] — présent dans doc 0 et 2
print(idx["génial"])  # [0, 1] — présent dans doc 0 et 1

# Recherche : quels documents contiennent "python" ET "IA" ?
resultat = set(idx.get("python", [])) & set(idx.get("ia", []))
print(resultat)  # {0, 2}

§4 Les ensembles (set) : des listes sans doublons

Un set (ensemble) est une collection non ordonnée d'éléments uniques. C'est comme un dictionnaire sans valeurs — juste des clés.

4.1 Création et opérations de base

# Création
vide = set()         # {} crée un dict vide, pas un set !
couleurs = {"rouge", "vert", "bleu", "rouge"}  # les doublons sont ignorés
print(couleurs)  # {'rouge', 'vert', 'bleu'} — l'ordre n'est pas garanti

# Ajout / suppression
couleurs.add("jaune")
couleurs.discard("vert")  # ignore si absent
print(couleurs)

# Test d'appartenance — O(1) (comme les clés de dict)
print("rouge" in couleurs)  # True
print("violet" in couleurs)  # False

4.2 Opérations ensemblistes

A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7}

print(A | B)   # Union           : {1, 2, 3, 4, 5, 6, 7}
print(A & B)   # Intersection    : {4, 5}
print(A - B)   # Différence      : {1, 2, 3}
print(A ^ B)   # Diff. symétrique: {1, 2, 3, 6, 7}

# Sous-ensemble / sur-ensemble
print({1, 2} <= A)  # True — {1,2} ⊆ A
print(A >= {1, 2})  # True — A ⊇ {1,2}

4.3 Applications pratiques

# Supprimer les doublons d'une liste
notes_avec_doublons = [12, 15, 8, 12, 15, 10]
notes_uniques = list(set(notes_avec_doublons))
print(notes_uniques)  # [8, 10, 12, 15] (ordre quelconque)

# Mots communs entre deux textes
texte1 = "Python IA apprentissage profond"
texte2 = "Python web java IA"
mots1 = set(texte1.lower().split())
mots2 = set(texte2.lower().split())
print("Communs :", mots1 & mots2)   # {'python', 'ia'}
print("Union :", mots1 | mots2)     # {'python', 'ia', 'apprentissage', 'profond', 'web', 'java'}

# Vérifier qu'une liste a des doublons
def a_doublons(liste):
    return len(liste) != len(set(liste))

print(a_doublons([1, 2, 3]))     # False
print(a_doublons([1, 2, 1]))     # True

def jaccard(A, B):
    if len(A | B) == 0:
        return 0
    return len(A & B) / len(A | B)

print(jaccard({1,2,3}, {2,3,4}))  # 2/4 = 0.5
# Très utilisé en NLP pour comparer des documents !

§5 Application complète : Bag of Words (sac de mots)

On assemble tout ce qu'on a vu pour construire un classifieur de textes minimal : on transforme chaque document en un vecteur de fréquences (grâce à un dictionnaire de vocabulaire), et on compare les vecteurs.

def sac_de_mots(textes):
    """Crée la matrice TF (term frequencies) pour une liste de textes.
    
    Retourne :
        vocabulaire — dict {mot: index}
        matrice    — liste de listes, chaque ligne est un vecteur de fréquences
    """
    # Étape 1 : construire le vocabulaire (ensemble de tous les mots)
    vocab = set()
    for texte in textes:
        mots = texte.lower().split()
        vocab.update(mots)   # ajoute tous les mots au set
    
    # Transformer le set en dict {mot: index}
    vocab_liste = sorted(vocab)  # ordre stable
    vocab_dict = {mot: i for i, mot in enumerate(vocab_liste)}
    
    # Étape 2 : pour chaque texte, créer un vecteur de fréquences
    matrice = []
    for texte in textes:
        vecteur = [0] * len(vocab)
        mots = texte.lower().split()
        for mot in mots:
            index = vocab_dict[mot]
            vecteur[index] = vecteur[index] + 1
        matrice.append(vecteur)
    
    return vocab_dict, matrice

textes = [
    "l'IA va dominer le monde",
    "Python domine le monde de l'IA",
    "le monde est vaste"
]

vocab, matrice = sac_de_mots(textes)
print("Vocabulaire :", vocab)
# Chaque ligne = un texte, chaque colonne = un mot
for i, vect in enumerate(matrice):
    print("Texte", i, ":", vect)

§6 Pour aller plus loin

6.1 defaultdict — le dictionnaire sans erreur

from collections import defaultdict

# Un dict qui initialise automatiquement les clés manquantes
freq = defaultdict(int)   # int() → 0
groupes = defaultdict(list)  # list() → []

for mot in ["a", "b", "a"]:
    freq[mot] = freq[mot] + 1  # pas de KeyError !

print(freq)  # {'a': 2, 'b': 1}

6.2 Dictionnaires ordonnés (Python 3.7+)

Depuis Python 3.7, les dictionnaires conservent l'ordre d'insertion. C'est pratique, mais ne comptez pas dessus pour trier — utilisez sorted().

6.3 frozenset — le set immuable (donc hashable)

# Utile quand on veut un set comme clé de dictionnaire
equipes = {frozenset(["Alice", "Bob"]): "Équipe A"}
# frozenset est immuable, donc hashable, donc utilisable comme clé

6.4 Limites : la mémoire des dictionnaires

Les dictionnaires sont rapides mais gourmands en mémoire (la table de hachage occupe de l'espace). Pour des millions d'entrées, il faut des structures spécialisées. Mais pour 99% des cas, un dict fait l'affaire.

§7 Le mot de la fin

Avec les dictionnaires et les ensembles, vous avez désormais toutes les structures de données fondamentales de Python : listes, tuples, dictionnaires, sets. Vous êtes équipés pour la quasi-totalité des problèmes d'IA.