SpellCorrector II

SpellCorrector: Theorie

Gegeben sei ein Query-Wort q mit 12 Buchstaben, und ein SpellCorrector in den mit add() 100.000 Worte unbekannter Länge aus einer unbekannten Alien-Sprache eingefügt wurden. Der SpellCorrector besitze den Parameter K=1. Das Alphabet der Alien-Sprache umfasse 52 Buchstaben.

Schätzen Sie ab wieviele Schritte im Worst Case nötig sind um mit match() die ähnlichsten Worte zu q zu finden. Als ein "Schritt" zählt hierbei der Besuch eines Elements in den verketteten Listen des Index (vgl. die Abbildung zu add() in Aufgabe 10.2: Das Durchlaufen der Liste mit "soap", "sophie" und "soup" entspräche drei Schritten).

  1. Überlegen Sie zunächst, wieviele reduzierte Versionen q' von q existieren.
  2. Schätzen Sie die maximale Listenlänge für das "schlimmste" q' ab und geben Sie diese Länge an.
  3. Berechnen Sie hieraus ein Gesamtergebnis.

Begründen Sie Ihre Antwort ausführlich.

SpellCorrector: Test

Testen Sie zuletzt Ihre Klasse SpellCorrector in einem realistischen Szenario. Sie finden in Stud.IP die Datei corncob_lowercase.txt. Diese enthält 58110 Englische Wörter, in jeder Zeile eines. Lesen Sie die Datei ein (erlaubt sind hierfür beliebige Methoden aus java.io). Erstellen Sie einen SpellCorrector mit K=2, und fügen Sie jedes Wort aus der Datei mit add() in den SpellCorrector ein.

Finden Sie dann mit der Methode match() des SpellCorrectors die ähnlichsten Worte für folgende Queries:

Notieren Sie für jeden Query das Ergebnis, und geben Sie die Daten ab.