Как работает Lucene

90

Я хотел бы узнать, как быстро работает поиск lucene. Я не могу найти никаких полезных документов в Интернете. Если у вас есть что прочитать (кроме исходного кода lucene), дайте мне знать.

В моем случае запрос текстового поиска с использованием текстового поиска mysql5 с индексом занимает около 18 минут. Поиск того же запроса в Lucene занимает меньше секунды.

Мидхат
источник
2
Могу ли я запросить преобразование этого вопроса в вики сообщества? Lucene теперь звучит как платформа.
asyncwait 03

Ответы:

75

Lucene - это перевернутый полнотекстовый индекс. Это означает, что он берет все документы, разбивает их на слова, а затем строит индекс для каждого слова . Поскольку индекс является точным совпадением строки, неупорядоченный, он может быть очень быстрым. Гипотетически, неупорядоченный индекс SQL для varcharполя может быть таким же быстрым, и на самом деле я думаю, вы обнаружите, что в этом случае большие базы данных могут очень быстро выполнять простой запрос на равенство строк.

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

Однако, в конце концов, если вы действительно хотите знать, вам нужно прочитать источник. В конце концов, обе вещи, на которые вы ссылаетесь, имеют открытый исходный код.

bmargulies
источник
Если я правильно понимаю, то, что отличает текстовые поисковые системы от других, это то, как они обрабатывают поиск по нескольким словам и объединяют результаты поиска по нескольким индексам в реальном времени. Я бы не советовал обращаться по этому поводу к источнику Lucene. Наверное, было бы лучше почитать немного о теории текстового поиска, мне помог ответ @ alienCoder.
Крис Датроу
1
@bmargulies, если индексация "по слову", то почему пользовательский поиск stackoverflow stackoverflow.com/users разрешает совпадения подстрок?
Pacerier 07
2
Здесь не место для ответов целиком. Там есть сколько угодно доработок по основной концепции.
bmargulies 07
Что вы имеете в виду «указатель для каждого слова» ... если я начну печатать «abc», как он найдет «abc» в документе?
Alexander Mills
1
Индекс (B-дерево) от слова к документу может искать документы по словам в документе, потому что таблица такого индекса (слово, документ), где индекс находится в столбце слова. Рассмотрим такой запрос: «Найти документы со словами« полиция »,« преступление »,« статистика »». Выполняя поиск по индексу слов, вы можете выполнить три поиска в журнале (N), чтобы получить O (N) документов с одним из этих слов в них. Затем вы можете выполнить два цикла O (N), чтобы создать набор, содержащий документы, содержащие все три слова. Хотя это теоретически операция O (N), в большинстве документов нет всех трех слов, поэтому ее O (n), где n <N.
Calicoder
34

Lucene создает большой индекс. Индекс содержит идентификатор слова, количество документов, в которых это слово присутствует, и позицию слова в этих документах. Поэтому, когда вы задаете запрос из одного слова, он просто выполняет поиск по индексу (временная сложность O (1)). Затем результат оценивается по разным алгоритмам. Для запроса из нескольких слов просто возьмите пересечение набора файлов, в которых присутствуют слова. Таким образом, Lucene очень-очень быстрая.

Для получения дополнительной информации прочтите эту статью разработчиков Google: http://infolab.stanford.edu/~backrub/google.html.

alienCoder
источник
8
Полистал эту бумагу, она оказалась очень полезной. В частности, "4.5 Searching" дал ответ, который я искал. В частности, это звучит так, как будто для отдельных слов используется поиск по хэшу O (1), но затем используется сканирование O (n) для объединения результатов с ограничением в 40 000 документов. Я предполагаю, что алгоритм сокращения карты используется для разделения этой работы, чтобы пользователь получал мгновенные результаты.
Крис Датроу
Одним из популярных алгоритмов является алгоритм ранга голубя. Хотя я мало что об этом знаю.
alienCoder
3
Эта статья забавна: «В этой статье мы представляем Google, прототип ...». Думаю, Google не всегда была мегакорпорацией.
Buttons840
не знаю Lucene, но один вопрос: ранжирование происходит при каждом поиске? Или он поддерживает предварительный рейтинг документов? Если он поддерживает документы в соответствии с рангом заранее, как он поддерживает запрос с несколькими словами?
Викас Прасад
Ссылка сейчас не работает. @alienCoder
CEGRD,
20

Одним словом: индексация.

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

То же самое различие между структурой данных списка O (N) и структурой данных хеш-таблицы O (1). Список должен пройти через всю коллекцию, чтобы найти то, что вам нужно. В хэш-таблице есть индекс, который позволяет точно определить, где находится нужный элемент, и просто извлечь его.

Обновить:

Я не уверен, что вы имеете в виду под «поиском по индексу Lucene намного быстрее, чем поиск по индексу MySQL».

Я предполагаю, что вы используете MySQL «WHERE document LIKE '% фраза%'» для поиска документа. Если это правда, то MySQL должен сканировать таблицу для каждой строки, которая будет O (N).

Lucene анализирует документ на токены, группирует их в n-граммы по вашему указанию и вычисляет индексы для каждого из них. Это O (1), чтобы найти слово в проиндексированном документе Lucene.

Duffymo
источник
10
Да, я понимаю часть индексации, но опять же, поиск по индексу lucene намного быстрее, чем поиск по индексу mysql. Как это случилось
Мидхат
9

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

Пример :

Файл 1: оперативная память - это основная память.

Файл 2: жесткие диски - это дополнительная память.

Lucene создает обратный индекс, что-то вроде

Файл 1:

Срок: случайный

Частота: 1

Место: 0

Срок: Память

Частота: 2

Результат: 3

Результат: 6

Таким образом, он может быстро искать и извлекать искомый контент. Когда для поискового запроса слишком много совпадений, он выводит результат на основе веса. Рассмотрим поисковый запрос «Основная память», он ищет все 4 слова по отдельности, и результат будет примерно таким:

Основной

Файл 1: Частота - 1

объем памяти

Файл 1: Частота - 2

Файл 2: Частота - 1

Результатом будет File1, за которым следует File2 . Чтобы перестать увлекаться утяжелением наиболее распространенных слов, таких как «и», «или», «the», он учитывает обратную частоту документа (т. Е. «Уменьшает вес слова, которое наиболее популярно в наборе документов).

Том Тейлор
источник