Baum Suchalgorithmus

[QFireball]

Hey,

ich muss gerade eine Autovervollständigung Programieren und habe da ein paar fragen zu Bäumen. Momentan hab ich es so das ich ein String Array einfach über die Binäre suche immer nach denn jeweils schon getippten wörtern durchsuche. Das klappt auch gut würde aber nochmal gerne was anderes für mein Program ausprobieren und da wurde mir gesagt das sollte ich mit Bäumen machen leider hab ich davon keine ahnung.
Die aufgabe ist es das ich ein Array habe mit allen oder sehr vielen deutschen Wörtern. Wenn ich Jetzt z.b "Hal" schreibe durchsucht er das Array nach allen einträgen die mit "Hal" anfangen bzw soll er mir ale möglichen volgenden Buchstaben anzeigen. Damit will ich sowas wie im Navi realisieren wo er die Buchstaben speert die garnicht mehr vorkommen können.

Kann ich sowas mit Bäumen realisieren? Muss ich dann für jeden Buchstaben einen Baum anlegen oder wie würde das ablaufen? Oder kann Java anhand des Arrays das selber machen?

[warfley]

Du könntest z.B. einen Baum konstruieren in welchem Pfade die Worte markieren. Jeder Knoten hält einen Boolean, der markiert das hier ein Wort endet, und jeder Knoten hat 26 Nachbarn, die den Buchstaben entsprechen. Ein Wort aus der Wörterliste ist dann die beschriftung des Pfades von der Wurzel zu einem Knoten dessen Markierung gesetzt ist. Knoten sind Blätter wenn es kein Wort gibt was sich aus der Verlängerung ihrer Wörter ergibt. Bei jedem Blatt sollte auch eine Markierung gesetzt sein, um unnütze Verzweigung zu vermeiden.

Um nun alle Worte mit einem entsprechendem Präfix zu finden musst du einfach für jeden Buchstaben des Präfixes den entsprechenden Pfad im Baum runtergehen, und vom letzten Knoten des Präfixes aus kannst du dann eine Breitensuche nach markierten Knoten durchführen.

[algernong]

Das hatte ich vor einiger Zeit beschrieben und implementiert

Hilft dir das?

[QFireball]

Originally Posted by algernong

Das hatte ich vor einiger Zeit beschrieben und implementiert

Hilft dir das?

Mein Problem ist das ich mir denn Baum irgendwie nicht vorstellten kann und dadurch auch nicht wie die suche darin funktioniert. Hab zwar Beispiele gefunden diese wahren aber immer nur mir zahlen daher weiß ich nicht wie ich das auf Buchstaben umsetzen kann da es ja auch Wörter mit doppelten Buchstaben gibt aber ich brauche dann trotzdem nur einen Baum? Gucke mir gleich die ganzen Dateien die du gepostet hast ganz genau an.
Edit: Ok hab es zum laufen gekriegt und geht ja richtig gut das hilft mir schon wirklich sehr danke dafür.
Verstehe halt nur immer noch nicht so ganz wie der Baum wirklich aussieht und Funktioniert vorallem unterscheidet er ja jetzt auch noch groß und klein schreibung.

[Menan]

@

Wenn du den Baum aufgebaut hast, kannst dir ja auch ne Ausgabe Funktion dafür schreiben, die dir den gesamten Baum einmal ausgibt. Gibt bereits fertige Baum Visualisierungsfunktionen im Netz.

Ich denke, dass der Baum sieht in etwa irgendwie so aus (nur ein sehr vereinfachtes Beispiel):



Die noch möglichen Wörter ergeben sich dann immer aus deiner aktuellen Position im Baum und allen Wegen bis zum Ende des Baumes.. Ich hoffe das wird dadurch irgendwie klar

[QFireball]

Originally Posted by Menan

@

Wenn du den Baum aufgebaut hast, kannst dir ja auch ne Ausgabe Funktion dafür schreiben, die dir den gesamten Baum einmal ausgibt. Gibt bereits fertige Baum Visualisierungsfunktionen im Netz.

Ich denke, dass der Baum sieht in etwa irgendwie so aus (nur ein sehr vereinfachtes Beispiel):



Die noch möglichen Wörter ergeben sich dann immer aus deiner aktuellen Position im Baum und allen Wegen bis zum Ende des Baumes.. Ich hoffe das wird dadurch irgendwie klar

Ok so hatte ich mir das auch vorgestellt nur hab ich dann einen
ganz großen Baum der alle wörter enthällt?

[Menan]

Originally Posted by QFireball

Ok so hatte ich mir das auch vorgestellt nur hab ich dann einen
ganz großen Baum der alle wörter enthällt?

Ja, aber du durchsuchst ja nur die entsprechenden Teilbäume und diese werden mit jedem weiteren Buchstaben ja wesentlich kleiner.