Поиск с привязкой к местности при помощи Apache Lucene и Solr

Расширение возможностей поисковых систем путем сочетания текстовых и географических данных

В настоящее время все больше людей использует поисковые сервисы с привязкой к местности для таких задач, как, например, поиск ближайшей кофейни при помощи смартфона с GPS, поиск друзей через социальную сеть или компаний, предоставляющих грузовики для доставки определенного груза. Раньше разработка подобных сервисов подразумевала использование дорогих коммерческих решений и услуг экспертов-географов. Однако недавно географические возможности были добавлены в популярную открытую поисковую библиотеку Apache Lucene и созданный на ее основе мощный поисковый сервер Apache Solr. В этой статье участник обоих проектов Грант Ингерсолл рассказывает об основах географического поиска и демонстрирует применение его возможностей при создании приложений, поддерживающих привязку к местности.

Грант Ингерсолл, технический специалист, Lucid Imagination

Grant IngersollГрант Ингерсолл (Grant Ingersoll) является основателем и техническим сотрудником компании Lucid Imagination. Его профессиональные интересы как разработчика включают такие вопросы, как информационный поиск, машинное обучение, категоризация и извлечение текста. Кроме того, Грант является разработчиком и представителем проектов Apache Lucene и Apache Solr, а также одним из основателей проекта Apache Mahout, посвященного машинному обучению.



31.12.2010

Местоположение и еще раз местоположение. Подобно тому, как местоположение имеет ключевое значение при выборе жилья, его использование в поисковых системах может существенно повысить эффективность нахождения нужной пользователю информации. Представим себе, что вы создали сайт-справочник для поиска компаний. Если пользователь ищет компании, предоставляющие услуги сантехников, сервис должен в первую очередь выдавать организации, находящиеся поблизости от его дома. Туристические сайты должны позволять туристам искать интересующие их объекты поблизости от их места отдыха, например, чтобы упростить поиск местных развлечений. В свою очередь, социальные сети могут использовать географическую информацию, чтобы помочь пользователям связываться с друзьями. С широким распространением устройств, определяющих местонахождение, таких как автомобильные спутниковые системы и фотокамеры с поддержкой GPS, возникло множество бесплатных картографических сервисов, и у вас появились широкие возможности для создания геоинформационных систем (ГИС), предоставляющих возможности поиска пользователям.

Область применения географической информации не ограничиваются поиском, но в этой статье рассказывается только о ее использовании для расширения возможностей поисковых приложений при помощи библиотек Apache Lucene и Apache Solr. Вы можете спросить, зачем использовать поисковую систему? Это не является строгим требованием, учитывая наличие хороших доступных ГИС, среди которых несколько бесплатных. Однако использование поисковой системы в качестве основы для вашего приложения открывает доступ к ряду мощных возможностей, имеющих преимущества над другими подходами. Поисковые системы способны эффективно комбинировать структурированные и неструктурированные данные, позволяя пользователям задавать запросы в произвольной форме (например, указывать названия объектов), в то же время фильтруя или изменяя результаты в зависимости от географической информации. Например, туристический сайт может предоставлять возможность найти все четырехзвездочные отели в Бостоне, штат Массачусетс, в описании которых встречаются слова "комфортная кровать" и "круглосуточное обслуживание", и при этом возвращать результаты в течение секунды. Поисковая система, например, Apache Solr, может также предоставлять возможности категоризации (информация о Solr и категориях приведена в разделе Ресурсы), подсветки, а также проверки орфографии, что помогает пользователям с максимальной эффективностью находить желаемую информацию.

Мы начнем с краткого обзора базовых понятий Lucene, оставив остальные детали для самостоятельного изучения. После этого мы рассмотрим основные аспекты геоинформационного поиска. ГИС - это обширная тема, на которую можно написать множество статей, поэтому мы уделим основное внимание лишь ключевым понятиям, которые легко объясняются в контексте нахождения сервисов, людей и других объектов. В конце статьи обсуждаются некоторые подходы к индексации и поиску географической информации с использованием Lucene и Solr. Все основные понятия в статье объясняются на реалистичных, но простых примерах, заимствованных из проекта OpenStreetMap (OMS, см. раздел Ресурсы).

Основные понятия в Lucene

Apache Lucene - это высокопроизводительная поисковая библиотека, написанная на Java™. В свою очередь, Solr представляет собой поисковый сервер, использующий Lucene и предоставляющий возможности поисковых возможностей, в частности, поиск по категориям, через протокол HTTP. Оба продукта выпускаются под лицензией Apache Software License, допускающей применение в коммерческих проектах. Более подробная информация о возможностях обеих библиотек и их API приведена по ссылкам в разделе Ресурсы.

