Scrabble-Wortfinder mit Platzhaltern

Ich habe ein Problem und es scheint, dass einige vor mir ähnliche Probleme hatten, aber ich konnte keine funktionierende Lösung für mich finden.

Ich baue gerade eine mobile Webanwendung mit C #, MySQL, HTML5 und Javascript. Die Anwendung wird verwendet, um Benutzern zu helfen, mögliche Wörter zu finden, die bei Spielen wie Scrabble zu spielen sind.

Das Problem, das ich habe: Wie bekomme ich die richtigen Wörter aus einer MySQL-database, die ein Wörterbuch enthält, aus der Eingabe von Benutzerbuchstaben?

Weitere Details: – Benutzer können eine beliebige Anzahl von Buchstaben eingeben und auch Platzhalterzeichen (für beliebige Buchstaben) verwenden. – Wenn der Benutzer “TEST” eingibt, darf das Ergebnis keine Wörter mit mehr als 1 E und S und Wörter mit mehr als 2 T enthalten. Ein Ergebnis mit “TESTER” wäre schlecht. – Das Ergebnis darf keine Wörter enthalten, die mehr Buchstaben enthalten als eingegeben.

UPDATE: Scheint, Trie ist die Lösung für mein Problem, wie von Eric Lippert hier vorgeschlagen .
Das Problem ist, dass ich sowohl mit C # als auch mit MySQL ein Anfänger bin. Nachfolgend einige Fragen:

  1. Wie erstelle ich einen Trie aus meinem MySQL-Wörterbuch? (400k + Wörter)
  2. Wie bewahre ich den Trie für einen schnellen und zukünftigen Zugriff auf?
  3. Wie kann ich auf den Trie zugreifen und mit C # Wörter daraus extrahieren?

Vielen Dank für die Hilfe!

Wie bekomme ich die richtigen Wörter aus einer MySQL-database, die ein Wörterbuch enthält, aus der Eingabe von Benutzerbuchstaben?

Du nicht Eine relationale databasetabelle ist keine geeignete Datenstruktur, um dieses Problem so effizient zu lösen, wie Sie es benötigen.

Stattdessen erstellen Sie eine Datenstruktur aus dem Wörterbuch (oder, wenn Sie wirklich buffig sind, erstellen Sie ein Dawg – eine gerichtete azyklische Wortgrafik – was eine Art komprimierter Text ist.)

Sobald Sie einen Trie / Dawg haben, wird es sehr kostengünstig, jedes Wort im Wörterbuch gegen ein bestimmtes Rack zu testen, da Sie ganze große Äste des Wörterbuchs “herausschneiden” können, die das Rack nicht finden kann.

Schauen wir uns ein kleines Beispiel an. Angenommen, Sie haben das Wörterbuch “OP, OPS, OPT, OPTS, POT, POTS, SOP, SOPS, STOP, STOPS”. Daraus erstellen Sie diesen Trie: (Knoten mit einem $ sind diejenigen, die als “Wort können hier enden” gekennzeichnet sind) .

^root^ / | \ OPS | | / \ P$ OOT / \ | | | T$ S$ T$ P$ O | | | | S$ S$ S$ P$ | S$ 

und du hast das Rack “OPS” – was machst du?

Zuerst sagst du “kann ich den O-Zweig hinuntergehen?” Ja, du kannst. Nun ist das Problem “PS” gegen den O-Zweig. Kannst du die P-Filiale hinuntergehen? Ja. Hat es eine Wortende-Markierung? Ja, also ist OP eine Übereinstimmung. Jetzt ist das Problem “S” gegen den OP-Zweig. Kannst du den T-Zweig hinuntergehen? Können Sie den S-Zweig hinuntergehen? Ja. Jetzt haben Sie das leere Rack und müssen es mit dem OPS-Zweig abgleichen. Hat es eine Wortende-Markierung? Ja! Also passt auch OPS zusammen. Kehren Sie jetzt bis zur Wurzel zurück.

Kannst du den P-Zweig hinuntergehen? Ja. Jetzt besteht das Problem darin, das Betriebssystem mit dem P-Zweig abzugleichen. Gehen Sie den PO-Zweig hinunter und passen Sie S an – das schlägt fehl. Zurück zur Wurzel gehen.

Und wieder siehst du, wie das geht. Schließlich gehen wir den SOP-Zweig hinunter und finden ein Wortende auf SOP. “SOP” passt zu diesem Rack. Wir gehen nicht in den ST-Zweig, weil wir kein T haben.

Wir haben jedes mögliche Wort im Wörterbuch ausprobiert und festgestellt, dass OP, OPS und SOP alle zusammenpassen. Wir mussten jedoch nie nach OPTS, POTS, STOP oder STOPS suchen, weil wir kein T hatten.

Sie sehen, wie diese Datenstruktur sie sehr effizient macht? Wenn Sie festgestellt haben, dass Sie nicht die Buchstaben auf dem Gestell haben, um den Anfang eines Wortes zu bilden, müssen Sie keine Wörterbuchwörter untersuchen, die mit diesem Anfang beginnen. Wenn Sie PO, aber kein T haben, müssen Sie POTSHERD oder POTATO oder POTASH oder POTLATCH oder POTABLE nicht untersuchen. all diese teuren und fruchtlosen Suchen gehen sehr schnell weg.

Die Anpassung des Systems an “wilde” Kacheln ist ziemlich unkompliziert. Wenn Sie OPS haben?, dann führen Sie den Suchalgorithmus 26 Mal auf OPSA, OPSB, OPSC aus. Es sollte schnell genug sein, dass es 26 Mal billig ist (oder 26 x 26 Mal, wenn Sie zwei Leerzeichen haben. )

