Trie

Kurz gesagt: Ein Trie ist ein Baum aus Buchstaben, in dem der gemeinsame Anfang der Wörter nur einmal gespeichert wird. Darum kostet eine Präfixsuche (Autovervollständigung) so viel wie die Länge des Präfixes.

Problem

Das Suchfeld

Der Shop hat 200.000 Produkte. Ein Kunde tippt „ko“ ins Suchfeld, und darunter sollen Vorschläge erscheinen: „kohl“, „kokos“, „korb“. Mit jedem neuen Buchstaben ändern sich die Vorschläge.

Die erste Lösung geht alle Namen durch und prüft, welche mit dem Getippten beginnen. Das ist eine lineare Suche: 200.000 Prüfungen bei jedem Tastendruck. Tausend Kunden, die gleichzeitig tippen, machen Hunderte Millionen Prüfungen pro Sekunde.

Und die meisten Namen beginnen gar nicht mit „k“. Warum sie überhaupt ansehen?

(Die Namen stehen im Katalog klein geschrieben. Warum, erklärt die Karte zu Groß- und Kleinschreibung weiter unten.)

Die Idee

Ein Baum aus Buchstaben

Zeichne die Namen als Pfade. Von der Wurzel gehen Äste nach dem ersten Buchstaben ab, von jedem von ihnen nach dem zweiten, und so weiter. „kohl“, „kokos“ und „korb“ beginnen mit „ko“: Diese zwei Buchstaben werden einmal gespeichert, und die Äste trennen sich erst danach.

Dieser Baum ist ein Trie (von retrieval, meist wie „try“ gesprochen). Jeder Knoten hält:

seine Kinder nach Buchstaben: eine Sammlung Buchstabe → Knoten;
eine Markierung, dass hier ein Name endet. Ein Name kann in einem anderen enden: „kohl“ und „kohlrabi“.

Eine Präfixsuche hat zwei Teile:

Hinabgehen entlang der Buchstaben des Präfixes, ein Schritt pro Buchstabe. Fehlt ein Buchstabe, gibt es keine solchen Produkte.
Einsammeln: den Ast unter dem letzten Knoten ablaufen. Jeder Knoten mit der Markierung „hier endet ein Name“ ist ein Vorschlag.

Das Hinabgehen kostet so viel wie die Buchstaben des Präfixes, nicht so viel wie die Produkte.

Sieh es dir an

Einfügen und Präfixsuche

TreeMap hält die Kinder nach Buchstaben sortiert, deshalb kommen die Vorschläge in alphabetischer Reihenfolge heraus.

class Node {
    final Map<Character, Node> kids = new TreeMap<>();
    boolean end;
    int count;
}

class Trie {
    private final Node root = new Node();

    void insert(String name, int count) {
        Node at = root;
        for (char ch : name.toCharArray()) {
            Node next = at.kids.get(ch);
            if (next == null) {
                next = new Node();
                at.kids.put(ch, next);
            }
            at = next;
        }
        at.end = true;
        at.count = count;
    }

    List<String> complete(String prefix) {
        Node at = root;
        for (char ch : prefix.toCharArray()) {
            at = at.kids.get(ch);
            if (at == null) return List.of();
        }
        List<String> found = new ArrayList<>();
        collect(at, prefix, found);
        return found;
    }

    private void collect(Node at, String word,
            List<String> found) {
        if (at.end) found.add(word);
        for (char ch : at.kids.keySet()) {
            collect(at.kids.get(ch), word + ch, found);
        }
    }
}

Das Einsammeln ist Rekursion, wie in der Lektion „Rekursion“: Jeder Knoten sammelt seine Namen ein und fragt seine Kinder. Der Basisfall ist ein Knoten ohne Kinder.

Vier Produkte und drei Suchen:

var trie = new Trie();
trie.insert("kohl", 120);
trie.insert("kokos", 15);
trie.insert("korb", 40);
trie.insert("tee", 60);
System.out.println("ko: " + trie.complete("ko"));
System.out.println("koh: " + trie.complete("koh"));
System.out.println("m: " + trie.complete("m"));

ko: [kohl, kokos, korb]
koh: [kohl]
m: []

class Node {
    final Map<Character, Node> kids = new TreeMap<>();
    boolean end;
    int count;
}

class Trie {
    private final Node root = new Node();

    void insert(String name, int count) {
        Node at = root;
        for (char ch : name.toCharArray()) {
            Node next = at.kids.get(ch);
            if (next == null) {
                next = new Node();
                at.kids.put(ch, next);
            }
            at = next;
        }
        at.end = true;
        at.count = count;
    }

