Levenshtein search

Question

Я работаю на сайте, который продает, скажем, и предлагает «поиск продавцов». В этом поиске вы вводите свой город или почтовый индекс или регион и расстояние (в км или мили), тогда сайт дает вам список поставщиков.

Для этого у меня есть база данных с поставщиками. В форме для сохранения этих поставщиков вы вводите полный адрес, и когда вы нажимаете кнопку «Сохранить», запрос на карты Google сделан для получения их широты и долготы.

Когда кто-то выполняет поиск, я смотрю на таблицу, где храню все условия поиска и их lat/lng. Эта таблица выглядит

+--------+-------+------+ 
| term | lat | lng | 
+--------+-------+------+ 

Так что первый запрос что-то очень простое

select lat, lng from my_search_table where term = "the term" 

Если я найду результат, я потом искать с хорошим способом для всех поставщиков в диапазоне посетитель хочет и распечатать результат на карте.

Если я не нахожу результат, я выполняю поиск с помощью функции levenshtein, потому что люди, пишущие bruxelle или bruxeles вместо bruxelles, являются чем-то действительно распространенным я не хочу постоянно делать запрос на карты google (I также есть столбец «сколько раз в столбце», чтобы получить некоторую статистику)

Поэтому я запрашиваю my_search_time без предложения where и прохожу через все результаты, чтобы получить наименьшее расстояние levensthein. Если наименьший результат больше 2, я запрашиваю координаты с карт Google.

Вот моя проблема. Для некоторых стран (у нас есть несколько сайтов по всему миру), my_search_table имеет 15-20k + записи ... и php не (действительно) не похож на такие записи (что я прекрасно понимаю), и мой запрос попадает под тайм-аут php , Я мог бы увеличить этот таймаут, но проблема будет такой же в течение нескольких месяцев.

Итак, я попробовал функцию MySQL levensthein (найдена на stackoverflow кстати), но она также очень медленная.

Итак, мой вопрос: «Есть ли способ быстро сделать этот поиск даже на очень больших наборах данных?»

Answer 1

Мое предложение основывается на трех вещах:

• Во-первых, ваш набор данных большой. Это означает, что это: достаточно большой отклонить идею «выбрать все» + «запустить levenshtein() в приложении PHP»
• Во-вторых, у вас есть контроль над вашей базой данных. Таким образом, вы можете настроить некоторые связанные с архитектурой вещи
• Наконец, производительность SELECT запросов является самой важной вещью, а производительность для добавления новых данных не имеет значения.

Дело в том, вы не можете выполнитьбыстрый поиск Левенштейн, потому что Левенштейн себя очень медленно. Я имею в виду, что вычисление расстояния левенштейна - это медленная вещь. Таким образом, вы не сможете решить проблему только с помощью «интеллектуального поиска». Вам нужно будет подготовить некоторые данные.

Возможное решение: создать индекс группы и присвоить его при добавлении/обновлении данных. Это означает, что вы сохраните дополнительный столбец, в котором будет храниться некоторый хеш (например, числовое). При добавлении новых данных, вы будете:

• Выполните поиск с Левенштейн (для этого вы можете либо использовать приложение или ту функцию, которую вы (уже упоминались) по всем записям в таблице против введенных данных
• Установить индекс группы для новой строки для значения индекса, который нашел строки на предыдущем шаге.
• Если ничего не найдено, установите значение нового индекса группы (это «первая строка, и еще нет похожих строк»), что будет отличаются от любых значений индекса группы, которые уже присутствуют в таблице

Для поиска нужных строк вам нужно просто выбрать строки с одинаковым значением индекса группы. Это означает: ваш выберите Запросы будут очень быстрыми. Но - да, это приведет к чрезвычайно огромным накладным расходам при добавлении/изменении ваших данных. Таким образом, это неприменимо для случая, когда производительность обновления/вставки вопросов.

Answer 2

Вы можете попробовать функцию MySQL SOUNDS LIKE

SELECT lat, lng FROM my_search_table WHERE term SOUNDS LIKE "the term" 

Answer 3

Вы можете использовать KD-дерево или троичный дерево, чтобы ускорить поиск. Идея заключается в использовании двоичного поиска.