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

Question 1

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

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

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

инкрементальный алгоритм:

поддерживать стек сегментных индексов

создать индекс для каждого входящего документа

помещать новые индексы в стек

пусть b = 10 - коэффициент слияния; M = 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-дерева или любой другой алгоритм, подобный этому, для индексации - или у него есть особый алгоритм?

Question 2

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

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

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

Question 3

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

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

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

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

Question 4

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

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

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

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

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

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

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

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

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

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

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

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

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

Question 5

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

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

Answer 1

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

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

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

инкрементальный алгоритм:

поддерживать стек сегментных индексов

создать индекс для каждого входящего документа

помещать новые индексы в стек

пусть b = 10 - коэффициент слияния; M = 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 2

Большинство ответов здесь верны, что сначала Lucene создает инвертированный индекс, но это не объясняет ключевой момент того, как этот термин индекс впоследствии будет искать (и, я считаю, это то, что на самом деле просил OP). Итак, ниже вы найдете новый ответ на этот довольно старый вопрос, который, надеюсь, поможет лучше понять ситуацию.

fnl

Answer 3

1

Обновил мой ответ еще раз, потому что текущие ответы (включая мой!) Не совсем удовлетворительны для ответа на два основных вопроса OP (как Lucene обеспечивает оптимизированную индексацию и с помощью какого конкретного алгоритма - Skip-List, а не B-Tree, Кстати). Надеюсь, мои последние обновления правильно ответят на актуальный вопрос!

фн

Answer 4

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

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

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

Answer 5

Спасибо за ответ и ссылки. Но я слышал, что у проекта Lucene есть специальный стеммер под названием "Snowball"? Вы что-нибудь слышали об этом?

M.Amrollahi

Answer 6

Это другой вопрос: см. Lucidimagination.com/search/. Кроме того, видя ваш шаблон вопросов, я предлагаю вам прочитать книгу «Lucene в действии»: manning.com/hatcher2 (Первое издание немного устарело , но может быть найдено в версии мертвого дерева. Второе издание можно купить как электронную книгу).

Yuval F

Answer 7

5

Вы можете изменить свой ответ, первая ссылка, которая является ссылкой IBM, не найдена :)

Аделин

Answer 8

Кроме того, как поля входят в общую картину? Если запрос относится к определенному полю, как и в какой момент lucene узнает, что термин, указывающий на документ, находится не в документе, а внутри запрошенного поля?

Левон Тамразов

Answer 9

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

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

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

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

Answer 10

1

Afaik они используют Skip List вместо B-tree, чтобы уменьшить количество обращений к диску, так как часть Skip List находится в памяти и очень мало

Антон

Answer 11

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 12

1

Итак, чтобы сначала найти самые свежие результаты, будет ли поиск начинаться с просмотра самых новых сегментов? Итак, чтобы уточнить - предположим, что документ обновлен. Более старая версия документа добавляется в список уничтожения, затем любые совпадения, обнаруженные в более старых сегментах, удаляются из результатов поиска, если их идентификатор документа совпадает с идентификатором в списке уничтожения?

Joel B

Answer 13

2

Да вы правы. Единственное, что следует упомянуть, это окончательный порядок определяется с помощью правил сортировки (индекс релевантности в тривиальном случае), поэтому порядок, в котором ищутся сегменты, не имеет значения.

Денис Баженов

Answer 14

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

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

Answer 15

1

Инвертированный индекс Lucene основан на пропускаемом списке, а не на B-дереве. По-прежнему древовидная структура в очень широком смысле, но для полноты - например, см. Этот вопрос SO re. Lucene использует список пропуска и этот вопрос SO, почему списки пропуска могут быть предпочтительнее B-деревьев .

фн

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

Ответы: