Как Lucene (Solr/ElasticSearch) так быстро фильтрует термин?

С точки зрения структуры данных, как Lucene (Solr/ElasticSearch) так быстро отфильтровывает термины? Например, для всех документов, содержащих слово "бекон", найти счетчики для всех слов в этих документах.

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

Но как же Луцен быстро определяет подсчеты для всех слов в документах, которые соответствуют "беку"? В моем наивном понимании Люцену пришлось бы взять бит-массив, связанный с беконом, и И это с битовыми массивами для каждого другого слова. Я что-то упускаю? Я не понимаю, как это может быть эффективно. Кроме того, нужно ли снимать эти битовые массивы с диска? Это звучит все хуже!

Как работает волшебство?

Ответ 1

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

Для этого Lucene хранит документы, индексы и их метаданные в разных форматах файлов. Перейдите по этой ссылке для получения подробной информации о файле http://lucene.apache.org/core/3_0_3/fileformats.html#Overview

Если вы читаете раздел document numbers, каждому документу присваивается внутренний идентификатор, поэтому при обнаружении документов со словом "consign" механизм lucene получает ссылку на его метаданные. Обратитесь к разделу обзора, чтобы увидеть, какие данные сохраняются в разных индексах Lucene. Теперь, когда у нас есть указатель на хранимые документы, Lucene может получить его одним из следующих способов

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

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

Изображение предоставлено http://leanjavaengineering.wordpress.com/

Проверьте формат файла индекса здесь http://lucene.apache.org/core/8_2_0/core/org/apache/lucene/codecs/lucene80/package-summary.html#package.description

Ответ 2

нет задействованных битов: его инвертированный индекс. Каждый термин отображает список документов. В lucene алгоритмы работают на итераторах этих "списков", поэтому элементы из итератора читаются по запросу, причем не все одновременно.

эта диаграмма показывает очень простой алгоритм соединения, который просто использует следующую операцию(): http://nlp.stanford.edu/IR-book/html/htmledition/processing-boolean-queries-1.html

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

DocIDSetIterator - это "перечислитель" в lucene. он имеет два основных метода: next() и advance(). И да, это правда, вы можете решить прочитать весь список + преобразовать его в биты в памяти и реализовать этот итератор над этим битетом в памяти. Это происходит, если вы используете CachingWrapperFilter.