Deutsche Wörter aus beliebigen Buchstabenkombinationen filtern

multimolti

multimolti

Erfahrenes Mitglied
Hallo!

Ich stehe wieder mal vor einem Problem. Gehen wir davon aus, ich habe ein Feld von 4x4 Buchstaben, das z.B. so aussehen kann:
Code: 
N I L O
S D E E
E C E I
S R E O
Jetzt soll mein Programm aus diesem Buchstabenfeld möglichst viele deutsche Wörter herausfinden können, wobei nicht nur gerade oder diagonale Kombinationen möglich sind, sondern kreuz und quer alles, was direkt verbunden ist, wobei jedes Feld nur ein mal verwendet werden darf. Somit kann man aus dem Beispiel etwa diese Wörter bilden:
Lee, Leer, des, leider, Diele, Silo, ...
Ich denke, das Prinzip ist jedem klar. Jetzt zu meinem eigentlichen Problem:

Ich gehe mal davon aus, dass ich eine Wörterdatenbank benötigen werde, ich der die Wörter, die das Programm finden können soll, enthalten sind. Gehen wir davon aus, dass ich eine solche Datenbank besitze, mein Problem ist die verwirklichung der Suche nach sinnvollen Wörtern.

Ich könnte:
  1. Von jedem Buchstaben aus starten und dann JEDE mögliche Kombination durchgehen und nachschauen, ob diese in der Datenbank vorkommt. Das ergäbe, wenn man jetzt mal ganz grob rechnet, 16! Möglichkeiten, also etwa 2*10^13, was extrem viel ist. Wenn man davon ausgeht, dass Wörter kürzer als 3 Buchstaben (außer Ei) und länger als 8 Buchstaben unwahrscheinlich sind, und die Kombinationen von Konsonanten wie "tkb" und sowas ausschließt, ließe sich die Zahl verringern, aber es ist glaube ich trotzdem noch zu rechenaufwändig.
  2. Man könnte jeden Eintrag in der Datenbank durchgehen, zuerst schauen, ob alle benötigten Buchstaben im Feld vorkommen, und wenn ja eine Kombination suchen, ob man die vorhandenen Buchstaben auch zu dem gewünschten Wort kombinieren kann. Das ist schon besser als Vorschlag 1, aber immer noch sehr ineffizient.
  3. Sicherlich gibt es eine bessere Idee als sich so blind durch alle Möglichkeiten durchzutasten, hier frage ich jetzt euch: Fällt euch was Gutes ein? Ich denke, das Ausschlussverfahren von Kombinationen ohne Vokale und mit unmöglichen Konsonanten bringt schon mal etwas, aber sicherlich gibt es noch bessere Vorschläge

Bitte helft mir bei dem Problem! Vielen Dank!
 
multimolti hat gesagt.:
  • Man könnte jeden Eintrag in der Datenbank durchgehen, zuerst schauen, ob alle benötigten Buchstaben im Feld vorkommen, und wenn ja eine Kombination suchen, ob man die vorhandenen Buchstaben auch zu dem gewünschten Wort kombinieren kann. Das ist schon besser als Vorschlag 1, aber immer noch sehr ineffizient.
  • Sicherlich gibt es eine bessere Idee als sich so blind durch alle Möglichkeiten durchzutasten, hier frage ich jetzt euch: Fällt euch was Gutes ein? Ich denke, das Ausschlussverfahren von Kombinationen ohne Vokale und mit unmöglichen Konsonanten bringt schon mal etwas, aber sicherlich gibt es noch bessere Vorschläge
Code: 
N I L O
S D E E
E C E I
S R E O
Zum Vergrößern anklicken....

Die Idee find ich gar nicht schlecht, aber sie müsste simplifiziert werden, indem Du von jeder Position ( also 9 Positionen ) einen Wörterbuchvergleich startest.

Beispiel:
1. Position : N -> Wörterbuch alle N Worte
-> kann man sogar weglassen
2. Position ( I D oder S ) Wörterbuchsuche NI, ND und NS
-> NS erfolgreich 1. Gefundender Begriff, und weiter im Spiel / NS kein Wort also raus / NI mehrere mTreffer also weiter
3. Position : bei I -> L D oder S
-> NIL Treffer
-> NID ( mögliche Treffer ( nida etc.. ) also weiter
-> NIS ( mögliche Treffer ( nisse etc..) also weiter
etc..

ZodiacXP hat es im Beitrag später genannt, aber leider gelöscht, es entsteht eine Baumstruktur, die aber meines Erachtens gar nicht erst aufgebaut (und im zweiten Schritt überprüft) werden muss, sondern man kann quasi gleich bei der Erstellung prüfen, ob es mögliche Treffer gibt.

Das hört sich nach einer rekursiven Funktion an.

mfg chmee
 
Gut, schon mal Danke für die ersten Antworten.

Ich habe mir jetzt eine Liste mit den 10000 häufigsten deutschen Wörtern organisiert (später werde ich eine größere brauchen, aber erst mal ist das OK), und eine Klasse gebastelt, die diese Liste liest und mir recht schnell alle Buchstaben, die mit einem bestimmten String beginnen, zurückgibt (also wenn ich alle mit "nach" haben will, bekomme ich "Nachbar, Nachtisch, Nacht, ...").

Das ist eine ganz gute Grundlage, um die verschiedenen Methoden zu testen, werde mich mal dran machen.
 
Hmm, zum Thema Wortschatz fällt mir ein, dass mein Deutschlehrer damals (in der 8. Klasse) gemeint hat, man solle bis zu dem Zeitpunkt mindestens 20.000 Wörter im Wortschatz haben, 3.000 wäre normal bei Personen, die an den Schwachsinn angrenzen.
Wenn 8. Klasse = 20.000 Wörter, dann kann man von 35.000 bei einem normalen Erwachsenen ausgehen, denke ich.
 
Ja ich bin auch nochmal in mich gegangen, und diese Worte entsprechen - glaube ich - dem Schatz einer gelernten Fremdsprache, nicht der Eigenen. Wie dem auch sei, dann die Pons- oder Langenscheidt-DVD angezapft..

mfg chmee
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück