Как искать фразы в инвертированном индексе?

Question

[pandaa]

На примере запроса "blue sky" поисковый индекс выдает все документы по слову blue и по слову sky. Дальше мы можем просто найти из этих документов одинаковые, и это и будут те документы на которых есть фраза blue sky.

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

Answer 1

[Иван Шумов]

Term в таком случае должен составлять 2 слова. Никакой магии

Comments

[pandaa]

Это антипаттерн. Прочитайте про инвертированный индекс

[Иван Шумов]

pandaa, антипаттерн это не плохо. Это то что работает. Я потратил время на то чтобы вытрясти из специалистов по search'у подобную информацию. Так это работает в реальной жизни. Все остальное не перформит никак и очень дорого по тому что идут вычисления. Если очень надо последовательность слов то можно извратиться и представлять документы в виде связанных списков, но это уже абсолютно другие решения и подходы, не имеющие ничего общего с данным вопросом.

Еще раз, для закрепления, антипаттерн это не плохо. Паттерны, имеющиеся сегодня это наследие IT из 90х и монолитных проектов. Сегодня многие из них уже устарели не применяются по тому что не подходят для быстро изменяющихся проектов. Антипаттерны появились как то что не эффективно решало проблемы ранее, но сегодня ветер дует в другую сторону

[pandaa]

Иван Шумов, вы предлагаете хранить в Term все поисковые запросы? Какие специалисты по search'у вам сказали это? При новом уникальном запросе, не будет не какой информации, потому что не будет поля в Term и это будет происходить.

[Иван Шумов]

pandaa, есть такой факт что задача поиска не выдавать всю информацию, а самую релевантную. С увеличением длины поисковой фразы число документов экспоненциально падает и после определенного значения практически не меняется. Самая большая длина полезной нагрузки фразы была что-то вроде 6 слов. Это предел. В мире поиска размер дискового пространства менее значим чем вычислительные ресурсы и время отклика. Term'ы создаются из документов, а не из запросов пользователей все-же. Не забываем что в мире search главную роль играет подготовка данных, которую проходят как документы так и поисковые запросы, где происходит вся магия и что является гарантией успеха

[Иван Шумов]

pandaa, ну и в догонку - в тегах у вас указан MySQL, который в таких системах не используется по тому что он не нужен. Там используются key-value или nosql решения

[Иван Шумов]

pandaa, посмотрите на ElastcSearch или Solr. Другие инструменты в этом мире сегодня не используются. Ну, за исключением таких проектов как Algolia. Я не в курсе что у них под капотом работает

[Иван Шумов]

pandaa, поисковая фраза преобразовывается, бьется на все термы от максимального к минимальному, по им ищутся документы с соответствующими дермами и раздаются веса исходя из размера терма и частотности. Есть различные формулы для расчета от довольно старых до совсем новых и прогрессивных.

[pandaa]

Иван Шумов, Term'ы создаются не из документов, а из слов, см. Яндекс Поиск

[Иван Шумов]

pandaa, термы состоят из слов, но для генерации термов необходимо подготовить документ специфическим образом и разделить его на наборы слов длиной от 1 и до необходимого значения. Подготовка в себя включает проведение

• в нижний регистр
  
• в один и тот же род и число
  
• исправление опечаток
  
• на один язык
  
• замена синонимов
  
• чистка от слов с избыточной частотностью (предлоги, междометия, местоимения, слова предметной области вроде "доктор" в документе про докторов)
  

есть еще разные преобразования и я не помню уже как они называются правильным образом

[pandaa]

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

[Иван Шумов]

pandaa, а Я.П при публикации красивых "обучающих материалов" вечно забывает рассказать как на самом деле работают те механизмы о которых они пишут.

[pandaa]

Иван Шумов, Можете посмотреть в Google или в википедию о том, как поисковики хранят данные, если не нравится яндекс

[Иван Шумов]

pandaa, про фразы я уже ответил. Можно принять реальность или думать что есть какая-то волшебная магия. Если нужны не фразы , а просто все слова в определенном порядке то там идет первичная выборка по индексу и далее уже расчет веса исходя из порядка слов в документе. Это достигается, как я уже говорил, связанными списками с последовательностью термов, связанных последовательно и расчётом расстояния между термами. Это дорого и долго и нужны серьезные вычислительные мощности

Answer 2

[Dimonchik]

скачай
https://www.ozon.ru/context/detail/id/5497130/

есть отсканированная в сети
там ответы на все вопросы

изначально - все как и пишешь
индекс - это список документов в которое входит слова

два слова - два списка
их пересечение - обычный XOR, хз кто сказал что оно ресурсоемко

а вот уже чтобы ответ был РЕЛЕВАНТЕН - там дофига чего наворочено сверху, что Иван Шумов тебе и пытается объяснить

и да, в современном поиске индекс это список документов соответствующих ВЕКТОРУ запроса

никто его онлайн не делает - все просчитано заранее
онлайн только пытаются свести запрос к наилучшему (нескольким) заренее просчитанным векторам

Comments

[Иван Шумов]

Спасибо за поддержку)

маленькое уточнение:

два слова - два списка
их пересечение - обычный XOR, хз кто сказал что оно ресурсоемко

я говорил про упорядоченный поиск слов. одним XOR'ом тут не отделаться)

[Dimonchik]

упорядоченный - это вектора,

конечно, long tail и все такое - ну так на то он и Гугл... а в простеньких объявлениях - маркетплейсах не такие кластеры и большие

мы ж тут разжевываем лекцию, азы так сказать

[Иван Шумов]

dimonchik2013, а при чем тут сравнение маркетплейсов и гугла? принципы везде одни и те же. А для проектов ниже поисковых гигантов хватает эластика и алголии, где не надо даже близко понимать что такое Inverted Index

[Dimonchik]

для маркелпейсов алгоритмы почти не нужны

Answer 3

[xmoonlight]

На примере запроса "blue sky" поисковый индекс выдает все документы по слову blue и по слову sky. Дальше мы можем просто найти из этих документов одинаковые, и это и будут те документы на которых есть фраза blue sky.

нет. Будут содержащие одновременно и blue, и sky. Но не лишь заданную фразу: blue sky.

Создавайте "дерево" связей всех слов (вектора следования) и ищите нужные "цепочки" (фразы) в этом "дереве" с любым максимальным "расстоянием".
При импорте нового документа - дополняйте/обновляйте "дерево" связей.

Comments

[pandaa]

xmoonlight, Это обычный intersect

[xmoonlight]

pandaa, где именно? В вопросе, в Вашем алгоритме или в моём ответе?