mysql - 从两个 mysql 表中查找字谜

Question

我目前正在尝试实现一种算法来查找看起来像真实姓名的字谜。我有一个可行的解决方案，但需要花费太多时间来处理某些查询，我想知道如何改进它。

我正在尝试根据包含 50k 个名字和 50k 个姓氏的数据库查找由名字和姓氏组成的字谜。数据库的架构如下:

CREATE TABLE `forename` (
  `id` int(11) NOT NULL,
  `q` varchar(32) COLLATE utf8mb4_unicode_ci NOT NULL,
  `label` varchar(255) COLLATE utf8mb4_unicode_ci NOT NULL,
  `labels` varchar(255) COLLATE utf8mb4_unicode_ci NOT NULL,
  `labels_length` int(11) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci;

CREATE TABLE `surname` (
  `id` int(11) NOT NULL,
  `q` varchar(32) COLLATE utf8mb4_unicode_ci NOT NULL,
  `label` varchar(255) COLLATE utf8mb4_unicode_ci NOT NULL,
  `labels` varchar(255) COLLATE utf8mb4_unicode_ci NOT NULL,
  `labels_length` int(11) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci;

ALTER TABLE `forename`
  ADD PRIMARY KEY (`id`),
  ADD KEY `idx_length` (`labels_length`);
ALTER TABLE `forename` ADD FULLTEXT KEY `idx_labels` (`labels`);

ALTER TABLE `surname`
  ADD PRIMARY KEY (`id`),
  ADD KEY `idx_length` (`labels_length`),
  ADD KEY `idx_labels` (`labels`);

每个表中各列的含义如下:

• 标签:名字或姓氏
• labels:标签的slugified版本:所有字符均按大写字母顺序排序；
• labels_length :标签中的字符数；

我目前正在使用 php 中生成的查询来查询此数据库，例如，对于 Ada Lovelace，它看起来像:

select distinct A.label as surname, B.label as forename 
from forename as A, surname as B WHERE (A.labels not like '%B%' and B.labels not like '%B%') AND 
(A.labels not like '%F%' and B.labels not like '%F%') AND 
(A.labels not like '%G%' and B.labels not like '%G%') AND 
(A.labels not like '%H%' and B.labels not like '%H%') AND 
(A.labels not like '%I%' and B.labels not like '%I%') AND 
(A.labels not like '%J%' and B.labels not like '%J%') AND 
(A.labels not like '%K%' and B.labels not like '%K%') AND 
(A.labels not like '%M%' and B.labels not like '%M%') AND 
(A.labels not like '%N%' and B.labels not like '%N%') AND 
(A.labels not like '%P%' and B.labels not like '%P%') AND 
(A.labels not like '%Q%' and B.labels not like '%Q%') AND 
(A.labels not like '%R%' and B.labels not like '%R%') AND 
(A.labels not like '%S%' and B.labels not like '%S%') AND 
(A.labels not like '%T%' and B.labels not like '%T%') AND 
(A.labels not like '%U%' and B.labels not like '%U%') AND 
(A.labels not like '%W%' and B.labels not like '%W%') AND 
(A.labels not like '%X%' and B.labels not like '%X%') AND 
(A.labels not like '%Y%' and B.labels not like '%Y%') AND 
(A.labels not like '%Z%' and B.labels not like '%Z%') AND 
(A.labels like '%A%' or B.labels like '%A%') AND 
(A.labels like '%C%' or B.labels like '%C%') AND 
(A.labels like '%D%' or B.labels like '%D%') AND 
(A.labels like '%E%' or B.labels like '%E%') AND 
(A.labels like '%L%' or B.labels like '%L%') AND 
(A.labels like '%O%' or B.labels like '%O%') AND 
(A.labels like '%V%' or B.labels like '%V%') AND 
(A.labels_length + B.labels_length) = 11

此查询的解释是 Ada Lovelace slug 是 AAACDEELLOV，因此我需要查找包含这些字母且不包含字母表中其他字母的姓氏和名字。我正在添加一个字符数过滤器，以尝试限制返回的行数。

通过此查询，我得到的结果需要使用 PHP 进行处理，以控制每个字符的使用次数是否正确(例如，对于 Ada Lovelace，我的结果包含 3 A)。

我当前的数据库包含大约 50k 个姓氏和 50k 个名字。当我搜索 Ada Lovelace 时，我在大约 0.30 秒内得到了 458 个 SQL 行(如果你想知道的话，可以找到 11 个精确的字谜词)。

如果我更改对 Sylvain Lovelace 的搜索，我会在 10 多秒内获得 1774 行。慢了 30 倍，并且 Ada Lovelace 可接受的持续时间现在超出了范围。我尝试删除字符数过滤器，持续时间减少到 8 秒，仍然太多。

我非常确定应该可以改进数据库的索引，或者构建查询的方式。如果有人有任何想法，我将非常乐意尝试!

如果有人想在真实数据上尝试，转储是 available on a github repository .

Answer 1

几个月后，我遇到了这个问题，现在找到了一种我认为可以接受的方法。解决方案是通过向两个表添加 26 列来更改我的数据模型，每个表包含字母数，每列上都有一个索引。

基于这个数据模型，我能够构建如下查询:

select distinct A.label as surname, B.label as forename 
from forename as A, surname as B 
WHERE 
(A.A >= 1 or B.A >= 1) AND 
(A.B = 0 and B.B = 0) AND 
(A.C = 1 xor B.C = 1) AND 
(A.D = 0 and B.D = 0) AND 
(A.E = 0 and B.E = 0) AND 
/--/
(A.Z = 1 xor B.Z = 1) AND 
(A.labels_length = 4) AND (B.labels_length = 9)

在此示例查询中，我正在搜索姓氏包含 4 个字母的 Aaron Schwartz(字母:AAACHNORRSTWZ)的字谜词。我需要其中至少一个姓氏和名字包含 A 的结果，因为我需要其中 3 个，名字和姓氏都不包含 B，因为我不想要任何 B，并且因为我只想要 C，所以名字 XOR 姓氏可能包含一个。

这个查询不会给我准确的结果，但返回的结果数量足以让我随后用 PHP 处理它们并控制它们是否是真正的字谜。

最终的网站已作为 http://apf.geobib.fr/ 上的概念验证而建立。