Нечеткий поиск строк является весьма дорогостоящей в смысле вычислительных ресурсов задачей, особенно если вам необходима высокая точность получаемых результатов. В статье описан алгоритм нечеткого поиска в словаре, который обеспечивает высокую скорость поиска при сохранении 100% точности и сравнительно низком потреблении памяти. Именно автомат Левенштейна позволил разработчикам Lucene повысить скорость нечеткого поиска на два порядка

В первой части статьи мы рассмотрели универсальный автомат Левенштейна — мощный инструмент для фильтрации слов, отстоящих от некоторого слова W на расстояние Левенштейна не более заданного. Теперь пришло время изучить способы применения этого инструмента для эффективного решения задачи нечеткого поиска в словаре.

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

Однажды, скучая дома на выходных, пришла в голову идея написать приложение для игрового сообщества, в котором я состою. Когда код был написан, протестирован, все устраивало в работе — пришло время публиковать в Play Store. Для меня всегда было проблемой нарисовать графику. Поэтому я все взял с нашего форума. Нажал кнопочку «паблиш», и через 10 минут моё приложение было в бане!

История под катом.

В последние несколько лет MongoDB приобрела огромную популярность среди разработчиков. То и дело в интернете появляются всякие статьи, как очередной молодой популярный проект выкинул на свалку истории привычные РСУБД, взял в качестве основной базы данных MongoDB, выстроил инфраструктуру вокруг неё, и как все после этого стало прекрасно. Даже появляются новые фреймворки и библиотеки, которые строят свою архитектуру целиком на Mongo (Meteor.js например).

По долгу работы я примерно 3 года занимаюсь разработкой и поддержкой нескольких проектов, которые используют MongoDB в качестве основной БД, и в этой статье хочу рассказать, почему на мой взгляд с MongoDB далеко не все так просто, как написано в мануалах, и к чему вы должны быть готовы, если вдруг решите взять MongoDB в качестве основной БД в ваш новый модный стартап :-)

Все что описано ниже можно воспроизвести с использованием библиотеки PyMongo для работы с MongoDB из языка программирования Python. Однако скорее всего с аналогичными ситуациями вы можете столкнуться и при использовании других библиотек для других языков программирования.

кадр из фильма Миссия Невыполнима II

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

Первый успех

Было решено попробовать следующий вариант:

• Добавить неизвестный номер в адресную книгу телефона;
• Зайти по очереди в приложения, привязанные к номеру (Viber, WhatsApp);
• Открыть новый чат с вновь созданным контактом и по фотографии определить отправителя.

Мне повезло и в моём случае в списке контактов Viber рядом с вновь созданным контактом появилась миниатюра фотографии, по которой я, не открывая её целиком, распознал отправителя и удовлетворенный проведенным «расследованием» написал смс с благодарностью за поздравления.

Сразу же за секундным промежутком эйфории от удачного поиска в голове появилась идея перебором по списку номеров мобильных операторов составить базу [номер_телефона => фото]. А еще через секунду идея пропустить эти фотографии через систему распознавания лиц и связать с другими открытыми данными, например, фотографиями из социальных сетей.

Этой весной мы в лаборатории экспериментировали с самыми разными данными: характеристиками танков в игре World of Tanks, статистикой правильных и неправильных ответов на тренажёре ПДД, температурными рекордами в городах России, нарушениями в работе маршрутных такси Нижнего Новгорода, историей изменения цен на авиабилеты. Результатом экспериментов стали 5 наглядных интерактивных визуализаций:



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

Google, Microsoft, Mozilla и инженеры проекта WebKit 17 июня сделали анонс, что они объединились для запуска WebAssembly, нового бинарного формата для компилирования веб-приложений.

Я — программист. А ещё я слеп. Слеп, как крот, как говорится. Таков я от рождения.

Когда я говорю об этом своим товарищам, то те из них, у кого никогда не было проблем со зрением, обычно задают один из трёх вопросов:

• Как же ты тогда можешь читать то, что я пишу?
• Ого. А как ты тогда можешь кодить?
• Или — самый популярный вопрос — А ты видишь сны?

Мне задают эти вопросы снова и снова. Поэтому в этой блогозаписи я хочу на них ответить. Я попытаюсь нарисовать картинку для тех из вас, кто интересуется доступностью и тем, как слепые люди пользуются компьютером, кодят и выполняют другие работы в 21 веке.

