Комментарии 43
Хорошая работа и фича. А за какое время, пилили первый рабочий вариант?
А как определяется относительная релевантность слов "слоник" и "слоновый", например? По тому, сколько символов есть в слове помимо основного для нас "слон" ?
И как вы поступаете со словами, которые имеют несколько значений? К примеру, "мышь полевка" и "компьютерная мышь" - 2 совершенно разных кейса использования слова "мышь". И если пользователь искал "проводная мышь", то не совсем очевидно, какой из результатов будет более релевантным.
Относительная релевантность слова на данный момент определяется просто по длине. Длина искомого слова делится на длину найденного слова (получается всегда меньше 1) и это как раз является коэффициентом релевантности слова.
Сейчас алгоритм не различает смыслов слов. Если по запросу "мышь" пользователь будет получать "мышь полёвка", то он сможет уточнить запрос добавлением "комп" или "прово", что уже однозначно выдаст искомый результат.
Да, вот про вычисление релевантности очень интересно. Отбрасывается ли окончание в случае русского языка? Т.е. будет ли искаться "делал" при запросе "делалА", или "красив" при запросе "красивЫЙ" и как посчитается релевантность, ведь тогда отношение длин больше 1?
Учитываются ли опечатки и ошибки - а/о, е/и, сдвоенные согласные? Индек строится прямо по словам или делается metaphone/soundex?
Учитывается ли порядок слов? Т.е. будет ли найдено "кофе был крепкий" в описанном примере?
Что делаете с местоимениями, предлогами, междометиями, сокращениями, аббревиатурами при индексировании, поиске, вычислении релевантности?
Сейчас окончание не отбрасывается, но в одной из следующих версий будет добавлен стемминг, который автоматически отбрасывает окончания и ищет по корню. Релевантность, видимо, будет вычисляться для "порезанных" слов отдельно. То есть для точного совпадения релевантность 1, для слов, найденных в результате стемминга формула будет несколько иная. Нужно подумать.
Опечатки и ошибки сейчас не анализируются, тоже задел на будущее.
Порядок слов не учитывается. Хотя и можно было бы добавить такую "фичу", но она больше мешает, чем помогает.
Члены предложений не определяются. Все слова считаются просто словами. Для коротких и часто встречающихся слов есть особенная ветка алгоритма, поскольку выборка может получиться очень большая и скрипт падает с out of memory. Для таких слов мы ограничиваем количество векторных пар. В будущем скорее всего такие слова будут автоматически заноситься в список "стоп-слов" и не учитываться на поиске.
Metaphone/soundex пробовали, результаты получаются довольно нерелевантные.
Надо заметить, что поиск очень часто используется для поиска по каталогам, например, запчастей. И тогда важно найти "MR776221E" и не найти "MR776321E". Поэтому достаточно важна точность.
Видимо, придётся обнаружение опечаток и ошибок делать опцией.
Спасибо за комментарий, очень много информации на подумать.
Немного смущает термин "быстрый" в заголовке. Если я верно понял из описания, то алгоритм, в целом, такой:
1) разбиваем поисковую строку на слова
2) находим записи по каждому слову из поиска
3) по всем найденным записям вычисляем релевантность
4) дергаем из базы записи в соответствии с релевантностью
Звучит все просто и логично (возникло даже желания в одном из своих проектов такой подход попробовать). Но насколько быстро это работает на больших объемах? Ведь п.2 может вернуть овердофига записей
Ну я так прикинул, если делать первичную выборку релевантности прямо в запросе, то должно получиться норм. Скажем, та самая степень совпадения и общий вес слова легко учитываются в запросе. Да и общий вес фразы, через group by + having. Вот жалко что именно таких подробностей в посте нету. Такое ощущение, что пост написан не на Хабр, а на сайт с плугинами для вордпресса, чисто инструкция по использованию.
Действительно, п.2 может вернуть очень много записей. Но, к счастью, это очень короткие записи (каждая содержит только ID слова и ID документа), и это ничего, если их будет пара-тройка миллионов, PHP сегодня быстр и такие данные обрабатывает влёт. Всё-таки самая долгая операция в этом алгоритме - запрос к MySQL, поэтому он максимально простой.
Мне кажется, про пару-тройку миллионов вы несколько эээ… преувеличили. В статье упоминается база с сотней тысяч постов — такая цифра будет ближе к реальности при таком-то варварском подходе. Но на то чтобы зафетчить в 20-30 раз больше, понадобится минимум секунда. А это уже неприемлемо для быстрого поиска. Не говоря обо всех последующих сортировках, нагрузке на канал и прочем.
Всё очень индивидуально на самом деле. Зависит от мощностей сервера на котором крутится MySQL, от размеров RAM и innodb_cache в частности. На практике мы получали результаты менее секунды при 400к постов, правда там и сервер не самый плохой - 16 Гбт памяти, MySQL настроен как нужно, 2048 Mb отдано под php memory_limit. Опять же хочу добавить, что алгоритм не ставит целью победить по скорости современные поисковые системы. Тут речь про инструмент, нативно работающий под WordPress.
Ну об этом я и говорю. 400к — это на порядок меньше заявленных выше "пары-тройки миллионов".
И дело тут не в конкуренции с поисковиками. А в пределе, на котором эта система загнётся. Просто в силу неоптимальной архитектуры. При том что могла бы ещё работать, на том самом копеечном хостинге, ради которого всё и затевалось :)
400k - это записей. А векторных пар при этом получается несколько миллионов, потому что слова встречаются в документах по нескольку раз.
Если у вас есть рекомендации по оптимизации кода или алгоритма (или полной перестройке системы, если старую не починить), то поделитесь. Свежие идеи со стороны - это всегда хорошо.
Хостинг не обязательно должен быть копеечный. Порой владельцы сайтов не используют мощные поисковые решения (и мощные современные движки для создания сайтов) совсем по другим причинам. Среди наших клиентов есть весьма небедные владельцы новостных порталов и онлайн-библиотек, которые продолжают пользоваться WordPress.
Я никогда не делал такой ручной индекс. Но у меня есть стойкое убеждение, что данные всегда оптимальнее обрабатывать на месте и сразу возвращать нужный результат, чем гонять между серверами. Плюс, в моей практике, при прочих равных у сервера БД всегда больше ресурсов, чем у РНР скрипта.
Поэтому предложения у меня есть, но не подкреплённые практикой. Тем не менее, я считаю их довольно логичными. Собственно, я их уже здесь озвучивал: сделать первичную сортировку по релевантности в запросе, и таким образом отсекать заведомо негодные результаты. Ну, скажем, тысячу.
Степень совпадения легко считается в запросе, она ничего не стоит. Вес слова, если он лежит в индексе, тоже легко учесть. Конечно, запрос с сортировкой, а тем более — с группировкой — будет тяжелее чем просто выборка из индекса, но учитывая, что эти данные всё равно придётся сортировать, но только перегнав их сначала в РНР — я считаю что можно было бы хотя бы попробовать.
select sum(weight) gross_weight from index where ...
group by post_id order by gross_weight descдаст нам сортировку по суммарным весам найденных слов. Разумеется, все участвующие в запросе данные должны быть в одном индексе.
Но в любом случае — код, который сначала делает миллион фетчей в массив, а потом ещё и этот массив сортирует в РНР — у меня в голове просто не укладывается. Я о таком никогда не слышал.
Ну то есть вы сделали такой полнотекстовый поиск на коленке, который чисто технически — это keyword like 'слово1%' or keyword like 'слово2%' и дальше всякая уличная магия по вычислению релевантности. Мне кажется, это полезно было бы упомянуть в статье. Так она станет ближе к читателю, которому всегда интереснее узнать, как работает некая штуковина, а не какие молодцы её создатели ;)
Не очень понятно, за счет чего достигается большая скорость, если встроенный полнотекстовый действует практически так же. Или MATCH AGAINST там случайно при построении фразы затесалось? :)
Есть ли первичный отбор по релевантности в запросе? Мне кажется, он должен быть, иначе придется на РНР перерабатывать много мусора. Вы же ограничиваете выборку?
При желании, можно поизучать код. Там не так много файлов. Один из недостатков, по моему, это зависимость от внешнего сервиса (микросервиса) (fulltextsearch.org/fire), который получает post-запрос с чем то, отдаёт что то.
Хм. Как-то странно. А этот микросервис точно нужен? Это же явно не внешний поисковик. Может быть, просто защитка/собиралка персональных данных?
Там написано в тексте про это:
Поиск медиа-файлов и файлов, прилинкованных к публикациям, по текстовому
содержимому файлов (поддерживаются PDF, DOC, DOCX, XLS, XLSX, RTF и
многие другие форматы) - для извлечения текста мы используем свой
собственный микро-сервис.
А, ну так это файло. При чём оно здесь? В статье-то речь идёт про поиск по базе. Плюс извлечение текста нужно только для индексирования, а для поиска-то оно зачем?
Для разбора файлов мы используем свой собственный сервис Textmill.io. В бесплатной версии (которая в репе WordPress) нет этого функционала, он есть только в платной версии.
Но для гика всё просто на самом деле - при индексировании каждого поста WP вызывается хук wpfts_index_post, и мы можем проверить тип поста. Если он "attachment", то есть медиафайл, то мы берём ссылку на файл, передаём его в Textmill.io, в ответ получаем разобранный файл в виде JSON, который уже индексируем как обычный текст.
Кстати в платной версии встроена библиотека для разбора PDF на PHP. Работает она неплохо, но очень большие файлы не тянет. Так что если у клиента есть необходимость искать только PDF, он может поставить побольше memory_limit, отключить Textmill.io и пользоваться только внутренним экстрактором.
Это микросервис fire-flare. На поиск он не влияет и единственный его смысл в том, чтобы уведомлять фронтенд о происходящих на сервере (внутри индексатора) событиях. Всё может работать и без этого микросервиса, но тогда приходится периодически (довольно часто, 1 раз в 5 секунд) делать запросы с клиента на сервер WP, отчего сильно увеличивается загрузка, особенно если открыто 10 вкладок одной и той же админки.
Зачем уведомлять фронтенд? В админке есть блок статистики, показывающий текущее состояние индекса (сколько документов проиндексировано, сколько в очереди и всё такое прочее) - эта информация динамично меняется и хотелось бы обновлять её 1 раз в 5 секунд хотя бы. Вот для того, чтобы не мучать WP мы и сделали такой внешний ретранслятор коротких информационных пакетов.
Первичного отбора по релевантности нет, нам показалось логичным, что право на попадание в список результатов могут получить абсолютно все документы, даже те, в которых есть одно-единственное малорелевантное слово. Таким образом, выборка векторов производится абсолютно по всем совпадениям.
Одна из операций выборки - это получение полного списка подходящих слов из таблицы слов. Тут используется LIKE 'слово%' либо LIKE '%слово%' (в зависимости от режима работы - есть два режима "простой поиск" и "глубокий поиск"). Но такой способ использования LIKE использует ключи, поэтому он очень быстр. А вот полнотекстовый поиск с использованием LIKE 'слово%' невозможен, потому что он будет искать слово только в начале текста, а в середине текста находить не будет. Поэтому в WordPress нативно используется только LIKE '%слово%', который ключи не использует и поэтому крайне медленный на больших объёмах данных.
Отдельно могу сказать по MATCH AGAINST. Да, скорее всего внутри MySQL используется похожий принцип, вот только настроить этот поиск никак невозможно. Есть несколько параметров внутри глобального конфига my.ini/my.cnf, которыми можно задать, например, минимальную длину слова (она по умолчанию выставлена в 3), то есть слова короче 3 символов просто игнорируются, независимо от их важности. Релевантность он считает по каким-то своим формулам. Изменить глобальный конфиг через PHP тоже не получится на большинстве хостингов.
И да, тесты показали, что MATCH AGAINST работает медленно на больших массивах. Наш алгоритм быстрее.
Я планирую в ближайшее время написать ещё одну статью с детальным разбором алгоритма релевантности и проведу сравнение с нативным LIKE-поиском и вариантом с MATCH AGAINST. Не хотелось перегружать обзорную статью техническими деталями.
Спасибо за подробный комментарий!
С поиском тут небольшая путаница. Сначала вы пишете что LIKE '%слово%' использует индекс, а чуть ниже — что не использует. Я думаю, в первом случае вы имели в виду, что поле целиком лежит в оперативке, то есть даже полный перебор будет быстрее, чем на диске — и в этом смысле наличие индекса ускоряет поиск. Но, всё-таки, в общепринятом смысле — практически мгновенный бинарный поиск за считанное количество переходов — индекс тут не используется.
Логику с одним-единственным малорелевантным словом я, честно говоря, не понял. Если результатов мало, то это слово и так попадёт. Если результатов много — то при сортировке это слово всё равно окажется в самом конце списка, и его никто не увидит. Я честно не понимаю, какой смысл его оставлять в больших выборках. Как-то мне идея с сортировкой на клиенте совсем не нравится. И по скорости, и по памяти. В конце концов, исходным посылом была забота про дешевые хостинги, а тягать из базы по 15-20 мегабайт на каждое нажатие клавиши даже и на дедике не кажется мне хороший идеей.
Буду с нетерпением ждать вторую статью.
Должен разъяснить. Дело в том, что MySQL по-разному оптимизирует LIKE в зависимости от того, какой параметр используется для поиска. Если LIKE используется без % в начале (например, LIKE 'слово%'), то MySQL будет использовать ключ фиксированного размера на соответствующем поле VARCHAR.Поэтому такая выборка работает очень быстро - не нужно ничего искать, MySQL уже знает, в каких строках таблицы слов находятся подходящие слова. Поэтому такой LIKE смело можно назвать не поиском, а выборкой по ключу. И по сути индексированный поиск WP FullText Search - это тоже не поиск, а выборка по ключу :-) поэтому и быстрый.
Если же LIKE используется с % в начале параметра (например, LIKE '%слово%'), то использование ключа становится невозможным. MySQL приходится проверять весь текст полностью, сравнивая '%слово%' со строкой в цикле. И это уже реальный поиск.
Есть немного информации тут
https://stackoverflow.com/questions/2042269/how-to-speed-up-select-like-queries-in-mysql-on-multiple-columns
Совсем неочевидно, сколько ещё будет результатов кроме одного найденного малорелевантного. Может быть десяток, а может быть, этот результат будет вообще один-единственный. Во всяком случае, мы не можем решать за пользователя, хочет ли он просмотреть все найденные документы или ему достаточно лишь 30% от найденного. Бывает, что запрос сложный.
Про сортировку на клиенте речи не было. Весь поиск, сортировка и генерация страницы с результатами поиска производится на стороне PHP, то есть, на сервере.
Нет ничего плохого гонять большие объёмы информации. Это бесплатно. В отличие от аренды VPS с root-доступом и программистом, который может всё настроить, или облачного решения для поиска. Хотя многие склоняются к такому варианту и вполне счастливы.
Это-то понятно, просто в комментарии выше у вас написано немного противоположное:
Тут используется LIKE 'слово%' либо LIKE '%слово%' (в зависимости от режима работы — есть два режима "простой поиск" и "глубокий поиск"). Но такой способ использования LIKE использует ключи, поэтому он очень быстр.
Видимо, вы просто тут оговорились. Хотя не очень понятно, что в итоге хотели сказать.
мы не можем решать за пользователя, хочет ли он просмотреть все найденные документы или ему достаточно лишь 30% от найденного
Смотрите, у вас типичная проблема, туннельное зрение. Вы забываете контекст. А контекст — я напомню — "пара-тройка миллионов" результатов. И в этом контексте вы прекрасно знаете, хочет пользователь просмотреть их все, или нет. Особенно если речь о живом поиске.
В отличие от аренды VPS с root-доступом и программистом, который может всё настроить
Ну то есть у вас такого программиста не нашлось, и вы переложили сортировку с SQL на РНР? Теперь понятно.
Нет ничего плохого гонять большие объёмы информации.
Проблемы никакой нет, но я вам советую не слишком громко об этом говорить. Могут программисты услышать.
повтор, удалено
И ещё конечно бесит это пещерное "Download". В 2022, чтобы посмотреть код его надо скачивать на компьютер, разворачивать, вот это вот всё — серьёзно? Ещё и хаб "Open source". Тут скорее бы подошёл хаб "Shareware". Непонятно, кстати, почему нет репозитория в открытом доступе. Ведь он по идее должен быть. Но получается, что приватный. Какой-то такой получается Open source с душком.
Во вкладке "Development", есть ссылка на просмотр кода "Browse the code".
Можно скачать напрямую из репозитория WordPress, он в открытом доступе
Есть еще файловый Хapian с 30-летней историей. Был весьма хорош для прототипов и однонодных решений, но биндинг остался с PHP5, увы.
А можно пример сайта, на котором установлен данный плагин ?
Публикации
Как работает быстрый текстовый поиск для WordPress