Index inverse

Deuxieme étape du moteur de recherche : l'index inverse. C'est LA structure de données qui fait fonctionner Google, Elasticsearch, et tous les moteurs de recherche.

L'idee est simple : au lieu de chercher dans chaque document un par un (trop lent), on construit a l'avance un dictionnaire qui dit pour chaque mot dans quels documents il apparait.

Par exemple, avec trois documents :
doc 0 : 'python est rapide'
doc 1 : 'python est simple'
doc 2 : 'java est verbeux'

L'index inverse serait :
'python' apparait dans [0, 1]
'java' apparait dans [2]
'est' apparait dans [0, 1, 2]

Écris une fonction construire_index(documents) qui prend une liste de chaines et retourne ce dictionnaire. Utilise la fonction tokeniser fournie. Attention : un mot ne doit apparaitre qu'une seule fois par document dans la liste (meme s'il y est plusieurs fois).

Tests (2/4)

Index simple

docs = ['python est rapide', 'python est simple', 'java est verbeux']
index = construire_index(docs)
assert set(index['python']) == {0, 1}

Mot dans tous

docs = ['python est rapide', 'python est simple', 'java est verbeux']
index = construire_index(docs)
assert set(index['est']) == {0, 1, 2}

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

import re
from collections import defaultdict

def tokeniser(texte):
    mots = re.findall(r'[a-zA-ZÀ-ÿ0-9]+', texte.lower())
    return [mot for mot in mots if len(mot) > 1]

def construire_index(documents):
    index = defaultdict(list)
    for i, doc in enumerate(documents):
        mots_vus = set()
        for mot in tokeniser(doc):
            if mot not in mots_vus:
                index[mot].append(i)
                mots_vus.add(mot)
    return dict(index)

← Tokenisation de documents Recherche simple dans l'index →

solution.py

Bravo!

Index inverse

Tests (2/4)

Indices (3 disponibles)

Solution officielle