Я прочитал некоторый документ о 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-дерева или какой-либо другой алгоритм как этот для индексации - или это имеет конкретный алгоритм?
Здесь есть неплохая статья: 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/
При отправке запроса он обрабатывается тем же анализатором, который использовался для построить индекс, а затем использовать его для поиска соответствующих терминов в индексе. Это предоставляет список документов, соответствующих запросу.
Это инвертированный индекс, но это не уточняет, какую структуру он использует.
Формат индекса в lucene имеет полную информацию.
Начните с 'Summary of File Extensions'.
Сначала вы заметите, что там говорится о различных индексах. Насколько я смог заметить, ни один из них не использует, строго говоря, B-дерево, но есть сходство - вышеупомянутые структуры действительно напоминают деревья.