Aufgabe: Reimwörterbuch

Diese Aufgabe hat das Ziel, die grundlegende Datenstruktur für ein Reimwörterbuch zu erstellen. In einem Reimwörterbuch können für ein gegebenes Wort andere Wörter gefunden werden, die sich auf das ursprüngliche Wort reimen. Die Datenstruktur, die in diese Aufgabe erstellt werden wird, soll diese Aufgabe möglichst schnell bewerkstelligen können. Um das Wörterbuch erweitern zu können, sollen Texte nach Wörtern durchsucht und noch nicht im Reimwörterbuch vorhandene Wörter automatisch eingefügt werden können.

Die Datenstruktur, die diese Aufgabe bewältigen kann, ist ein sogenannter Suffix-Baum. In diesem wird jedem Knoten des Baumes ein Buchstabe zugeordnet. Reiht man die Buchstaben ausgehend von der Wurzel bis hin zu einzelnen Blättern oder Knoten aneinander, so erhält man ein Wort, und zwar rückwärts buchstabiert.

Knoten im Baum, die einen Wortanfang markieren, müssen dazu speziell gekennzeichnet werden. Alle Blätter (=Knoten ohne Kinder) sind per Konvention automatisch Wortanfänge. Die Wurzel enthält als einziger Knoten keinen wirklich verwendeten Buchstaben, sondern dient lediglich als „Stopper“.

Zur Vereinfachung werden alle Buchstaben zu Kleinbuchstaben umgewandelt.

Im abgebildeten Baum sind die Wörter „Schein“, „Wein“ und „Schwein“ sowie die Wörter „Maschine“ und „Sabine“ eingetragen. Es ist deutlich zu sehen, dass - beginnt man bei den markierten Knoten und hangelt sich von dort hoch zur Wurzel - alle Wörter im Baum enthalten sind, außerdem ist klar zu erkennen, dass Wörter mit gleicher Endung in gleichen Teilbäumen zu finden sind.

Die Wurzel selbst markiert das Wortende, sie ist mit einem speziellen Buchstaben versehen, der sozusagen als „Stopper“ fungieren kann. Man erkennt auch, dass alle Blätter als Wortanfänge markiert sind. In diesem Beispiel gibt es außerdem einen inneren Knoten, welcher markiert ist. Dieser bezeichnet den Anfang des Wortes „Wein“, welches auch die Endung von „Schwein“ ist. Auch das ist aus dem Baum ersichtlich.

Jeder Knoten hat für jeden Buchstaben maximal ein Kind. Somit ist jeder Knoten im Baum eindeutig durch ein Wort (bzw ein Suffix) identifizierbar.

Das Wort (= die Folge von Buchstaben) was wir erhalten, wenn wir von einem bestimmten Knoten K bis hoch zur Wurzel laufen, nennen wir im Folgenden das Suffix von K. Dabei wird das Symbol des Wurzelknotens weggelassen, das Suffix des Wurzelknotens ist also ein Wort ohne Buchstaben, also das „leere Wort“.

Ausschließlich die Suffixe markierter Knoten ergeben dann „sinnvolle“ Wörter.

Mit Hilfe dieser Datenstruktur lassen sich nun schnell alle Wörter finden, die auf ein bestimmtes Suffix enden: Es sind ganz einfach alle Wörter, die in dem Teilbaum (also allen Kindknoten und deren Kindknoten etc) unterhalb des Knotens existieren, welcher das gegebene Suffix repräsentiert.

Im Beispiel lassen sich so schnell alle Wörter finden, die auf „ein“ enden: Es sind ganz einfach die markierten Knoten, die unterhalb des Knotens sind, dessen Suffix „ein“ ist, also „Wein“, „Schein“ und „Schwein“.

Es soll eine Datenstruktur erstellt werden, die in der Lage ist, einen wie oben beschriebenen Suffix-Baum zu speichern und zu verwalten.

Da die Wahl der Programmiersprache freigestellt sein soll, gibt es keine genaueren Regeln zur Implementation. Es wird aber Folgendes empfohlen:

• Eine Klasse/Struktur SuffixNode. Diese Klasse soll einen Knoten im Baum darstellen. Sie muss dazu folgendes mindestens enthalten:
  1. Einen Zeiger auf den Elternknoten.
  2. Ein „char“, um den Buchstaben, welcher mit dem Knoten assoziiert ist zu speichern.
  3. Eine Datenstruktur (z.B. eine Map, Arrays, Listen) die geeignet ist, um die Zeiger auf die Kindknoten zu speichern. Die Datenstruktur muss neue Zeiger aufnehmen können.
  4. Einen Wahrheitswert (boolean), der aussagt, ob es sich bei dem Knoten um einen Wortanfang handelt oder nicht.

