I am currently trying to implement an algorithm to find anagrams that look like real names. I have a solution that is working but takes too much time for some queries and I am wondering how to improve it.
I am trying to find anagrams composed of a forename and a surname, based on a database holding 50k forenames and 50k surnames. The schema of the database is the following :
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`);
In each table the meaning of the columns is as follow:
label
: forename or surenamelabels
: a slugified version of the label : all characters in upper case alphabetically sorted;labels_length
: the number of characters inlabels
;
I am currently querying this database using a query generated in php which, for Ada Lovelace for example, looks like :
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
The explanation of this query is that Ada Lovelace slug is AAACDEELLOV
so I need to find surnames and forenames that contain these letters and that don't contains other letters from the alphabet. I am adding a filter on the number of characters to try to limit the number of rows returned.
With this query I get results that needs to be processed using PHP to control that the number of times each character is used is correct (for example that for Ada Lovelace my result contains 3 A).
My current database contains approximately 50k surnames and 50k forenames. When I search for Ada Lovelace I get 458 SQL rows in ~ 0,30 second (11 exact anagrams found if you wonder).
If I change my search for Sylvain Lovelace, I get 1774 rows in more than 10 seconds. 30 times slower and the duration that was acceptable for Ada Lovelace is now out of range. I have tried to remove the filter on the number of characters, and the duration steps down to 8 seconds, still too much.
I am pretty sure that it should be possible to improve, either the indexes of my database, either the way my query is built. If anyone has any idea, I would be more than happy to try them!
In case someone wants to try it on real data, the dump is available on a github repository.
concat(a.labels, b.labels) = 'AAACDEELLOV'
?a.labels
is "AALO" andb.labels
is "ACDEELV" the concat won't return these two values that interest me because overall they are anagrams of my initial string.