Wie funktioniert eine Suchmaschine?

Das lernst du

Verstehen, warum Suchmaschinen nicht jede Seite einzeln durchlesen
Einen Index aus Wörtern und Seiten bauen
Mit Mengen Seiten finden, auf denen mehrere Wörter vorkommen

Milliarden Seiten in einer halben Sekunde

Eine Suchmaschine kennt Milliarden Webseiten. Trotzdem bekommst du die Ergebnisse in Sekundenbruchteilen. Sie liest die Seiten also nicht erst durch, wenn du suchst. Das macht sie vorher – und baut daraus einen Index.

Ohne Index: alles durchlesen

So würde es ohne Index gehen. Bei drei Seiten ist das kein Problem:

seiten = {
    "hunde": "hunde sind treue tiere",
    "katzen": "katzen sind tiere die gern schlafen",
    "fische": "fische leben im wasser",
}

gesucht = "tiere"
gelesen = 0
for name, text in seiten.items():
    gelesen = gelesen + len(text.split())
    if gesucht in text.split():
        print("Gefunden auf:", name)
print("Dafür gelesene Wörter:", gelesen)

Bei Milliarden Seiten müsste der Computer aber für jede Suche Billionen Wörter lesen. Viel zu langsam!

Der Index: wie im Register eines Buchs

Hinten in einem Sachbuch steht ein Register: „Roboter … Seite 12, 48, 97“. Du musst nicht das ganze Buch lesen. Eine Suchmaschine macht dasselbe. Für jedes Wort merkt sie sich, auf welchen Seiten es vorkommt. Dafür passt ein Dictionary mit Mengen perfekt:

seiten = {
    "hunde": "hunde sind treue tiere",
    "katzen": "katzen sind tiere die gern schlafen",
}

index = {}
for name, text in seiten.items():
    for wort in text.split():
        if wort not in index:
            index[wort] = set()
        index[wort].add(name)

for wort in sorted(index):
    print(f"{wort:8} → {sorted(index[wort])}")

Jetzt ist die Suche nach „tiere“ nur noch ein Blick ins Dictionary: index["tiere"].

Mehrere Wörter: die Schnittmenge

Suchst du „treue tiere“, willst du Seiten, auf denen beide Wörter stehen. Das ist die Schnittmenge der beiden Mengen. In Python schreibst du dafür &:

tiere = {"hunde", "katzen", "pferde"}
treue = {"hunde", "pferde", "freunde"}

print("Beide Wörter:", tiere & treue)
print("Mindestens eins:", tiere | treue)

Gut zu wissen: Echte Suchmaschinen merken sich außerdem, wie oft und wo ein Wort vorkommt. Und sie bewerten, wie viele andere Seiten auf eine Seite verlinken. So kommen die besten Treffer nach oben. Das Grundprinzip ist aber genau dein Index.

Deine Aufgabe

Jetzt bist du dran

Bau eine Mini-Suchmaschine. index_bauen(seiten) bekommt ein Dictionary „Seitenname → Text“ und gibt den Index zurück: ein Dictionary „Wort → Menge der Seitennamen“. Wörter werden klein geschrieben, die Satzzeichen .,!? vorher entfernt. suchen(index, anfrage) gibt eine alphabetisch sortierte Liste der Seiten zurück, auf denen alle Wörter der Anfrage vorkommen (Groß-/Kleinschreibung egal). Kennt der Index ein Wort nicht, ist das Ergebnis leer.

seiten = {
    "hunde": "Hunde sind treue Tiere. Hunde spielen gern.",
    "katzen": "Katzen sind Tiere, die gern schlafen.",
    "fische": "Fische leben im Wasser!",
}


def index_bauen(seiten):
    index = {}
    return index


def suchen(index, anfrage):
    return []


index = index_bauen(seiten)
print(suchen(index, "Tiere gern"))

Denkanstoß
Für jedes Wort: if wort not in index: index[wort] = set() – danach index[wort].add(name).
Welcher Befehl hilft?
Die Schnittmenge zweier Mengen bekommst du mit &: treffer = treffer & index[wort].
Kommt ein Wort nicht im Index vor, gib sofort eine leere Liste zurück.

Lückencode – ergänze die ___

                        seiten = {
    "hunde": "Hunde sind treue Tiere. Hunde spielen gern.",
    "katzen": "Katzen sind Tiere, die gern schlafen.",
    "fische": "Fische leben im Wasser!",
}


def woerter(text):
    for zeichen in ___:
        text = ___
    return ___


def index_bauen(seiten):
    index = {}
    for name, text in ___:
        for wort in ___:
            if ___:
                index[wort] = ___
            ___
    return index


def suchen(index, anfrage):
    treffer = ___
    for wort in ___:
        if ___:
            return []
        if ___:
            treffer = ___
        else:
            treffer = ___
    return ___


index = index_bauen(seiten)
print(suchen(index, "Tiere gern"))

Ohne Hinweise gelöst gibt es einen ⭐ auf deiner Fortschrittsseite.

Lösung anzeigen

Versuch es erst selbst – aus Fehlern lernt man am meisten. Hier ist eine mögliche Lösung:

seiten = {
    "hunde": "Hunde sind treue Tiere. Hunde spielen gern.",
    "katzen": "Katzen sind Tiere, die gern schlafen.",
    "fische": "Fische leben im Wasser!",
}


def woerter(text):
    for zeichen in ".,!?":
        text = text.replace(zeichen, "")
    return text.lower().split()


def index_bauen(seiten):
    index = {}
    for name, text in seiten.items():
        for wort in woerter(text):
            if wort not in index:
                index[wort] = set()
            index[wort].add(name)
    return index


def suchen(index, anfrage):
    treffer = None
    for wort in woerter(anfrage):
        if wort not in index:
            return []
        if treffer is None:
            treffer = set(index[wort])
        else:
            treffer = treffer & index[wort]
    return sorted(treffer or [])


index = index_bauen(seiten)
print(suchen(index, "Tiere gern"))