В основе как Lucene, так и Solr лежит представление информации в виде документов. Каждый документ представляет собой одно или несколько полей, а также необязательное значение boost, определяющее степень его важности. Поля служат для хранения индексируемой информации, а также метаданных, в которых описывается, как именно Lucene должен обрабатывать содержимое поля и его важность. Выбор того, как именно информация должна представляться в виде документов и полей, остается за вами и, как правило, определяется тем способом доступа и критериями поиска данных в документах. Lucene и Solr поддерживают разные связи типа "один-к-одному" и "один-к-многим" между разными информационными элементами. Например, Web-страница может быть представлена в виде документа с такими полями, как заголовок, ключевые слова и тело. Если же речь идет о книге, то каждая страница может храниться в виде отдельного документа. Как вы увидите ниже, подобные различия оказываются важными при представлении географической информации в пригодном для поиска виде. Содержимое поля может индексироваться, что позволяет использовать его для поиска, или храниться в виде обычного текста. Индексированные данные также могут анализироваться для генерации термов (term), иногда также называемых токенами (token). На термах основан механизм подстановок (lookup); они также используются в процессе поиска. Как правило, но не всегда, они представляют собой отдельные слова. Если вас интересует более подробная информация об основных понятиях Lucene и Solr, обратитесь к разделу Ресурсы.

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

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


Основные понятия геопространственного поиска

Первое и главное, с чем необходимо определиться при создании системы с поддержкой геопространственного поиска — это то, какие пространственные данные должны быть представлены в приложении. Часто эти данные представляются в соответствии с некоторой системой географических координат, например, в виде широты, долготы и высоты над уровнем моря, или почтового индекса, либо названия улицы и номера дома. При этом чем строже формализация системы представления данных, тем проще процесс создания приложения. Например, в старой народной песне поется "Over the River and Through the Woods to Grandmother's house we go". В этих стихах (см. раздел Ресурсы) содержится немало географической информации, однако она совершенно бесполезна с точки зрения любой геоинформационной системы, которая не знает, о какой реке или о каком лесе идет речь. Гораздо полезнее было бы точное указание маршрута к дому бабушки, включающее исходную точку и точный адрес назначения. При этом системы, которые способы распознавать и правильно представлять более общие инструкции и оперировать неточно описанными географическими объектами, например, "переправиться через реку" или "около того коричневого дома", также могут оказаться весьма полезными, однако их обсуждение выходит за рамки этой статьи.

Многие ГИС позволяют не только работать с сырыми координатами объектов, но и добавлять информацию, относящуюся к определенным точкам на карте. Например, навигационные системы могут использовать упорядоченные массивы точек на карте, представляющих собой маршрут из пункта А в пункт Б. В свою очередь, метеоприложения могут наносить на карту данные о выпадении осадков или сложных погодных условиях, делая эту информацию доступной в качестве результатов поиска по местоположению. При этом можно использовать условные обозначения областей компактного проживания людей, такие как зоны почтовых индексов, телефонных кодов, а также города и страны. Пользователи системы OpenStreetMap (OSM) могут наносить новую и редактировать существующую информацию на базовую карту, например, описания интересных мест и даже улиц. Можно легко вообразить множество других динамических и многофункциональных приложений, представляющих возможности интеграции подобной картографической информации и отслеживания ее изменений во времени.

Представление пространственных данных

Вне зависимости от того, какая именно информация нанесена на карту или связана с географическими объектами, для реализации поиска эти данные должны быть представлены эффективным способом. Существует несколько способов хранения информации о точках на карте, но мы рассмотрим только те, которые поддерживаются Lucene. Первый и главный момент заключается в том, что многие разновидности пространственных данных могут храниться в "сыром" формате и, тем не менее, прекрасно использоваться при поиске. Например, для представления названия города Сиракузы вполне подойдет строка Сиракузы, а пользователи, которые наберут ее в строке поиска, получат искомые документы, содержащие упоминание об этом городе. На практике именно так чаще всего хранятся наименования объектов, в том числе городов, штатов, а также почтовые индексы. Учтите, что термин "сырой формат" (raw data) совершенно не означает, что вы не можете преобразовывать данные, в частности, нормализовать их. Например, вполне разумно преобразовать все упоминания Нью-Йорка, например, New York, к единому представлению SyracuseNY.

Перед тем как переходить к рассмотрению представлений данных, используемых в Lucene, важно отметить, что во всех представлениях необходимо учитывать пространственные координаты объектов (см. раздел Ресурсы). В США пространственные координаты чаще всего задаются по Всемирной Геодезической Системе (WGS 84, см. раздел Ресурсы). Несмотря на возможность преобразования координат, указанных в разных системах, лучше хранить все данные в одном представлении. Ниже будет подразумеваться, что мы работаем с единой системой представления пространственных координат.

Наибольший интерес в Lucene и Solr представляет хранение числовой пространственной информации, например широты и долготы (сокращенно шир/дол). Широта и долгота обычно представляются в виде градусов, минут и секунд, отсчитываемых от нулевого меридиана, проходящего через г. Гринвич в Англии, и, как правило, хранятся как минимум с двойной точностью. Например, географические координаты г. Сиракузы в штате Нью-Йорк выглядят следующим образом: 76.150026 градусов восточной долготы (или просто -6.150026 градусов долготы) и 43.049648 градуса северной широты.

