Organisatorische Hinweise

Dieses Übungsblatt ist Ihre zweite bewertete Abgabe. Es gelten prinzipiell dieselben organisatorischen Rahmenbedingungen wie bei Aufgabenblatt 07:

• Spätester Abgabetermin ist Sonntag, der 20.06., um 23:59 Uhr.
• Jedes Team lädt seine Abgabe in Subato hoch und schickt vor der Deadline eine Info-Mail an adrian.ulges@hs-rm.de (es reicht im Gegensatz zur ersten Abgabe eine Mail an Prof. Ulges). Mails an andere Adressen (z.B. die/den Praktikumsleiter:in) gelten als nicht abgegeben.
• Wie bei Abgabe 1 enthält diese Mail:
  • die Namen sämtlicher Team-Mitglieder
  • die Praktikumsgruppe in der Sie teilnehmen
  • den Subato-Account, unter dem Ihre Abgabe hochgeladen wurde (es reicht ein Account - schicken Sie uns mehrere werden wir einen zufällig ausgewählten korrigieren).
• Bei Nicht-Einhaltung dieser Formalien behalten wir uns Punktabzüge vor.

Beachten Sie außerdem noch einmal folgende Hinweise:

• Verwenden Sie neben Grundtypen und Arrays nur die jeweils erlaubten Datenstrukturen.
• Behalten Sie prinzipiell die Teams aus der ersten Abgabe bei.
• Auch bezüglich Plagiaten gelten immer noch dieselben Regeln.

Einführung

Ziel dieses Übungsblatts wird es sein, mit Hilfe unserer Datenstrukturen (vor allem: Hash-Tabellen) eine effiziente Spell Correction zu realisieren. Gegeben sei ein Vokabular W, d.h. eine Menge an bekannten Worten, und ein neues Wort, der sogenannte Query q. Im allgemeinen existiert kein zu q identisches Wort in unserem Vokabular, z.B. weil q Tippfehler enthält. Unser Ziel ist es daher, das zu q ähnlichste Wort w aus W zu finden.

"Ähnlichkeit" bedeutet hierbei, dass wir mit möglichst wenig Änderungsoperationen q in w verwandeln können. Eine Änderungsoperation wäre das Entfernen oder Einfügen eines Buchstabens. Im Beispiel oben wäre dementsprechend für q="missippi" das ähnlichste Wort "mississippi", mit drei Änderungsoperationen (dem Einfügen der Buchstaben "ssi").

Offensichtlich ist das Vokabular in der Praxis groß (hunderttausende bekannter Worte). Wir werden deshalb eine Datenstruktur aufbauen, so dass wir nicht sämtliche Wörter des Vokabulars einzeln durchlaufen und ihre Ähnlichkeit prüfen müssen, sondern gezielt das "passende" Wort finden.

Unsere Strategie ist hier abgebildet: Für jedes Wort unseres Vokabulars (z.B. w="tank") erzeugen wir reduzierte Versionen, indem wir null Buchstaben ("tank"), einen Buchstaben ("tan", "tnk", "tak", "ank"), zwei Buchstaben ("ta", "tn", "tk", "an", "ak", "nk") usw. entfernen. Diese reduzierten Versionen fügen wir in einen Index in Form einer Hash-Tabelle ein, und merken uns für jede Version aus welchem Originalwort sie stammt und mit wievielen Änderungen Δ_w man wieder zum Originalwort w gelangt.

Wird nun mit einem neuen Query angefragt (z.B. q="think", rechts), führen wir erneut Reduktionen durch. Für jede reduzierte Version können wir nun in der Hash-Tabelle nachschlagen und erhalten Distanzen zu den Worten des Vokabulars: z.B. können wir mit Δ_q=2 Änderungen aus "think" die reduzierte Version "tnk" erzeugen, und hieraus widerum in Δ_w=1 Änderungen das Wort w="tank". Die Distanz zwischen "think" und "tank" beträgt somit maximal 3. Wiederholen wir dieses "Nachschlagen" für sämtliche Reduktionen von q, finden wir die ähnlichsten Worte, d.h. die mit den wenigsten Änderungsoperationen, in W.