Как заставить мое слово unscrambler возвращать более релевантные результаты
Я создаю слово unscrambler (php/mysql), которое принимает пользовательский ввод от 2 до 8 букв и возвращает слова от 2 до 8 букв, которые могут быть сделаны из этих букв, не обязательно используя все буквы, но определенно не включая больше букв, чем указано.
Пользователь вводит что-то вроде MSIKE или MSIKEI (два i) или любую комбинацию букв или нескольких вхождений буквы.
В нижеприведенном запросе будут найдены все вхождения слов, содержащих M, S, I, K или E.
Однако в приведенном ниже запросе также возвращаются слова, которые имеют несколько вхождений писем, которые не запрашиваются. Например, слово meek будет возвращено, хотя оно имеет два e, и пользователь не вводил два e или поцелуй слова, даже если пользователь не вводил s дважды.
SELECT word
FROM words
WHERE word REGEXP '[msike]'
AND has_a=0
AND has_b=0
AND has_c=0
AND has_d=0
(we skip e) or we could add has_e=1
AND has_f=0
...and so on...skipping letters m, s, i, k, and e
AND has_w=0
AND has_x=0
AND has_y=0
AND has_z=0
Обратите внимание, что столбцы has_a, has_b и т.д. равны 1, если буква имеет слово в слове или 0, если нет.
Я открыт для любых изменений в схеме таблиц.
Этот сайт: http://grecni.com/texttwist.php - хороший пример того, что я пытаюсь подражать.
Вопрос заключается в том, как изменить запрос, чтобы не возвращать слова с несколькими вхождениями буквы, если только пользователь не ввел букву несколько раз. Группировка по длине слова будет дополнительным бонусом.
Большое спасибо.
EDIT: я изменил db по предложению @awei, has_ {letter} теперь count_ {letter} и сохраняет общее количество вхождений соответствующей буквы в соответствующее слово. Это может быть полезно, когда пользователь вводит письмо несколько раз. Например: пользователь вводит MSIKES (два с).
Кроме того, я отказался от подхода REGEXP, как показано в исходной инструкции SQL. Работая над большей частью работы со стороны PHP, но многие препятствия все еще на пути.
EDIT: Включено первые 10 строк из таблицы
id word alpha otcwl ospd csw sowpods dictionary enable vowels consonants start_with end_with end_with_ing end_with_ly end_with_xy count_a count_b count_c count_d count_e count_f count_g count_h count_i count_j count_k count_l count_m count_n count_o count_p count_q count_r count_s count_t count_u count_v count_w count_x count_y count_z q_no_u letter_count scrabble_points wwf_points status date_added
1 aa aa 1 0 0 1 1 1 aa a a 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 1 2015-11-12 05:39:45
2 aah aah 1 0 0 1 0 1 aa h a h 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 6 5 1 2015-11-12 05:39:45
3 aahed aadeh 1 0 0 1 0 1 aae hd a d 0 0 0 2 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 9 8 1 2015-11-12 05:39:45
4 aahing aaghin 1 0 0 1 0 1 aai hng a g 1 0 0 2 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 6 10 11 1 2015-11-12 05:39:45
5 aahs aahs 1 0 0 1 0 1 aa hs a s 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 4 7 6 1 2015-11-12 05:39:45
6 aal aal 1 0 0 1 0 1 aa l a l 0 0 0 2 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 4 1 2015-11-12 05:39:45
7 aalii aaiil 1 0 0 1 1 1 aaii l a i 0 0 0 2 0 0 0 0 0 0 0 2 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 6 1 2015-11-12 05:39:45
8 aaliis aaiils 1 0 0 1 0 1 aaii ls a s 0 0 0 2 0 0 0 0 0 0 0 2 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 6 6 7 1 2015-11-12 05:39:45
9 aals aals 1 0 0 1 0 1 aa ls a s 0 0 0 2 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 4 4 5 1 2015-11-12 05:39:45
10 aardvark aaadkrrv 1 0 0 1 1 1 aaa rdvrk a k 0 0 0 3 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 1 0 0 0 0 0 8 16 17 1 2015-11-12 05:39:45
Ответы
Ответ 1
Подумайте, что вы уже сделали тяжелую работу с вашей пересмотренной схемой. Все, что вам нужно сделать, это изменить запрос, чтобы найти <= количество отсчетов каждой буквы, как указано пользователем.
например. если пользователь ввел "ALIAS":
SELECT word
FROM words
WHERE count_a <= 2
AND count_b <= 0
AND count_c <= 0
AND count_d <= 0
AND count_e <= 0
AND count_f <= 0
AND count_g <= 0
AND count_h <= 0
AND count_i <= 1
AND count_j <= 0
AND count_k <= 0
AND count_l <= 1
AND count_m <= 0
AND count_n <= 0
AND count_o <= 0
AND count_p <= 0
AND count_q <= 0
AND count_r <= 0
AND count_s <= 1
AND count_t <= 0
AND count_u <= 0
AND count_v <= 0
AND count_w <= 0
AND count_x <= 0
AND count_y <= 0
AND count_z <= 0
ORDER BY CHAR_LENGTH(word), word;
Примечание: В соответствии с запросом это упорядочивается по длине слова, а затем в алфавитном порядке. Использовали <= даже для <= 0, чтобы упростить изменение вручную для других букв.
Это возвращает "aa", "aal" и "aals" (но не "aalii" или "aaliis", так как они оба имеют два "i" s).
См. Демо-версия SQL Fiddle.
Ответ 2
Поскольку у вас есть два разных требования, я предлагаю реализовать оба разных решения.
Если вам не нравятся дублированные буквы, создайте тип данных SET с 26 буквами. Заполняйте биты в соответствии с тем, что имеет слово. Это игнорирует повторяющиеся буквы. Это также облегчает поиск слов с подмножеством букв: (the_set & ~the_letters) = 0.
Если вы заботитесь о дублирующих устройствах, соберите буквы в слове и сохраните их как ключ. "msike" становится "eikms".
Создайте таблицу, содержащую 3 столбца:
eikms -- non unique index on this
msike -- the real word - probably good to have this as the PRIMARY KEY
SET('m','s','i',','k','e') -- for the other situation.
msikei и meek будут введены как
eikms
msikei
SET('m','s','i',','k','e') -- (or, if more convenient: SET('m','i','s','i',','k','e')
ekm
meek
SET('e','k','m')
REGEXP не подходит для вашей задачи.
Изменить 1
Я думаю, вам также нужен столбец, который указывает, есть ли в слове буквы с удвоенным значением. Таким образом, вы можете отличить, что kiss разрешено для msikes, но для msike.
Изменить 2
A SET или INT UNSIGNED может содержать 1 бит для каждого из 26 букв - 0 для нет, 1 для настоящего.
msikes и msike будут входить в набор с включенным точно 5 битами. Значение INSERT будет 'm,s,i,k,e,s' для msikes. Поскольку остальное должно включать логическую арифметику, возможно, было бы лучше использовать INT UNSIGNED. Так что...
a is 1 (1 << 0)
b is 2 (1 << 1)
c is 4 (1 << 2)
d is 8 (1 << 3)
...
z is (1 << 25)
В INSERT используется оператор |. bad становится
(1 << 1) | (1 << 0) | (1 << 3)
Обратите внимание, как выкладываются биты, а внизу - "a":
SELECT BIN((1 << 1) | (1 << 0) | (1 << 3)); ==> 1011
Аналогично, "объявление" равно 1001. Значит, "объявление" соответствует "плохо"? Ответ приходит от
SELECT b'1001' & ~b'1011' = 0; ==> 1 (meaning 'true')
Это означает, что все буквы в "объявлении" (1001) найдены в "плохом" (1011). Пусть вводится "слой", который равен 11010.
SELECT b'11010' & ~b'1011' = 0; ==> FALSE because of 'e' (10000)
Но "папа" (1001) будет работать нормально:
SELECT b'1001' & ~b'1011' = 0; ==> TRUE
Итак, теперь появляется флаг "dup". Поскольку "папа" имеет двойные буквы, но "плохо" не сделал этого, ваши правила говорят, что это не совпадение. Но для завершения решения потребовалось "dup".
Если у вас не было курса по булевой арифметике, я просто представил первую пару глав. Если бы я накрыл его слишком быстро, найди математическую книгу по таким и прыгаю. "Это не ракетостроение".
Итак, вернемся к тому, какой код нужен, чтобы решить, имеет ли my_word подмножество букв и разрешено ли иметь дубликаты букв:
SELECT $my_mask & ~tbl.mask = 0, dup FROM tbl;
Затем сделайте подходящий символ AND/OR для завершения логики.
Ответ 3
С ограниченной поддержкой Regex в MySQL лучше всего я могу сделать PHP script для генерации запроса, предполагая, что он включает только английские буквы. Кажется, что выражение для исключения недопустимых слов проще, чем их включение.
<?php
$inputword = str_split('msikes');
$counter = array();
for ($l = 'a'; $l < 'z'; $l++) {
$counter[$l] = 0;
}
foreach ($inputword as $l) {
$counter[$l]++;
}
$nots = '';
foreach ($counter as $l => $c) {
if (!$c) {
$nots .= $l;
unset($counter[$l]);
}
}
$conditions = array();
if(!empty($nots)) {
// exclude words that have letters not given
$conditions[] = "[" . $nots . "]'";
}
foreach ($counter as $l => $c) {
$letters = array();
for ($i = 0; $i <= $c; $i++) {
$letters[] = $l;
}
// exclude words that have the current letter more times than given
$conditions[] = implode('.*', $letters);
}
$sql = "SELECT word FROM words WHERE word NOT RLIKE '" . implode('|', $conditions) . "'";
echo $sql;
Ответ 4
Что-то вроде этого может сработать для вас:
// Input Word
$WORD = strtolower('msikes');
// Alpha Array
$Alpha = range('a', 'z');
// Turn it into letters.
$Splited = str_split($WORD);
$Letters = array();
// Count occurrence of each letter, use letter as key to make it unique
foreach( $Splited as $Letter ) {
$Letters[$Letter] = array_key_exists($Letter, $Letters) ? $Letters[$Letter] + 1 : 1;
}
// Build a list of letters that shouldn't be present in the word
$ShouldNotExists = array_filter($Alpha, function ($Letter) use ($Letters) {
return ! array_key_exists($Letter, $Letters);
});
#### Building SQL Statement
// Letters to skip
$SkipLetters = array();
foreach( $ShouldNotExists as $SkipLetter ) {
$SkipLetters[] = "`has_{$SkipLetter}` = 0";
}
// count condition (for multiple occurrences)
$CountLetters = array();
foreach( $Letters as $K => $V ) {
$CountLetters[] = "`count_{$K}` <= {$V}";
}
$SQL = 'SELECT `word` FROM `words` WHERE '.PHP_EOL;
$SQL .= '('.implode(' AND ', $SkipLetters).')'.PHP_EOL;
$SQL .= ' AND ('.implode(' AND ', $CountLetters).')'.PHP_EOL;
$SQL .= ' ORDER BY LENGTH(`word`), `word`'.PHP_EOL;
echo $SQL;
