2

我有一个 MySQL 数据库，其中包含标准英文字母表中的所有单词，我用它来创建一个简单的 Scrabble 单词生成器。该数据库分为 26 个表：字母表中的每个字母对应一个表。每个表包含两列：

  • “Word”列：该列是主键，类型为 char(12)，不接受空值。
  • “长度”列：该列包含一个无符号的 tinyint 值并且不接受空值。

在我的应用程序中，用户在文本框中输入任意数量的字母（表示他们的图块），然后我使用以下代码查询数据库：

// this is looped over 26 times, and $char is a letter between 'A' and 'Z'
// check if the user entered in character $char or a blank tile (signified by ? in app)
// this check prevents me from having to query useless tables
if (in_array($char, $lettersArray) || $blanks)
{
    // if so, select all words that have a length that's possible to make
    $query = 'SELECT Word FROM '.$char.'Words WHERE Length <= '.strlen($letters);
    $result = $db->query($query);
    $num_results = $result->num_rows;

    for ($j = 0; $j < $num_results; $j++)
    {
        // determine if it's possible to create word based on letters input
        // if so, perform appropriate code
    }
}

一切正常，但与竞争对手相比，我的应用程序需要很长时间（即理论上的竞争；这更像是我为自己创建的一个学习项目，我怀疑我会在互联网上发布它），尽管事实上应用程序在我的本地计算机上。我尝试使用 phpMyAdmin 的自动优化功能，但这并没有提供明显的速度提升。

4

3 回答 3

3

我不认为性能问题真的是数据库。数据存储的结构将对算法的性能产生最显着的影响。

解决该问题的一种相当容易理解的方法是将问题作为字谜来处理。您可以按字母顺序排列每个单词中的所有字母，并将其存储为带有索引的列。

word      dorw
--------  -------
DALE      ADEL
LEAD      ADEL
LED       DEL
HELLO     EHLLO
HELP      EHLP

然后，给定一组字母，您可以在数据库中查询所有匹配的字谜。只需按字母顺序排列传入的字母集，然后运行查询。

SELECT word FROM dictionary WHERE dorw = 'AERT'

RATE
TARE
TEAR

然后，您可以查询字母的子集：

SELECT word FROM dictionary WHERE dorw IN ('AER','AET','ART','ERT')

这种方法会让你首先返回最长的单词。

这不是最有效的方法，但它是可行的。

处理“空白”图块将需要更多工作，您需要用一个可能的字母代替它，并且可以在一个查询中完成所有 26 种可能性的检查，

例如，如果他们有字母 ABCD 和空白瓷砖......

SELECT word FROM dictionary WHERE dorw IN ('AABCD','ABBCD', 'ABCCD'
 , 'ABCDD', 'ABCDE', 'ABCDE', 'ABCDF', ..., 'ABCDZ')

当您开始处理子集时，这会变得更加痛苦......

（在填字游戏和拼图游戏中，没有任何空白图块）

所以这可能不是最适合拼字游戏的算法。

还有其他算法可能更有效，尤其是在首先返回较短的单词时。

一种方法是构建一棵树。

根节点是一个“零”字母词。作为根节点的子节点，将是所有单字母单词的节点。每个节点都将被标记它是否代表一个有效的单词。作为这些节点的子节点，您将拥有所有可能的三字母词，再次标记为它是否有效。

那将是很多节点。对于长度不超过 12 个字母的单词，可能的总空间为1 + 26 + 26**2 + 26**3 + 26**4 + ...

但是您不需要存储每个可能的节点，您只需存储那些产生有效单词的分支。你不会在下面有分支 ->Z->Z 或 ->X->Q

但是，您将在 ->X->Y->L 下有一个分支，即使 XYL 不是一个词，它也会是通向“XYLOPHONE”的分支的开始

但那是一种树遍历算法，这是根本不同的。

于 2012-07-07T04:55:16.040 回答
2

听起来您需要了解索引。如果在数据库中创建索引，即使所有数据都在一张表中，也不会查询“无用字母”。

不过，您应该提供更多信息，如果从 mysql 控制台运行查询需要多长时间才能返回结果，将结果从数据库移动到 PHP 引擎需要多长时间。例如，您可能会为正在运行的每个查询带回一个 100 兆的结果集，如果是这种情况，请将结果限制为第一个或多个可能的结果。

要查看返回了多少数据，请在控制台中手动运行一个查询，然后查看返回了多少记录。如果数字很大，则将数据传递给 PHP 需要更长的时间，但这也意味着您的代码必须遍历更多的结果。for在找到第一个可以接受的单词后，您可能需要考虑删除我们的循环。如果至少有一个单词是可能的，在放置另一个字母之前不要再次检查它。

于 2012-07-07T04:15:19.703 回答
1

我知道这个问题是关于优化你的数据库，但如果我这样做，我只会从数据库中读取一次单词，初始化一些数据结构并搜索该结构，而不是不断地查询数据库。

抱歉，如果这完全无关紧要。

于 2012-07-07T04:21:14.917 回答