1

我正在分析一个类似拼字游戏的文字游戏，以找出放置在板上的一块字母是否会使无法放置更多字母，即“锁定”游戏。让我尝试通过 2x2 块的示例来解释：

我已经建立了一个有效的 2x2 块列表（大约 5000 个块）。该列表如下所示：

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 查询确实有效，也不能很好地解释我所追求的。让我试着澄清一下我所追求的：

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

既然不是QX任何英文单词QQ的XX子串，那么放置在棋盘上的 QX,QX 将“锁定”游戏（即无法放置额外的字母）。

我关注这些锁定矩阵，并从查看所有有效的 2x2 矩阵开始。正如我们所说，我正在构建所有有效 3x3 块的列表 - 到目前为止已发现超过 200.000 个。

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

4

2 回答 2

1

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

相反，我会创建一个后缀索引表：

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 命令行工具中，这可以通过命令 DELIMITER ;;来实现。

可以创建几个存储过程来帮助填充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;;

还可以定义触发器suffixes以根据表的更改自动维护dic_word表：

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

最后，从现有记录中填充表（使用上面创建的过程 - NB，可能需要一段时间才能运行）：

CALL FillAllSuffixes;
于 2012-12-05T12:43:23.037 回答
0

到目前为止，这是我的解决方案。

它将遍历所有 2x2 字母（矩阵）块并计算可以放置多少个单词。然后将结果插入到表 lock2 中。如果一个矩阵的计数为 0，那么我们就有一个锁定的游戏情况。

它正在工作，但速度非常慢。2x2 列表的性能是可以接受的，但 3x3 列表在我的一生中不会结束——而且我只有 41 岁，并且拥有一台速度相当快的计算机。

非常欢迎提出提高性能的建议。

DELIMITER $$

DROP PROCEDURE IF EXISTS `wsolver`.`analyse2_2` $$
CREATE PROCEDURE analyse2_2()
BEGIN
  DECLARE done INT DEFAULT FALSE;
  DECLARE a INT;
  DECLARE b VARCHAR(45);

  DECLARE cur1 CURSOR FOR SELECT Matrix FROM matrix2x2;
  DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = TRUE;

  OPEN cur1;

  read_loop: LOOP
    FETCH cur1 INTO a;

    IF done THEN
      LEAVE read_loop;
    END IF;


      SET @w1 = SUBSTRING(a, 1, 2);
      SET @w2 = SUBSTRING(a, 4, 2);
      SET @w3 = CONCAT(SUBSTRING(@w1, 1, 1), SUBSTRING(@w2, 1, 1));
      SET @w4 = CONCAT(SUBSTRING(@w1, 2, 1), SUBSTRING(@w2, 2, 1));


      SELECT COUNT(*) INTO @w5 FROM dan WHERE (instr(dic_word, @w1) OR instr(dic_word, @w2) OR instr(dic_word, @w3) OR instr(dic_word, @w4)) AND (dic_word NOT IN(@w1,@w2,@w3,@w4));

      INSERT INTO `lock2` (matrix, `count`) VALUES (a, @w5);


  END LOOP;

  CLOSE cur1;

END $$

DELIMITER ;
于 2012-12-05T15:47:54.623 回答