Предыстория

При разработке проекта для онлайн навигации (в будущем и оффлайн) возникла необходимость разработки собственных онлайн карт. Сервисы от Google, Bing и т.п. имеют ограничения в использовании их карт в коммерческих целях. Бесплатные же, типа OpenStreetMap, не удовлетворяли требования заказчика.
Стал вопрос о создании онлайн карты (тайлов карты) для всего мира. Стиль приближенный к Google и Skobbler. Данные на основе OpenStreetMap.

Занимаясь разработкой веб-карт, использующих данные OpenStreetMap, часто возникает вопрос о том, как показывать карты с корректными русскими названиями. Этой проблемы не возникает, если ваши карты показывают исключительно Россию. Однако, если вы посмотрите, например, карту Китая, то вам вряд ли понравится такое обилие иероглифов, а тщетные попытки найти Пекин на такой карте, скорее всего, не увенчаются успехом.



Известно, что свободолюбивый проект OpenStreetMap позволяет сохранять названия географических объектов на разных языках. Для этого используются специальные теги, типа name:ru, name:en или name:es, и что самое главное, они заполняются участниками OpenStreetMap. Конечно, наиболее подробные надписи создают пользователи на том языке, на котором они говорят: в России — на русском, в Китае — на китайском, в африканских странах — на местных языках. Шансов, что какая-то улочка в Нигерии будет иметь русский перевод, мало, но все же основные географические объекты (страны, города, реки и т.п.) имеют переводы. Этой небольшой картографической информации бывает вполне достаточно, чтобы русскоязычный пользователь открыл, например, карту Китая и нашел на ней основные названия. Таким образом, ваш ресурс станет чуть более дружелюбным для пользователя.

Совсем недавно возникла задача создания программного обеспечения по генерации картографических тайлов. В качестве основы выбор пал на mapnik (альтернатив ему немного). Как оказалось, здесь на пути поджидало множество сложностей, непредвиденных ошибок, а более менее внятной документации по настройке всего «под ключ» найти не удалось. Повозившись какое-то время, мне удалось собрать множество граблей, которые могут возникнуть ну и довести дело до победного конца. Об этом и статья.

… эта история началась давным-давно в далекой-далекой стране Краковия, чьи жители беспечно проживали свои жизни и не знали…

Но сам я местный, и сегодня расскажу вам страшную историю, о том, что мешало спать (лично мне) долгие годы. И это не налоги (с ними все нормально), это — геокодер Яндекс.Карт!

Геокодер — это один из HTTP-сервисов Яндекс.Карт, получающий в запросе текстовое представление адреса и возвращающий в ответе найденные на его основании объекты. Либо наоборот: получающий координаты и отвечающий адресом.

Именно геокодер подскажет, где на карте находится чудная страна Краковия. И именно он будет главным героем этой истории, завязка которой была описана совершенно в другой книге — в древнем фолианте Пользовательское соглашение API Яндекс.Карт. Легенда гласит, что существует ограничение на количество запросов к функции геокодирования. Максимально допустимо делать в сутки не более 25 000 запросов к HTTP и JS геокодеру в сутки. Или овсянка, сэр.

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



Что делать? Для наглядности достанем из кустов рояль — 8 лет назад на Хабре засветился проект «еСоседи» — «Карта интересных мест». Все эти годы я продолжаю работать над ним.

Совсем недавно на хабре была статья от AirBnb — «Создавая карту мира». Хорошая и красивая статья про административное деление мира. Один минус — у статьи один комментарий, и то мой.

Пользуясь случаем проведу опрос — хотели ли бы вы такую карту административных делений?

А то она у меня есть:



Вы наверное замечали, что Google.Карты умеют подсвечивать контура городов. С недавнего времени такое есть и на Яндекс.Картах. Мало кто знает, что геометрия есть и на eSosedi.

А вот когда такая возможность появится на вашем сайте — теперь зависит только от тебя %username%.

Для достижения эффекта достаточно зайти на data.esosedi.org или GitHub, ознакомиться с документацией библиотеки osmeRegions и начать использовать.

P.S.: 3 признака того, что год минувший все сделал красиво: 1. Районы 2. Кварталы. 3. Детализация до «Жилые массивы» доступна для некоторых городов.

Откиньтесь на спинку кресла и отдохните – пришло время рассказать об одном из моих самых любимых багов.

