Wörterbuch - String Teilmengen vergleich (Scrabble Algorithmus)

[#basTi]

Hallo zusammen,

ich habe 2 Probleme:

1. Ich suche ein Wörterbuch in Englisch & evtl auch Deutsch (gemeint ist keine Übersetzung sondern lediglich eine Auflistung der in der Sprache vorhandenen Wörter)
2. Einen Algorithmus, um Strings aus diesem Wörterbuch auf Teilmengen zu vergleichen

zu 1.) Am besten wäre natürlich eine kostenlose Variante. Dazu sei gesagt, dass ich das ganze für ein kommerzielles Projekt brauche.

zu 2.) Gemeint ist, ob ich aus einem Wort ein anderes bilden kann (ähnlich wie bei Scrabble).

Beispiel:
Hat "xyz" die Teilmenge "ab" ? - Nein
Hat "xyz" die Teilmenge "zx" ? - Ja
Hat "Stop" die Teilmenge "Post" ? - Ja

Ich denke, dass es so etwas bestimmt schon gibt aber ich habe bisher noch nichts gefunden.

 

[r0b0t]

Hallo, zu 1)

Wikipedia ist schon mal eine gute Ausgangsbasis:

[url]http://de.wikipedia.org/wiki/Liste_der_h%C3%A4ufigsten_W%C3%B6rter_der_deutschen_Sprache[/url]

Du kannst dir die Dumps der englischen und/oder deutschen Wiktionaries herunterladen. Die Lizenzbedingungen musst du selbst prüfen.

[url]http://de.wiktionary.org/wiki/Wiktionary:Download[/url]

zu 2) Weiß nicht, ob's da was schnelleres gibt, aber sonst alle Permutationen der Buchstaben eines Wortes in der Liste der Wörter suchen. Dies für alle "Teilmengen" des Wortes wiederholen. Mathematisch ist "Menge" ja nicht ganz korrekt, da ja Elemente (Buchstaben) mehrfach vorkommen dürfen. Das kann man sicherlich noch optimieren.

 

[#basTi]

Schonmal danke für die Links! Helfen auf jeden Fall schon einmal

Zu 2) Also im Moment hätte ich sowas im Kopf wie:

Nehme Wort#1 und zähle alle Buchstaben. Speichere diese Liste ( A:2, B:0, C:1, ... )
Nehme Wort#2 und zähle alle Buchstaben -> Liste. Vergleiche jedes Element dieser Liste mit derer von Wort#1 auf kleiner/gleich. Stimmt das für alle Elemente, hat man eine Lösung.

Ich glaube das ist von der Performance schon einmal nicht schlecht. Aber für weitere Anregungen bin ich immer offen

 

[DjNDB]

Zum abgleichen fällt mir spontan folgendes ein:
- Kopie des Buchstabenvorrats in einer Map ablegen (Buchstabe als Schlüssel, Anzahl als Wert)
- Jeden Buchstaben des zu prüfenden Wortes aus der Map abgleichen (Schnell möglich, je nach Implementierung idealerweise O(1)). Wenn von einem Buchstaben 0 in der Map sind ist das Wort nicht bildbar. Ansonsten Anzahl des jeweiligen Buchstaben reduzieren

Dadurch sollte das abgleichen recht schnell laufen. Die Map kann schon im Vorfeld gepflegt werden und beim abgleichen wird eine Kopie verwendet. Durch das abgleichen der einzelnen Buchstaben wird die Suche so früh wie möglich beendet.

Wenn es am Ende wirklich ein Scrabble Spiel wird, dann spielt die Performance allerdings eine geringere Rolle. Die Länge der Wörter ist dann ja eher gering, und das ganze wird durch den Menschen ausgebremst der jedes einzelne Wort erstmal eingeben muss.

 

