Problème — Construction d'un index inversé
Application directe du cours · niveau 2 · NSI (terminale), chapitre 2 — Dictionnaires et tables de hachage
É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 en moyenne ; la construction est donc linéaire par rapport au nombre total de mots.
Les autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.