9 апреля в Международном информационно-выставочном центре ИнфоПространство прошел пятый Форум технологий Mail.Ru Group. Ведущим Форума выступил вице-президент и технический директор Mail.Ru Group Владимир Габриелян.

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

Ведущий программист Mail.Ru Group Алексей Романенко рассказал о поиске нечетких дубликатов в масштабах рунета. Алексей начал с общей постановки вопроса, потом рассказал о существующих алгоритмах и о том, как они используются, и как это реализовано в поиске Mail.Ru.

Реализация многих задач сталкивается с тем, что нужно найти одинаковые или похожие объекты. Это требуется, например, в классификации и кластеризации, в определении зеркала сайта, в поисках плагиата. В рекомендательных системах ― для определения схожих вкусов пользователя. Еще одна из прикладных задач ― находить похожие изображения.

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

По оценкам специалистов компании, в рунете 20-30% страниц считаются дубликатами.

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

Неточные, нечеткие дубликаты ― это, например, динамические страницы, рерайтинг.

Для определения того, что считать дубликатом документа, нужно ввести меру похожести, от 0 до 100%. В итоге нужно посчитать эту меру и выбрать некое пороговое значение, после какого документ будет считаться дубликатом.

Для работы используются следующие алгоритмы.

Шинглирование (Shingling) ― преобразовать множество документов в множество шинглов; k-шингл ― k символов или слов.

Minhashing (Andrei Broder) ― преобразовать большое множество шинглов в короткую сигнатуру; Locality-sensitive hashing (LSH).

Супер-шинглы ― отобрать только те сигнатуры, которые будут похожи с большой долей вероятности.

Формируется множество шинглов, строится для каждого документа, и определяется мера сходности.

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

Выбор, по какому количеству слов (k) будет определяться сходство, очень сильно влияет на результат, и зависит и от размера документа, и от количества слов в нем.

Сравнивать большие множества документов ресурсоемко, к тому же хранение большого числа шинглов затратно. Поэтому был предложен алгоритм Min-hashing, который позволяет снизить размер множества. Идея ― представить документ в виде небольшой сигнатуры (вектора) и на этом основании делать вывод о похожести документов.

В итоге получается табличка, которая сформирована следующим образом.

Для каждой хеш-функции выбираем минимальный хеш.

Вероятность того, что мин-хеш документа «а» равен мин-хешу документа «б» говорит нам, что эти документы похожи между собой на 25%.

На практике используется порядка 100 хеш-функций (их количество рассчитывается из количества документов, которые нужно сравнить). В итоге получается вектор из 100 чисел. То есть, в итоге на хранение каждого документа нужно порядка 800 байт.

Но и тут не все просто. Даже на современном оборудовании на вычисление уйдет около трех лет. Поэтом применяется подход «супершинглы».

То есть, будут сравниваться документы, которые похожи между собой с большей вероятностью.

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

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

В итоге наш алгоритм выглядит так

Для каждого документа имеется сжатое представление того, что будет сравниваться.

Многие задачи по обработке схожести данных в поиске решаются через MapReduce.

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

Далее Алексей рассказал, как поиск дубликатов реализуется в Mail.ru.

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

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

Вторая фаза, синхронная первой ― сканирование базы. Данные поступают на вход второй MapReduce-задачи, где происходит следующее преобразование. Теперь у нас ключом становится хеш супершингла, а значением ― тот DocID, который ему соответствует.

По идеологии MapReduce, все одинаковые хеши поступают на вход одного редьюсера. И им будет соответствовать весь вектор документов, где этот хеш встречался.

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

И в заключение Алексей коснулся вопросов, которые остаются открытыми. Это касается, в первую очередь, фильтрации html-тегов: не ясно, что делать с тегами, которые не несут смысловую нагрузку (, ), а также с JavaScript, AJAX, Flash. Казалось бы, вырезаем весь тег, оставляем только текст, и считаем. Но на практике получается, что в каком-то случае сайт практически состоит из картинок, где-то мало текста, где то подписи к картинкам, к ссылкам, сами ссылки несут смысловую нагрузку, и нельзя их просто так вырезать потому, что для пользователя это важно. А если вырезать ― то документы окажутся дубликатами, хотя, по факту, это не так.

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

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

Вопрос: При построении шинглов учитывается морфология?

Алексей Романенко: Да. Слова приводятся к канонической форме. А если сразу не ясно, какая форма будет канонической, – то можно сказать, что не настолько страшно это будет влиять. Обычно текст большой, и слов с неоднозначным смыслом не много, потому, что в зависимости от того, как это же слово употребляется далее в разных формах, можно его уточнить.

Вопрос: Как выбрать оригинал из дубликатов, и важно ли это?

Алексей Романенко: У нас много информации по сайтам ― по их посещаемости, по возрасту. По комплексу факторов принимается решение об оригинальности. Если сравниваются документы на одном сайте ― то будет оставлена основная версия, если на разных ― то оригинал. Но, к сожалению, простого способа решения нет. Это решается по совокупности факторов и на основании той информации, которую мы знаем о рунет.

Вопрос: Работа таких систем, как определение дубля, оценивается, как минимум, двумя показателями: точность и полнота. Каковы эти показатели в определении нечетких дублей в поиске Mail.ru, и как это измеряется ― особенно полнота?

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

Вопрос: А учитываются ли картинки?

Алексей Романенко: Картинки не учитываются, обычно фильтруются, мы стараемся брать только текст.

Обзор подготовила Александра Кирьянова