    List<String> complete(String prefix) {
        Node at = root;
        for (char ch : prefix.toCharArray()) {
            at = at.kids.get(ch);
            if (at == null) return List.of();
        }
        List<String> found = new ArrayList<>();
        collect(at, prefix, found);
        return found;
    }

    private void collect(Node at, String word,
            List<String> found) {
        if (at.end) found.add(word);
        for (char ch : at.kids.keySet()) {
            collect(at.kids.get(ch), word + ch, found);
        }
    }
}

Schritt für Schritt, in Worten

Ein leerer Trie: nur die Wurzel. Jeder Schritt nach unten ist ein Buchstabe, darum buchstabiert ein Pfad von der Wurzel einen Namen.
insert(„kohl“): Buchstaben gibt es noch keine, darum macht jeder Schritt einen neuen Knoten. Der letzte wird grün: Hier endet ein Name.
„kokos“ beginnt wie „kohl“: Die ersten beiden Buchstaben gibt es schon, man geht nur durch sie hindurch. Neue Knoten entstehen nur dort, wo sich die Namen trennen.
„korb“ teilt den Anfang ebenfalls, und „tee“ beginnt einen eigenen Ast an der Wurzel. Vier Namen, ein gemeinsamer Anfang.
complete(„ko“): zwei Schritte nach unten, einer pro Buchstabe des Präfixes. Das ist die ganze Suche, egal wie viele Produkte es gibt.
Einsammeln: Nur der Ast unter dem Präfix wird abgelaufen, die Kinder in alphabetischer Reihenfolge. Jeder grüne Knoten ist ein Name und kommt in die Liste.
Drei Vervollständigungen: kohl, kokos, korb. „tee“ wurde nie angesehen: Sein Ast liegt nicht unter dem Präfix.

„tee“ wird nie angesehen: Sein Ast liegt nicht unter „ko“.

Probier es aus

Sage die Ausgabe voraus

Drei Produkte. Ein Name ist der Anfang eines anderen:

var trie = new Trie();
trie.insert("kohl", 1);
trie.insert("korb", 1);
trie.insert("kohlrabi", 1);
System.out.println("koh: " + trie.complete("koh"));

Antwort

koh: [kohlrabi]

koh: [kohl, kohlrabi]

koh: [kohl, kohlrabi, korb]

Probier es aus

Ergänze

Was macht beim Einsammeln einen Knoten zu einem Vorschlag?

if (at.) found.add(word);

Die Idee

Was es kostet

Einfügen: ein Schritt pro Buchstabe des Namens: O(m), wobei m seine Länge ist.
Ein Präfix hinabgehen: ein Schritt pro Buchstabe des Präfixes: O(m), egal wie viele Produkte es gibt.
Einsammeln: so groß wie der Ast unter dem Präfix. Zeigst du nur die ersten 5 Vorschläge, hörst du nach dem fünften auf.

Lass die drei Wege laufen. Der Katalog besteht aus n Namen mit 4 bis 8 Buchstaben, in alphabetischer Reihenfolge. Der Kunde tippt 20 Präfixe mit je zwei Buchstaben, und für jedes werden die ersten 5 Namen gebraucht. Gezählt werden die Zeichen, die die Suche ansieht: der Vergleich eines Buchstabens des Namens mit einem Buchstaben des Präfixes oder ein Schritt von einem Knoten zu einem Kind. Der Trie wird einmal gebaut, wenn der Katalog geladen wird, und nicht mitgezählt.

Alle Namen durchgehen O(n)
Binäre Suche im sortierten Katalog O(log n)
Trie O(1)

Algorithmus	n = 10	n = 1.000	n = 10.000	n = 100.000
Alle Namen durchgehen	223	11.778	93.071	1.303.482
Binäre Suche im sortierten Katalog	125	542	676	808
Trie	46	403	342	266

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

class Node {
    final Map<Character, Node> kids = new TreeMap<>();
    boolean end;
    int count;
}

class Trie {
    private final Node root = new Node();

    void insert(String name, int count) {
        Node at = root;
        for (char ch : name.toCharArray()) {
            Node next = at.kids.get(ch);
            if (next == null) {
                next = new Node();
                at.kids.put(ch, next);
            }
            at = next;
        }
        at.end = true;
        at.count = count;
    }

    List<String> complete(String prefix) {
        Node at = root;
        for (char ch : prefix.toCharArray()) {
            at = at.kids.get(ch);
            if (at == null) return List.of();
        }
        List<String> found = new ArrayList<>();
        collect(at, prefix, found);
        return found;
    }

    private void collect(Node at, String word,
            List<String> found) {
        if (at.end) found.add(word);
        for (char ch : at.kids.keySet()) {
            collect(at.kids.get(ch), word + ch, found);
        }
    }
}