Dies ist der grundlegende Algorithmus, den professionelle Scrabble-KI-Programme verwenden, obwohl sie sich natürlich auch mit der Position des Boards, dem Rack-Management usw. beschäftigen müssen, was die Algorithmen etwas komplizierter macht. Diese einfache Version des Algorithmus ist schnell genug, um alle möglichen Wörter in einem Rack zu generieren.

Vergessen Sie nicht, dass Sie den Trie / Dawg natürlich nur einmal berechnen müssen , wenn sich das Wörterbuch nicht im Laufe der Zeit ändert. Es kann sehr zeitaufwändig sein, den Trie aus dem Wörterbuch zu erstellen, daher sollten Sie es einmal tun und dann herausfinden, wie der Trie auf einem Datenträger in einer Form gespeichert werden kann, die ihn schnell wieder vom Datenträger aufbauen kann.

Sie können die Speichernutzung optimieren, indem Sie eine DAWG aus dem Trie erstellen. Beachten Sie, dass es viele Wiederholungen gibt, da im Englischen viele Wörter gleich enden , genau wie viele Wörter gleich anfangen . Der Trie ist am Anfang eine großartige Aufgabe, Knoten zu teilen, am Ende aber eine miese Aufgabe. Sie können zum Beispiel feststellen, dass das Muster “S $ ohne Kinder” äußerst üblich ist, und den Trie in folgendes verwandeln:

  ^root^ / | \ OPS | | / \ P$ OOT / \ | | | T$ | T$ P$ O | \ | | | \ \| / P$ \ |/ | \ | / \ | / \ | / \| / |/ | S$ 

Einen ganzen Haufen Knoten speichern. Und dann werden Sie vielleicht feststellen, dass zwei Wörter mit OP $ – S $ enden und zwei Wörter mit T $ – S $ enden, sodass Sie es weiter komprimieren können:

  ^root^ / | \ OPS | | / \ P$ O \ T / \| \ | | | \| | | O | T$ | \ | P$ \ | / \| / | / |/ S$ 

Und jetzt haben wir die minimale DAWG für dieses Wörterbuch.

Lesen Sie weiter:

http://dl.acm.org/citation.cfm?id=42420

http://archive.msdn.microsoft.com/dawg1

http://www.gtoal.com/wordgames/scrabble.html

So würde ich das Problem lösen (vorausgesetzt natürlich, Sie haben die Kontrolle über die database und können Tabellen ändern / Tabellen hinzufügen oder sogar die ursprüngliche Last der database steuern).

Meine Lösung würde 2 Tabellen verwenden -> eine Tabelle wäre nur eine Liste aller möglichen Buchstabenkombinationen aus Ihrem Wörterbuch, wobei die Komponentenbuchstaben alphabetisch sortiert sind. (IE TEST wäre ESTT, TESTER wäre ERSTT, DAD wäre ADD).

Die zweite Tabelle hätte jedes Wort und einen Verweis auf den Schlüssel für die erste Tabelle.

Tabelle eins – LetterInWord

 Index Letters 1 ESTT 2 ESTTER 3 EST 4 ADD 5 APST 

In der ersten Tabelle fügen Sie die Wörter Buchstaben in alphabetischer Reihenfolge ein – Test wird estt

Tabelle zwei – Wörter

 Index LetterInWordIndex Word 1 1 TEST 2 2 TESTER 3 3 SET 4 4 ADD 5 4 DAD 6 5 SPAT 7 5 PAST 

In Tabelle 2 fügen Sie das Wort mit der entsprechenden Wort- und Indexreferenz ein.

Dies wird eine Eins-zu-viele-Beziehung sein -> Ein Eintrag in der LetterInWord-Tabelle kann mehrere Einträge in der Words-Tabelle haben

Nicht-Platzhalter suchen: Sagen Sie, dass meine Eingabebuchstaben SETT sind. Sortieren Sie sie alphabetisch.

In der Suche wählen Sie dann alle Buchstaben aus LetterInWord aus, wobei Buchstaben = Wert und verbinden Sie sich mit Tabellenwörtern. Ihre Ausgabe in einer Abfrage ist eine Liste aller Wörter, die nur diese Buchstaben enthalten

Nun zu Platzhaltern: Angenommen, meine Eingabebuchstaben sind EST. * Denken Sie an die Länge – 4 Entfernen Sie die Platzhalter. – Sie erhalten EST (stellen Sie sicher, dass Sie diese alphabetisch sortieren.) Wörter Tabelle

Das würde TEST, REST, SET usw zurückgeben

Ich bin nicht sicher, ob dies die effizienteste Methode ist, aber es funktioniert. Ich habe es in der Vergangenheit verwendet, um Wörter in Wörterbüchern nachzuschlagen, und es bietet eine vernünftige performance bei minimaler Komplexität.

Dies ist sehr schwierig, wenn Sie nur das Wörterbuch haben. Wenn Sie die Möglichkeit haben, eine neue Tabelle oder neue Spalten zu erstellen, würde ich Folgendes tun:

Erstellen Sie eine Tabelle mit einer Spalte für das Wort und 26 Spalten (eine für jeden Buchstaben). Führen Sie einen gespeicherten process für proc / backend aus, der die Vorkommen jedes Buchstabens in einem Wort zählt und in die entsprechende Spalte einfügt.

Dann (ignorieren Sie Platzhalter) können Sie tun

Wählen Sie ein Wort aus dem Wörterbuch aus, bei dem tcount < = 2 und ecount <= 1 und scount <= 1

Für Platzhalter können Sie < = number_of_letters tun

Verwenden Sie eigentlich immer die Längenklausel, da Sie dann zur Verbesserung der performance darauf indexieren können.

Alles andere wird während der Abfrage außergewöhnlich langsam sein