Это была моя самая первая работа в сфере IT – летняя практика в компании, разрабатывающей очень серьезное медицинское оборудование, в частности системы подачи анестезии и мониторы для пациентов больниц. Монитор для пациента – это такая попискивающая коробка рядом с лежачим больным, которая меряет пульс, давление, частоту дыхание и прочее, а также оповещает медсестер в случае неприятностей. Офис был полон двухметровых баллонов с веселящим газом, по нему расхаживали роскошнобородые гуру-эксперты по встраиваемым системам, и были целые комнаты-хранилища специально для документации, необходимой для сертификации различного оборудования. Народ до сих пор шепотом рассказывал об одном баге, пропущенном тестировщиками с десяток лет назад, из-за которого система подачи анестезии перезапустилась посреди операции. Стоит ли говорить, что зеленого сопляка-студента вроде меня и за километр бы не подпустили к боевым системам?

Вместо этого мне поручили проект-прототип с целью опробовать в действии самые горячие технологические новинки 1997 года – сервер на C++, который бы слушал мониторы по последовательному порту, сливал интересные данные в базу на SQL Server и отправлял их на Java-апплет через CORBA, чтобы доктора и родственники могли следить за самочувствием больного через интернет. Красота же! Особенно с учетом того, что практического опыта у меня не было ни с одной из этих систем и технологий!

Можно прочитать много книг по базам данных, написать кучу приложений на аутсорс или для себя. Но при этом невозможно не наступить на грабли, при работе с действительно большими базами/таблицами особенно, когда downtime на большом проекте хочется свести к минимуму, а еще лучше совсем избежать. Вот здесь самые простые операции, как например изменение структуры таблицы может стать более сложной задачей. Наиболее интересные случаи, проблемы, грабли и их решения из личного опыта с которыми нам на проекте Pushwoosh пришлось столкнуться описаны под катом. В статье нет красивых картинок, зато есть много сухого текста.

Просматривая ленту новостей я наткнулся на рекомендацию от Типичного Программиста на статью «Implementing a Search Engine with Ranking in Python», написанную Aakash Japi. Она меня заинтересовала, подобного материала в рунете не очень много, и я решил перевести её. Так как она довольно большая, я разделю её на 2-3 части. На этом я заканчиваю своё вступление и перехожу к переводу.

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

Но в то время как Google является невероятно сложным, основная концепция поисковой системы, которые ищут соответствия и оценивают (ранжируют) результаты относительно поискового запроса не представляет особой сложности, и это может понять любой с базовым опытом программирования. Я не думаю, что в данный момент возможно превзойти Google в поиске, но сделать поисковой движок — вполне достижимая цель, и на самом деле это довольно поучительное упражнение, которое я рекомендую попробовать.

Это то, что я буду описывать в этой статье: как сделать поисковую систему для локальных текстовых файлов, для которых можно обрабатывать стандартные запросы (по крайней мере, одно из слов в запросе есть в документе) и фразу целиком (появляется вся фраза в тексте) и может ранжировать с использованием базовой TF-IDF схемы.

Есть два основный этапа в разработке поискового движка: построение индекса, а затем, используя индекс, ответить на запрос. А затем мы можем добавить результат рейтинга (TF-IDF, PageRank и т.д.), классификацию запрос/документ, и, возможно, немного машинного обучения, чтобы отслеживать последние запросы пользователя и на основе этого выбрать результаты для повышения производительности поисковой системы.

Итак, без дальнейших церемоний, давайте начнем!

Первое видео курса

Массачусетский технологический институт выложил в свободный доступ курс лекций по теме «Теория и аналитика игры в покер» (на английском языке). Доступны видеолекции, конспекты и специальные заметки по курсу. Это событие – часть программы OpenCourseWare, которая посвящена организации бесплатного доступа к избранным лекциям института для всех желающих – даже для тех, кто не учится в нём.

Помните, как в школе многие говорят: «Ну зачем мы это учим, нам это не пригодится!»?



Так вот, лекции по покеру – пожалуй, могут оказаться не просто интересными, но и весьма полезными с практической точки зрения.

Лекции ведёт магистрант института Кевин Дезмонд, который получил степень бакалавра по финансам. И, что логично, его лекции как раз рассказывают о технологиях анализа и планирования, предназначенных для максимизации выгоды от игры на деньги.

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

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

Сегодня я постараюсь объяснить простыми словами принципы работы 10 самых эффективных data mining-алгоритмов, которые описаны в этом докладе.

Когда вы узнаете, что они собой представляют, как работают, что делают и где применяются, я надеюсь, что вы используете эту статью в качестве отправной точки для дальнейшего изучения принципов data mining.

Натолкнулся в разделе QA на интересный вопрос. Ответ на него заставил написать эту статью как бОлее полный ответ на вопрос «как организовать поиск по множеству параметров, как в Яндекс-маркете, например».

Я знаю, что на Хабре, да и вообще есть много сторонников noSQL решений (сам не без греха), но все же я сторонник сначала подумать, а уже потом выбирать решение.

