php - 如何从字符数组中找到字符串匹配项？前任。给定 a,n,t 在单词列表中查找字符串匹配 ant, an, tan

Question

到目前为止，我的数据库中有 27 个表。一张单词表(拼字游戏单词列表)和 26 个关联表。

Table  Fields
================
word   [id,word]
a      [word_id,count]
b      [word_id,count]
...
z      [word_id,count]

我正在尝试找出给定字符串的匹配单词。

例如，如果给定数组是 a,n,t 我想知道:ant, tan, at, ta, an, na。

我当前的策略是分解字符串中的每个字母并找到与所有字母匹配的关联单词。

例如:

SELECT word.word
FROM word, a, n, t
WHERE
    word.id = a.word_id OR
    word.id = n.word_id OR
    word.id = t.word_id

但这最终会打印所有包含 a,n 或 t 的单词。

如果我将所有运算符切换为 AND，我就只能匹配一个:ant。

你能帮我解答这个谜语吗？

我还关心如何处理字符串中的重复字母。我认为字母关联表中的 count 字段可以在这里提供帮助。如果单词是 app，则 p 关联表中的计数将为 2。

我的关联表是否走在正确的轨道上，或者有更好的方法吗？

我正在尝试在 php/mysql 中相当有效地处理这个问题。我知道其他人之前已经用 C、perl、java 等解决了这个难题。

Answer 1

如果您想要标准化的方法，那就是:

wordLetters{
  INT wordID,
  CHAR[1] letter,
  INT count,
  PK(wordID, letter)
}

words{
  INT wordID PK,
  VARCHAR(255) word UNIQUE
}

但是这种方法在性能方面有一个严重的问题——即它需要对单词表进行全表扫描。我假设没有太多字母并建议采用这种方法:

words{
  INT wordID PK,
  VARCHAR(255) word UNIQUE,
  INT cA KEY,
  INT cB KEY,
  ...
  INT cZ KEY,
  KEY (cE, cT, cA, cO, cI, cN),
  ...
}

查找查询会很长，但它会有效地使用索引，并且无论如何它都是由 PHP 代码生成的:

如果用户有[a,n,t]，则获取可用单词:

SELECT word FROM words WHERE
   cA <= 1 AND cB = 0 AND cC = 0 AND ... AND cY = 0 AND cZ = 0

此查询(可能)将使用“ETAOIN”索引，因为不需要“E”的单词并不存在。

此时，性能取决于仅可用于数据库的索引的选择，并且您始终可以添加更多认为有用的索引(即使在运行时)。

<小时/>

关于数据库索引:

普通索引只是一个排序的项目列表，并在该列表上构建适当的树，从而实现高效的范围查找(获取从 x 到 y 的所有元素)。

普通索引由其排序顺序定义。排序顺序是:首先按某列排序，然后按另一列排序，然后再按另一列排序......

例如，[E,T,A,O,I,N] 索引将对所有单词进行排序:首先是不需要 E 的所有单词>，然后是所有需要一个 E 的单词，然后是所有需要两个 E 的单词...。需要相同数量 E 的单词将被排序:首先是所有不需要 T 的单词，然后是所有需要一次的单词，然后是所有单词需要两个 T ... 。在需要相同数量 E 和 T 的单词中，那些不需要 A 的单词排在前面。

如果要求数据库获取所有不需要 E 或 T 且最多一个“X”的单词，它可以使用此索引来满足前两个要求，然后检查 E=0, T=0 范围内的所有单词。

特定的选择ETAOIN基于短语ETAOIN SHRDLU它按频率对英语中 12 个最常见的字母进行排序 - 这意味着如果使用此索引，它应该过滤掉尽可能多的单词。

您使用示例RSTLNE。当玩家没有 R 或 S 时，将/可能会使用此索引。对查找进行基准测试可能会告诉您使用每个特定索引节省了多少时间。

您可以使用EXPLAIN EXTENDED查询以查看哪些索引被考虑并随后用于每个特定查询以及预计将过滤掉多少行。例如:

EXPLAIN EXTENDED
  SELECT word FROM words
  WHERE cA=0 AND cB<=1 AND cC=0 AND ...