PostgreSQL và từ trò chơi

Question

Trong một trò chơi chữ tương tự như Ruzzle hoặc Letterpress, nơi người sử dụng phải xây dựng từ ra khỏi một tập hợp các chữ cái:

tôi giữ từ điển của tôi trong một bảng SQL đơn giản:

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

Vì thời lượng trò chơi rất ngắn nên tôi không muốn kiểm tra từng từ được nhập bằng cách gọi tập lệnh PHP, từ này sẽ hiển thị trong bảng good_words.

Thay vào đó, tôi muốn tải xuống tất cả các từ có thể bằng một cuộc gọi tập lệnh PHP trước khi bắt đầu vòng - vì tất cả các chữ cái đều được biết.

Câu hỏi của tôi là: nếu có cách SQL đẹp để tìm những từ như vậy?

I.e. Tôi có thể chạy tập lệnh dài hơn một lần để thêm cột vào bảng good_words, có cùng các chữ cái như trong cột word, nhưng được sắp xếp theo thứ tự bảng chữ cái ... Nhưng tôi vẫn không thể nghĩ ra cách phù hợp cho nó thiết lập các chữ cái.

Và thực hiện kết hợp từ bên trong của tập lệnh PHP (so với bên trong cơ sở dữ liệu) có thể mất quá nhiều thời gian (vì băng thông: phải lấy mọi hàng từ cơ sở dữ liệu đến tập lệnh PHP).

Bất kỳ đề xuất hoặc thông tin chi tiết nào?

Sử dụng postgresql-8.4.13 với CentOS Linux 6.3.

UPDATE:

khác ý tưởng tôi có:

1. Tạo một kịch bản liên tục chạy (cronjob hoặc daemon) mà sẽ điền trước một bảng SQL với chữ precompiled bảng và lời nói có thể - nhưng vẫn cảm thấy như lãng phí băng thông và CPU, tôi muốn giải quyết vấn đề này bên trong cơ sở dữ liệu
2. Thêm cột số nguyên a, b, ..., z và bất cứ khi nào tôi lưu trữ word vào good_words, lưu trữ các chữ xuất hiện ở đó. Tôi tự hỏi if it is possible to create an insert trigger in Pl/PgSQL cho điều đó?

Answer 1

Đây có thể là khởi đầu, ngoại trừ việc nó không kiểm tra xem chúng tôi có đủ chữ cái hay không, chỉ khi anh ta có đúng chữ cái.

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:

Truy vấn này chỉ chọn những từ hợp lệ mặc dù nó có vẻ hơi thừa. Nó không hoàn hảo nhưng chắc chắn chứng minh nó có thể được thực hiện.

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 với tất cả khả năng 3+ thư từ (485) cho hình ảnh đó: http://sqlfiddle.com/#!1/2fc66/1 Fiddle với 699 từ trong đó 485 là chính xác: http://sqlfiddle.com/#!1/4f42e/1

Chỉnh sửa 2: Chúng ta có thể sử dụng các toán mảng như để có danh sách các từ chứa các chữ cái chúng tôi muốn:

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

Vì vậy, chúng tôi có thể sử dụng nó để thu hẹp danh sách các từ cần kiểm tra.

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

Chúng ta có thể sử dụng chỉ số GIN để làm việc trên mảng vì vậy chúng tôi có thể có thể tạo ra một bảng mà sẽ lưu trữ các mảng của các chữ cái và làm cho các từ trỏ đến nó (hành động, mèo và khéo léo sẽ tất cả các điểm để mảng [a, c, t]) nên có lẽ điều đó sẽ tăng tốc mọi thứ nhưng điều đó là để thử nghiệm.

Answer 2

Tạo bảng có mục nhập (id, char), là n số ký tự bạn đang truy vấn.

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

OR (cho phù hợp với từng phần)

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

Kết quả của truy vấn đó có tất cả các của word-id phù hợp với các thông số kỹ thuật. Cache kết quả trong một HashSet và đơn giản làm một tra cứu bất cứ khi nào một từ được nhập vào.

Answer 3

Câu hỏi hay, tôi đã bỏ phiếu.

Những gì bạn đang làm là danh sách tất cả các hoán vị có thể có của các chữ cái đã cho của một độ dài nhất định. Như đã trình bày trong PostgreSQL wiki, bạn có thể tạo một hàm và gọi nó như thế này (trận đấu nhấn mạnh chữ trong ảnh chụp màn hình của bạn):

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

Bây giờ, để truy vấn một cái gì đó good_words sử dụng như:

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

Liệu không hoạt động ở 8.4. Có lẽ chỉ 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

Bạn có thể thêm cột có các ký tự sắp xếp được định dạng như '% a% c% t%'. Sau đó, sử dụng truy vấn:

select * from table where 'abcttx' like sorted_letters 

để tìm các từ có thể được tạo từ chữ 'abcttx'. Tôi không biết về hiệu suất, nhưng đơn giản có thể không thể bị đánh bại :)

Answer 6

Đây là truy vấn tìm thấy câu trả lời có thể tìm thấy bằng cách đi bộ qua các trường liền kề.

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) 

(các câu trả lời khác không tính đến điều này).

Liên kết Sql fiddle: http://sqlfiddle.com/#!1/013cc/14 (thông báo Bạn cần một chỉ mục có varchar_pattern_ops để truy vấn nhanh hợp lý).

Answer 7

giải pháp của riêng tôi là để tạo ra an insert trigger, mà viết tần số ký tự vào một cột mảng:

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

Sau đó, tôi tạo ra mảng tương tự cho chuỗi bảng ngẫu nhiên tesereroremasdss và so sánh cả hai mảng bằng cách sử dụng array contains hành @>

Mọi ý tưởng hoặc cải tiến mới luôn được chào đón!