Поиск в MySQL с перестановками

Question

Мне нужна помощь.
У меня есть таблица, где только два столбца: ID и ИМЯ и эти данные:

ID | NAME
1    HOME
2    GAME
3    LINK

И я хочу показать, например. строка с именем: HOME, если поиск пользователя: HOME или OMEH или EMOH или HMEO и т. д. - все перестановки из слова HOME.

Я не могу сохранить в mysql все эти перестановки и выполнить поиск в этих столбцах, потому что некоторые слова будут слишком большими (9-10 символов) и более 40 МБ для каждых 9 слов символов.

Answer 1

Это звучит как вопрос "пожалуйста, сделай мою домашнюю работу для меня". Трудно представить, к какой реальной проблеме это применимо, и не существует стандартного решения. Здесь можно попросить помочь вам с домашним заданием, но вы должны заявить, что это так.

более 40 МБ на каждые 9 символов слова

Ваша математика немного сложновата, но на самом деле хранилище плохо масштабируется. OTOH, оставляя в стороне объем хранилища, с точки зрения рабочей нагрузки обработки, он хорошо масштабируется как решение.

Вы можете просто перебрать динамический запрос:

 function mkqry($word)
 {
     $qry="SELECT * FROM yourtable WHERE 1 ";
     $last=strlen($word);
     for ($x=0; $x<$last; $x==) {
          $qry.=" AND word LIKE '%" . substr($word, $x, 1) . "%'";
     } 
     return $qry;
 }

Однако это всегда приведет к полному сканированию таблицы (медленно) и не будет правильно обрабатывать случаи, когда буква встречается дважды в слове.

Решение состоит в том, чтобы использовать функцию индексации, которая не зависит от порядка, в котором появляются символы, - некриптографический хеш. Очевидным кандидатом будет XOR для символов вместе, хотя это приводит только к одному символьному идентификатору, который не очень избирателен. Поэтому я бы предложил просто добавить коды символов:

 function pos_ind_hash($word)
 {
     $sum=0;
     for ($x=0; $x<$last; $x==) {
         $sum+=ord(substr($word, $x));
     }
     return $sum;
 }

 function mkqry($word)
 {
     $qry="SELECT * FROM yourtable WHERE 1 ";
     $last=strlen($word);
     for ($x=0; $x<$last; $x==) {
          $qry.=" AND word LIKE '%" . substr($word, $x, 1) . "%'";
     }
     $qry.=" AND yourtable.hash=" .  pos_ind_hash($word);
     return $qry;
 }

Обратите внимание, что механизм хеширования здесь не однозначно идентифицирует одно слово, но достаточно специфичен, чтобы уменьшить громкость до точки, в которой индекс (для хэша) будет эффективным.

Умножение, а не сложение создаст меньше коллизий, но с большим риском переполнения (что приведет к неоднозначности между реализациями).

Но и хеш, и одиночный символ LIKE только уменьшают количество возможных совпадений. Чтобы запрос вел себя окончательно, вам нужно пойти дальше. Вы можете добавить атрибут к таблице (и к индексу с хэшем), содержащий длину строки - это будет более избирательным (то есть повысить эффективность индекса), но все же не окончательным.

Для точного метода вам необходимо указать в своем запросе, что данные НЕ содержат символов, которые НЕ находятся в искомом слове.

Неправильный способ сделать это состоит в том, чтобы добавить цикл, указывающий «И НЕ КАК ....».

Допустимый способ сделать это - добавить в запрос тест, который заменит все буквы в атрибуте таблицы, которые появляются в искомом слове, что приводит к строке нулевой длины.

Answer 2

Один из способов решения этой проблемы - сохранить отсортированный набор символов для каждого имени в вашей базе данных в качестве дополнительного столбца, а затем отсортировать строку, введенную пользователем, перед поиском, например, база данных имеет

ID   NAME   CHARS
1    HOME   EHMO
2    GAME   AEGM
3    LINK   IKLN

Тогда при поиске в PHP вы должны сделать следующее:

$search = 'MEHO';                // user input = MEHO
$chars = str_split($search);
sort($chars);
$search = implode('', $chars);   // now contains EHMO
$sql = "SELECT ID, NAME FROM table1 WHERE CHARS = '$search'";
// perform query etc.

выход

ID   NAME
1    HOME