Итак, что имеем в «ДАНО»

• Имеем 120 чекбоксов — вариант 1/0
• Имеем 30 «радио» с выбором «да/нет/не важно»
• Имеем 2-3 слайдера для указания диапазона цен/размера чего нить
• Имеем самое главное: 12 млн записей в БД.
• Имеем Select * From tovar Where (wifi=true) and (led=false) and (type=3) and ….остальные параметры …; со временем выполнения близкому к истерике клиента.

Не секрет, что каждый интернет-магазин должен помогать пользователям найти то, что им нужно. Особенно, если товаров у вас много (> 10). На помощь приходит каталогизация товаров, но разбить товары по категориям — полдела. Товары внутри категории нужно уметь фильтровать по их свойствам. Особенно, если товары у вас разношёрстные, например, одежда, электроника, ювелирные изделия и т.д. И тут любой разработчик, пишущий свой e-commerce продукт, сталкивается с неприятными реалиями жизни: у товаров могут быть совершенно разные свойства, у некоторых товаров они могут отсутствовать, некоторые товары по одному свойству могут попадать под разные значения (цвет платья то ли синий, то ли голубой, соответственно, неплохо бы его показать и по синему и по голубому цвету). Проще говоря, у вас EAV. Бывает ещё, что EAV вам диагностирует заказчик ближе к концу разработки, а то и просит добавить фильтр по динамическим свойствам уже после релиза.

По долгу службы мне часто нужно находить все пересечения между текстами (например, все цитаты из одного текста в другом). Я достаточно долго искал стандартное решение, которое бы позволило бы это делать, но найти его мне так и не удалось — обычно решается какая-то совсем или немного другая задача. Например, класс SequenceMatcher из difflib в стандартной библиотеке Питона находит самую длинную общую подпоследовательность в двух последовательностях hashable элементов, а потом рекурсивно повторяет поиск слева и справа от нее. Если в одном из текстов будет более короткая подпоследовательность, которая содержится внутри уже найденной (например, если кусок длинной цитаты где-то был повторен еще раз), он ее пропустит. Кроме того, когда я загнал в него «Войну и мир» и «Анну Каренину» в виде списков слов и попросил для начала найти самую длинную подпоследовательность, он задумался на семь минут; когда я попросил все совпадающие блоки, он ушел и не вернулся (в документации обещают среднее линейное время, но что-то в прозе Льва Толстого, по-видимому, вызывает к жизни worst-case квадратичное).

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

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

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

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

Привет, Хабр!

Мы в HumanFactorLabs парсим адреса в особо крупных размерах. Наши продукты упрощают ввод контактных данных и работу с ними.

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

Недавно на Хабре нас попросили привести примеры необычных адресов, в связи с чем и написана эта статья.

Хотел бы поведать свою историю об установке геокодера Nominatim на выделенный сервер. Изначально предполагалось, что эта задача займёт у меня около 5-7 часов, но не тут то было… Поэтому было решено написать статью c описанием разворачивания Nominatim на сервер до полной работоспособности сайта. Но обо всём по порядку.

Цель статьи – показать применение шаблонов Remote Facade и Data Transfer Object к структуризации кода, управляемой формы в среде 1С 8.2.

В свое время у меня накопилось достаточное количество прикольных, но тем не менее бесполезных в быту вещей, одной из которых была трубка для рентгеноструктурного анализа «БСВ-25».

Введение

Алгоритмы нечеткого поиска (также известного как поиск по сходству или fuzzy string search) являются основой систем проверки орфографии и полноценных поисковых систем вроде Google или Yandex. Например, такие алгоритмы используются для функций наподобие «Возможно вы имели в виду …» в тех же поисковых системах.

В этой обзорной статье я рассмотрю следующие понятия, методы и алгоритмы:

• Расстояние Левенштейна
• Расстояние Дамерау-Левенштейна
• Алгоритм Bitap с модификациями от Wu и Manber
• Алгоритм расширения выборки
• Метод N-грамм
• Хеширование по сигнатуре
• BK-деревья

А также проведу сравнительное тестирование качества и производительности алгоритмов.

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

Часто довольно трудно найти в базе нетипичную фамилию, например:

— Леха, поищи в нашей базе Адольфа Швардсенеггера,
— Шворцинегира? Нет такого!

В этом случае использование фонетических алгоритмов (особенно в сочетании с алгоритмами нечеткого сопоставления) может значительно упростить задачу.

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

В этой статье я рассмотрю наиболее известные алгоритмы, такие как Soundex, Daitch-Mokotoff Soundex, NYSIIS, Metaphone, Double Metaphone, русский Metaphone, Caverphone.