SpellCorrector
Um unseren SpellCorrector zu realisieren, bauen wir einen Index auf. Kernbestandteil dieses Index sollen sogenannte Entries sein: Ein Entry (nicht zu verwechseln mit dem Entry der Hash-Tabelle aus Aufgabe 1) besteht aus einem reduzierten Wort (z.B. "sop"), sowie einem zugehörigen Originalwort (z.B. "soup"). Entries sind als interne Klasse im Programmgerüst vordefiniert.
Hinweis: In dieser Aufgabe sind Listen und Hash-Tabellen erlaubt. Verwenden Sie für Hash-Tabellen nicht Ihre eigene Implementierung aus Aufgabe 1, sondern java.util.Hashtable (mit Methoden put() und get()). Die beiden Parameter N und basis können Sie dementsprechend ignorieren. Verwenden Sie für Listen java.util.LinkedList und/oder java.util.ArrayList.
generate()
Implementieren Sie zunächst die Methode generate(). Diese soll - gegeben ein Eingabewort w (z.B. "baby") und eine Zahl maximal zu entfernender Buchstaben K (z.B. 3) - sämtliche möglichen Reduktionen erzeugen, in denen 0 bis K Buchstaben aus w entfernt sind. Zurückgegeben werden soll eine Liste von Entries. Die Reihenfolge der Einträge in der Liste ist egal.
Hinweis: Die Verwendung einfacher String-Operationen wie charAt(), substr(), toCharArray() ist erlaubt. Auch die Verwendung von StringBuilder ist gestattet.
Wie dieser Baum illustriert, erhält man beim Entfernen der Buchstaben einige Duplikate ("by" kommt z.B. gleich viermal im Baum vor). In der Ergebnisliste von generate() sollen diese Duplikate *nicht* mehrfach vorkommen. Nutzen Sie deshalb als interne Datenstruktur für generate() eine Hash-Tabelle und verwandeln Sie diese zur Rückgabe in eine Liste.
add()
Implementieren Sie dann die Methode add(). Diese erzeugt zunächst mit generate() reduzierte Varianten eines Wortes. Zum Beispiel würde für w=soap die Varianten "sap", "sop" usw. erzeugt. Diese reduzierten Varianten werden nun als Schlüssel in eine Hash-Tabelle eingefügt. Aber Achtung: Das gleiche reduzierte Wort (z.B. "sop") kann auf verschiedene Originalworte verweisen (z.B. "soap", "soup", "sophie"). Deshalb verweist jeder Eintrag der Hash-Tabelle auf eine verkettete Liste, mit deren Hilfe wir sämtliche eingefügten Originalworte zum reduzierten Wort finden.
Hinweise: Sie können davon ausgehen, dass add() je Wort nur einmal aufgerufen wird. Unterstützen Sie aber auch den leeren String (w="").
match()
Implementieren Sie zuletzt die Methode match(). Diese erhält einen Query q mit Tippfehler (z.B. q="soop") und liefert die Worte mit kürzester Distanz, die vorher mit add() in den Index eingefügt wurden. Hierzu werden mit generate() reduzierte Versionen von q erzeugt (es werden erneut 0 bis K Buchstaben entfernt). Für jede reduzierte Version q' werden über die obige Hash-Tabelle und verkettete Liste Worte w (z.B. "soap", "soup", "sophie") nachgeschlagen. Die Distanz zwischen q und w entspricht der Distanz zwischen q und q', plus der Distanz zwischen q' und w. Im Beispiel wäre die Distanz zwischen soop und sop = 1, die Distanz zwischen sop und soap = 1, und somit die Distanz zwischen soop und soap = 2.
match() soll das Wort w mit minimaler Distanz zu q zurückgeben. Weil es mehrere solcher Worte geben kann (im Beispiel "soap" und "soup"), ist eine Liste von Strings zurück zu geben. Diese Liste sollte frei von Duplikaten sein, die Reihenfolge ihrer Einträge ist aber egal.
Hinweis: Unterstützen Sie aber auch den leeren String (q="").
package de.hsrm.ads;
import java.util.LinkedList;
import java.util.List;
public class SpellCorrector {
static class Entry {
String reducedWord;
String origWord;
public Entry(String changedWord, String origWord) {
this.reducedWord = changedWord;
this.origWord = origWord;
}
// how many letters have been removed?
public int nchanged() {
return origWord.length() - reducedWord.length();
}
}
// Die Anzahl durchzuführender Reduktionen jedes Wortes
int K;
// Die beiden Parameter N und basis
// können Sie ignorieren.
int N;
int basis;
public SpellCorrector(int K, int N, int basis) {
this.K = K;
}
public void add(String word) {
// FIXME: implement
}
public List<Entry> generate(String word, int K) {
// FIXME: implement
}
public List<String> match(String query) {
// FIXME: implement
}
}
Subato
