Écrire index inverse(lignes) qui, à partir d'un tableau de lignes de…

def index_inverse(lignes):
    """mot -> liste TRIEE et SANS DOUBLON des numeros de lignes ou il figure.

    Precondition  : lignes est un tableau de chaines.
    Postcondition : chaque liste du resultat est strictement croissante.
    """
    index = {}
    for numero, ligne in enumerate(lignes):
        for mot in ligne.lower().split():
            mot = mot.strip(".,;:!?\"'()")
            if mot == "":
                continue
            if mot not in index:
                index[mot] = [numero]
            elif index[mot][-1] != numero:     # deja vu SUR CETTE LIGNE ?
                index[mot].append(numero)
    for positions in index.values():
        assert positions == sorted(set(positions))
    return index


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

L'astuce qui évite les doublons sans rien trier. Les lignes sont parcourues dans l'ordre croissant : il suffit donc de comparer le numéro courant au dernier enregistré, index[mot][-1]. Si c'est le même, le mot a déjà été vu sur cette ligne. La liste reste automatiquement triée et sans doublon — la postcondition positions == sorted(set(positions)) le vérifie, et elle vérifie les deux propriétés d'un coup.

Combien de lignes sont lues lors d'une recherche ? Aucune. C'est tout l'intérêt de la structure : le texte a été parcouru une fois, à la construction ; ensuite, chaque recherche est un accès par clé, au coût indépendant de la taille du texte. C'est le principe de l'index d'un livre, et celui des moteurs de recherche — qui n'explorent pas le web quand on les interroge, mais consultent l'index construit à l'avance.

La normalisation, et ce qu'elle décide. lower() rend la recherche insensible à la casse ; strip retire la ponctuation collée aux mots, sans quoi « dort. » et « dort, » seraient deux entrées distinctes. Ce sont des décisions : elles appartiennent à la spécification, pas au hasard de l'écriture. Un index qui ne les prendrait pas répondrait « absent » à une recherche parfaitement légitime.

Vérification.

texte = ["Le chat dort.", "Le chien dort, le chat non.", "Rien ne bouge."]
idx = index_inverse(texte)

assert idx["le"] == [0, 1]      # deux fois sur la ligne 1, UNE seule entree
assert idx["chat"] == [0, 1]
assert idx["chien"] == [1]
assert rechercher(idx, "Chat") == [0, 1]
assert rechercher(idx, "souris") == []

Le premier assert est le seul qui teste l'anti-doublon : « le » figure deux fois sur la deuxième ligne, et l'index n'en garde qu'une trace.