Über Methoden oder Funktionen sollen folgende Operationen durchführbar sein:

• Es soll möglich sein, den Buchstaben eines Knotens geliefert zu bekommen.
• Es soll möglich sein, zu testen, ob ein Knoten Kindknoten besitzt.
• Es soll eine Möglichkeit geben, zu testen, ob der Knoten der Wurzelknoten ist.
• Es soll eine Möglichkeit geben, einen Zeiger auf den Wurzelknoten zurückgeben zu lassen.
• Es soll eine Abfrage durchgeführt werden können, ob es sich bei dem Knoten um einen Wortanfang handelt.
• Es soll das Suffix des Knotens zurückgegeben werden können.
• Es soll die Möglichkeit geben, ein Wort relativ zum Knoten einzufügen. Dabei müssen unter Umständen auch neue Knoten erstellt werden. Ein Rückgabewert von „True“ (bzw Wahr) soll hier andeuten, dass neue Knoten erstellt wurden oder dass ein Knoten, der zuvor keinen Wortanfang markiert hat, nun den Anfang eines Wortes darstellt. Das Wort soll relativ vom gegebenen Knoten eingefügt werden. Nach dieser Operation MUSS es also einen Knoten geben, dessen Suffix aus der Aneinanderreihung des gegebenen Wortes und des Suffixes des aktuellen Knoten besteht.
• Weiterhin soll es möglich sein, einen Knoten (unterhalb des aktuellen Knotens) mit Hilfe eines Wortes (alle Buchstaben vom gesuchten Knoten bis zum aktuellen) zu finden.
• Zu guter Letzt soll die Möglichkeit bestehen eine Liste (oder eine andere passende Datenstruktur) mit allen sinnvollen Wörtern unterhalb des aktuellen Knotens erhalten zu können.

• Eine Klasse/Struktur SuffixTree existieren, welche die folgenden Eigenschaften aufweisen sollte:
  1. Einen Zeiger auf die Wurzel des Baumes.
  2. Einen Wert, der die aktuelle Anzahl gültiger Wörter im Baum angibt.

Außerdem sollen Methoden/Funktionen implementiert werden, die die folgenden Operationen bereitstellen:

• Hinzufügen eines sinnvollen Wortes zum SuffixTree. Ein sinnvolles Wort ist dabei alles, was aus den Buchstaben [a-z], [0-9] und [äöüß] besteht.
• Rückgabe der Anzahl der gültigen Wörter im SuffixTree.
• Rückgabe des Knotens, der für ein bestimmtes Suffix steht.
• Die Möglichkeit, Wörter (im obigen Sinn) aus einem Text zu extrahieren und in den Baum einzufügen.
• Die Möglichkeit, alle Wörter mit einer gegebenen Endung zu finden.

Dazu ist es hilfreich, sich Methoden/Funktionen zu schaffen, die einen String von ungültigen Zeichen befreien (Großbuchstaben zu Kleinbuchstaben, alle Sonderzeichen zu Leerzeichen).

Die Programmiersprache kann (und soll) frei gewählt werden. Wenn ihr auf Probleme stoßt, dann sprecht sie im Forum an, am besten im Brett zu entsprechender Programmiersprache. Wenn ihr die Aufgabenstellung nicht versteht oder ihr einen Fehler gefunden habt bzw Verbesserungsvorschläge/Kritik habt, dann bitte im Forum unter dem Brett „Tutorials“. Bitte gebt immer einen Link auf diese Seite mit an, damit jeder weiß, worum es geht!

Falls ihr euch jetzt von der Aufgabenstellung etwas erschlagen fühlt, dann macht das nichts. Fangt einfach an, und schaut, wie weit ihr kommt. Bei Problemen gibt es ja das Forum :)

Beispiel einer Implementierung:

• In Java von Daniel Oertwig rhymes_java_danieloertwig.tar.bz2

Noch geplant:

• Tipps und Tricks
• Fertige Lösungen in versch. Sprachen
• Schritt f. Schritt Anleitungen mit kurzen Erklärungen der Sprachfeatures (bzw Links auf die entsprechenden Seiten) in versch. Sprachen

Please ;)