Problème — Construction d'un index inversé

Dictionnaires et tables de hachage · niveau 2

Énoncé

Problème — Construction d'un index inversé.

Un index inversé associe à chaque mot la liste des documents (identifiés par un numéro) dans lesquels il apparaît. C'est le cœur d'un moteur de recherche. On donne une liste de documents, chacun étant une chaîne de mots. Construire l'index inversé, puis écrire une fonction de recherche renvoyant les documents contenant un mot donné.

Corrigé

On parcourt chaque document et chacun de ses mots, en ajoutant le numéro du document à la liste associée au mot. On utilise un ensemble intermédiaire pour éviter les doublons au sein d'un même document.


def construire_index(documents):
    index = {}
    for numero, texte in enumerate(documents):
        for mot in set(texte.split()):     # mots distincts du doc
            if mot not in index:
                index[mot] = []
            index[mot].append(numero)
    return index

def rechercher(index, mot):
    return index.get(mot, [])

docs = [
    "le chat dort",
    "le chien dort",
    "le chat et le chien"
]
index = construire_index(docs)
print(rechercher(index, "chat"))   # [0, 2]
print(rechercher(index, "dort"))   # [0, 1]
print(rechercher(index, "souris")) # []

Chaque insertion et chaque recherche dans l'index coûtent $O (1)$ en moyenne ; la construction est donc linéaire par rapport au nombre total de mots.