PostgreSQL и словесные игры

Question

В словесных играх подобно Ruzzle или Letterpress, где пользователи должны построить слова из заданного набора букв:

я держу мой словарь в виде простой таблицы SQL:

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

Поскольку продолжительность игры очень короткая, я не хочу, чтобы проверить все введенные слова, вызывая PHP скрипт, который будет выглядеть это слово вверх в good_words таблицы.

Вместо этого я хотел бы загрузить все возможные слова одним вызовом PHP-скрипта до начала раунда - так как все буквы известны.

Мой вопрос: если есть хороший язык в SQLish, чтобы найти такие слова?

I.e. Я могу запустить более длинный сценарий один раз, чтобы добавить столбец в таблицу good_words, которая будет иметь те же буквы, что и в столбце word, но отсортирована в алфавитном порядке ... Но я все еще не могу придумать способ сопоставления для него, учитывая набор букв.

И выполнение соответствия слов внутри скрипта PHP (по сравнению с внутренней частью базы данных), вероятно, займет слишком много времени (из-за полосы пропускания: нужно будет извлекать каждую строку из базы данных в PHP-скрипт).

Любые предложения или идеи, пожалуйста?

Использование postgresql-8.4.13 с CentOS Linux 6.3.

UPDATE:

Других идей у ​​меня есть:

1. Создать постоянно работает скрипт (cronjob или демон), который будет автоматически дополняется таблицей SQL с доской скомпилированных букв и возможными словами - но по-прежнему чувствует себя как потеря полосы пропускания и процессора, я бы предпочел решить это в базе данных.
2. Добавить целые столбцы a, b, ..., z и всякий раз, когда я храню word в good_words, храните там письма. Мне интересно, if it is possible to create an insert trigger in Pl/PgSQL?

Answer 1

Это может быть начало, за исключением того, что оно не проверяет, достаточно ли у нас писем, только если у него есть правильные буквы.

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:

Этот запрос выбрать только действительные слова, хотя это кажется немного излишним. Это не идеально, но, безусловно, доказывает, что это можно сделать.

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); 

Fiddle со всеми возможными 3+ букв слов (485) для этого изображения: http://sqlfiddle.com/#!1/2fc66/1 Fiddle с 699 слов, из которых 485 являются правильными: http://sqlfiddle.com/#!1/4f42e/1

Edit 2: Мы можем использовать операторы массива, как так, чтобы получить список слов, которые содержат буквы, которые мы хотим:

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']; 

таким образом, мы можем использовать его, чтобы сузить список слов, которые мы должны проверить.

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

Мы можем использовать индексы Gin для работы с массивами, поэтому мы, вероятно, могли бы создать таблицу, которая будет хранить массивы букв и сделать слова указывают на него (акт, кошка и тактом бы все точки к массиву [a, c, t]), так что, вероятно, это ускорит процесс, но это еще не все.

Answer 2

Создайте таблицу, в которой есть записи (id, char), n количество символов, на которое вы запрашиваете.

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

ИЛИ (для частичного совпадения)

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

В результате этого запроса имеет все слова-идентификаторы, которые соответствуют спецификациям. Загрузите результат в HashSet и попробуйте выполнить поиск каждый раз, когда вводится слово.

Answer 3

Хороший вопрос, я одобрил.

Что вы делаете, это список всех возможных перестановок заданных букв заданной длины. Как описано в PostgreSQL wiki, вы можете создать функцию и вызвать его, как это (матчи выделены буквы в скриншоте):

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

Теперь, чтобы запросить good_words использовать что-то вроде:

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

Does не работают в 8.4. Вероятно, только 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

Вы можете добавить столбец с sorterd буквами, отформатированные как '% на% C% т%'. Затем используйте запрос:

select * from table where 'abcttx' like sorted_letters 

найти слова, которые могут быть созданы из букв «abcttx». Я не знаю о производительности, но простота, вероятно, не может быть избита :)

Answer 6

Вот запрос, который находит ответы, которые можно найти, пройдя через соседние поля.

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) 

(другие ответы не учитывают это).

Sql fiddle link: http://sqlfiddle.com/#!1/013cc/14 (уведомление Вам нужен индекс с varchar_pattern_ops, чтобы запрос был достаточно быстрым).

Answer 7

Мое собственное решение создать an insert trigger, который пишет письмо частоты в столбец массива:

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(); 

Затем я генерировать подобный массив для случайной последовательности борту tesereroremasdss и сравнить оба массива с помощью array contains оператора @>

Любые новые идеи или улучшения всегда приветствуются!