Bei 100.000 Namen sieht das Durchlaufen 1.303.482 Zeichen an, die binäre Suche im sortierten Katalog 808 und der Trie 266. Je mehr Namen es gibt, desto dichter ist der Baum und desto früher sind die fünf eingesammelt: Bei 1000 Namen sieht der Trie 403 Zeichen an, bei 100.000 weniger.

Die binäre Suche ist hier dabei, weil der Katalog sortiert ist: Dann findet sie den ersten Namen mit dem Präfix in log₂ n Vergleichen (binäre Suche). Mehr dazu weiter unten.

Sieh es dir an

Das Meistgekaufte zuerst

Die alphabetische Reihenfolge ist nicht die nützlichste. Wenn ein Kunde „ko“ tippt, will er eher kohl als kokos. Darum hält jeder Knoten, in dem ein Name endet, auch fest, wie oft das Produkt gekauft wurde (count). Die Vorschläge werden danach sortiert:

int countOf(String name) {
    Node at = root;
    for (char ch : name.toCharArray()) at = at.kids.get(ch);
    return at.count;
}

List<String> suggest(String prefix, int k) {
    List<String> names = new ArrayList<>(complete(prefix));
    names.sort(Comparator.comparingInt(this::countOf).reversed());
    return names.subList(0, Math.min(k, names.size()));
}

var trie = new Trie();
trie.insert("kohl", 120);
trie.insert("kokos", 15);
trie.insert("korb", 40);
trie.insert("tee", 60);
trie.insert("kohlrabi", 8);
trie.insert("kopfsalat", 25);
System.out.println("ko: " + trie.suggest("ko", 3));

ko: [kohl, korb, kopfsalat]

Die Sortierung ist stabil (siehe Stabilität): Bei gleich vielen Käufen bleibt die alphabetische Reihenfolge erhalten.

Genauer, für Neugierige

Hier sammelt jede Suche alle Namen unter dem Präfix ein und sortiert sie dann. Bei „k“ sind das in einem echten Katalog Zehntausende. Darum halten große Suchmaschinen in jedem Knoten die fertigen ersten 5 bis 10 Vorschläge für den Ast darunter. Die Suche ist dann nur noch das Hinabgehen, und der Preis wird beim Einfügen gezahlt: Jeder Knoten auf dem Pfad eines neuen Namens prüft, ob der Name in seine Bestenliste kommt.

Probier es aus

Finde den Fehler

Ein Kollege hat das Einsammeln geschrieben, aber die Vorschläge sind voller Wortstücke:

private void collect(Node at, String word, List<String> found) {
    found.add(word);
    for (char ch : at.kids.keySet()) {
        collect(at.kids.get(ch), word + ch, found);
    }
}

var trie = new Trie();
trie.insert("kohl", 120);
trie.insert("kokos", 15);
trie.insert("korb", 40);
trie.insert("tee", 60);
System.out.println("ko: " + trie.complete("ko"));

ko: [ko, koh, kohl, kok, koko, kokos, kor, korb]

In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Groß- und Kleinschreibung und ähnlich aussehende Zeichen

Für den Trie sind „K“ und „k“ verschiedene Buchstaben: verschiedene Kinder des Knotens. Ein Kunde, der „Kohl“ tippt oder „ kohl“ mit einem Leerzeichen davor, findet nichts. Darum gehen sowohl der Name beim Einfügen als auch der Text bei der Suche durch ein und dieselbe Normalisierung: keine Leerzeichen an den Enden, ein Leerzeichen zwischen Wörtern, Kleinbuchstaben. (Deshalb stehen die Namen im Katalog klein geschrieben.)

static String normalize(String text) {
    return text.strip().toLowerCase(Locale.ROOT).replaceAll("\\s+", " ");
}

var trie = new Trie();
trie.insert("kohl", 120);
trie.insert("kokos", 15);
trie.insert("korb", 40);
trie.insert("tee", 60);
trie.insert("kohlrabi", 8);
trie.insert("kopfsalat", 25);
trie.insert("müsli", 30);
System.out.println("KoHl: " + trie.complete(normalize("  KoHl ")));
System.out.println("musli: " + trie.complete(normalize("musli")));

KoHl: [kohl, kohlrabi]
musli: []

Die zweite Suche findet nichts, obwohl der Katalog „müsli“ hat. „u“ und „ü“ sind verschiedene Zeichen, verschiedene Kinder im Baum. Dasselbe passiert bei Buchstaben, die genau gleich aussehen: das lateinische „a“ und der kyrillische Buchstabe, der genauso aussieht, in einem Shop, der in zwei Alphabeten verkauft. Die Normalisierung behebt das nicht von allein: Du brauchst einen ausdrücklichen Ersatz (zum Beispiel das Entfernen der Umlautpunkte), wenn du es verzeihen willst.

