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

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

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

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

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

2 ответа

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

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

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

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

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

Кредит изображения http://*******************.wordpress.com/


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

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

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

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

licensed under cc by-sa 3.0 with attribution.