Exploring Java: Lucene

Lucene – это open-source библиотека для полнотекстового поиска. К сожалению, документация к нему не всегда хорошо организована, и новичку бывает сложно сориентироваться среди десятков новых понятий и названий. В этом посте я попробую немного исправить ситуацию, вкратце описав, что есть что в мире Lucene.

Apache Lucene и смежные проекты

Сам по себе Lucene – это Java-библиотека, однако если вы не пишите для JVM, не спешите закрывать статью. Во-первых, существует огромное количество портов этой библиотеки на другие языки программирования. В частности, для .NET есть class-per-class порт, который так и называется – Lucene.net. Во-вторых, если вы не хотите мучиться с тонкостями API, Apache предлагает готовый поисковый сервер – Solr. Если вы создаёте сайт на PHP и просто хотите добавить в него эффективный поиск а-ля Google, то вероятнее всего Solr – это именно то, что вам нужно. Нельзя не упомянуть и о самом «навороченном» проекте из ветки Lucene - Nutch. Этот проект представляет из себя синтез Solr и великого и ужасного Hadoop - распределённой файловой системы со встроенным MapReduce. Проще говоря, Nutch переносит возможности Solr’а с одного сервера на целый кластер, так что если ваша цель – создать мини-гугль, то вы попали по адресу. Тем более что кроме собственно поиска Nutch включает в себя свой собственный crawler и ряд парсеров для наиболее популярных форматов документов (HTML, PDF, DOC и др.). Так или иначе, все эти проекты построены вокруг одной архитектуры, имеют единый язык запросов и схожие компоненты. Обо всём этом и пойдёт речь далее.

Как работают поисковые движки

В Information Retrieval (IR) встречаются различные задачи, связанные с поиском по тексту, однако нас будет интересовать только одна – поиск наиболее релевантных документов по набору ключевых слов. Такой вид поиска обычно называют полнотекстовым. Важно понимать, что IR не сводится только к полнотекстовому поиску, и движки вроде Lucene могут оказаться бесполезны для других задач, таких задач, как, например, поиск подстроки в строке. Задача эффективного полнотекстового поиска делится на две части: индексирование и собственно поиск. Обе эти стадии мы ещё обсудим ниже, но вначале поговорим о том, что находится между ними – о хранилище. Хранилище в большинстве современных поисковых движков организовано в виде так называемого обратного индекса (inverted index). Обратный индекс организован аналогично предметному указателю в конце книги – каждому слову соответствует список документов, в которых он встречается (если быть более точным, список ID этих документов):

Такая структура позволяет практически за константное время извлекать список документов, в которых встречается определённое слово. Сам список слов организован в виде либо префиксного дерева, либо хеш-мэпа. Кроме собственно номеров документов для каждого слова сохраняется ряд атрибутов, таких как все позиции, на которых встречается данное слово в данном документе (необходимы для подсветки и создания сниппетов), сдвиги относительно предыдущего слова (для обработки синонимов), ряд других встроенных атрибутов, а также произвольный payload – набор байт, которые программист может использовать по своему усмотрению:

Хотя при стандартном сценарии программисту нет необходимости работать напрямую с обратным индексом, Lucene предоставляет доступ к нему через методы termDocs и termPositions класса IndexReader (подробнее об API ниже). Обычно под текстовым документом мы понимаем просто именованный текст. Однако в терминологии Lucene документ представляет собой нечто большее, а именно набор пар поле-значение, где текст документа является всего лишь значением одного из полей. Среди других полей могут быть заголовок, авторы, краткое описание и вообще что угодно, что может быть представлено в текстовом формате. Кроме того, значением поля может быть число, и в том числе дата. Это оказывается особо полезным в сочетании с возможностью Lucene’а искать по интервалу. Например, можно указать год издания статьи и затем найти все статьи в период между 2005 и 2010-м годами.

По сути, индекс Lucene представляет собой базу данных с объектами и полями этих объектов. Однако база эта – документно-ориентированная, а это значит, что в отличие от реляционных баз объекты в ней не обязаны подчиняться какой-либо схеме. Каждый документ может иметь сколько угодно каких угодно полей, независимо от того, какие поля имеют другие документы. Здесь же стоит отметить, что Lucene имеет один большой недостаток по сравнению с традиционными БД – он не создаёт ID для документов. Все документы внутри Lucene имеют свой номер, доступный извне, однако при удалении документа и оптимизации индекса Lucene может переставить номера. Поэтому если необходимо ввести уникальный идентификатор для каждого документа, то лучше добавить дополнительное поле и генерировать ID-шники самостоятельно.