Для ряда приложений хранение широты и долготы каждого географического объекта может привести к необходимости индексации большого числа термов. Это не обязательно имеет критическое значение, однако, во-первых, может существенно замедлять поиск, а во-вторых, как будет показано ниже, далеко не всегда является необходимым. Во многих картографических приложениях важна только возможность поиска в некоторой области карты, поэтому достаточно хранить приближенные координаты, что позволяет сократить объем индексов без существенного ухудшения результатов поиска. Для достижения нужного баланса между точностью и производительностью географические координаты часто разбивают на т.н. декартовы уровни. Каждый уровень — это фактически уровень масштабирования определенной области на карте. Например, уровень 2 с центром над США, скорее всего, будет включать весь Североамериканский континент, а уровень 19 — двор чьего-то дома. Если быть более точным, то каждый уровень делит карту на номер уровня квадратов или ячеек. Каждой ячейке присваивается номер и индекс внутри документа. Ниже будет рассказано о том, как использовать эту информацию для повышения производительности поиска.

Широта и долгота в Lucene часто хранятся в виде двух отдельных полей, и в некоторых случаях это может сказываться на производительности. При необходимости широта и долгота могут быть представлены в виде единого строкового поля с кодировкой Geohash (см. раздел Ресурсы). Преимущество кодов Geohash состоит в возможности получения нужной точности координат простым отбрасыванием символов в конце строки. Во многих случаях объекты, находящиеся поблизости друг от друга на карте, имеют общие префиксы в представлении. Например, для г. Сиракузы (штат Нью-Йорк) сервис geohash.org выдаст строку dr9ughxjkrt4b, а для его пригорода под названием Цицеро (Cicero) - dr9veggs4ptd3. Как видите, оба хэш-кода начинаются с префикса dr9.

До этого моменты мы рассматривали только точки на карте, однако во многих геоинформационных приложениях не менее важно оперировать объектами, имеющими сложную форму, маршрутами и другими структурами данных. На данный момент подобные объекты выходят за рамки возможностей Lucene и Solr. Более подробную информацию о них можно найти по ссылкам в разделе Ресурсы.


Сочетание текстовых и пространственных данных при поиске

После индексации данные становятся доступными для поиска. При этом можно выделить как минимум пять различных сценариев использования данных.

  • Вычисление расстояния от исходной точки до одной или нескольких точек назначения.
  • Ограничивающий фильтр: поиск всех документов, относящихся к указанной области.
  • Сортировка: упорядочивание результатов поиска по расстоянию от заданной точки.
  • Повышение релевантности: использование расстояния при ранжировании документов (при этом ранг должен также учитывать другие возможные факторы).
  • Разбор запросов: получив на вход адрес или другое описание местоположения, необходимо представить запрос в форме, которая позволит выполнить поиск по индексированным данным.

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

Вычисление расстояний

При вычислении расстояний в ГИС-приложениях важно четко представлять себе сильные и слабые стороны каждого из вычислительных методов. Все методы могут быть разделены на три группы, различающиеся по способу моделирования земной поверхности. В некоторых случаях допустимо представлять Землю в виде плоской поверхности, жертвуя точностью вычислений в пользу скорости. При использовании этой модели большинство подсчетов сводятся к различным вариациям теоремы Пифагора. Плоская модель, как правило, применима при вычислении расстояний между объектами, находящимися в непосредственной близости друг от друга и на значительном удалении от полюсов Земли. В других случаях можно использовать сферическую модель поверхности, при которой вычисления производятся по формуле расстояния по дуге большого круга (great-circle distance, см. раздел Ресурсы). Эта формула вычисляет кратчайшее расстояние между любыми двумя точками, лежащими на поверхности сферы. Эта модель имеет преимущества при вычислении расстояния между удаленными точками с повышенной точностью. Наконец, можно использовать эллипсоидную модель Земли и соответствующую ей формулу Винсенти (Vincenty formula, см. раздел Ресурсы). Она позволяет вычислять расстояния с точностью до полумиллиметра, однако для большинства приложений такая точность не окупает сложности вычислений.

Точность вычислений: от дюймов до миль

Точность вычисления расстояний, как правило, определяется нуждами приложения. В некоторых случаях погрешность величиной в милю не является проблемой, а других — нельзя отклоняться даже на считанные миллиметры. Например, евклидово расстояние может быть недостаточно точной метрикой при измерении существенных расстояний, в частности, между двумя штатами. Более того, даже вычисление по формуле гаверсинуса (расстояние по дуге большого круга) может приводить к недопустимой погрешности, поскольку Земля по своей форме ближе к эллипсоиду, чем к сфере. В таких ситуациях может иметь смысл использовать формулу Винсенти (Vincenty). Для других приложений значение может иметь только сравнительный порядок результатов, поэтому можно использовать, например, квадрат евклидова расстояния (который, строго говоря, вообще не является метрикой расстояния), тем самым избегая вычисления квадратного корня.

