php - 优化我的 MySQL 数据库的方法

Question

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

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

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

// 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 的自动优化功能，但没有提供明显的速度提升。

Answer 1

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

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

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')

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

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

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

例如，如果他们有字母 ABCD 和空白图 block ......

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

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

(在填字游戏和拼图游戏中，没有任何空白方 block )

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

---

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

一种方法是构建一棵树。

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

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

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

下面有分支

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

但那是树遍历算法，根本不同。