python - postgresql 中拼字游戏的最佳查询

Question

我有一个包含 500 万行的表。想要编写有助于拼字游戏玩家的查询。有8个字母，其中2个可以是通配符。

可能的组合数是 itertools.permutations(letters)，在最坏的情况下是 8!。假设这个词是 ex*ampl*然后我编写查询 SELECT * from words where word like 'exampl_' or name like 'ex_ample'...

但有 8! 或子句，查询速度太慢。有没有更快的方法？

Answer 1

您正在查询单词中但不在手中的字符数小于可用的通配符。

要找到候选词中的额外字符集:

-- characters in the word
SELECT unnest(regexp_split_to_array(word, ''))
-- except those in the hand
EXCEPT ALL
SELECT unnest('{E, X, A, M, P, L}' :: CHAR [])

您可以使用它来选择额外字符集少于可用通配符数量的单词。在你的例子手包含字符 {E, X, A, M, P, L} 和两个通配符，所以查询是:

SELECT word
FROM words
WHERE
  (
    SELECT count(*)
    FROM
      (
        SELECT unnest(regexp_split_to_array(word, ''))
        EXCEPT ALL
        SELECT unnest('{E, X, A, M, P, L}' :: CHAR [])
      ) extra
  ) <= 2
;

这需要表扫描，所以不会很快。加快速度的一种方法是稍微去规范化；存储单词作为字符数组，您将能够利用 GIN 索引并使用 postgres 数组运算符缩小要搜索的词集。

带有索引的 chars 列:

-- Add a chars column to the words table
ALTER TABLE words ADD COLUMN chars CHAR [];

-- Populate it
UPDATE words SET chars = regexp_split_to_array(word, '');
ALTER TABLE words ALTER COLUMN chars SET NOT NULL;

-- A GIN index on the chars column
CREATE INDEX ix_word_chars ON words USING GIN (chars);

-- An index on word length
CREATE INDEX ix_word_length ON words (char_length(word));

您可以使用 postgres @> 数组操作来快速查找单词的字谜:

SELECT word
FROM words
WHERE
  chars @> '{E, X, A, M, P, L, E}' :: CHAR []
  AND
  char_length(word) = 7
  AND
  (
    SELECT count(*)
    FROM
      (
        SELECT unnest(chars)
        EXCEPT ALL
        SELECT unnest('{E, X, A, M, P, L, E}' :: CHAR [])
      ) extra
  ) = 0
;

注意:即使上面的例子中没有通配符，我们仍然需要过滤掉带有extra的单词人物。 @> 运算符只是检查左边的数组是否包含右边数组的所有元素正确的;它不检查基数，因此具有重复字母的词将匹配。

扩展它以查找具有不同输入字符组合的单词需要做更多的工作。注意到一个字长度为七的必须匹配手牌中五个字符的某种组合(加上两个通配符)，我们可以过滤针对这些组合的候选集(由 python 的 itertools.combinations('EXAMPL', 5) 提供帮助):

WITH combinations (combination) AS (
  VALUES
    ('{E, X, A, M, P}' :: CHAR []),
    ('{E, X, A, M, L}' :: CHAR []),
    ('{E, X, A, P, L}' :: CHAR []),
    ('{E, X, M, P, L}' :: CHAR []),
    ('{E, A, M, P, L}' :: CHAR []),
    ('{X, A, M, P, L}' :: CHAR [])
)
SELECT DISTINCT word
FROM words w
  JOIN combinations c ON w.chars @> c.combination
WHERE
  char_length(word) = 7
  AND
  (
    SELECT count(*)
    FROM
      (
        SELECT unnest(chars)
        EXCEPT ALL
        SELECT unnest('{E, X, A, M, P, L}' :: CHAR [])
      ) extra
  ) <= 2;

它可以根据需要扩展以适应更短的单词或更少的通配符。