Разумеется, существуют и другие метрики, например, манхэттенское расстояние (Manhattan distance), которое представляет собой длину маршрута, напоминающего по своей форме маршрут такси в Манхэттене (т.е. все повороты совершаются под прямым углом). Однако в этой статье мы ограничимся двумя способами вычисления расстояний: на основе плоской и сферической модели Земли, оставив остальные методы для самостоятельного изучения. Кроме того, в статье игнорируется такой фактор, как высота над уровнем моря, хотя он может играть важную роль в некоторых приложениях. За более подробной информацией о вычислении расстояний в географии обратитесь к разделу Ресурсы.

Ограничивающий фильтр

Многие приложения предоставляют возможности поиска информации, охватывающей миллионы точек на карте. Если осуществлять поиск документов, содержащих нужные ключевые слова и находящиеся в необходимой близости от местоположения пользователя, путем полного перебора географических точек, то это займет колоссальное количество времени. Гораздо логичнее сначала ограничить набор документов, а уже затем выбирать нужные документы из этого набора. Если приложение оперирует только данными широты и долготы, то можно сузить область поиска, передав приложению интервалы географических координат, в которые должны попадать документы. Пример такого метода показан на рисунке 1, на котором полупрозрачный прямоугольник представляет собой область поиска вокруг центра Чарльстона, Южная Каролина.

Рисунок 1. Пример ограничивающего фильтра с исходной точкой в центре Чарльстона
Downtown Charleston, S.C., courtesy OpenStreetMap

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

Разбор запросов

Разбор (parsing) – это процесс определения ключевых слов, содержащихся в запросе, а также того, какие части запроса содержат информацию, относящуюся к определению местоположения. Последнее также называется геокодированием (см. Ресурсы). В данной статье геокодирование рассматривается исключительно в контексте разбора запросов, однако оно может применяться при индексации. Рассмотрим следующие примеры пользовательских запросов:

  • 1600 Пенсильвания ав. Вашингтон, округ Колумбия (DC)
  • 1 Вашингтон ав. Филадельфия, Пенсильвания
  • "Mall of America", 60 Восточный Бродвей, Блумингтон, MN 55425
  • Рестораны около "Mall of America"
  • Рестораны внутри "Mall of America"

Первые два запроса позволяют задуматься о следующих интересных моментах:

  • В отличие от обычных текстовых запросов, в географических запросах практически всегда следует учитывать порядок ключевых слов.
  • Gazetteers и другие географические ресурсы, например, GeoNames (см. раздел Ресурсы), могут оказаться весьма полезными при конвертации адресов в точки на карте. Подобные ресурсы часто предоставляют списки интересных географических объектов, например, "Белый Дом".
  • Очень важно либо нормализовывать аббревиатуры, такие как "ав." или "DC", либо использовать списки синонимов, используемых пользователями при написании адресов.

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

Несмотря на все сложности геокодирования, существует ряд сервисов для преобразования адресов в пункты на карте. В число подобных повсеместно используемых сервисов входят API Google Maps и GeoNames (см. раздел Ресурсы). К сожалению, работа с такими сервисами заставляет вас соблюдать правила их использования, которые часто ограничивают число обращений, а также связана с расходом трафика. При создании серьезной системы имеет смысл задуматься о разработке собственного сервиса. Создание сервиса разрешения адресов выходит за рамки этой статьи, но имейте в виду, что данные GeoNames можно загрузить бесплатно, точно так же, как и данные других географических ресурсов, например, CIA Factbook (см. раздел Ресурсы). Имея качественные данные, следует начать с базовых функций, таких как распознавание адресов, городов и штатов, а затем переходить к другим географическим объектам и работать над надежной обработкой ошибок. Не забывайте вести журналы учета запросов, которые со временем превратятся в ценный ресурс для написания кода разбора запросов, какими бы разнообразными они ни были. Не забывайте, что в поисковых приложениях важно уметь угадывать намерения пользователя, одновременно запрашивая уточнения запроса подобно тому, как это делает Google Maps (рисунок 2).

Рисунок 2. Попытки угадать намерения пользователя и уточняющий запрос в Google Maps
Mall of America Did You Mean Screen Capture

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


Подготовка к запуску примеров

Для запуска примеров к этой статье необходимо установить следующее программное обеспечение:

Также необходимо загрузить исходный код примеров (см. раздел Загрузка), который включает копию Apache Solr и все необходимые библиотеки. Выполните следующие команды:

  1. unzip sample.zip
  2. cd geospatial-examples
  3. ant install
  4. запустите Solr: ant start-solr (для остановки Solr выполните команду ant stop-solr)
  5. перейдите по адресу http://localhost:8983/solr/admin в браузере, чтобы убедиться, что Solr запустился успешно. Вы должны увидеть страницу административного интерфейса с текстовым полем для выполнения запросов.

Установив и запустив Solr, можно приступать к реализации поиска с привязкой к местности в Lucene. Команда install должна загрузить набор демонстрационных данных из проекта OSM, которые я разместил на странице http://people.apache.org/~gsingers/spatial/. Для примеров к этой статье были включены данные, относящиеся к четырем точкам на карте США, представляющие интерес для меня лично (ссылки на OSM находятся внутри файлов).

  • г. Сиракузы, штат Нью-Йорк
  • центр Миннеаполиса, штат Миннесота
  • окрестности торгового центра "Mall of America" в Блумингтоне, Миннесота
  • центр Чарльстона, Южная Каролина

Для демонстрации основных функций географического поиска я написал фрагмент кода для индексации данных OSM в Solr, а также для привязки некоторых простых фактов к заданным точкам на карте (см. файл syracuse.facts в директории data). Моей задачей было показать, как можно сочетать работу с неструктурированным текстом и пространственными данными при реализации приложений для поиска с привязкой к местности. Обратите внимание, что я использую Solr версии 1.5-dev, которая на данный момент находится в разработке (последней была выпущена версия 1.4).


Индексация пространственной информации в Lucene

В Lucene 2.9 были добавлены две возможности, которые играют важную роль при поиске с привязкой к местности. Первой из них является улучшенный поиск по численным интервалам, а также усовершенствованная фильтрация, которые часто используются при работе с ограничивающими фильтрами. Во-вторых, в Lucene появился новый модуль contrib, включающий в себя самостоятельный проект, который ранее назывался Local Lucene (см. Ресурсы). Этот модуль находится в директории contrib/spatial и загружается по ссылке в разделе Загрузка. Он предоставляет средства для создания декартовых уровней и кодов Geohash, а также функции для формирования запросов к Lucene и объектов-фильтров.

Перед тем, как переходить к рассмотрению кода индексации данных, необходимо определить, как вы оцениваете работу с данными и то, с какими объемами данных вам придется работать в вашем приложении. Например, для большинства приложений, работающих со скромным числом документов (скажем, до 10 миллионов) достаточно индексации по широте/долготе, а также использования простых запросов с числовыми диапазонами. При этом более крупным приложениям могут потребоваться более специфические методы, такие как декартовы уровни, для сужения числа ключевых слов, а также фильтруемых и ранжируемых документов. Кроме того, важно продумать формат хранения данных. Одни алгоритмы определения расстояния используют данные в радианах, другие — в градусах. Таким образом, имеет смысл преобразовать все значения широты и долготы в радианы на этапе индексации вместо того, чтобы заниматься этим в процессе поиска. При этом вам может потребоваться больше места на диске (и, возможно, в оперативной памяти), если нужно хранить данные в обоих форматах. Наконец, следует определиться, интересует вас поддержка категорий (facets), сортировки и ранжирования с привязкой к местности или географическую информацию достаточно использовать только для фильтрации? Если интересует, то не исключено, что вам придется также рассмотреть альтернативные форматы хранения.

Эта статья призвана лишь продемонстрировать основные аспекты поиска, а не готовый к серьезному использованию продукт, поэтому индексация с применением Geohash, декартовых слоев, а также работа с широтой и долготой будут продемонстрированы в одном наборе Java-файлов. Вначале обратите внимание на ряд значений, определенных в схеме Solr (файл geospatial-examples/solr/conf/schema.xml) для работы с данными OSM. Основные поля для хранения географических данных приведены в листинге 1.

Листинг 1. Пример схемы Solr
<!-- Широта -->
   <field name="lat" type="tdouble" indexed="true" stored="true"/>
<!-- Долгота -->
   <field name="lon" type="tdouble" indexed="true" stored="true"/>
<!--
   Широта/долгота заданы в радианах.
   В реальном приложении следует использовать поля типа "copy"
   вместо передачи по сети -->
   <field name="lat_rad" type="tdouble" indexed="true" stored="true"/>
   <field name="lon_rad" type="tdouble" indexed="true" stored="true"/>
<!-- Для этого атрибута может понадобиться специальный тип поля -->
   <field name="geohash" type="string" indexed="true" stored="true"/>
<!-- Высота над уровнем моря -->
   <field name="ele" type="tfloat" indexed="true" stored="true"/>
<!-- Информация, относящаяся к декартовым уровням -->
   <dynamicField name="tier_*"  type="double" indexed="true"  stored="true"/>

Lucene и Solr

В этой статье используется схема Solr для демонстрации индексируемых полей, однако для этой цели вполне хватило бы возможностей Lucene. Например, tdouble – это не что иное, как тип NumericField в Lucene с показателем точности 8.

Как видите, значения широты и долготы сохраняются в полях типа tdouble. Тип tdouble — это double, представленный внутри в виде структуры Trie. Эта структура данных может использоваться Lucene для сокращения числа термов, проверяемых при диапазонных вычислениях (ограничивающих фильтрах), несмотря на то, что она добавляет термы в индекс. Коды Geohash сохраняются в виде простых, не проанализированных объектов string, поскольку нас интересует только строгое соответствие. Высота над уровнем моря, хотя она не требуется в приложениях подобного рода, хранится в полях типа tfloat, т.е. float в виде Trie. Наконец, динамическое поле tier_* позволяет приложению динамически добавлять декартовы уровни без необходимости предварительного декларирования. Остальные поля метаданных, используемые в процессе индексации, остаются вам для самостоятельного изучения.

