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

Question

Я прочитал какой-то документ о 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-дерева или любой другой алгоритм для индексации? - или у него есть определенный алгоритм?

Answer 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 индексирует документ, он разбивает его на несколько терминов. Затем он сохраняет термины в индексном файле, где каждый термин связан с документами, которые его содержат. Вы можете думать об этом как о хеш-таблице.

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

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

Answer 2

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

Итак, как только из документов создается индекс (термин), который основан на структуре данных списка пропусков , индексхранится на диске.Затем Lucene загружает (как уже говорилось: возможно, только некоторые из) эти термины в Finite State Transducer , в реализации FST со слабым вдохновением от Morfologick .

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

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

Answer 3

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

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

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

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

На самом деле, конечно, все сложнее:

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

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

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

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

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

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

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

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

Answer 4

Это инвертированный индекс , но это не указывает, какую структуру он использует. Индексный формат в люцене содержит полную информацию.
Начните с «Сводка расширений файлов».

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