Вот уже более 60 лет австралиец Джеймс Харрисон (James Harrison) практически каждую неделю ходит сдавать плазму крови. Почётный донор давным-давно удостоился прозвища Человек с золотой рукой, и это не просто так. Своей правой рукой, куда ему более 1000 раз вставляли иглу аппарата для плазмофереза, за прошедшие годы он спас более двух миллионов человек!

Ещё в юности Джеймс пережил серьёзную операцию на грудной клетке, ему удалили лёгкое. Это произошло в далёком 1951 году, когда нашему герою было 14 лет. Жизнь подростку удалось спасти благодаря неизвестным донорам, которые пожертвовали 13 единиц крови (6,5 л). Тогда Джеймс раз и навсегда решил, что он достаточно взрослый и тоже станет донором крови.

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

UPDATE: Всем привет! Сегодня с удивлением узнал от коллег об этой записи. Выяснилось, что мой аккаунт взломали — представители Хабрахабра это подтвердили и восстановили мне доступ и сейчас разбираются, как так получилось. Но я оставляю эту запись как есть, для истории.
В комментариях уже отметились представители Яндекса: говорят, что уязвимость закрыта, ведётся аудит безопасности софта.

И, пользуясь случаем, хочу напомнить, что у нас в Badoo уже несколько лет идет программа "Проверь Badoo на прочность" и мы платим за найденные уязвимости.

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

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

Начну с нетехнической части.

Введение

Несмотря на обилие социальных сетей, за последние несколько лет появился целый ряд новых, оригинальных и необычных социальных приложений, таких как just yo, snapchat, secret, и пр. Успех приложения just yo, ограниченного единственной функцией – отправкой сообщения фиксированного содержания, меня заинтересовал и мы с друзьями тоже решили попробовать написать очередную социальную сеть на Android. Нашей целью было очертить круг задач общий для большинства подобных приложений, предложить их решения и подготовить скелет, из которого каждый сможет сделать что-то своё и оригинальное, не тратя время на решение рутинных вопросов. С результатами работы можно сразу ознакомиться на github – android клиент и сервер на ruby on rails.

Добрый день, уважаемое хабрасообщество!

В конце ноября 2013 года мы с коллегой устроили встречу, на которой провели сеанс «интенсивного введения Scala в мозг добровольцев».

Выкладываю на суд общественности наше творчество и краткое описание «эксперимента».

Только что в Париже на конференции LeWeb Яндекс объявил об открытии нового важного направления своей деятельности — по коммерческой обработке больших данных — Yandex Data Factory.

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



Перед публичным запуском Yandex Data Factory мы провели несколько пилотных проектов с компаниями-партнёрами. Для компании, обслуживающей линии электропередач, в Yandex Data Factory создали систему, которая анализирует сделанные беспилотниками снимки и автоматически выявляет угрозы: например, деревья, растущие слишком близко к проводам. А для автодорожного агентства проанализировали данные о загруженности дорог, качестве покрытия, средней скорости движения транспорта и аварийности. Это позволило в режиме реального времени составлять прогноз заторов на дорогах на ближайший час и выявлять участки с высокой вероятностью ДТП.

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

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

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

Дело в том, что все (или почти все) поисковые запросы в Яндексе, пусть и в анонимизированном виде, в реальном времени доступны по адресу export.yandex.ru/last/last20x.xml

На основе этого API я сделал маленький проект на Openresty (nginx + Lua + imagemagick), предоставляющий высокопроизводительную реализацию CAPTCHA.



Предусмотрена возможность встраивания в виде iframe.

GitHub, demo

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

В последнее время заметно, что компания Microsoft уделяет повышенное внимание развитию своих средств разработки, новым инструментам и механизмам разработки программ на своей платформе .net. Быстро развивается язык C#, четвертая версия которого не за горами. Представлен и активно продвигается новый язык F#. Для разработчиков баз данных разработан Entity Framework, который уже доступен в виде финальной версии в первом сервиспаке к .Net Framework 3.5 и Visual Studio 2008. Microsoft активно занялась и клиентской частью разработки web-проектов. Для нашего внимания предложен путь развития Ajax.Net 4.0. Internet Explorer 8 все больше соответствует стандартам и становится привлекательным инструментом для web-программистов, так например, его вкладка Developer Tools включает в себя профайлер JavaScript. Очень хорошей новостью стало недавно объявление о полной поддержке и включении JavaScript-библиотеки jQuery в следующее обновление Visual Studio. В этом свете возникает вопрос, что же предложено разработчикам ASP.NET? Ответ — MVC Framework. Целью данной статьи рассмотреть некоторые общие проблемы, с которыми могут столкнуться программисты, решившие использовать MVC Framework для своих web-проектов, и их решения.

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

