go.mail.ru - Последние записи

Выдача как книга кулинарных рецептов

Tue, 11 Nov 2014 07:24:36 -0600

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

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

Кроме этого мы улучшили внешний вид и обычных результатов: выделили ингредиенты и способ приготовления – [рецепт юшки рыбной].

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

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

Помогите сделать наш Поиск еще лучше!

Wed, 21 May 2014 02:37:48 -0500

Каждую неделю в нашем Поиске появляется что-то новое. Внедряются новые алгоритмы и меняется интерфейс. Так совсем недавно, мы запустили новый внешний вид Поиска по изображениям.

Примите участие в опросе, который посвящен поиску картинок. Опрос очень короткий и займет буквально 1-2 минуты.

Вы можете сделать наш продукт лучше, ответив всего на два вопроса!

Один клик до цели

Thu, 20 Feb 2014 01:26:17 -0600

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

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

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

Проиллюстрируем, что у нас получилось.

Строка поиска

Скачивание установочного файла

Прослушивание радио в прямом эфире

Быстрый доступ в интернет-банк

Запись на прием к врачу

Просмотр прямого эфира

Покупка билетов в театр

Онлайн-игры, в которые можно играть прямо из браузера

Заказ такси

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

Олимпиада

Mon, 10 Feb 2014 05:47:56 -0600

На прошлой неделе началось главное спортивное событие четырехлетия – Олимпиада в Сочи. В ней принимают участие более 80 стран мира в 15 дисциплинах.

Бесспорно тяжело ориентироваться в таком большом количестве соревнований. И мы, совместно с проектом Спорт Mail.Ru, разработали блок, который поможет вам быть в курсе результатов игр, положении стран в турнирных таблицах и не пропустить все интересные события на Олимпиаде.

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

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

Сегодня проходят соревнования по керлингу, санному спорту, скоростному бегу на коньках, фристайлу, хоккею и шорт-треку. Не пропустите Игры!

Жаркие. Зимние. Твои.

Ноябрь: о чем мы не рассказали

Fri, 29 Nov 2013 04:51:38 -0600

По традиции в конце месяца мы рассказываем о тех небольших нововведениях и изменениях, которые произошли с Поиском Mail.Ru.

На всех платформах:

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

Веб-версия поиска:

В результатах поиска с сайтов кинобаз появилась справочная информация о фильме, например, [фильм «Любовь на кончиках пальцев» смотреть онлайн].

Отличительной чертой результатов видеохостингов теперь является постер к ролику с указанием его продолжительности, например, [ролики котики].

На отдельной странице теперь собрана информация обо всех наших новостных партнерах и их информационные сообщения.

Мобильная версия поиска:

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

Обновление приложения Поиска для Андроида

Fri, 22 Nov 2013 04:07:21 -0600

Сегодня мы рады анонсировать обновление нашего приложения для Андроида. С момента последнего релиза оно значительно изменилось и обзавелось новыми функциями:

Управление через боковое меню. Выбор поисковых разделов и навигация по результатам стали удобнее и доступнее.
Голосовой поиск. Нажимайте иконку микрофона и произносите свой запрос вслух, все остальное Поиск сделает за вас.
Быстрые ссылки на популярные сайты и последние новости на стартовом экране.
Поисковые подсказки и переформулировки. Уточняйте свой запрос на ходу и экономьте время, набирая текст на экранной клавиатуре.
Находите картинки, видео, мобильные приложения, актуальные новости и ответы на вопросы, слушайте любимую музыку.
Новый виджет с настраиваемым оформлением предоставляет быстрый доступ к возможностям Поиска@Mail.Ru с домашнего экрана телефона, а при увеличении размера добавляются анонсы актуальных новостей.

Скачать обновление можно в Google Play, перейдя по ссылке.

Поиск в интернете в новом, удобном формате!

Оплата мобильного в Поиске

Fri, 08 Nov 2013 01:49:55 -0600

Нас часто спрашивают, как [оплатить мобильный], [положить деньги на телефон], и мы теперь знаем, что ответить на такие вопросы - вносите деньги на телефон прямо из Поиска.

Вам достаточно указать номер телефона и сумму денег, а дальше Деньги Mail.Ru все сделают за вас. Главное не забудьте, чтобы на вашем счете на money.mail.ru было необходимое количество средств.

Оплатить телефон также можно и со своего мобильного.

Оставайтесь на связи!

Октябрь: о чем мы не рассказали

Fri, 01 Nov 2013 03:43:03 -0500

По традиции, мы рассказываем о тех небольших нововведениях и изменениях, что произошли с Поиском Mail.Ru за прошедший месяц.

На всех платформах:

Еще сомневаетесь на какие дни брать отпуск? Календарь на 2014 год со всеми официальными праздниками и их переносами подскажет вам. Календарь с праздниками доступен для России, Украины, Казахстана и Беларуси.

Результаты Википедии стали еще нагляднее: появились картинки и быстрые ссылки на разделы статьи. Так теперь выглядит описание Афины.

В результатах поиска теперь можно найти ссылки на статьи новостных агентств и СМИ, по недавно произошедшим событиям. В новостных результатах, пример [д тп Самара], теперь отображается фото, время выхода новости и название источника.

Для пользователей, которые ищут работу в определенной компании или вакансии по профессии, мы разработали специальный поисковый блок совместно с сервисом Работа Mail.Ru. Например, [работа Первый канал].

Искать музыку теперь можно не только с указанием исполнителя в запросе [Nickelback], но и просто по названиям популярных песен. Умный алгоритм отличает обычное слово [notebook] от музыкального [yesterday].

«Нет носок» или «нет носков»?

Mon, 07 Oct 2013 02:43:50 -0500

Как правильно: «салат из помидор» или «салат из помидоров»? Где нужно ставить ударение «то’рты» или «торты’»?

Теперь Поиск@Mail.ru знает ответы на эти и другие вопросы, связанные со склонением и ударением существительных.

Сомневаетесь, что написать в письме, проверяете домашнее задание, просто интересуетесь сложностями русского языка? — Спросите у нашего Поиска.

Что касается носков, то правильно говорить «нет носков».

Проверка ударений и склонений существительных также доступна и на мобильной версии Поиска.

Говорите правильно!

Сентябрь: о чем мы не рассказали

Thu, 03 Oct 2013 02:43:14 -0500

По традиции в конце месяца мы рассказываем о тех небольших нововведениях и изменениях, что произошли с Поиском Mail.Ru.

На всех платформах:

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

Чем примечательна Ботсвана? Что можно увидеть в Париже, помимо Эйфелевой башни? Где остановиться на Коста дель Соль? Сервис Путешествия Mail.Ru ответит на все ваши вопросы. Он не только даст общую информацию о стране/городе/курорте и достопримечательностях, но и подскажет, в каких отелях лучше остановиться, как добраться, а также познакомит с отзывами людей, которые уже там были.

Теперь, помимо электроники и бытовой техники, вы можете увидеть результаты для других товарных категорий, например, колец.

Веб-версия Поиска:

В разделе «Новости» добавилась новая рубрика «Здоровье», которая позволит вам следить за новостями с медицинских полей.

Если под рукой не оказалось печатной версии календаря, не беда. Распечатайте наш календарь!

Ссылки для быстрого перехода на популярные страницы сайта теперь есть у первых трех результатов.

Мы улучшили результаты с отображением информации о видеоторрентах. Теперь информация о качестве, формате, переводе и размере файла представлена в описании в удобном структурированном виде. Например, [сладкий ноябрь торрент].

Перемещаться между страницами выдачи стало возможным и с помощью клавиатуры. Для этого нажмите ctrl + стрелка вправо/влево.

Мобильная версия Поиска:

Поддержка Retina-дисплеев.
Планшетная версия Поиска теперь выглядит также, как и веб-версия.

Метаописания в результатах выдачи

Wed, 21 Aug 2013 06:28:20 -0500

Сниппет — это текстовый блок под заголовком и URL-ом результата, который содержит краткую информацию о найденной странице.

В общем случае сниппет формируется из пересечения пользовательского запроса и содержимого страницы. К сожалению, некоторые интернет-страницы устроены так, что не всегда получается сформировать хорошую аннотацию к результату. Это может происходить в тех случаях, когда на странице нет ни одного слова из запроса, но несмотря на это страница релевантна. Например, один из результатов по запросу [программа телепередач на следующую неделю СТС] — страница http://tv.i.ua/channels/sts/. Её содержимое состоит только из списка программ телепередач. До недавнего времени сниппет этой страницы выглядел так:

Согласитесь, что это не очень информативно.

Но теперь мы выявляем потенциально некачественные сниппеты и заменяем их описанием, которое содержится в теле самой страницы —содержимым метатега Description (Meta Description). Не все страницы снабжены таким описанием, и не везде оно выглядит хорошо, но в случае, если оно доступно, наш поиск выдает Meta Description вместо «мусорного» сниппета. В результате сниппет для вышеприведенного примера теперь выглядит так:

