php - 对字谜解算器实现空白平铺搜索的最佳实践

Question

我的网站上目前有一个字谜解算器，运行良好且快速。

我使用数组结构来保存每个单词中使用的每个字母的数值。因此，基本上，当有人输入字母“fghdywkjd”时，我的求解器将遍历其数据库中的每个单词，并将每个单词中的字母数量与与输入的字母相关的值进行匹配。 “fghdywkjd”

我像这样构建数组

$a = array('a' => 1, 'b' => 1, 'c' => 1, 'd' => 1, 'e' => 1, 'f' => 1, 'g' => 1, 'h' => 1, 'i' => 1, 'j' => 1, 'k' => 1, 'l' => 1, 'm' => 1, 'n' => 1, 'o' => 1, 'p' => 1, 'q' => 1, 'r' => 1, 's' => 1, 't' => 1, 'u' => 1, 'v' => 1, 'w' => 1, 'x' => 1, 'y' => 1, 'z' => 1);

它在遍历每个单词时计算值。

我正在尝试想出向其添加空白图 block 功能的最佳方法，并且不会减慢速度。

我能弄清楚如何添加此功能的唯一方法是等到我得到所有结果，然后取出找到的每个单词并添加字母“a”并找到可能性，然后添加后面的“b”等等。对于每个词来说，这将是巨大的。

有什么想法吗？

Answer 1

我可能会这样做。我会像这样设置单词数据库表结构:(这样做的主要原因是速度。我们可以按字母拆分每个查询的名称，但我认为这种方式更快，尽管我没有进行基准测试)。

name    a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
----    -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
test    0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  1  2  0  0  0  0  0  0
tests   0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  2  2  0  0  0  0  0  0
foo     0  0  0  0  0  1  0  0  0  0  0  0  0  0  2  0  0  0  0  0  0  0  0  0  0  0

然后在 PHP 中我会这样做:这假设单词中的字母数量必须与字谜完全匹配(没有额外的字母)。

<?php
$letters = array_fill_keys (range('a', 'z'), 0);

$word = 'set'; // start with the word 'set'
$wordLetters = str_split(preg_replace("/[^a-z]/", '', strtolower($word))); // remove invalid letters, lowercase, and convert to array

$numberOfWildcards = 1; // Change this to the number of wildcards you want

foreach ($wordLetters as $letter) {
    $letters[$letter]++;
}

$query = 'SELECT `name`, 0';

foreach ($letters as $letter => $num) {
    // $query .= "+ABS(`$letter`-$num)";
    $query .= "+IF(`$letter` > $num, `$letter` - $num, 0)";
}

$query = ' AS difference
    FROM `word_table`
    WHERE 
        LENGTH(`name`) = ' . (strlen($word) + $numberOfWildcards) . '
    HAVING
        difference = ' . $numberOfWildcards;

如果您想查看正在检查的单词与数据库中的所有单词之间的差异，请去掉 where 和having 子句。

让我知道这对您来说效果如何。