Индексирование

Индексирование документов, таких как PDF-файлы, происходит в 2 этапа: вначале из них извлекается текст, а затем уже этот текст анализируется, и полученные данные попадают в поисковый индекс.

К сожалению, сам по себе Lucene, в отличие от Solr и Nutch, не умеет работать ни с PDF, ни с каким бы то ни было другим сложным форматом файлов. Для извлечения текста из таких файлов вам придётся использовать другие библиотеки. При поиске таких библиотек можно отталкиваться от соответствующих плагинов Nutch’а. При индексировании текста он проходит несколько стадий. Во-первых, текст разбивается на токены, то есть токенизируется (tokenizing). В простейшем случае разбиение происходит по пробелам и знакам препинания, однако это поведение может регулироваться. Во-вторых, каждый токен приводится к своей морфологической основе (stemming): обрезаются окончания, распространённые суффиксы заменяются на стандартную форму и т.д. Например, слово «questioning» из примера выше будет преобразовано в «question». В дальнейшем это позволит игнорировать при поиске форму слова, выдавая более точные результаты. Преобразование происходит на основе ряда простых логических правил и не всегда даёт правильный с точки зрения лингвистики результат, однако в большинстве случаев это не играет значительной роли. В-третьих, из списка токенов выбрасываются так называемые stop-words – наиболее распространённые, но не несущие особой смысловой нагрузки слова. Для английского языка это такие слова как “a", “the", “and" и т.д. В-четвёртых, каждому токену присваивается ряд атрибутов, часть из которых в дальнейшем попадает в индекс, а часть – используется на более поздних стадиях, но отбрасывается при сохранении в индекс. (На самом деле в последних версиях Lucene даже сам токен рассматривается просто как атрибут некоторого объекта.) В Lucene все эти стадии объединены в так называемых анализаторах. Выбор анализатора зависит от нескольких параметров, и в первую очередь от языка текста. Ветвь contrib из репозитория Lucene предоставляет довольно интересный анализатор – SnowballAnalyzer. В отличие от прочих анализаторов, SnowballAnalyzer не заточен ни на один конкретный язык, а принимает название языка в виде строки в своём конструкторе. В сочетании с автоматическим определителем языка из проекта Tika, он может оказаться прекрасным решением для многоязычных корпусов текстов. Среди других анализаторов стоит выделить KeywordAnalyzer, который индексирует всё анализируемое поле как единый токен. Это может быть полезно для таких полей как номер телефона, ID, различные коды и т.д.

Поиск

При стандартном сценарии поиск сводится к трём стадиям: разбору строки запроса на ключевые слова, извлечению документов, где эти слова встречаются и сортировке полученных документов по релевантности. Однако, несмотря на кажущуюся простоту, каждая из этих стадий имеет свои особенности и подводные камни. Первое, что стоит запомнить, это то, что при разборе строки запроса она должна анализироваться точно так же, как и документы при индексировании. На уровне API это означает, что парсер запроса принимает в своём конструкторе анализатор. Очень важно, чтобы этот анализатор совпадал с тем, который использовался для индексирования, иначе вы рискуете не получить вообще никаких результатов. Например, предположим, что при индексировании цитаты Эйнштейна из первого примера вы использовали английский анализатор. Тогда в индекс пойдёт морфологическая основа слова «questioning», т.е. просто «question». Если же затем при поиске вы используете русский анализатор, то слово «questioning» не будет никак преобразовано, и Lucene попытается найти именно токен «questioning», а не «question». Естественно, такого токена в индексе нет, и запрос вернёт пустой список результатов. Поэтому если вы не планируете активно использовать многоязычные корпусы, самым простым и правильным способом будет жёстко задать анализатор, как при индексировании, так и при поиске. Второе, на что следует обратить внимание, это язык запросов. Возможно, не все знают, но Google предоставляет гораздо более широкие возможности, чем просто поиск по словам из запроса. По умолчанию поисковик ищет документы с любым из ключевых слов, а количество совпадений в запросе и документе используется только для вычисления релевантности. Тем не менее, вы можете заставить Google искать только документы с определённым словом, просто поставив перед ним знак «+». Аналогично, если вы не хотите видеть результаты с каким-то словом, вы можете поставить перед ним «-» и поисковик отфильтрует результаты, убрав из них документы с нежелательным токеном. Lucene не отстаёт от поискового гиганта и предоставляет свой, аналогичный язык запросов. Кроме указанных операторов Lucene поддерживает логические запросы с использованием AND и OR, символы замены (wildcards), нечёткий поиск (fuzzy search) и многое другое. Здесь ненадолго прервёмся и вспомним, как Lucene хранит документы. Как уже было сказано выше, он хранит их в виде списке пар поле-значение. Например, сохранённый документ может иметь вид:

