Как документы индекса lucene?

Я прочитал несколько документов о Люцене; также я прочитал документ в этой ссылке (http://lucene.sourceforge.net/talks/pisa).

Я действительно не понимаю, как Lucene индексирует документы и не понимает, какие алгоритмы использует Lucene для индексирования?

В приведенной выше ссылке говорится, что Lucene использует этот алгоритм для индексирования:

  • инкрементный алгоритм:
    • поддерживать стек индексов сегмента
    • создать индекс для каждого входящего документа
    • введите новые индексы в стек
    • пусть b = 10 - коэффициент слияния; М = 8
for (size = 1; size < M; size *= b) {
    if (there are b indexes with size docs on top of the stack) {
        pop them off the stack;
        merge them into a single index;
        push the merged index onto the stack;
    } else {
        break;
    }
}

Как этот алгоритм обеспечивает оптимизированное индексирование?

Использует ли Lucene алгоритм B-дерева или любой другой алгоритм, подобный индексированию - или у него есть определенный алгоритм?

Ответы

Ответ 1

Здесь неплохая статья: https://web.archive.org/web/20130904073403/http://www.ibm.com/developerworks/library/wa-lucene/

Редактировать 12/2014: Обновлено до заархивированной версии из-за того, что оригинал был удален, вероятно, лучшим последним вариантом является http://lucene.apache.org/core/3_6_2/fileformats.html

Там еще более поздняя версия на http://lucene.apache.org/core/4_10_2/core/org/apache/lucene/codecs/lucene410/package-summary.html#package_description, но, похоже, в ней меньше информации, чем в старой.

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

Сроки генерируются с помощью анализатора, который сужает каждое слово в его корневой форме. Самым популярным алгоритмом для английского языка является алгоритм генерации Porter: http://tartarus.org/~martin/PorterStemmer/

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

Ответ 2

Кажется, ваш вопрос больше связан с слиянием индексов, чем с индексированием.

Процесс индексирования довольно прост, если вы игнорируете детали низкого уровня. Lucene формирует так называемый "инвертированный индекс" из документов. Поэтому, если в документ входит текст "Быть ​​или не быть" и id = 1, инвертированный индекс будет выглядеть так:

[to] → 1
[be] → 1
[or] → 1
[not] → 1

Это в основном это - индекс от слова к списку документов, содержащих заданное слово. Каждая строка этого индекса (слова) называется списком проводки. Этот индекс сохраняется при долгосрочном хранении.

В действительности, конечно, вещи сложнее:

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

Есть еще много осложнений, которые не так важны для базового понимания.

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

Итак, возникает вопрос - как мы можем изменить уже проиндексированный документ?

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

Здесь происходит слияние. Слияние - это процесс объединения нескольких индексов для повышения эффективности индекса. То, что в основном происходит при слиянии, - это живые документы, скопированные в новый сегмент, и старые сегменты полностью удалены.

Используя этот простой процесс, Lucene может поддерживать индекс в хорошей форме с точки зрения производительности поиска.

Надеюсь, это поможет.

Ответ 3

Это инвертированный индекс, но это не указывает, какую структуру он использует. Формат индекса в lucene содержит полную информацию.
Начните с "Резюме расширений файлов".

Вы сначала заметите, что речь идет о разных разных индексах. Насколько я мог заметить, ни один из них не использует строго говоря B-tree, но есть сходства - вышеупомянутые структуры напоминают деревья.

Ответ 4

В двух словах Lucene строит инвертированный индекс, используя Пропустить-списки на диске, а затем загружает сопоставление для индексированных терминов в память, используя Конечный преобразователь состояния (FST). Обратите внимание, однако, что Lucene не (обязательно) загружает все индексированные термины в ОЗУ, как описано Майклом Маккандлесом, автором самой системы индексации Lucene, Обратите внимание, что с помощью Skip-Lists индекс может быть перенесен с одного удара на другой, делая такие вещи, как set и, в частности, диапазоны запросов (как B-Trees). И Википедия в индексировании Skip-Lists также объясняет, почему реализация Lucene Skip-List называется многоуровневым Skip-List - по существу, чтобы сделать O(log n) возможен поиск (опять же, как и B-деревья).

Итак, как только инвертированный (термин) индекс, основанный на Структура списка Skip-List - создается из документов, индекс хранится на диске. Затем Lucene загружает (как уже говорилось: возможно, только некоторые из) эти термины в Конечный преобразователь состояний в реализацию FST слабо вдохновил на Morfologick.

Майкл МакКандлесс (также) делает довольно хорошую и краткую работу объясняя, как и почему Lucene использует (минимальный ациклический) FST для индексации Термины Lucene хранятся в памяти, по существу, как SortedMap<ByteSequence,SomeOutput>, и дают основную идею о том, как работают FST (т.е. как FST сжимает байтовые последовательности [то есть индексированные термины], чтобы сделать использование памяти этим отображением, линейный). И он указывает на документ, описывающий конкретный алгоритм FST. Также использует Lucene.

Для любопытных, почему Lucene использует Skip-Lists, в то время как большинство баз данных используют (B +) - и/или (B) -Trees, посмотрите правильный ответ SO по этому вопросу (Skip-Lists vs. B-Trees). Этот ответ дает довольно хорошее, глубокое объяснение - по существу, не, так что сделайте параллельные обновления индекса "более поддающимися" (потому что вы можете решить не перебалансировать B-Tree сразу, тем самым набрав примерно такая же одновременная производительность, как Skip-List), а, скорее, Skip-Lists избавляет вас от необходимости работать с (с задержкой или нет) балансировкой (в конечном счете), необходимой для B-деревьев (на самом деле, как показывает ответ/ссылок, вероятно, очень мало различий в производительности между B-Trees и [многоуровневыми] Skip-Lists, если они "сделаны правильно".)