Genauer, für Neugierige

toLowerCase() ohne Argument benutzt die Sprache des Rechners. Auf einem türkischen Rechner wird „I“ zu „ı“ (i ohne Punkt), und die Suche nach lateinischen Namen bricht. Locale.ROOT gibt überall dieselbe Regel. Noch etwas: char ist in Java 16 Bit groß. Lateinische und kyrillische Buchstaben passen in ein char, ein Emoji braucht aber zwei, und ein Trie nach char zerschneidet es in Hälften.

Wie es in den anderen Sprachen ist: Java und C# laufen nach 16-Bit-char, Python und for…of in JavaScript nach Zeichen. Für lateinische und kyrillische Buchstaben gibt es keinen Unterschied.

Die Idee

Speicher, und wann ein sortiertes Array reicht

Jeder Knoten hält seine Kinder. Dafür gibt es zwei Wege:

Eine Sammlung Buchstabe → Knoten, wie hier: Der Knoten hält nur die Kinder, die er hat.
Ein Array aus Plätzen, einer pro Buchstabe: 26 für das lateinische Alphabet, 30 für das deutsche mit ä, ö, ü und ß, 32 mit Leerzeichen und Bindestrich. Das Kind findet man sofort über die Nummer des Buchstabens, aber jeder Knoten hält alle Plätze, auch die leeren.

Wie leer sind sie? Der Trie im Bench für 100.000 Namen (631.833 Buchstaben) hat 210.642 Knoten, im Mittel ein Kind pro Knoten: Der gemeinsame Anfang ist kurz, danach geht jeder Name für sich weiter. Ein Array mit 30 Plätzen pro Knoten hält mehr als 6,3 Millionen Verweise, von denen 210.641 belegt sind. Die Sammlung ist kleiner, und das Array ist nur in den oberen Ebenen schneller, wo es viele Kinder gibt.

Wenn sich die Namen selten ändern und du nur „alle, die mit … beginnen“ brauchst, reicht oft ein sortiertes Array. Die binäre Suche findet den ersten Namen, der nicht vor dem Präfix steht, und die Treffer liegen danach nebeneinander:

List<String> names = List.of("kohl", "kohlrabi", "kokos", "kopfsalat", "korb", "tee");
String prefix = "ko";
int at = Collections.binarySearch(names, prefix);
if (at < 0) at = -at - 1;
List<String> found = new ArrayList<>();
while (at < names.size() && names.get(at).startsWith(prefix)) {
    found.add(names.get(at++));
}
System.out.println(prefix + ": " + found);

ko: [kohl, kohlrabi, kokos, kopfsalat, korb]

Collections.binarySearch gibt −(Einfügestelle) − 1 zurück, wenn das Präfix kein Name ist. Mit -at - 1 bekommst du also den ersten Namen, der nicht davor steht.

Ein Trie gewinnt, wenn ständig Namen hinzukommen und verschwinden, wenn du Zähler und das Meistgekaufte für jedes Präfix brauchst oder wenn du Buchstabe für Buchstabe suchst, während der Kunde tippt: Jeder neue Buchstabe ist ein Schritt von dem Knoten, den du schon erreicht hast.

Übung

Wie viele Produkte beginnen mit …

Löse die Aufgabe in deinem Editor.

Die Anzahl unter einem Präfix. Neben jedem Vorschlag zeigt das Feld, wie viele Produkte mit dem Getippten beginnen. Füge dem Knoten einen Zähler hinzu, wie viele Namen durch ihn gehen, und eine Methode countPrefix, die das Präfix hinabgeht und den Zähler zurückgibt, ohne Namen einzusammeln. Füge den ganzen Katalog aus der Karte „Das Meistgekaufte zuerst“ ein und prüfe die Präfixe „ko“, „koh“, „t“ und „m“:

ko: 5
koh: 2
t: 1
m: 0

Weitere Aufgaben

Löschen. Ein Produkt wird nicht mehr verkauft. Entferne den Namen aus dem Trie, ohne die Namen zu zerstören, die durch dieselben Knoten gehen.
Anzahl der Knoten. Zähle die Knoten nach dem Einfügen des Katalogs und vergleiche mit der Gesamtzahl der Buchstaben in den Namen.
Buchstabe für Buchstabe. Baue eine Suche, die den erreichten Knoten behält und für jeden neuen Buchstaben nur einen Schritt macht.

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·

Trie

Cookies