Алгоритм Луцен - программирование

Я прочитал статью Дуга Реттинга; "Оптимизация пространства для общего рейтинга.

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

В частности, описанный здесь алгоритм общего ранжирования включает в себя просмотр всего списка проводок для каждого термина запроса, поэтому в случае очень распространенных терминов запроса, таких как "желтая собака", у любого из двух терминов может быть очень длинный список проводок в случае веб-поиска. Все ли они действительно пройдены в текущей Lucene/Solr? Или есть эвристика для усечения списка?

В случае возвращения только лучших результатов k я могу понять, что распределение списка проводок на нескольких машинах, а затем объединение верхнего-к каждого из них будет работать, но если мы должны вернуть "100-й результат страница", то есть результаты оцениваются с 990-1000-го, тогда каждый раздел должен будет найти верхнюю 1000, поэтому разделение не поможет.

В целом, есть ли какая-либо современная подробная документация по внутренним алгоритмам, используемым Lucene?

Ответ 1

Мне не известно о такой документации, но поскольку Lucene является открытым исходным кодом, я рекомендую вам прочитать исходный код. В частности, текущая версия trunk включает гибкую индексацию, что означает, что обход списка хранилищ и проводки был отделен от остальной части кода, что позволяет писать собственные кодеки.

Вы предположения корректны относительно обхода списка проводок по умолчанию (это зависит от вашей Scorer). Lucene пересекает весь список проводки для каждого термина, присутствующего в запрос и помещает соответствующие документы в кучу размера k для вычисления верхних k-документов (см. TopDocsCollector). Таким образом, возвращаемые результаты с 990 до 1000 заставляют Lucene создавать кучу размера 1000. И если вы разбиваете свой индекс по документу (другой подход может заключаться в раздельном распределении), каждый осколок должен будет отправить первые 1000 результатов на сервер, который ответственный за объединение результатов (например, Solr QueryComponent, который переводит запрос с N на P > N на несколько запросов осколков от 0 до P sreq.params.set(CommonParams.START, "0");). Вот почему Solr может быть медленнее в распределенном режиме, чем в автономном режиме в случае экстремального пейджинга.

Я не знаю, как Google удается эффективно оценивать результаты, но Twitter опубликовал документ на своем поисковом движке Earlybird, где они объясняют, как они исправили Lucene, чтобы сделать эффективный обратный хронологический порядок прохождения списков проводки, что позволяет им возвращать самые последние твиты, соответствующие запросу, без прохождения всего списка проводки для каждого термина.

Update: Я нашел эту презентацию из Google Googler Jeff Dean, в которой объясняется, как Google построила свою широкомасштабную информационно-поисковую систему. В частности, речь идет о стратегиях ошпаривания и кодировании списка проводки.