Код, отвечающий за индексацию данных, находится в дереве файлов внутри архива sample.zip. Класс Driver представляет собой утилиту командной строки, служащую для запуска процесса индексации. Сама индексация выполняется классом OSMHandler, который реализует SAX-интерфейс ContentHandler. Наибольший интерес в OSMHandler представляет метод startElement(), который мы разобьем на три секции. В первом примере, показанном в листинге 2, выполняется индексация по широте и долготе, а также преобразование значений в радианы.

Листинг 2. Пример индексации широты и долготы
//... текущим элементом является SolrInputDocument
double latitude = Double.parseDouble(attributes.getValue("lat"));
double longitude = Double.parseDouble(attributes.getValue("lon"));
current.addField("lat", latitude);
current.addField("lon", longitude);
current.addField("lat_rad", latitude * TO_RADS);
current.addField("lon_rad", longitude * TO_RADS);

Как видите, в индексации широты и долготы нет ничего сложного. Далее мы перейдем к кодированию координат в формат GeoHash (листинг 3).

Листинг 3. Пример индексации кодов Geohash
//...
//см. статью http://en.wikipedia.org/wiki/Geohash
String geoHash = GeoHashUtils.encode(latitude, longitude);
current.addField("geohash", geoHash);

В примере использования Geohash, показанном в листинге 3, используется метод GeoHashUtils.encode() (также существует обратный метод decode), который предоставляется пакетом contrib в Lucene. Этот метод преобразует широту и долготу в одно строковое значение, которое затем добавляется в Solr. Наконец, для добавления поддержки декартовых уровней, использующихся в классе OSMHandler, делается следующее:

  • В конструкторе создается n экземпляров класса CartesianTierPlotter. Каждый экземпляр соответствует своему уровню индексации.
  • В методе startElement() выполняется цикл по всем экземплярам CartesianTierPlotter, в котором извлекается идентификатор каждого элемента сетки, включающего координаты текущего элемента OSM. Пример кода приведен в листинге 4.
    Листинг 4. Пример индексации декартовых уровней
    //...
    //Декартовы уровни
    int tier = START_TIER; //4
    //Создание нескольких уровней. 
    //Каждый новый уровень имеет повышенную точность по сравнению с предыдущим
    for (CartesianTierPlotter plotter : plotters)
       {current.addField("tier_" + tier, plotter.getTierBoxId(latitude, longitude));
    tier++;
    }

Как правило, большинство запросов затрагивают только один уровень, поэтому работа с несколькими уровнями не представляет проблем. Вам нужно выбрать число требуемых уровней исходя из того, насколько точным должен быть поиск. Если вы просмотрели остальной код индексирования, то, наверное, заметили, что он содержит ряд других метаданных, относящихся к данным OSM. В текущей реализации индексируются только два типа данных OSM: вершина (node) и путь (way). Вершинами называются точки на карте, имеющие собственные координаты, в то время как путь — это набор вершин, связанных между собой, например, улица. Если вас интересует более подробная информация о файлах OSM, то обратитесь к документу "OSM Data Primitives" (базовые типы данных OSM), ссылка на который приведена в разделе Ресурсы.

Что собой представляет класс CartesianTierPlotter?

Задача класса CartesianTierPlotter заключается в том, чтобы взять проекцию Земли (в данном случае используется синусоидальная проекция, см. раздел Ресурсы), географические координаты, преобразовать ее в координатные сетки, используемые на декартовых уровнях, и присвоить каждой ячейке сеток уникальный идентификатор. В процессе поиска можно указывать эти идентификаторы для ограничения набора документов.

Теперь, когда у вас есть представление о создании документов Solr с географической информацией, пришло время запустить приложение. Класс Driver принимает на вход файлы данных и фактов, а также URL, по которому выполняется Solr, после чего передает выполнение классу OSM2Solr. Этот класс использует Java-клиент для Solr под названием SolrJ, который получает документы, созданные классом OSMHandler, и отправляет их серверу Solr. Класс Driver может запускаться из командной строки либо при помощи команды ant index (в этом случае вся работа по запуску ложится на Ant). После окончания выполнения перейдите по адресу http://localhost:8983/solr/select/?q=*:* в браузере и убедитесь, что Solr нашел 68945 документов. Постарайтесь внимательно рассмотреть полученные результаты и разобраться с форматом их представления.

Это лишь один из множества способов получения среза данных OSM. Далее мы перейдем к обсуждению использования данных в демонстрационном приложении.


Поиск по местонахождению

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

Способы вычисления расстояния

