Étude — l'index des mots, de bout en bout

(a)

def index_inverse(mots: list) -> dict:
    index = {}
    for i in range(len(mots)):
        mot = mots[i]
        if mot not in index:
            index[mot] = []
        index[mot].append(i)
    return index

Cette construction effectue un seul parcours de la liste de mots de longueur $n$. À chaque mot, l'accès ou l'insertion dans le dictionnaire s'effectue en $O(1)$ moyen. La complexité de construction est donc linéaire, en $O(n)$ en moyenne. (b)

• Recherche des positions d'un mot : index.get(mot, []) s'exécute en $O(1)$ moyen, tandis qu'un parcours complet du texte pour chaque recherche prendrait $O(n)$.
• Recherche des mots apparaissant plus de $k$ fois : il suffit de parcourir les couples de l'index et de filtrer sur la longueur de la liste associée (len(index[mot]) > k). Cette opération prend $O(V)$ où $V$ est la taille du vocabulaire unique ($V\le n$). (c) L'index requiert un espace mémoire supplémentaire en $O(n)$ car il duplique l'ensemble des positions des mots. C'est l'illustration de l'échange espace-temps : on alloue une quantité mémoire proportionnelle à la taille des données pour pouvoir interroger ces données instantanément et de façon répétée. (d) Un moteur de recherche Web construit un gigantesque index inverse associant chaque mot du Web à la liste des identifiants des pages Web qui le contiennent. Lors d'une requête de l'utilisateur, le moteur n'a pas à parcourir le Web ou les bases de données textuelles brutes : il interroge son index en $O(1)$ pour récupérer instantanément les listes de pages associées aux mots-clés, puis calcule leur intersection si la requête contient plusieurs termes.