«Дадата» с 2014 года пилит «Подсказки». Они помогают быстро и без ошибок вводить контактные данные: адреса, реквизиты банков и компаний, емейлы — вот это все.

Штука устроена затейливо, и мы решили о ней рассказать. Возьмем подсказки по адресам, потому что они самые сложные.

Справочники и индексация

«Подсказки» знают, что подсказывать, потому что у них есть гигантские справочники. Хоть статья эта о подсказках по адресам, для пользы дела перечислю и другие справочники «Дадаты».

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

Поисковый индекс — такой формат, при котором находить информацию можно оооочень быстро.

Физически индекс представляет из себя набор двух типов файлов:

• файлы с собственно индексом, по ним «Подсказки» ищут. Индексную часть мы держим в оперативной памяти, чтобы сервис был бодрым и подтянутым;
• файлы с данными. Из них «Подсказки» возвращают ответ.

Индекс и данные по адресам в сумме занимают 20 гигабайт. По компаниям примерно столько же, а остальные весят меньше.

Из официальных справочников для экономии убираем данные, по которым не ищем и которые не возвращаем. Также вычищаем дубли и очевидные ошибки. Например, в индексе по адресам нет:

• литер домов. В ФИАС колоссальное количество литер, которых на самом деле не существует;
• заведомо невозможных объектов вида «дом 21/2, стр 21/2».

Поиск адекватных подсказок

«Подсказки» работают довольно заковыристо. Для простоты разобью процесс на этапы и расскажу о каждом подробнее. Если останутся вопросы, спрашивайте в комментариях.

1. Поехали: человек вводит символы в поле «Подсказок».

2. Плагин «Подсказок» собирает запрос. Между человеком и сервером трудится диспетчер — jQuery-плагин «Подсказок» (исходный код на GitHub).

Плагин принимает данные для поиска, упаковывает в запрос и передает на сервер.

От себя плагин добавляет, сколько адресов вернуть. Число задают как параметр при интеграции «Подсказок». Если количество не указали, «Подсказки» возвращают 10 результатов. Больше 20 просить бесполезно — вернутся только 20 вариантов.

Также плагин передает параметры фильтрации, их тоже задают при интеграции «Подсказок». Вот какие фильтры существуют:

• по родителю (искать только по Московскому шоссе в Самаре);
• по уровню ФИАС (искать только населенные пункты);
• по типу объекта (полезно, потому что в ФИАС на уровне городов лежат посторонние объекты вроде сельсоветов. Если не указать тип «город», «Подсказки» вернут и сельсоветы).

А еще есть такая штука как geoboost. Похожа на ограничение по родителю, но влияет только на ранжирование адресов. Хотите, чтобы омские улицы стояли выше московских — пожалуйста.

По умолчанию в плагине включена геолокация: он передает на сервер местоположение пользователя. Это тоже параметр поиска.

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

Плагин работает в IE начиная с версии 10 и всех нормальных браузерах. Еще ему нужен jQuery 1.10+.

3. Проверяем кэш. Когда запрос приходит на сервер, «Подсказки» первым делом смотрят в кэш. Ищут там совпадение по всем параметрам запроса до единого.

Кэширование спасает от коротких запросов вроде «М», «Мо», «С». Таких однотипных комбинаций приходит колоссальное количество. Поскольку каждая буква — это отдельный запрос, кэширование защищает сервер от миллионов обращений к поисковому индексу.

Кэш целиком помещается в оперативной памяти, в нем лежит 100 000 результатов.

4. Ищем подходящие подсказки в индексе. Если в кэше ничего подходящего нет, «Подсказки» направляются в поисковый индекс.

«Подсказки» ищут адреса? по:

• любой части;
• почтовому индексу;
• устаревшим названиям;
• синонимам и сокращениям. Для них мы составили словарь: «Мск», «Спб», «Ебург», «Б.» — «большая» и т. д.

Алгоритм подразумевает, что неполное или ошибочное в запросе только последнее слово. Если человек написал «Москва Турч», «Подсказки» ищут «Москва Турч*».

Если в плагине отключили геолокацию, по запросам в 1-2 символа, «Подсказки» ищут только регионы, муниципальные районы и города. Дома? сервис ищет со второго слова в запросе.

Каждому результату «Подсказки» назначают вес. Вес нужен, потому что алгоритм порой находит тысячи вариантов, особенно для коротких запросов. А вернуть можно максимум 20 штук. Поэтому «Подсказки» сортируют результаты по весу и возвращают топовые.

Алгоритм ранжирования результатов — ноу-хау «Дадаты». Это такая серьезная штука, что описывать ее подробно я не могу: проклянут разработчики.

5. Сортируем результаты. Если у результатов поиска одинаковый вес, «Подсказки» их сортируют. Алгоритм сортировки тоже самописный, поэтому снова сохраняю таинственность.

6. Готовим ответ. Адреса, которые возвращают «Подсказки», по формату немного отличаются от ФИАС:

• города-регионы вроде Москвы возвращаются в полях и region, и city. В ФИАС они только в region. О доработке просили интернет-магазины: курьерские службы требуют от них, чтобы город стоял непременно в поле «город» (каковы!);
• адрес одной строкой записан по правилам Почты России. Поэтому центр региона отдается без названия региона, а центр района — ну вы поняли. Например, Новосибирск вернется без Новосибирской области. Полный адрес тоже есть, он возвращается в поле unrestrictabled_value;
• тип «улица», «переулок», «шоссе» подставляются перед или после объекта в зависимости от того, как лучше звучит. Благозвучность оцениваем по окончаниям: «Авиационный переулок», но «переулок Васнецова»;
• к садовым товариществам и всему остальному с 65-го уровня ФИАС добавляется название родительского населенного пункта. Например, «снт Гигант (п. Новый)». По ФИАС садовые товарищества входят в населенные пункты, но людям такая иерархия непривычна. Поэтому последние просто выводятся в скобках как ориентир на местности.

7. Кэшируем. Прежде чем вернуть результат, «Подсказки» кэшируют запрос со всеми параметрами и с ответом.

Кэш ограничен 100 000 записей по алгоритму LRU, поэтому сервис выкидывает оттуда редкие запросы. Популярные же вроде «Мо» висят в кэше вечно.

8. Плагин рисует подсказки. Он принимает ответ от сервера, показывает адреса? на экране и подсвечивает совпадения. Если во время ввода нажать Enter, плагин сравнит текст с найденными подсказками и подставит в поле самую подходящую.

Вот так все и работает. Если возьметесь за свои подсказки, статья хоть немного поможет. А лучше приходите к нам работать, будем вместе придумывать крутые штуки. Прямо сейчас ищем джависта на «Подсказки» и еще 7 специалистов.