9

Ruzzle や Letterpress に似た単語ゲームでは、ユーザーは特定の文字セットから単語を作成する必要があります。

ここに画像の説明を入力

単純な SQL テーブルに辞書を保持します。

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

ゲームの所要時間は非常に短いため、PHP スクリプトを呼び出して、入力されたすべての単語をチェックしたくはありません。PHP スクリプトは、その単語をgood_wordsテーブルで検索します。

代わりに、すべての文字がわかっているため、ラウンドが始まる前に 1 回の PHP スクリプト呼び出しで可能なすべての単語をダウンロードしたいと考えています。

私の質問は次のとおりです。そのような単語を見つけるための優れた SQL の方法がある場合は?

つまり、テーブルに列を追加するために、時間がかかるスクリプトを 1 回実行することができgood_wordsます。これは、列と同じ文字wordですが、アルファベット順に並べ替えられます...文字の。

また、PHP スクリプト内 (データベース内) で単語の照合を行うと、おそらく時間がかかりすぎます (帯域幅のため: データベースからすべての行を PHP スクリプトにフェッチする必要があります)。

提案や洞察をお願いします。

CentOS Linux 6.3 で postgresql-8.4.13 を使用します。

アップデート：

私が持っている他のアイデア：

  1. SQLテーブルにプリコンパイルされたレターボードと可能な単語を事前に入力する、常に実行されるスクリプト（cronjobまたはデーモン）を作成します-それでも帯域幅とCPUの無駄のように感じます。データベース内でこれを解決することをお勧めします
  2. 整数列a, b, ...を追加し、 aをzに格納するたびに、そこに文字の出現を格納します。そのためにPl/PgSQLで挿入トリガーを作成することは可能でしょうか?wordgood_words
4

7 に答える 7

4

いい質問です、私は賛成しました。

あなたがやろうとしているのは、与えられた長さの与えられた文字のすべての可能な順列のリストです。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, '');
于 2013-03-05T10:07:26.783 に答える
2

これは、十分な文字があるかどうかをチェックせず、彼が正しい文字を持っている場合にのみチェックすることを除いて、出発点になる可能性があります。

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

編集：

このクエリは、少し冗長に見えますが、有効な単語のみを選択します。完璧ではありませんが、それが可能であることは確かに証明されています。

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

その画像の可能なすべての3文字以上の単語（485）をいじります：http://sqlfiddle.com/#!1/2fc66/1 699の単語をいじって、そのうち485が正しい：http://sqlfiddle.com/# !1/4f42e/1

編集 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 インデックスを使用して配列を操作できるので、おそらく文字の配列を格納するテーブルを作成し、単語がそれを指すようにすることができます (act、cat、および tact はすべて配列 [a,c,t] を指します)。それは物事をスピードアップしますが、それはテスト用です。

于 2013-03-05T09:58:40.057 に答える
1

エントリ（id、char）を含むテーブルを作成します。これは、クエリする文字数です。

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;

そのクエリの結果には、仕様に一致するすべての単語IDが含まれます。結果をHashSetにキャッシュし、単語が入力されるたびに単純にルックアップを実行します。

于 2013-03-05T09:46:29.013 に答える
1

8.4 では機能しません。おそらく9.1+のみ。SQLフィドル

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))
于 2013-03-05T17:52:52.200 に答える
1

これは、隣接するフィールドをたどって見つけることができる答えを見つけるクエリです。

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 リンク: http://sqlfiddle.com/#!1/013cc/14 (クエリを適度に高速にするには、varchar_pattern_ops を使用したインデックスが必要であることに注意してください)。

于 2013-03-05T21:05:45.123 に答える
1

「%a%c%t%」のように書式設定された並べ替え文字で列を追加できます。次に、クエリを使用します。

 select * from table where 'abcttx' like sorted_letters

文字「abcttx」から作成できる単語を検索します。パフォーマンスについてはわかりませんが、シンプルさはおそらく打ち負かすことはできません:)

于 2013-03-05T19:39:36.787 に答える
0

私自身の解決策は、文字の頻度を配列列に書き込む挿入トリガーを作成することです。

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 を使用して両方の配列を比較します@>

新しいアイデアや改善点はいつでも大歓迎です!

于 2013-03-07T15:21:36.483 に答える