Поисковые системы не любят дубли страниц. Поисковые системы помечают дубли страниц, чтобы от них могли избавляться. И мы на нашем агрегаторе презентаций (slide-share.ru) тоже избавлялись. К сожалению, постфактум — условный Яндекс уже их находил и не был этому рад. Нужно было решение для удаления дублей до их публикации на сайте.
В какой-то момент мы решили сделать сводного брата Slide-Share: сеть сайтов Doc-Share. Только вместо парсинга презентаций — парсинг текстовых документов. Обработка проще, накладных расходов меньше. Обязательно расскажем об этом, но пока рассмотрим только решение проблемы с дублями. Оно зародилось именно на Doc-Share, а затем эволюционировало несколько раз и переехало на Slide-Share.
Поиск похожих документов — не новая задача. Условный антиплагиат существует очень давно и занимается ее решением. Жаль, что мы не смогли найти (вероятно, и не искали), что и как они делают под капотом. Поэтому изобрели собственные велосипеды.
Используем алгоритм шинглов
В первом приближении задачу поиска дублей решал наш младший (научный) сотрудник — Дима. Я сразу сказал ему, что в душе не чаю, что и как тут можно делать, поэтому он искал варианты решения самостоятельно. Поиски привели Диму туда, куда, наверное, приходят многие разработчики в России и СНГ — сюда, на Хабр. На Хабре некий товарищ рассказывал про алгоритм шинглов и его применимость для оценки уникальности текстов.
Прочитав статью и найдя код на GitHub, Дима скопировал его и сообщил, что нашел решение поставленной задачи. Я был настроен чуть более скептически. При совместном изучении исходного кода реализованного решения сделали выводы, что оно не выполняет нужной задачи. Однако сам подход заинтересовал.
Используя волшебные пендали и несколько итераций, мы смогли получить более рабочее решение, которое позволяло определять дубли. Подход сводится к следующему:
Нормализация исходного текста. Тут довольно большой простор для вариантов, но мы решили обойтись без стемминга и каких-то сложных NLP-подходов. Переводили в нижний регистр, выкидывали «короткие» слова: меньше трех символов. После этого в исходном тексте удаляли все пробелы.
Определяли длину шингла. Если очень просто, то это ширина «окна» в символах, которое будет ползти по нашему тексту. Мы выбирали именно символы, а не слова, так как нормализацией не занимались. На выходе получали словарь, где ключом были шинглы, а значениями — количество их вхождений. Такой словарь мы называем профилем текста.
Профиль текста мы интерпретируем как вектор в N-мерном пространстве. Соответственно, если возьмём два текста и получим их профили, то у нас будет два вектора. Для вектора мы можем вычислить его норму (например, обычную евклидову), а для пары векторов — их скалярное произведение. Найдя скалярное произведение, можем найти косинус угла между векторами. Интерпретируя этот угол, можно определить как сильно два текста похожи друг на друга.
Решение начало выполнять исходную задачу. Но был один ключевой изъян — время работы. Если мы берём уникальный документ, то нам всё равно придётся сравнить его со всеми документами, чтоб подтвердить уникальность. Постепенно количество уникальных документов будет расти, и добавление нового будет занимать непозволительно много времени.
Я начал с простых и тривиальных оптимизаций: хранилище профилей, чтобы не считать их каждый раз для текстов; хранение длины вектора рядом с профилем, чтобы не считать и его. Это дало прирост, но не разительный. В какой-то момент проверка документа на уникальность начала занимать 10–15 минут. А в очереди документов были десятки тысяч, и добавление нового документа увеличивало время проверки на уникальность ещё сильнее.
Оставлять решение в таком виде было нельзя: при переносе решения на Slide-Share мы могли получить еще более крупное время обработки. В базе были сотни тысяч презентаций.
Подключаем к решению Elasticsearch
Казалось очевидным, что нет смысла сравнивать документ со всеми. Нужно находить «похожие», а не проходить по всей базе профилей каждый раз. Я пытался строить «базу» шинглов, чтоб быстро находить похожие документы, но локальные тесты показали, что такой подход не дает ускорения.
Небольшое отступление. Когда-то давно маркетологи попросили добавить на страницы Slide-Share блок с «похожими» презентациями. В Elasticsearch реализован полнотекстовый поиск (в том числе и для русского языка), а также замечательный запрос more_like_this, с помощью которого мы и сделали блок с похожими презентациями. Помимо поиска похожих документов запрос позволял ранжировать их по «схожести». И первыми всегда отдавал презентации, которые максимально похожи на заданную.
К этому и сводилось дальнейшее решение. С помощью Elasticsearch мы не могли отличать дубли (хотя, подозреваю, можно было бы зарыться в его документацию и решить задачу только им), а алгоритм шинглов заставлял проверять весь пул документов. Нужно было взять от обоих решений лучшее и объединить.
Не было никакого смысла получать все похожие документы. Если документ дубль, то он будет в самом начале результата more_like_this. Поэтому я оставил стандартное значение для размера — 10 документов. Теперь новый документ сравнивался только с 10, а не с десятками тысяч. Прирост производительности получился ожидаемым и приятным: с десятка минут время обработки сократилось до одной-двух секунд. Теперь требовалось перенести решение в проект, чем я и занялся. И огрёб.
В случае с Doc-Share мы со старта проекта сохраняли уникальные документы. Slide-Share же впитывала вообще всё. Единственная проверка была на полные дубли: мы не сохраняли презентации с одинаковым хэшем. Но контентные дубли были, мы про это знали из данных Яндекса. Периодически их удаляли, но теперь у нас появился механизм, который позволял проверить всю базу…
В процессе работы над решением задачи Дима выставил порог уникальности в 60%. Значение определено после определенных экспериментов (от балды), каких-то адекватных данных не было. Поэтому оставили и решили посмотреть, как будет работать.
Я начал проверять базу презентаций на дубли. При этом почему-то решил, что их следует объединять в кластеры. Искать «пачки» похожих презентаций, а потом удалять непосещаемые дубли или делать редиректы для страниц с трафиком.
Набросал решение, которое пыталось достать дубли из базы с уникальностью в 60%, и поймал странное поведение. В какой-то момент кластер начинал бесконечно расти, то есть все презентации начинали быть похожими друг на друга. Такое поведение удивило, поэтому я полез разбираться в причине. Она оказалась простой: 60% уникальности — слишком высокий порог. Тексты могут быть похожи по смыслу или по использованным оборотам, но не являться дублями. Они могут быть написаны об одном, с одними терминами, но по-разному. И снова не являться дублями. А нам нужны дубли!
Применив более экспериментальные методы, определили приемлемое значение для порога уникальности — 20%. Собрали все дубли, что были в базе. Далее с помощью API Яндекс Метрики проверили посещаемость страниц. Всё, что было не очень посещаемым, без жалости удалили. База становилась все чище, алгоритм для поиска дублей — все более адекватным. Сейчас у нас очищенные диски. Очищенная база без дублей. Достаточно высокая скорость отдачи контента и статики. И пессимизация в поиске от Google, потому что всё это нужно было делать раньше. Сильно раньше. Но времени на pet-проекты всегда не хватает, да?