Ранжирование и сортировка документов по удаленности от заданной точки являются типичными требованиями для геоинформационных приложений. Lucene и Solr предоставляют ряд возможностей для выполнения этих действий (см. раздел Ресурсы). Lucene включает функции для сортировки и фильтрации на основе формулы дуги большого круга (формула гаверсинуса, см. классы DistanceUtils и DistanceFieldComparatorSource), а Solr - ряд функций класса FunctionQuery для вычисления расстояний, в том числе по следующим методам:

  • метод большого круга (гаверсинус и гаверсинус Geohash);
  • евклидово расстояние и его квадрат;
  • манхэттенское расстояние и другие прямоугольные метрики.

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

Выше было определено несколько полей для хранения данных OSM, в том числе lat/lon, lat_rad/lon_rad и geohash. Теперь эти поля можно использовать при поиске и ранжировании.

  • hsin (метод большого круга): http://localhost:8983/solr/select/?q=name:Minneapolis AND _val_:"recip(hsin(0.78, -1.6, lat_rad, lon_rad, 3963.205), 1, 1, 0)"^100
  • dist (евклидово расстояние и манхэттенское расстояние): http://localhost:8983/solr/select/?q=name:Minneapolis AND _val_:"recip(dist(2, lat, lon, 44.794, -93.2696), 1, 1, 0)"^10
  • sqedist (квадрат евклидова расстояние): http://localhost:8983/solr/select/?q=name:Minneapolis AND _val_:"recip(sqedist(lat, lon, 44.794, -93.2696), 1, 1, 0)"^100
  • ghhdist (гаверсинус Geohash): http://localhost:8983/solr/select/?q=_val_:"recip (ghhsin(geohash(44.79, -93), geohash, 3963.205), 1, 1, 0)"^100

В этих примерах сочетается использование ключевых слов с обращением к классу FunctionQuery для получения результатов, в которых ранг документов вычисляется как на основе слов, так и расстояния. Для того чтобы увидеть влияние обоих факторов на ранг документов, добавьте параметр &debugQuery=true в каждый из запросов и посмотрите на пояснения, сгенерированные Solr. Учтите, что эти запросы - лишь примеры использования функций Solr. Если вас интересует полное описание этих и других функций FunctionQuery, обратитесь к разделу Ресурсы. С их помощью вы можете влиять на приоритеты факторов и варьировать запросы по своему усмотрению.

Что касается сортировки по расстоянию, то Solr предоставляет единственную возможность, которая фактически представляет собой обходной путь решения проблемы отсутствия упорядочивания по результатам вычисления функции. Кроме того, пока нет поддержки собственных типов полей (FieldType). Тем не менее решение оказывается достаточно простым. Достаточно просто использовать те же запросы, как и ранее, но обнулить ключевые слова (q=name:Minneapolis^0 AND _val_:...). В результате вклад ключевых слов в ранг документов будет нулевым, но сами документы будут возвращены, и их ранг будет определяться исключительно значением функции. Если вас интересует более основательное решение, то следите за тем, когда будет реализована поддержка FieldType, после чего вам не понадобится очищать список ключевых слов в запросах.

Рассмотрев сортировку и ранжирование, самое время переходить к фильтрации.

Фильтрация

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

Таблица 1. Методы фильтрации
НазваниеОписаниеПример
Диапазонный методДиапазон – это прямоугольная область, заданная при помощи географических координат (широты и долготы). Для повышения производительности при использовании этого метода следует использовать тип TrieField (NumericField).http://localhost:8983/solr/ select/?q=*:*&fq=lon:[-80 TO -78]&fq=lat:[31 TO 33]
Метод на основе декартовых уровнейМетод получает на вход широту, долготу и расстояние, после чего определяет те ячейки сетки, которые находятся на не более чем указанном расстоянии от центра. Метод возвращает набор документов, относящихся к этим ячейкам. Реализация метода подробнее описана в заметке Что такое QParserPlugin?.http://localhost:8983/solr/ select/?q=*:*&fq={!tier x=32 y=-79 dist=50 prefix=tier_}
Дистанционный методМетод использует функцию frange в Solr, возможности QParserPlugin, а также функции вычисления расстояния (см. раздел Вычисление расстояний) для определения дистанции между двумя точками и сужения области поиска документов.http://localhost:8983/solr/ select/?q=*:*&fq={!frange l=0 u=400}hsin(0.57, -1.3, lat_rad, lon_rad, 3963.205)

Несколько слов о плотности

Плотность данных в заданном диапазоне часто играет важную роль при работе с приложением. Например, информация, с которой работает приложение для поиска компаний в Манхэттене (Нью-Йорк), размещена значительно плотнее, чем в случае города Баффало в Миннесоте (см. Ресурсы). Вследствие этого имеет смысл учитывать плотность при реализации фильтрующих функций, чтобы приложение могло выбирать расстояние максимально удачным образом. К сожалению, рассмотрение этого вопроса не укладывается в рамки данной статьи.

Возникает вопрос, какой из методов наиболее подходящий? Ответ зависит от плотности точек на карте (см. заметку Несколько слов о плотности), но, как правило, следует начинать с наиболее простого способа, а затем, если потребуется, переходить к уровням. Ключевую роль играет число термов, которые должны обрабатываться при вычислении диапазона, поскольку именно оно непосредственно определяет нагрузку на Lucene для ограничения результирующего набора документов.

