Как Google комбинирует разные алгоритмы (Shingling и SimHash) для точного определения дубликатов контента

Описание

Какую задачу решает

Патент решает проблему неточности (ложных срабатываний и пропусков) и неэффективности существующих алгоритмов обнаружения почти дубликатов (near-duplicate documents), таких как алгоритмы Бродера (Broder) и Чарикара (Charikar), при обработке больших наборов данных, например, веб-страниц. Особое внимание уделяется проблеме низкой точности при обнаружении дубликатов на одном и том же веб-сайте, часто возникающих из-за шаблонного текста (boilerplate). Цель — повысить точность (precision) идентификации дублирующегося контента для экономии ресурсов при сканировании, индексировании и для улучшения качества поисковой выдачи.

Что запатентовано

Запатентованы методы для обнаружения почти дубликатов, которые комбинируют различные техники оценки схожести документов. Описаны два основных подхода. Первый — каскадный (двухэтапный): использование первой техники (например, зависящей от порядка токенов) для генерации начального набора кандидатов и второй техники (например, не зависящей от порядка, но зависящей от частоты) для его уточнения. Второй подход (отраженный в Claims 30-38 данного документа) — контекстно-зависимый: применение разных техник в зависимости от того, находятся ли сравниваемые документы на одном сайте или на разных.

Как это работает

Система принимает набор документов и обрабатывает их для выявления дубликатов.

В каскадном подходе: сначала применяется быстрая техника (например, алгоритм Бродера, основанный на Shingling), чтобы найти потенциальные дубликаты. Затем к этому сокращенному списку применяется вторая, более точная техника (например, алгоритм Чарикара/SimHash), которая проверяет кандидатов по высокому порогу схожести (упоминается порог в 97%), отсеивая ложные срабатывания.

В контекстно-зависимом подходе: система сначала определяет, принадлежат ли два документа одному веб-сайту. Если да, используется первая техника схожести. Если нет, используется вторая, отличная от первой, техника.

Актуальность для SEO

Высокая. Обнаружение дубликатов является фундаментальной задачей для любой поисковой системы для обеспечения эффективности индексации и качества ранжирования. Описанные техники, в частности комбинация Shingling (MinHash) и SimHash (Random Projections), являются стандартными и широко используемыми методами в индустрии для крупномасштабного обнаружения дубликатов.

Важность для SEO

Патент имеет высокое значение для SEO (8/10). Понимание механизмов, с помощью которых Google идентифицирует дубликаты, критически важно для управления каноникализацией, фасетной навигацией, синдикацией контента и обеспечения индексации уникального контента. Патент раскрывает, что система чувствительна как к порядку слов, так и к их частоте, и может использовать разные подходы для внутрисайтовых и внешних дубликатов.

Детальный разбор

Термины и определения

Document (Документ)

Любой контент, подлежащий анализу: веб-страницы, текстовые файлы, мультимедиа и т.д.

Token (Токен)

Элемент последовательности, полученный из документа. Обычно это слово или хеш слова (например, с использованием Rabin’s fingerprinting), полученный после удаления разметки и форматирования.

Shingles (Шинглы, k-grams)

Перекрывающиеся подпоследовательности из k последовательных токенов документа. Используются в алгоритме Бродера.

Minvalues (Минимальные значения)

В алгоритме Бродера: наименьшие значения хешей шинглов, полученные при использовании m различных хеш-функций. Составляют m-мерный вектор.

Supershingles (Супершинглы)

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

Broder Algorithm (Алгоритм Бродера)

Техника обнаружения дубликатов, основанная на Shingling и Minvalues. Она зависит от порядка токенов (order dependent), но не зависит от их частоты (frequency independent). Оценивает схожесть как пересечение множеств (Jaccard Index).

Charikar Algorithm (Алгоритм Чарикара, SimHash)

Техника, основанная на случайных проекциях (random projections). Каждый токен проецируется в b-мерное пространство, векторы токенов суммируются для получения вектора документа, который затем преобразуется в битовую строку. Не зависит от порядка токенов (order independent), но зависит от их частоты (frequency dependent). Оценивает схожесть по косинусному расстоянию (Hamming distance).

Boilerplate (Шаблонный текст)

Повторяющиеся блоки текста на сайте (меню, футер, сайдбары), которые могут приводить к ложному определению страниц как дубликатов.

Ключевые утверждения (Анализ Claims)

Данная публикация (US20120290597A1) является продолжением (continuation) более ранней заявки. Claims 1-29 отменены (canceled). Анализируются Claims 30-38, которые фокусируются на контекстно-зависимом подходе.

Claim 30 (Независимый пункт): Описывает метод обработки набора документов для определения почти дубликатов.

1. Система принимает набор документов.
2. Для одной или нескольких пар документов система определяет, происходят ли документы в паре с одного и того же веб-сайта (same Website).
3. Если документы с одного сайта, для определения схожести используется первая техника (first document similarity technique).
4. Если документы с разных сайтов, используется вторая техника (second document similarity technique).
5. Первая и вторая техники отличаются друг от друга.

Ядром изобретения в этой публикации является адаптивный выбор алгоритма определения схожести в зависимости от источника документов (внутрисайтовый или межсайтовый анализ).

Claim 31 (Зависимый от 30): Уточняет характеристики первой техники (для одного сайта). Она может быть зависящей от порядка токенов (token order dependent) и не зависящей от частоты токенов (token frequency independent). Это характеристики алгоритма Бродера.

Claim 32 (Зависимый от 30): Уточняет характеристики второй техники (для разных сайтов). Она может быть не зависящей от порядка токенов (token order independent) и зависящей от частоты токенов (token frequency dependent). Это характеристики алгоритма Чарикара (SimHash).

Примечание: Хотя Claims фокусируются на контекстно-зависимом подходе, значительная часть описания патента (Description) посвящена каскадному подходу (использование Техники 1 для фильтрации и Техники 2 для уточнения). Это важно для понимания общего контекста изобретения.

Где и как применяется

Изобретение применяется на ранних этапах обработки контента для повышения эффективности всей системы.

CRAWLING – Сканирование и Сбор данных
На этом этапе система может использовать обнаружение дубликатов для оптимизации краулингового бюджета, избегая повторной загрузки уже известного контента с зеркальных сайтов или других URL.

INDEXING – Индексирование и извлечение признаков
Основное применение. Система анализирует документы в репозитории для выявления почти дубликатов. Это необходимо для выбора канонической версии документа (Canonicalization), экономии места в индексе и предотвращения кластеризации идентичного контента.

RANKING – Ранжирование
Хотя это не основная цель патента, результаты обнаружения дубликатов используются на этапе ранжирования, чтобы избежать показа нескольких идентичных результатов (SERP Clustering) пользователю.

Входные данные:

• Набор документов (например, веб-страницы из репозитория).
• URL документов (для определения принадлежности к сайту).

Выходные данные:

• Идентифицированные наборы (кластеры) почти дублирующихся документов.

На что влияет

• Конкретные типы контента: В первую очередь влияет на веб-страницы и текстовые документы.
• Конкретные ниши или тематики: Сильное влияние в E-commerce (вариации товаров, фасетная навигация), новостных сайтах (агрегация, синдикация новостей), и на любых крупных сайтах с большим количеством шаблонного контента (boilerplate).
• Структура сайта: Влияет на то, как обрабатывается контент внутри одного домена по сравнению с контентом на разных доменах. Патент явно признает проблему boilerplate для внутрисайтового анализа.

Когда применяется

• Условия применения: Алгоритмы применяются при обработке документов для включения в индекс или при обновлении индекса.
• Триггеры активации: Триггером для выбора конкретного алгоритма (в подходе Claims 30-38) является сравнение источников (URL/доменов) двух документов. Триггером для активации второго этапа (в каскадном подходе) является обнаружение потенциальной схожести на первом этапе.

Пошаговый алгоритм

Алгоритм А: Контекстно-зависимый подход (на основе Claims 30-38)

1. Прием данных: Система принимает набор документов для анализа.
2. Итерация по парам: Система начинает процесс сравнения пар документов.
3. Определение контекста: Для текущей пары документов определяется, принадлежат ли они одному и тому же веб-сайту (например, путем анализа домена в URL).
4. Выбор техники схожести:
   • Если документы с одного сайта: выбирается Техника 1 (например, алгоритм, устойчивый к boilerplate, или алгоритм, зависящий от порядка слов).
   • Если документы с разных сайтов: выбирается Техника 2 (например, алгоритм, зависящий от частоты слов).
5. Вычисление схожести: Применяется выбранная техника для определения, является ли пара почти дубликатом.
6. Агрегация результатов: Формируется список идентифицированных дубликатов.

Алгоритм Б: Каскадный подход (на основе Description патента)

1. Прием данных: Система принимает набор документов.
2. Первичная обработка (Этап 1): Набор документов обрабатывается с использованием первой техники схожести (например, алгоритм Бродера: Shingling -> Minvalues -> Supershingles).
3. Генерация кандидатов: Определяется начальный набор потенциальных почти дубликатов (например, пары, у которых совпали хотя бы два Supershingles).
4. Вторичная обработка (Этап 2): Начальный набор кандидатов обрабатывается с использованием второй техники схожести (например, алгоритм Чарикара: Токены -> Random Projections -> Битовый вектор/SimHash).
5. Вычисление точной схожести: Для каждой пары вычисляется значение схожести по второй технике (например, количество совпадающих битов).
6. Фильтрация по порогу: Проверяется, превышает ли значение схожести установленный высокий порог (например, 97%).
7. Формирование финального набора: Пары, не достигшие порога, удаляются из набора. Оставшиеся пары формируют финальный набор почти дубликатов.

Какие данные и как использует

Данные на входе

• Контентные факторы: Текст документа. Перед анализом HTML-разметка заменяется пробелами или игнорируется. Текст преобразуется в последовательность токенов (token sequence).
• Технические факторы: URL документа. Используется для определения, находятся ли документы на одном сайте (Claim 30).
• Мультимедиа факторы: Упоминается возможность использования URL в тегах IMG как токенов для различения страниц с разными изображениями. Если URL изображения указывает на тот же хост, может использоваться только имя файла.

Какие метрики используются и как они считаются

Патент использует метрики из двух основных алгоритмов:

Метрики Алгоритма Бродера (Shingling):

• Схожесть (B-similarity): Основана на аппроксимации коэффициента Жаккара (Jaccard Index) — пересечение множеств шинглов, деленное на их объединение. На практике измеряется количеством совпадающих Minvalues или Supershingles.
• Пороги: Два документа считаются B-similar, если их векторы Supershingles совпадают как минимум в двух супершинглах.
• Параметры: Длина шингла k (например, от 5 до 10 токенов).

Метрики Алгоритма Чарикара (SimHash):

• Схожесть (C-similarity): Пропорциональна косинусному сходству (cosine similarity) документов. На практике измеряется количеством битов, по которым совпадают финальные битовые векторы (расстояние Хэмминга).
• Пороги: Два документа считаются C-similar, если количество совпадающих битов превышает порог t.
• Параметры: Размерность проекции b (например, 384 бита).

Метрики Комбинированного подхода:

• Пороговые значения: В каскадном методе используется высокий порог для второго этапа (фильтрации). В патенте упоминаются пороги около 97% (или как минимум 96%) от размерности b. Например, 372 из 384 битов.

Выводы

1. Комплексный подход к дубликатам: Google не полагается на один алгоритм для обнаружения дубликатов. Используется комбинация техник (каскадная или контекстно-зависимая), чтобы повысить точность и полноту.
2. Важность порядка и частоты слов: Система учитывает оба аспекта. Алгоритмы типа Бродера (Shingling) чувствительны к порядку слов (структуре предложений), а алгоритмы типа Чарикара (SimHash) чувствительны к общему составу и частоте слов, игнорируя порядок.
3. Адаптация к контексту (Сайт vs. Веб): Патент явно указывает на возможность применения разных алгоритмов для анализа дубликатов внутри одного сайта и между разными сайтами. Это связано с тем, что внутрисайтовые дубликаты часто вызваны boilerplate-контентом.
4. Высокие пороги схожести: Для того чтобы контент был признан почти дубликатом, он должен быть чрезвычайно похож. Упомянутый порог в 97% совпадения по SimHash на финальном этапе фильтрации указывает на очень строгие критерии.
5. Уникальность требует существенных изменений: Чтобы избежать классификации как дубликата, изменения в контенте должны быть достаточно значительными, чтобы повлиять как на последовательность шинглов, так и на финальный хеш (SimHash).

Практика

Best practices (это мы делаем)

• Обеспечение глубокой уникальности контента: При создании или переработке контента необходимо изменять не только отдельные слова (синонимы), но и структуру предложений (порядок слов) и общий состав текста. Это гарантирует, что и Shingling, и SimHash будут существенно отличаться от оригинала.
• Управление Boilerplate-контентом: Необходимо следить за соотношением уникального основного контента и шаблонного текста (меню, футер, сайдбары). Если boilerplate доминирует, страницы внутри сайта могут быть ошибочно классифицированы как дубликаты, что может привести к проблемам с индексацией (например, ‘Duplicate without user-selected canonical’).
• Контроль каноникализации: Поскольку система эффективно обнаруживает дубликаты (например, версии для печати, AMP, вариации товаров с разными параметрами), критически важно активно управлять выбором канонической версии с помощью rel=canonical, чтобы избежать автоматического выбора неверной страницы.
• Использование уникальных медиа: Патент предполагает, что URL изображений могут использоваться как токены. Использование уникальных изображений с уникальными именами файлов может помочь дифференцировать страницы, которые в остальном похожи (например, карточки товаров).

Worst practices (это делать не надо)

• Поверхностный рерайтинг и синонимайзинг: Если сохраняется исходный порядок слов, алгоритм Бродера (Shingling) может идентифицировать контент как дубликат. Если общий состав слов остается близким к оригиналу, SimHash также покажет высокую схожесть.
• Создание множества страниц с минимальными отличиями: Генерация страниц, отличающихся только несколькими словами (например, названием города в SEO-лендингах), будет легко обнаружена как создание почти дубликатов.
• Синдикация контента без добавленной ценности: Публикация идентичного контента на разных доменах приведет к его кластеризации. Только один источник будет ранжироваться, если не добавить существенный уникальный контекст или функционал.
• Игнорирование внутрисайтовых дубликатов: Полагаться на то, что Google сам разберется с техническими дубликатами (например, из-за параметров URL), опасно. Система обнаружит их, но может выбрать неверный каноникал.

Стратегическое значение

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

Практические примеры

Сценарий: Уникализация карточек товаров в E-commerce

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

1. Проблема: Алгоритмы Shingling и SimHash покажут очень высокую схожесть (близкую к 97%+), так как большая часть токенов и их порядок совпадают. Страницы могут быть кластеризованы, и только одна версия попадет в индекс.
2. Решение на основе патента:
   • Изменение состава (для SimHash): Добавить уникальный контент для каждой вариации. Например, пользовательские отзывы, относящиеся именно к этому цвету, или уникальные советы по использованию.
   • Изменение порядка (для Shingling): Изменить структуру представления характеристик или описания для разных вариаций.
   • Использование медиа (Токены): Убедиться, что изображения имеют уникальные имена файлов (например, product-red.jpg, product-blue.jpg), так как они могут учитываться как токены.
3. Ожидаемый результат: Снижение схожести ниже пороговых значений, что позволит страницам индексироваться как уникальным (при условии правильной настройки каноникализации, если это необходимо).

Вопросы и ответы