• title: Einstein
• content: The important thing is not to stop questioning.

Так вот, на самом деле в индексе также хранятся не просто токены, а так называемые «термы» (terms). Терм представляет из себя точно такую же пару поле-значение, но в качестве значения хранится не всё поле, а отдельные токены. То есть приведённый выше документ в индексе будет храниться как список следующих термов (для простоты будем считать, что к токенам не были применены морфологические и другие преобразования):

• content: important
• content: is
• content: not
• content: questioning
• content: stop
• content: The
• content: thing
• content: to
• title: Einstein

Соответственно, при поиске Lucene выбирает документы не по токенам, а именно по термам. Термы могут быть заданы напрямую в запросе в виде «имя_поля:токен», например, «content:questioning» или «title:Einstein». Если же в запросе встречается не квалифицированный именем поля токен (т.е. просто «questioning»), то используется поле по умолчанию, задаваемое при создании парсера запросов. Стоит отметить, что поиск по термам, а не просто по ключевым словам, не является чем-то исключительным для Lucene. Google, например, использует такую же схему для хранения информации о проиндексированных сайтах. В частности, каждый документ имеет поле site, поэтому чтобы найти все упоминания слова «Lucene» на dev.by достаточно ввести в Google’е запрос «lucene site:dev.by». Полную информацию по языку запросов Lucene можно получить здесь. Понятно, что Lucene извлекает все документы, удовлетворяющие логически поисковому запросу, однако алгоритм вычисления релевантности и, соответственно, сортировки результатов не так уж прост. По сути, этот алгоритм основан на одной из моделей векторного пространства (Vector Space Model), о которых я уже когда-то писал, и дополнен некоторыми специфическими для Lucene фичами. Подробно прочитать про этот алгоритм можно прямо в JavaDoc для класса, реализующего его по умолчанию – Similarity. Кроме того, Lucene позволяет сортировать результаты не только по релевантности, но и по одному из полей. Правда, на эти поля налагаются определённые ограничения, в частности, они не должны быть токенезированы. Поэтому, например, если вы хотите искать по заголовку и, в то же время, иметь возможность получить отсортированный по тому же заголовку список результатов, то придётся создать два разных поля с одним значением, но разными настройками индексирования. Функционал сортировки результатов в Lucene сосредоточен в классе, который так и называется – Sort.

API

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

• Analyzer, а также его потомки – отвечают за токенезацию, морфологические преобразования, фильтрация стоп-слов и т.д.
• TokenStream – представляет интерфейс для работы с потоком токенов. В последних версиях представляет их себя набор ленивых списков атрибутов, для чего наследуется от AttributeSource. Наследники же самого TokenStream делятся на две крупные группы, представленные классами Tokenizer и TokenFilter.
• Directory – интерфейс, отвечает за хранилище для индекса. Чаще всего используются две имплементации – FSDirectory для дискового индекса и RAMDirectory для индекса в памяти.
• Document – документ Lucene.
• Field – поле документа. В конструкторе принимает как минимум 4 параметра – имя поля, значение и два флага, отвечающие за хранение оригинального поля и за способ анализа.
• IndexWriter – класс, используемый для добавления документов в индекс, а также для их удаления.
• IndexReader – инкапсулирует весь функционал по чтению из индекса. Используется другими классами для поиска, предоставляет доступ к обратному индексу и многое другое.
• IndexSearcher – название говорит само за себя.
• Query – внутреннее представление запроса.
• QueryParser – то, что преобразует String в Query.
• TopScoreDocCollector и ScoreDoc – используются для сохранения и итерирования по результатам поиска.

Подробный пример индексирования и поиска можно найти на StackOverflow. Для ещё более детального изучения данного движка крайне рекомендую признанный бестселлер Lucene in Action.

Помогаете devby = помогаете ИТ-комьюнити.

Засапортить сейчас.