Hier ist das Szenario: Bei einem Wort entfernen Sie in jedem Schritt ein einzelnes Zeichen aus einem Wort, sodass das reduzierte Wort immer noch ein Wort im Wörterbuch ist. Fortfahren, bis keine Zeichen mehr übrig sind.
Hier ist der Haken: Sie müssen das richtige Zeichen entfernen, z. in einem Wort kann es zwei mögliche Zeichen geben, die entfernt werden können, und beide können bewirken, dass das reduzierte Wort ein gültiges Wort ist, aber zu einem späteren Zeitpunkt kann man bis zum Ende reduziert werden, d. h. keine Zeichen mehr übrig bleiben, während das andere aufhängt.
Beispiel:
ODER
Siehe meinen Code, ich verwende Rekursion, würde aber gerne wissen, ob es effizientere Lösungen gibt, um das gleiche zu tun.
%Vor%Führen Sie einen BFS-Algorithmus aus. Wenn Sie mehr als ein Zeichen entfernen können, entfernen Sie diese einzeln und fügen Sie eine Prioritätswarteschlange ein. Wenn Sie den Pfad zurückverfolgen möchten, behalten Sie den Zeiger auf das übergeordnete Element (das ursprüngliche Wort, aus dem Sie dieses Wort durch Entfernen eines Zeichens erstellt haben) ) des Wortes im Knoten itslef. Und wenn Sie alle Zeichen entfernen, den Pfad beenden und zurückverfolgen oder wenn es keinen gültigen Weg gibt, haben Sie eine leere Prioritätswarteschlange
Ich habe Porter Stemming in ein paar Projekten verwendet - das wird dir natürlich nur helfen, das Ende zu kürzen das Wort.
Der Porter stemming algorithm (oder 'Porter stemmer') ist ein Prozess für Entfernen der üblichen morphologischen und inflexionalen Enden von Wörtern auf Englisch. Seine Hauptverwendung ist als Teil eines Termnormierungsprozesses Dies geschieht normalerweise beim Einrichten von Information Retrieval Systemen.
Ein Nachdruck fand in M.F. Porter, 1980, Ein Algorithmus für Suffix Stripping, Programm, 14 (3) S. 130-137 .
Martin hat sogar eine Java-Version auf seiner Seite.
Hier gehen Sie. Die Mash-Methode wird eine Lösung (Liste von Wörterbuchwörtern) für jeden gegebenen String finden, wobei ein Dictionary verwendet wird, das an den Konstruktor übergeben wird. Wenn es keine Lösung gibt (die auf ein aus einem Buchstaben bestehendes Wort endet), gibt die Methode null zurück. Wenn Sie sich für alle Teillösungen interessieren (die vor dem Ein-Wort-Wort enden), sollten Sie den Algorithmus ein wenig optimieren.
Es wird angenommen, dass das Wörterbuch eine Menge von Strings in Großbuchstaben ist. Sie können natürlich Ihre eigene Klasse / Schnittstelle verwenden.
%Vor%Beispiel:
%Vor%Hier ist ein Algorithmus, der Tiefensuche zuerst verwendet. Bei einem Wort überprüfen Sie, ob es gültig ist (im Wörterbuch). Wenn es gültig ist, entfernen Sie ein Zeichen aus der Zeichenfolge bei jedem Index und überprüfen Sie rekursiv, ob das Wort "zerhackt" wieder gültig ist. Wenn das gehackte Wort zu irgendeinem Zeitpunkt ungültig ist, befinden Sie sich auf dem falschen Pfad und kehren zum vorherigen Schritt zurück.
%Vor%