Tries für Präfix-Lookups: Autovervollständigung und Longest-Prefix-Matching

Worum es geht

Das NIST-Wörterbuch definiert einen Trie als Baum zum Speichern von Strings mit einem Knoten für jedes gemeinsame Präfix. Jede Kante trägt ein Symbol (ein Byte, Zeichen oder Bit), und eine Terminal-Markierung oder ein Blatt identifiziert gespeicherte Schlüssel. Das Nachschlagen eines Schlüssels durchläuft eine Kante pro Symbol, sodass die Kosten von der Länge des Schlüssels abhängen, nicht von der Anzahl gespeicherter Schlüssel. Alle Schlüssel mit gemeinsamem Präfix liegen im Teilbaum unter dem Knoten dieses Präfixes. Ein Radix-Baum (Patricia- oder kompakter Trie) verschmilzt Ketten von Knoten mit nur einem Kind zu einer beschrifteten Kante, um Speicher zu sparen. Die IPv4-Routing-Tabelle des Linux-Kernels ist ein LC-Trie, dessen Lookup, wie seine Dokumentation beschreibt, durch den Trie zurückverfolgt, um das längste passende Präfix für eine Zieladresse zu finden.

Warum es wichtig ist

Zwei Operationen sind mit Hash-Tabellen unhandlich: «jeder Schlüssel, der mit X beginnt» und «der längste gespeicherte Schlüssel, der ein Präfix von X ist». Tries machen aus der ersten einen Teilbaum-Durchlauf und aus der zweiten einen einzigen Abstieg, der sich den zuletzt passierten Terminal-Knoten merkt. Autovervollständigung, HTTP-Pfad-Router, IP-Longest-Prefix-Matching, Tokenisierer und Sperrlisten lassen sich alle auf eine der beiden zurückführen.

So wird es angewendet

• Zuerst das Alphabet festlegen: Bytes sind am einfachsten; bei Text die Normalisierung (Unicode-NFC, Case Folding) beim Einfügen und beim Nachschlagen identisch anwenden und entscheiden, ob Knoten Codepoints oder UTF-8-Bytes sind.
• Das Knoten-Layout nach Alphabetdichte wählen: ein Array von Kindern für kleine, dichte Alphabete, ein kleines sortiertes Array oder eine Hash-Map für spärliche, Radix-Kompression, wenn Schlüssel lange gemeinsame Abschnitte teilen.
• Autovervollständigung: zum Präfix-Knoten hinabsteigen, dann mit einer Ergebnisbegrenzung durchlaufen; Zähler pro Knoten oder ein zwischengespeichertes Top-k speichern, um «häufigste Vervollständigungen» zu beantworten, ohne den ganzen Teilbaum zu durchlaufen.
• Longest-Prefix-Matching: die Anfrage durchlaufen, den tiefsten gesehenen Terminal-Knoten festhalten, ihn zurückgeben, wenn der Durchlauf endet oder fehlschlägt.
• Vor dem Bau eines Tries ein sortiertes Array probieren: bisect_left auf dem Präfix, gefolgt von einem Scan, solange Einträge noch damit beginnen, deckt Autovervollständigung über statischen Daten mit deutlich weniger Speicher ab. Ein Trie lohnt sich bei häufigen Aktualisierungen, Longest-Prefix-Abfragen oder sehr langen gemeinsamen Präfixen.

Stolpersteine

Naive Knoten mit 256 Zeigern kosten jeweils Kilobytes; Speicher, nicht Geschwindigkeit, ist meist das Problem. Beim Löschen müssen nicht-terminale Knoten entfernt werden, die ohne Kinder zurückbleiben. Abweichungen bei der Normalisierung machen Schlüssel unsichtbar. Rekursives Durchlaufen bei langen Schlüsseln stösst an Stack-Grenzen. Tries beantworten keine Infix-, Suffix- oder Fuzzy-Anfragen; dafür braucht es andere Indexstrukturen.