PostgreSQL e giochi di parole

Question

In un gioco di parole simile a Ruzzle o tipografica, dove gli utenti devono costruire parole di un dato insieme di lettere:

mi tengo il mio dizionario in una semplice tabella SQL:

create table good_words (
     word varchar(16) primary key 
); 

Poiché la durata del gioco è molto breve non voglio controllare ogni parola inserita chiamando uno script PHP, che cercare quella parola nella tabella good_words.

Invece mi piacerebbe scaricare tutte le parole possibili da una chiamata di script PHP prima che inizi il turno - dal momento che tutte le lettere sono conosciute.

La mia domanda è: se c'è un bel modo SQLish per trovare tali parole?

I.e. Potrei eseguire uno script più lungo una volta per aggiungere una colonna alla tabella good_words, che avrebbe le stesse lettere del columnt word, ma in ordine alfabetico ... Ma non riesco ancora a pensare a un modo di eguagliarlo dato un set di lettere.

E fare la corrispondenza di parole all'interno di uno script PHP (rispetto all'interno del database) richiederebbe probabilmente troppo tempo (a causa della larghezza di banda: dovrebbe recuperare ogni riga dal database allo script PHP).

Eventuali suggerimenti o approfondimenti per favore?

Utilizzo di postgresql-8.4.13 con CentOS Linux 6.3.

UPDATE:

altre idee che ho:

1. creare uno script costantemente in esecuzione (cronjob o daemon) che precompilare una tabella SQL con trattamento di pensione lettere precompilate e parole possibili - ma sente ancora come uno spreco di larghezza di banda e CPU, preferirei risolvere questo all'interno del database
2. Aggiungi colonne intero a, b, ..., z e ogni qualvolta memorizzo un word in good_words, memorizzare le occorrenze delle lettere lì. Mi chiedo if it is possible to create an insert trigger in Pl/PgSQL per quello?

Answer 1

Questo potrebbe essere un inizio, tranne che non controlla se abbiamo abbastanza lettere, solo se ha le lettere giuste.

SELECT word from 
(select word,generate_series(0,length(word)) as s from good_words) as q 
WHERE substring(word,s,1) IN ('t','h','e','l','e','t','t','e','r','s') 
GROUP BY word 
HAVING count(*)>=length(word); 

http://sqlfiddle.com/#!1/2e3a2/3

EDIT:

Questa query di selezione solo le parole valide anche se sembra un po 'ridondante. Non è perfetto ma certamente dimostra che si può fare.

WITH words AS 
(SELECT word, substring(word,s,1) as sub from 
(select word,generate_series(1,length(word)) as s from good_words) as q 
WHERE substring(word,s,1) IN ('t','e','s','e','r','e','r','o','r','e','m','a','s','d','s','s')) 

SELECT w.word FROM 
(
SELECT word,words.sub,count(DISTINCT s) as cnt FROM 
(SELECT s, substring(array_to_string(l, ''),s,1) as sub FROM 
(SELECT l, generate_subscripts(l,1) as s FROM 
(SELECT ARRAY['t','e','s','e','r','e','r','o','r','e','m','a','s','d','s','s'] as l) 
as q) 
as q) as let JOIN 
words ON let.sub=words.sub 
GROUP BY words.word,words.sub) as let 
JOIN 
(select word,sub,count(*) as cnt from words 
GROUP BY word, sub) 
as w ON let.word=w.word AND let.sub=w.sub AND let.cnt>=w.cnt 
GROUP BY w.word 
HAVING sum(w.cnt)=length(w.word); 

violino con tutte le possibili 3+ lettere parole (485) per quell'immagine: http://sqlfiddle.com/#!1/2fc66/1 violino con 699 parole di cui 485 sono corrette: http://sqlfiddle.com/#!1/4f42e/1

Edit 2: possiamo utilizzare operatori di matrice come in modo da ottenere un elenco di parole che contengono le lettere che vogliamo:

SELECT word as sub from 
(select word,generate_series(1,length(word)) as s from good_words) as q 
GROUP BY word 
HAVING array_agg(substring(word,s,1)) <@ ARRAY['t','e','s','e','r','e','r','o','r','e','m','a','s','d','s','s']; 

in modo che possiamo usare per ridurre l'elenco delle parole che ci servono per controllare.

WITH words AS 
(SELECT word, substring(word,s,1) as sub from 
(select word,generate_series(1,length(word)) as s from 
(
    SELECT word from 
(select word,generate_series(1,length(word)) as s from good_words) as q 
GROUP BY word 
HAVING array_agg(substring(word,s,1)) <@ ARRAY['t','e','s','e','r','e','r','o','r','e','m','a','s','d','s','s'] 
)as q) as q) 
SELECT DISTINCT w.word FROM 
(
SELECT word,words.sub,count(DISTINCT s) as cnt FROM 
(SELECT s, substring(array_to_string(l, ''),s,1) as sub FROM 
(SELECT l, generate_subscripts(l,1) as s FROM 
(SELECT ARRAY['t','e','s','e','r','e','r','o','r','e','m','a','s','d','s','s'] as l) 
as q) 
as q) as let JOIN 
words ON let.sub=words.sub 
GROUP BY words.word,words.sub) as let 
JOIN 
(select word,sub,count(*) as cnt from words 
GROUP BY word, sub) 
as w ON let.word=w.word AND let.sub=w.sub AND let.cnt>=w.cnt 
GROUP BY w.word 
HAVING sum(w.cnt)=length(w.word) ORDER BY w.word; 