... что уже гораздо лучше описывает страницу.

Возьмём страницы часто посещаемого сайта прогнозов погоды Gismeteo. На них нет связного текста, который можно было бы использовать в качестве аннотации — есть только разрозненные слова и словосочетания. На запрос [Первоуральск погода] отвечала страница http://www.gismeteo.ru/city/daily/11325/, ее сниппет был таким:

Тут и текст с кнопки пользовательской оценки, и вопрос, и ненужные повторения слов из запроса. Гораздо аккуратнее (и полезнее) сниппет с использованием Meta Description, который мы показываем сейчас:

Другие примеры:

По запросу [работа для студентов в Астане вакансии] для страницы http://gojob.kz/students/ мы раньше выдавали сниппет:

Теперь всё гораздо приличнее:

Для запроса [поговорки о рекламе] и страницы http://www.adme.ru/articles/reklamnye-poslovicy-i-pogovorki-200805/ было:

стало:

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

Поиск на Windows 8

Thu, 18 Jul 2013 03:59:35 -0500

Несколько дней назад в Marketplace было одобрено наше поисковое приложение для Windows 8.

Показ результатов может быть оформлен в нестандартном виде – одновременно с отображением сайта. В Windows 8 эта функция называется Snap-режим.

Обратиться к поисковой системе стало еще проще: для этого достаточно выбрать кнопку «Поиск» на панели чудо-кнопок, появившейся в Windows 8.

Скачать приложение можно, перейдя по ссылке. Если у вас возникли предложения или проблемы при работе с нашим приложением — пишите нам.

В последующих версиях мы начнем расширять возможности приложения. Как говорится, stay tuned!

Инфографика: запросы в дни ЕГЭ

Thu, 06 Jun 2013 07:36:02 -0500

Специалисты нашего сервиса проанализировали, о чем чаще всего спрашивали пользователи 17-18 лет в дни сдачи экзаменов по русскому языку и математике. Большинство запросов было получено в мобильной версии поиска, а самые смекалистые искали опубликованные ответы от школьников из Дальнего Востока.

Большинство запросов относилось к выполнению конкретных заданий. Например, во время сдачи ЕГЭ по русскому языку школьники задавали запросы (оригинальная орфография всех запросов сохранена):

«причастие образовано от»
«способ образования слова путешествие»
«составить предложение со словом не садилось»
«какие зависимые слова при связи согласование?»
«отчасти какая часть речи»

Много запросов связано с поиском аргументов для сочинений:

«любовь к родине аргументы»
«аргументы на взаимоотношения между людей»
«аргументы егэ про брак»

Некоторые пользователи прямо в поиске проверяют, как пишется слово или сочетание слов («несдобровать», «и то и то»). Следующий по популярности вид запросов — поиск ответов на все задания сразу:

«егэ по русскому языку 2013 27 мая ответы»
«ответы на егэ по русскому 2013 вк»
«решу егэ»

Выпускники знают, что на Дальнем Востоке ЕГЭ сдают раньше, чем в западных регионах России, поэтому задают запросы вида «егэ по русскому языку 2013 27 мая ответы дальний восток» или «владивосток егэ по русскому 2013 ответы».

Во время сдачи ЕГЭ по математике школьники искали сразу весь текст задачи:

«окружности радиусов 5 корень из 2 и 8 корень из 2 с центрами О1 и О2 соответственно касаются в точке L. Прямая проходящая через точку L вторично пересекает меньшую окружность в точке К, а большую…»
«десять одинаковых рубашек дешевле куртки на 8 процентов на сколько процентов пятнадцать таких же рубашек дороже куртки»

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

Небольшое число запросов относится к процедуре сдачи ЕГЭ:

«из черновика не перенесла в бланк»
«сколько времени отведено на сдачу русского языка на егэ»
«можно ли пересдавать егэ»
«на егэ по математике записан ответ в не то поле»
«если не здал егэ можно перездать»

Как говорится, учите матчасть!

Май: о чем мы не рассказали

Fri, 31 May 2013 05:00:02 -0500

По традиции в конце месяца мы рассказываем о тех небольших нововведениях и изменениях, произошедших с Поиском@Mail.Ru за месяц.

Веб-версия поиска:

В результатах поиска по производителям авто вы можете ознакомиться с представленным модельным рядом, например, [Тойота]. Клик по выбранной модели приведет вас на страницу с подробной информацией на сайте производителя.

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