[#basTi]

Dein Vorschlag geht ja auch in meine Richtung ... hätte es wahrscheinlich auch mit einer Map realisiert.

Ich weiss noch nicht, ob ich es für das Spiel on-the-fly berechnen lasse. Eine Methode wäre auch alles vorberechnen zu lassen und zu speichern (worauf es wahrscheinlich hinaus läuft)

Weitere Quellen für Wörterbücher wären noch super

 

[DjNDB]

Ich weiss noch nicht, ob ich es für das Spiel on-the-fly berechnen lasse. Eine Methode wäre auch alles vorberechnen zu lassen und zu speichern (worauf es wahrscheinlich hinaus läuft)

Was willst du denn da vorberechnen? Für die aktuelle Buchstabenkombination jedes mögliche Wort? Das wäre weitaus aufwendiger als nur das Nötige zu prüfen (ob das aktuelle Wort gültig ist und alle Buchstaben dafür verfügbar).

Für deutsch nutze ich derzeit dieses Wörterbuch in Firefox. Falls GPL für das Projekt in Frage kommt.

 

[#basTi]

Also ich beschreib mal n bisl genauer wies aussehn wird, damit wir net aneinander vorbei reden

Es wird ein Multiplayer Spiel, bei dem jeder Mitspieler dieselben Buchstaben bekommt.
Ich habe es mir bisher so gedacht, dass der Server die Buchstaben, samt aller Lösungen zu den Clients schickt.
Somit kann ich die komplette Liste der Wörter und die Berechnung auf den Server auslagern.

Und vorberechnen deswegen, weil der Server dann auch nicht mehr rechnen müsste sondern nur sagt: "Schicke Wortpacket#3" (oder "Verwende Wortpacket#3" falls ich die fertige liste doch auf dem Client speicher).

Zudem hät ich auch mehr Kontrolle ... ich kann die Listen vorher sichten.
Aber ich bin noch ganz am Anfang von dem Projekt deswegen höre ich mir gern alle Meinungen an.

 

[DjNDB]

Das klingt für mich so, als könnte das als Spiel gegeneinander gedacht sein. Dann wäre es Cheatern natürlich sehr leicht gemacht, wenn du die Lösungen an den Client übertragen würdest.


Falls es sehr viele Mitspieler gleichzeitig werden sollen, wäre mal ein kleiner Benchmark interessant, um zu ermitteln wie viele Wörter durchschnittlicher Länge pro Sekunde geprüft werden können.
Erst wenn diese Anzahl nicht ausreicht um alle Spieler in angemessener Zeit zu bedienen könnte vorberechnen sinnvoll sein. Schließlich hat man dadurch für jede Runde den maximalen Rechenaufwand. Alternativ könnte man natürlich auch enorm viel Speicherplatz aufwenden und für jeden erdenklichen Buchstabenvorrat bis zur maximalen Wortlänge alle Lösungen abspeichern.

Ich denke aber es ist wahrscheinlich wesentlich einfacher für 10000 einzelne Anfragen zu prüfen ob das Wort gültig ist, als für das komplette Wörterbuch. Zum vorberechnen lassen sich zwar sicher auch Algorithmen finden, damit nicht jedes Wort geprüft werden muss, aber ob sich er der Aufwand lohnt steht auf einem anderen Blatt.


Ist für die Prüfung wirklich nur ein Buchstabenvorrat mit beliebiger Reihenfolge relevant, oder kommt wie bei Scrabble dazu, dass einzelne Buchstaben an bestimmten Positionen vorgegeben sind?

 

[#basTi]

Reihenfolge spielt keine rolle.

Also der Server muss auf jeden Fall die Buchstaben auswählen und diese an alle Clients schicken.
Auswahl geschieht über ein existierendes Wort der Länge X, damit man definitiv aus allen Buchstaben ein Wort konstruieren kann.

Nun muss aber auch noch geprüft werden, ob es zu diesen Buchstaben genügend Wörter gibt (sollten schon so im Bereich von 30 sein) und diese sollten auch alle gut gestreut von der Länge sein ( 10 Wörter mit 3 Buchstaben, 10 mit 4 Buchstaben , etc ).
Weil diese Prüfung sowieso stattfinden muss (damit kein Buchstabensalat geschickt wird zu dem es nur 2 Lösungen gibt), dachte ich es wäre auch klug diese vorhandenen Lösungen direkt mit an die Clients zu schicken.
Nachteil hierbei wäre der Mehraufwand an Datenvolumen das verschickt werden muss - und zwar an alle Spieler.

Durch diesen Gedankengang kannst du evtl auch meine Idee zur Vorberechnung nachvollziehen.

Falls ich die Lösungen nicht mitschicke geht es mit dieser Frage weiter:
Wird der Client selber die Lösungen seines Spielers prüfen oder werden diese an den Server übergeben
( Vorteil: Client hat keinen Prüfcode und kein Wörterbuch intern. Server kennt die Lösungen schon und muss also nur abgleichen; Nachteil: Jede Eingabe muss an den Server zur Prüfung geschickt werden )



Cheaten ist wieder ein neues Thema, bei dem ich aber keine große Sorgen hab, dass jmd den Netzverkehr abhört um dies dann einzugeben ... Verschlüsselung gibts ja auch noch.

// Weitere Wörterbücher evtl auch ohne GPL sind immer erwünscht