mysql - 查找一个表中的字符串是否是另一个列表中字符串的子字符串

Question

我正在分析一个类似拼字游戏的文字游戏，看看是否一 block 放在棋盘上的字母会导致无法放置更多字母，即“锁定”游戏。让我尝试通过 2x2 block 的示例来解释:

我已经构建了一个有效的 2x2 block 列表(大约 5000 个 block )。该列表如下所示:

matrix_2x2

AA,AA
AA,AB
AA,AD
AA,AE
etc...

在棋盘上“AA,AE”看起来像这样(真正的棋盘是 15x15):

[ ][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][A][A][ ][ ][ ]
[ ][ ][ ][A][E][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ]

我还有完整的有效单词列表。看起来像这样

dic_word

AA
AAH
AAHED
AAHING
AAHS
AAL
etc...

我在 MySQL 中有两个列表。

我知道我可以在代码中通过遍历矩阵列表中的每个条目并进行 SELECT 查询来完成此操作。每个矩阵行都是这样的:

SELECT COUNT(word) > 0 FROM dic_word d WHERE (INSTR(word, "AA") OR INSTR(word, "AE") OR INSTR(word, "AA") OR INSTR(word, "AE")) AND (word <> "AA" AND word <> "AB" AND word <> "AA" AND word <> "AB")

我只是想知道这是否可以完全在 MySQL 中完成。

---

更新

上面的 sql 查询确实有效，也不能很好地解释我所追求的。让我试着澄清我在追求什么:

假设 QX 和 QQ 和 XX 都是英文的合法单词，那么 QX,QX 将是我的矩阵列表中的一个条目.

因为 QX 和 QQ 或 XX 都是任何英文单词的子串，那么放在棋盘上的 QX,QX 会“锁定”游戏(即无法放置额外的字母)。

我在寻找这些锁定矩阵后，首先查看所有有效的 2x2 矩阵。就在我们说话的时候，我正在构建所有有效 3x3 block 的列表 - 到目前为止已找到超过 200.000 个。

作为旁注 - 我真的怀疑这种锁矩阵是否存在，但这正是我正在检查的内容。

Answer 1

您现有查询的问题是扫描子字符串效率极低。特别是不能使用索引——因此需要对 dic_word 表进行全面扫描，然后必须单独扫描其中的每个 word 以查找所需的子字符串。

我会创建一个 suffixes 的索引表:

CREATE TABLE suffixes (
  suffix VARCHAR(15) NOT NULL,
  word   VARCHAR(15) NOT NULL,
  PRIMARY KEY (suffix, word),
  FOREIGN KEY (word) REFERENCES dic_word (word)
);

然后可以执行以下非常高效查询:

SELECT 1
FROM   suffixes
WHERE (
       suffix LIKE 'AA%'
    OR suffix LIKE 'AE%'
    OR suffix LIKE 'AA%'
    OR suffix LIKE 'AE%'
      ) AND word NOT IN ('AA','AE','AA','AE')
LIMIT  1

注意:

• LIMIT 子句使 MySQL 在找到单个结果后立即停止搜索；

• 结果集要么包含一条记录以表明存在一个或多个可能的词，要么不包含任何记录以表明没有可能的词；

• 此查询不考虑板上剩余的空间——例如，如果包含子字符串的唯一单词太长以至于超出了板的边缘，但是可以通过添加CHAR_LENGTH(word) 的附加过滤器，如果需要，可以将其保存在另一个索引列中；

• 此优化不会轻易扩展到更复杂的情况，例如有间歇空格和已知字母的地方——例如 'A__DE____J__':虽然可以使用 LIKE 要找到这样的模式，索引不能帮助超出初始已知字符；如果这符合您的要求，可以对数据结构进行进一步修改。

填充和维护suffixes 表

对于本文的其余部分，我使用 ;; 作为我的语句分隔符——必须相应地配置自己的客户端:在 MySQL command-line tool 中, 这可以通过 command 来实现DELIMITER ;;.

一个人可以创建一对 stored procedures协助填充 suffixes 表:

1. 添加给定单词的所有后缀:

   CREATE PROCEDURE FillSuffixes(IN p_word VARCHAR(15)) BEGIN
     DECLARE i TINYINT UNSIGNED DEFAULT 1;
     WHILE i <= CHAR_LENGTH(p_word) DO
       INSERT IGNORE INTO suffixes
         (suffix, word)
       VALUES
         (SUBSTRING(p_word, i), p_word)
       ;
       SET i := i + 1;
     END WHILE;
   END;;
   

2. 添加 dic_word 表中所有单词的所有后缀，这些后缀还没有在 suffixes 表中:

   CREATE PROCEDURE FillAllSuffixes() BEGIN
     DECLARE w VARCHAR(15);
     DECLARE done BOOLEAN DEFAULT FALSE;
   
     DECLARE cur CURSOR FOR
       SELECT word
       FROM   dic_word LEFT JOIN suffixes USING (word)
       WHERE  suffixes.word IS NULL
     ;
     DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = TRUE;
   
     OPEN cur;
   
     read_loop: LOOP
       FETCH cur INTO w;
       IF done THEN
         LEAVE read_loop;
       END IF;
       CALL FillSuffixes(w);
     END LOOP;
   
     CLOSE cur;
   END;;
   

也可以定义triggers根据对 dic_word 表的更改自动维护 suffixes 表:

CREATE TRIGGER add_suffixes AFTER INSERT ON dic_word FOR EACH ROW
CALL FillSuffixes(NEW.word);;

CREATE TRIGGER upd_suffixes AFTER UPDATE ON dic_word FOR EACH ROW
IF NEW.word <> OLD.word THEN
  DELETE FROM suffixes WHERE word = OLD.word;
  CALL FillSuffixes(NEW.word);
END IF;;

CREATE TRIGGER del_suffixes AFTER DELETE ON dic_word FOR EACH ROW
DELETE FROM suffixes WHERE word = OLD.word;;

最后，从现有记录填充表(使用上面创建的过程——注意，可能需要一小段时间才能运行):

CALL FillAllSuffixes;