Blockchain

Блокчейны – технология распределённых вычислениях и общем консенсусе пользователей, созданная таинственным Сатоши Накамото. В ней отсутствует центральное управление, а для верификации транзакций используются P2P-сети, кодификации и криптография. Более того, транзакциями можно управлять при помощи программируемых контрактов/договоров. В блокчейне Биткоина любые транзакции не считаются легитимными (подтверждёнными), пока информация о них не будет сгруппирована в специальные структуры — блоки. Структура и информация в блоках подчиняется заданным правилам и её можно быстро проверить. Каждый блок всегда содержит информацию об одном предыдущем блоке. Это позволяет все существующие блоки выстроить в одну цепочку, которая представляет собой распределённую базу данных и содержит информацию о всех совершённых когда-либо операциях с bitcoin.

Bitcoin – это первое и самое успешное применение технологии блокчейнов, но есть и многие, многие другие криптовалюты, известные как альткоины. Более того, есть много примеров того, как новые блокчейны используются не только для криптовалютных целей – Ethereum, Ripple и Storj.io, о них мы сегодня и поговорим в первой части нашего цикла статей про децентрализованные сервисы. В свете последних событий, целью статьи является также показать, что кролики это не только ценный мех Bitcoin это не только платежная система, а новая революционная технология, которая открывает целый ряд возможностей для построения принципиально новых программных продуктов.

Я люблю находить на новостных ресурсах статьи о том, что программисты получают очень много денег. Я сразу пролистываю их до комментариев и с теплом в душе читаю гневные отзывы о том, что программисты ничего не делают и не заслуживают таких денег. Но после прочтения возникает мысль: знают ли они, кто такие программисты? Или они исходят в своих суждениях из неверного знания, даже не подозревая об этом. Например, мало кто знает, почему трава зеленая. Подумайте об этом. Следует ли из ваших объяснений зелености травы именно зеленый цвет?

Функциональность In-Memory OLTP (проект Hekaton) призвана ускорить обработку типовых OLTP-операций в SQL Server. Как известно, нагрузку, приходящуюся на сервер баз данных, будь то Microsoft SQL Server или Oracle/MySQL или SAP/Sybase или IBM DB2 и т.д., можно условно разбить на два класса: сбор данных и анализ того, что собрали, потому что зачем в противном случае было собирать? Первый класс задач называется OLTP (On-Line Transactional Processing). Для него характерны короткие обновляющие транзакции, затрагивающие относительно небольшое число таблиц в базе. Примеры таких приложений — операционный день в банке, биллинг в телекоме и т.д. Второй класс задач называется OLAP (On-Line Analytical Processing) и характеризуется массивным длительным чтением, охватывающим значительное количество таблиц и собирающим из них, как правило, по максимуму записей, изобилующим предикатами связывания, сортировки, группирования, агрегатными функциями и т.д. Как правило, структуры данных для разных классов задач разделяют, чтобы не мешали друг другу, и если первая структура базы строится с учетом многочисленных правил Кодда, то вторая, напротив, денормализована и выполняется по схеме «звезда (снежинка)».
Устремление СУБД в память проявилось в начале нового тысячелетия, когда выяснилось, что несмотря на закон Мура тактовая частота и быстродействие процессоров растут отнюдь не по экспоненте, а наоборот, выходят на плоскую прямую насыщения невзирая на ILP и прочие ухищрения. В то же время цены на оперативную память, когда-то неприлично дорогую, катастрофически снижаются и по сравнению с 90-ми упали в тысячи раз. Ага, сказали себе производители серверов баз данных. В 2005-м Oracle прикупил in-memory СУБД TimesTen, IBM в 2007-м — компанию Solid, а в Microsoft в данном случае ничего со стороны брать не стали, потому что решили воспитать в своем коллективе.