http://sqlfiddle.com/#!1/4f42e/44

Possiamo utilizzare gli indici GIN per lavorare su array in modo probabilmente potremmo creare una tabella che memorizzare le matrici di lettere e fare le parole indicano esso (atto, il gatto e il tatto sarebbe tutto punto per array [a, c, t]), quindi probabilmente ciò velocizzerebbe le cose, ma questo è compito dei test.

Answer 2

Creare una tabella con voci (id, char), essere n il numero di caratteri per cui si sta eseguendo una query.

select id, count(char) AS count from chartable where (char = x or char = y or char = z ...) and count = n group by id; 

OR (per corrispondenza parziale)

select id, count(char) AS count from chartable where (char = x or char = y or char = z ...) group by id order by count; 

Il risultato di tale query ha tutte le word-id che misura le specifiche. Memorizza il risultato in un HashSet e fai una ricerca ogni volta che viene inserita una parola.

Answer 3

Bella domanda, ho svalutato.

Quello che stai facendo è un elenco di tutte le possibili permutazioni delle lettere specificate di una determinata lunghezza. Come descritto nella PostgreSQL wiki, è possibile creare una funzione e chiamare in questo modo (partite evidenziate le lettere nel vostro screenshot):

SELECT * FROM permute('{E,R,O,M}'::text[]); 

Ora, per interrogare la good_words uso qualcosa come:

SELECT gw.word, gw.stamp 
    FROM good_words gw 
    JOIN permute('{E,R,O,M}'::text[]) s(w) ON gw.word=array_to_string(s.w, ''); 

Answer 4

fa non funziona in 8.4. Probabilmente solo 9.1+. SQL Fidlle

select word 
from (
    select unnest(string_to_array(word, null)) c, word from good_words 
    intersect all 
    select unnest(string_to_array('TESTREROREMASDSS', null)) c, word from good_words 
) s 
group by word 
having 
    array_agg(c order by c) = 
    (select array_agg(c order by c) from unnest(string_to_array(word, null)) a(c)) 

Answer 5

È possibile aggiungere la colonna con le lettere sorterd formattati come '% a% c% t%'. Quindi utilizzare la query:

select * from table where 'abcttx' like sorted_letters 

per trovare le parole che possono essere generate dalle lettere "abcttx". Non conosco le prestazioni, ma probabilmente la semplicità non può essere battuta :)

Answer 6

Ecco una query che trova le risposte che possono essere trovate camminando attraverso i campi adiacenti.

with recursive 
input as (select '{{"t","e","s","e"},{"r","e","r","o"},{"r","e","m","a"},{"s","d","s","s"}}'::text[] as inp), 
dxdy as(select * from (values(-1,-1),(-1,0),(-1,1),(0,1),(0,-1),(1,-1),(1,0),(1,1)) as v(dx, dy)), 
start_position as(select * from generate_series(1,4) x, generate_series(1,4) y), 
work as(select x,y,inp[y][x] as word from start_position, input 
union 
select w.x + dx, w.y + dy, w.word || inp[w.y+dy][w.x+dx] 
    from dxdy cross join input cross join work w 
    inner join good_words gw on gw.word like w.word || '%' 
) 
select distinct word from work 
where exists(select * from good_words gw where gw.word = work.word) 

(altre risposte non tenerne conto).

Sql fiddle link: http://sqlfiddle.com/#!1/013cc/14 (avviso È necessario un indice con varchar_pattern_ops affinché la query sia ragionevolmente veloce).

Answer 7

La mia soluzione è quella di creare an insert trigger, che scrive le frequenze lettera in una colonna array:

create table good_words (
     word varchar(16) primary key, 
     letters integer[26] 
); 

create or replace function count_letters() returns trigger as $body$ 
    declare 
     alphabet varchar[]; 
     i integer; 
    begin 

     alphabet := regexp_split_to_array('abcdefghijklmnopqrstuvwxyz', ''); 
     new.word := lower(new.word); 

     for i in 1 .. array_length(alphabet, 1) 
     loop 
       -- raise notice '%: %', i, alphabet[i]; 
       new.letters[i] := length(new.word) - length(replace(new.word, alphabet[i], '')); 
     end loop; 
     return new; 
    end; 
$body$ language plpgsql; 

create trigger count_letters 
    before insert on good_words 
    for each row execute procedure count_letters(); 

Poi ho generare serie simile per la stringa di bordo casuale tesereroremasdss e confrontare due matrici utilizzando l'array contains operatore @>

Tutte le nuove idee o miglioramenti sono sempre benvenuti!