PostgreSQL und Wortspiele
In einem Wortspiel ähnlich wie Ruzzle oder Letterpress, wo Benutzer Wörter aus einem gegebenen Satz von Buchstaben konstruieren müssen:
Ich halte mein Wörterbuch in einer einfachen SQL-Tabelle:
%Vor% Da die Spieldauer sehr kurz ist, möchte ich nicht jedes eingegebene Wort überprüfen, indem ich ein PHP-Skript aufruft, das dieses Wort in der good_words -Tabelle sehen würde.
Stattdessen möchte ich alle möglichen Wörter vor Beginn der Runde durch einen PHP-Script-Aufruf herunterladen - da alle Buchstaben bekannt sind.
Meine Frage ist: Wenn es eine nette SQLish-Methode gibt, solche Wörter zu finden?
i.e. Ich könnte ein länger dauerndes Skript ausführen, um eine Spalte zu good_words table hinzuzufügen, die die gleichen Buchstaben wie in word columnt hätte, aber alphabetisch sortiert ... Aber ich kann mir immer noch keine passende Methode vorstellen dafür eine Reihe von Buchstaben gegeben.
Und das Word-Matching innerhalb eines PHP-Skripts (vs. innerhalb der Datenbank) würde wahrscheinlich zu lange dauern (wegen Bandbreite: müsste jede Zeile von der Datenbank zum PHP-Skript holen).
Irgendwelche Vorschläge oder Einsichten bitte?
Verwenden von postgresql-8.4.13 mit CentOS Linux 6.3.
UPDATE:
Andere Ideen, die ich habe:
- Erstellen Sie ein ständig laufendes Skript (Cronjob oder Daemon), das eine SQL-Tabelle mit vorkompilierten Buchstaben und möglichen Wörtern vorfüllt - aber immer noch wie eine Verschwendung von Bandbreite und CPU wirkt, würde ich dies lieber in der Datenbank lösen
- Ganzzahlige Spalten hinzufügen
a,b, ...,zund, wenn ich einwordingood_wordsablege, die Buchstabenvorkommen dort speichern. Ich frage mich, wenn es möglich ist, einen Insert-Trigger in Pl / PgSQL zu erstellen dafür?
7 Antworten
Das könnte ein Anfang sein, außer dass es nicht prüft, ob wir genug Buchstaben haben, nur wenn er die richtigen Buchstaben hat.
%Vor%BEARBEITEN:
Diese Abfrage wählt nur die gültigen Wörter aus, obwohl sie etwas überflüssig erscheint. Es ist nicht perfekt, aber es beweist, dass es möglich ist.
%Vor%Fiedel mit allen möglichen 3+ Buchstaben Wörtern (485) für das Bild: Ссылка Geige mit 699 Wörtern, von denen 485 richtig sind: Ссылка
Bearbeiten 2: Wir können Array-Operatoren wie diese verwenden, um eine Liste von Wörtern zu erhalten, die die gewünschten Buchstaben enthalten:
%Vor%Damit können wir die Liste der Wörter eingrenzen, die wir überprüfen müssen.
%Vor%Wir können GIN-Indizes verwenden, um an Arrays zu arbeiten, also könnten wir wahrscheinlich eine Tabelle erstellen, die die Buchstabenfelder speichert und Wörter darauf zeigen lässt (act, cat und tact würden alle auf array [a, c, t] zeigen) ) Also wahrscheinlich würde das die Dinge beschleunigen, aber das ist zum Testen.
Nette Frage, ich habe abgestimmt.
Was Sie vorhaben, ist eine Liste aller möglichen Permutationen der gegebenen Buchstaben einer gegebenen Länge. Wie im PostgreSQL-Wiki beschrieben, können Sie eine Funktion erstellen und sie wie folgt aufrufen (entspricht markierten Buchstaben in Ihrem Screenshot):
%Vor% Nun, um die good_words abzufragen, benutze etwas wie:
Erstellen Sie eine Tabelle mit Einträgen (id, char) und geben Sie die Anzahl der Zeichen an, nach denen Sie suchen.
%Vor%ODER (für Teilvergleich)
%Vor%Das Ergebnis dieser Abfrage enthält alle Wort-IDs, die den Spezifikationen entsprechen. Cache das Ergebnis in einem HashSet und einfach nachschlagen, wenn ein Wort eingegeben wird.
Sie können die Spalte mit sortierten Buchstaben wie '% a% c% t%' hinzufügen. Dann benutze die Abfrage:
%Vor%um Wörter zu finden, die aus den Buchstaben "abcttx" erstellt werden können. Ich weiß nichts über die Leistung, aber Einfachheit kann wahrscheinlich nicht geschlagen werden:)
Hier ist eine Abfrage, die die Antworten findet, die gefunden werden können, indem sie durch angrenzende Felder gehen.
%Vor%(andere Antworten berücksichtigen dies nicht).
Sql fiddle link: Ссылка (Hinweis: Sie benötigen einen Index mit varchar_pattern_ops, damit die Abfrage einigermaßen schnell abläuft) .
Funktioniert nicht in 8.4. Wahrscheinlich nur 9.1+. SQL Fidlle
%Vor%Meine eigene Lösung besteht darin, einen Einfügetrigger zu erstellen, der Buchstabenhäufigkeiten in die Datei schreibt eine Array-Spalte:
%Vor% Dann erzeuge ich ein ähnliches Array für die zufällige Board-Zeichenkette tesereroremasdss
und vergleichen Sie beide Arrays mit dem Array enthält operator @>
Irgendwelche neuen Ideen oder Verbesserungen sind immer willkommen!
Tags und Links postgresql permutation string-matching plpgsql postgresql-8.4