Разбор запросов при помощи сервиса geonames.org

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

Что такое QParserPlugin?

В терминах Solr QParserPlugin - это подключаемый модуль (плагин) для разбора запросов. Многие функции в Solr реализуются в виде подключаемых модулей, и разбор запросов - не исключение. В этой статье используются три различных модуля, один из которых поставляется вместе с Solr ( FunctionRangeQParserPlugin ({!frange})), а остальные два (CartesianTierQParserPlugin ({!tier}) и GeonamesQParserPlugin) я написал самостоятельно. Исходный код обоих модулей находится в архиве с остальными примерами. Кроме того, модули были сконфигурированы для использования в Solr в файле solrconfig.xml. Обращение к ним через запросы выполняется следующим образом: {!имя_модуля [параметры]}[запрос], (параметры и запрос можно не указывать), например: {!tier x=32 y=-79 dist=50 prefix=tier_} или {!frange l=0 u=400}hsin(0.57, -1.3, lat_rad, lon_rad, 3963.205).

Класс для разбора запросов принимает следующие параметры:

  • topo. Сокращение от топоним (toponym, см. документацию по GeoNames). Этот параметр определяет искомое местонахождение. Является обязательным.
  • rows. Число результатов, ожидаемых от GeoNames. Необязательный параметр, значение по умолчанию - 1.
  • start. Начальный индекс результатов. Необязательный параметр, значение по умолчанию - 0.
  • lat. Имя поля широты, которое будет использоваться в качестве ValueSource для класса FunctionQuery. Если этот параметр задан, то также должен быть задан параметр lon.
  • lon. Имя поля долготы, которое будет использоваться в качестве ValueSource для класса FunctionQuery. Если этот параметр задан, то также должен быть задан параметр lat.
  • gh. Имя поля Geohash, которое будет использоваться в качестве ValueSource для класса FunctionQuery. Если этот параметр задан, то параметры lat/lon должны быть не заданы.
  • dist. Строковой параметр, задающий функцию вычисления расстояния. Допустимые значения: [hsin, 0-Integer.MAX_VALUE, ghhsin]. Если параметр geohash задан, то этот параметр игнорируется и используется функция ghhsin. Значение по умолчанию - 2 (евклидово расстояние).
  • unit - KM|M. Задает единицы измерения расстояния. KM обозначает метрическую систему измерения, M - английскую. Значение по умолчанию - M.
  • boost - float. Коэффициент повышения ранга в функциональных запросах. Значение по умолчанию - 1.

Исходный код этого примера находится в файле GeonamesQParserPlugin.java (сервер Solr, включенный в архив для загрузки, уже сконфигурирован). Запуск примера аналогичен выполнению CartesianTierQParserPlugin, которое было рассмотрено выше. Например, для поиска всех торговых центров, находящихся около Блумингтона (штат Миннесота) следует обратиться по URL http://localhost:8983/solr/select/?q=text:mall AND _query_:"{!geo topo='Bloomington, MN' lat=lat_rad lon=lon_rad dist=hsin}".

QParserPlugin позволяет сосредоточиться на разборе только той части запроса, которая относится к географии, в то время как текстовая часть запроса была разобрана стандартным образом.

GeonamesQParserPlugin можно расширять различным образом, например, добавлять поддержку почтовых индексов и других способов указания местонахождения. Кроме того, имеет смысл заняться обработкой ошибок, а также использовать базу данных GeoNames (см. раздел Ресурсы), чтобы не зависеть от вызовов Web-сервиса. Наконец, в настоящее время рассматривается вопрос добавления классов для разбора географических запросов непосредственно в Solr (см. раздел Ресурсы).


Что дальше?

В этой статье были продемонстрированы возможности Lucene и Solr для поиска, сортировки и фильтрации документов на основе точечной модели определения местоположения. Опираясь на этот фундамент, при разработчику серьезных поисковых приложений следует определиться с обеспечением масштабируемости, поддержкой пользовательских запросов и визуализацией результатов. Масштабируемость можно частично оценить на основе того, сколько термов необходимо анализировать при наложении ограничивающих фильтров. Кроме того, следует принять во внимание стандартные соображения, связанные с масштабируемостью поисковых приложений, например, следует ли поддерживать распределенные индексы или достаточно репликации. Более подробная информация о Lucene и Solr приведена по ссылкам в разделе Ресурсы.

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

Благодарности

Автор выражает благодарность коллегам по проектам Lucene/Solr Райану МакКинли (Ryan McKinley) и Йонику Сили (Yonik Seeley) за ценные замечания в процессе подготовки статьи.


Загрузка

ОписаниеИмяРазмер
Исходный код примеровj-spatial.zip52.4 МБ

Ресурсы

Научиться

Получить продукты и технологии

Обсудить

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Технология Java, Open source
ArticleID=605783
ArticleTitle=Поиск с привязкой к местности при помощи Apache Lucene и Solr
publish-date=12312010