В сниппетах некоторых сайтов добавлена форма поиска, которая позволяет, не переходя на сайт, обратиться к поиску соответствующего сайта сразу из Поиска@Mail.Ru. Например, такой механизм реализован для сайта Ozon, где люди сразу ищут конкретные товары.

Не определились с именем для ребенка? Хотите узнать историю имени? Введите в поиск запрос, например, [значение имени Сергей], и мы подскажем, что означает ваше имя, и откуда оно произошло.

Мобильная версия поиска:

В конце марта мы писали о запуске спортивного блока в веб-версии Поиска. Теперь этот блок доступен и в мобильном Поиске. Счет обновляется в режиме онлайн. Вы всегда будете в курсе текущего счета игры, даже стоя в пробке.

Вебмастер:

В выдаче Поиска отображаются быстрые ссылки на разделы сайта и адреса компаний. Теперь у вебмастеров появилась возможность управлять этими данными, что позволит исправить ошибки и показывать актуальную информацию. Для это нужно загрузить метаданные в формате xml. Форму для загрузки вы можете найти напротив названия сайта, нажав на карандашик.

Обработка и классификация запросов. Часть третья

Mon, 13 May 2013 04:28:59 -0500

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

О различных подходах к исправлению опечаток написано уже более чем достаточно, поэтому в этой статье я не буду повторять уже известное, а покажу, как написать спеллчекер с нуля — простой, но вполне дееспособный. Всё, что для этого нужно — это список правильных слов и немного С++.

Список слов я взял здесь, но подойдёт и любой другой словарь. Хранить его будем в префиксном дереве (оно же Trie). Вот его несколько экзотическая, не вполне оптимальная, довольно опасная, но, пожалуй, самая лаконичная реализация:

Структура trie_t наследует все методы map. В ключах у этой map записываются буквы слов, а значениями являются снова структуры trie_t, которые наследуют … ну и так далее. Несколько медитативно, но для прототипа сойдёт.

Добавим в структуру вес узла, он пригодится в дальнейшем:

Записывать слова в дерево будем с помощью такой функции:

Работает она так: берём первый символ слова, записываем в ключ мапы, получаем ссылку на соответствующее поддерево (при необходимости оно тут же и создаётся). Рекурсивно записываем остаток строки в это поддерево. Когда строка исчерпана, добавляем к последнему узлу «знак остановки» — ключ '$' с пустым поддеревом.

Прочитав слова из заданного файла, занесем их все в словарь:

В результате в поле w каждого узла дерева будет записано количество слов, прошедших через этот узел.

Что со всем этим можно делать? Можно распечатать содержимое дерева, перебирая унаследованным итератором ключи и поддеревья каждого узла:

Можно определить наличие или отсутствие заданного слова в дереве:

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

Нечёткий поиск

Если представить дерево как некую многократно разветвляющуюся дорогу, то функция поиска слова — путник, идущий по этой дороге. Путнику дан маршрут (искомое слово), и в соответствии с ним он переходит от узла к узлу, зачеркивая пройденные буквы маршрута. Если буквы кончились, остаётся проверить, виден ли «знак остановки».

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

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

Если искомое слово присутствует в словаре, то один путник пройдёт весь путь без штрафов – в отсортированном списке он будет первым. Если слово в словаре отсутствует, то лидировать будет тот, кто прошёл путь с минимальным количеством нарушений.

Собственно, это почти весь алгоритм. Фокус в том, что путь, пройденный лидером, будет ближайшим исправлением заданного слова (или самим этим словом, если опечаток нет), а количество нарушений (отклонений от заданного маршрута) — количеством опечаток.

На старт

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

В полях хранится следующее:

todo — путь, который предстоит пройти. Вначале это тот самый маршрут путешествия, то есть исправляемое слово. В конце там остаётся пустая строка.
done — пройденная часть пути. Вначале — пустая строка, в конце — перечень пройденных узлов, то есть исправленное слово.
cost — сумма наложенных штрафов. На старте — ноль, на финише — как получится.
road — местоположение путника. В начале — корень дерева, в конце — один из листьев.

Итак, путник стоит в исходной точке, можно отправляться:

Первый шаг

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

После совершения шага значения полей структуры изменятся следующим образом:

С оплатой за проезд возможны два варианта. Если выбранное направление совпадает с «генеральной линией», то переход бесплатен, иначе +1:

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

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

Описанный выше «поворот не туда», соответствующий замене буквы слова на другую букву — лишь одна из разновидностей опечаток. Существуют ещё как минимум две: удаление и вставка.

