PostgreSQL和文字游戏

Question

在类似于Ruzzle或Letterpress的文字游戏中,用户必须使用给定的一组字母构造单词:

我将字典保存在一个简单的SQL表中:

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

由于游戏持续时间非常短,我不想通过调用PHP脚本来检查每个输入的单词,这将在good_words表格中查找该单词.

相反,我希望在回合开始前通过一个PHP脚本调用下载所有可能的单词 - 因为所有字母都是已知的.

我的问题是:如果有一个很好的SQLish方法来找到这样的单词？

即我可以运行一个较长的脚本一次向good_words表添加一个列,它将具有与wordcolumnt 相同的字母,但按字母顺序排序...但我仍然想不出一种方法来匹配它给定一个集合的字母.

在PHP脚本内部(与数据库内部)进行单词匹配可能需要很长时间(因为带宽:必须从数据库中获取每一行到PHP脚本).

有什么建议或见解吗？

在CentOS Linux 6.3中使用postgresql-8.4.13.

更新:

我有其他想法:

1. 创建一个不断运行的脚本(cronjob或daemon),它可以预填充一个带有预编译字母板和可能单词的SQL表 - 但仍然感觉浪费带宽和CPU,我宁愿在数据库中解决这个问题
2. 添加整数列a,b......,z每当我存储word到good_words,存储字母出现次数在那里.我想知道是否可以在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

编辑：

该查询仅选择有效的单词，尽管看起来有点多余。它并不完美，但确实证明了它是可以做到的。

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]），所以可能这会加快速度，但这需要测试。