Autocomplete mit Tries
Wir alle kennen das Autocomplete-Feature von Suchmaschinen wie Google: Der Nutzer gibt den Beginn einer Anfrage (eines Queries) ein, die Suchmaschine prognostiziert den vollständigen Query. Dahinter steckt eine Datenstruktur, der sogenannte Trie (oder Präfixbaum). In dieser Abgabe werden Sie Ihren eigenen Trie implementieren und ausprobieren.
Abbildung 1: Ein Trie (rechts) mit Trainingsdaten (links).
Abbildung 1 zeigt einen Trie: Gegeben sind Trainingsdaten (links), die Beispiel-Queries mit ihrer jeweiligen Häufigkeit enthalten. Zum Beispiel kommt der Query "trump usa" 30 mal vor und der Query "trump mad" 40 mal. Hieraus wird der Trie aufgebaut: Sämtliche Kanten sind mit Buchstaben gelabelt sowie mit Zählern, die die Häufigkeit des jeweiligen Präfixes angeben. Zum Beispiel kommt das Präfix "tru" insgesamt 120 mal vor (30 x "trump usa", 40 x "trump mad", 30 x "trump", 20 x "trumpet"). Wir erkennen das Ende eines Queries am Sonderzeichen "*".
Mit Hilfe dieses Tries können wir nun Autocompletion betreiben: Gegeben den Beginn (das Präfix) eines Queries wie z.B. "tru", folgen wir zunächst von der Wurzel den Buchstaben des Präfix und landen im Beispiel an Knoten x. Von dort aus folgen wir nun immer der Kante mit der höchsten Zahl, solange bis wir ein Wortende (*) erreichen. Im Beispiel ergibt sich der rote Pfad, als vollständiger Query wird somit "trump mad" vorgeschlagen.
Abbildung 2: In Ihrer Implementierung sollen die Kinder von TrieNodes (links) über interne Suchbäume erreicht werden (rechts).
Bei der Implementierung stellt sich ein Problem: Knoten in Präfixbäumen besitzen nicht nur zwei Kinder sondern viele Kinder (maximal eines für jeden Buchstaben unseres Alphabets). Deshalb fügen wir jedem Knoten n eines Tries (TrieNode) in unserer Implementierung einen eigenen Suchbaum hinzu, über den wir schnell den nächsten Buchstaben finden und hierüber zu n's Kindern (ebenfalls TrieNodes) gelangen. Dies ist in Abbildung 2 (ohne Zähler) dargestellt.
Implementierung
Wir implementieren den Trie in drei Stufen (Sie finden ein Programmgerüst in Subato). Generell gilt wie immer: Sie können gerne weitere sinnvolle Attribute und Methoden hinzufügen.
Stufe 1: SearchTree
Implementieren Sie zunächst die interne Suchbaum-Klasse. Knoten des Baums besitzen (neben zwei Kindern) als Schlüssel einen Buchstaben (char), einen Zähler (siehe Abbildung 1), und einen Verweis auf ihr zugehöriges (TrieNode-)Kind (siehe Abbildung 2). Der Baum bietet folgende Methoden:
void inc(char key, int count): Erhöht den Zähler des Schlüssels um count. Falls der Schlüssel noch nicht vorhanden ist, wird ein neuer Knoten mit Zähler count eingeführt.int getCount(char key): liefert den Zähler des Schlüssels key zurück.TrieNode getNode(char key): liefert das (TrieNode-)Kind für key zurück.
Stufe 2: TrieNode
Implementieren Sie nun die Knoten des Tries. Jeder besitzt einen eigenen Suchbaum (siehe Abbildung 2). Er merkt sich zusätzlich per Referenz sein Kind (TrieNode) mit dem höchsten Zähler. Pflegen Sie diesen Zähler wenn auf dem Suchbaum des Knotens inc() aufgerufen wird. Verwenden Sie ihn später zur Autocompletion im Trie.
void add(char c, int count): fügt den Buchstaben c in den Suchbaum des TrieNodes ein.TrieNode get(char c): liefert den zu c gehörigen TrieNode zurück.
Stufe 3: Trie
Implementieren Sie zuletzt die Trie-Klasse. Die zwei Methoden dieser Klasse sollten soweit möglich die obigen Methoden von TrieNode und SearchTree verwenden.
void add(String s, int count): Fügt einen Trainingsquery zum Trie hinzu (siehe ein Beispiel in Abbildung 3 unten).String predict(String prefix): Sagt für den Präfix eines Queries den vollständigen Queries voraus. Ist ein Präfix nicht im Baum vorhanden, wird null zurückgegeben. Sie können davon ausgehen, dass prefix nicht den Sonderbuchstaben '*' enthält.
Abbildung 3: Der Query "bcd" wird in einen Trie eingefügt. Der Zähler des Präfixes "b" erhöht sich, die Präfixe "bc" und "bcd" werden hinzugefügt.
package de.hsrm.ads;
public class Trie {
static class TrieNode {
public void add(char c, int count) {
// FIXME
}
public TrieNode get(char c) {
// FIXME
}
}
public static class SearchTree {
Node root;
class Node {
Node left;
Node right;
char key;
long count;
}
public SearchTree() {
root = null;
}
public void inc(char key, int count) {
// FIXME
}
public long getCount(char key) {
// FIXME
}
public TrieNode getNode(char key) {
// FIXME
}
}
// Trie-Klasse
TrieNode root;
public Trie() {
root = new TrieNode('*');
}
public void add(String s, int count) {
// FIXME
}
public String predict(String prefix) {
// FIXME
}
public static void eval() {
// FIXME (siehe Aufgabe 2)
}
}
Subato