Удаление

Это ситуация «заплатил, но не поехал»: вычёркиваем первую букву из todo, самооштрафовываемся, но перехода не совершаем и ничего не добавляем в done.

В результате буква из todo просто теряется по пути, что равносильно её удалению.

Вставка

Тут, наоборот, «бег на месте»: перемещаемся вглубь дерева, добавляем букву в done, но не вычёркиваем ничего из todo.

Пройденная буква в done возникает вне плана, из ниоткуда, что равносильно её вставке.

Отцы и дети

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

В вектор team попадают те, кто ещё будет продолжать движение, а в finished — дошедшие до конца, то есть те, у кого todo опустошён, а текущий узел дерева содержит баксы отметку конца слова.

Естественный отбор

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

Во-первых, назначим максимально допустимую сумму штрафов, и будем выкидывать всех, кто её превысил, слишком сильно отклонившись от заданного пути.

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

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

Зачем тут логарифм? Что за битовые сдвиги? Почему функция именно такая? Можно попробовать объяснить. Очевидно, что чем больше сумма уже полученных штрафов, тем меньше вероятность дойти до конца. И чем больше слов в поддереве, тем выше вероятность найти среди них хотя бы одно подходящее. А длина уже пройденного пути как бы свидетельствует о «выносливости».

Нужно признать, последнее совсем уж жестоко притянуто за уши. Но в любой эвристике главное — чтоб работала. Эта работает. И, так или иначе, мы близимся к завершению. Обозначим максимальную сумму штрафов как max_cost, максимальный размер команды как team_size.

Поставим первопроходца в начале всех дорог:

Делаем шаг, генерируя следующее «поколение»:

В leads записываются завершившие свой путь, в next_g попадают ещё не дошедшие. Сортируем ещё не дошедших по убыванию их шансов дойти:

И повторяем всё это до тех пор, пока ещё есть кому двигаться дальше. Игнорируем тех, чьи штрафы превысили max_cost, и тех, кто не вошёл в team_size лучших:

Кстати, в leads могут оказаться по несколько структур с одинаковыми строками done. Догадаетесь, откуда они там?

Оставим только уникальные элементы:

Вот почти и всё.

Сложим всё вышеописанное в функцию spellcheck, передадим в неё наше слово, максимальный штраф и количество кандидатов. Можно употреблять:

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

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

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

Итоги пути

Уверен, многие узнали в описании одну из разновидностей информированного поиска — алгоритм А*, вернее, его вариацию — алгоритм А* с итеративным углублением и ограничением по памяти. Разумеется, описанный алгоритм является лишь первым, грубым приближением к тому, что реально используется в бою.

Что ещё должен уметь настоящий, боевой спеллчекер?

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

Проблема решится, если добавить сведения о частоте употребления слов.

Все ошибки равны. Отсюда проистекают такие неуверенные результаты:

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

«Пунто свитчинг». Тут всё просто. Добавляем таблицу соответствия вида q-й, w-ц, a-ф и ещё один тип опечатки — смена раскладки. Готово.
Склейка и расклейка слов. Это несколько сложнее. Необходимо научить «путников» прыгать из листовых узлов дерева в его корень и отдельно обрабатывать пробелы в их «маршрутах».
Контекстные исправления. Одни и те же слова в разных ситуациях должны исправляться по-разному. Например, пришла веспа и сушите веспа, пиковый балет и проездной балет, футбольный меч и джедайский мяч. Для исправления таких опечаток нужны статистические данные и/или грамматические правила. Иными словами, модель языка. Вот это уже совсем другая история.

Побочные эффекты

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

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

Переходы по дереву по правилам, заданным соответствием цифр и букв превратят спеллчекер в систему набора Т9:
Стоимость ошибки, рассчитанная не на вероятностях опечаток, а исключительно на расстояниях между клавишами (вернее, их изображениями на сенсорном экране) служит основой системы «скользящего» ввода слов — Swype.
Задача нечёткого поиска является частью систем распознавания речи, рукописных текстов… Впрочем, достаточно. Об этом написано уже действительно очень много.

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

Небесполезные ссылки

Источник вдохновения: Online Spelling Correction for Query Completion
Самый короткий в мире спеллчекер от Питера Норвига
1200 способов написать слово «одноклассники» — можно использовать для расчёта модели ошибок
Альтернативные подходы: раз, два, три

Михаил Долинин, руководитель группы обработки поисковых запросов

Источник: habrahabr.ru