Как Google использует алгоритмы "Shingling" для эффективного обнаружения дубликатов и похожего контента в масштабах веба

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

Token (Токен)

Элементарная единица последовательности. В контексте веб-документов это может быть буква, символ, слово или строка символов.

Fingerprint (Отпечаток) / Numerical Value

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

Sequence (Последовательность)

Упорядоченный набор токенов. Например, текст документа.

Shingle (Шингл) / Subsequence (Подпоследовательность)

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

k-tuple (k-кортеж)

Шингл, состоящий ровно из k токенов.

Shingling (Шинглирование)

Процесс извлечения набора шинглов из последовательности. Обычно реализуется как скользящее окно размером k.

Consistency (Консистентность/Согласованность)

Свойство алгоритма выбора шинглов, гарантирующее, что для идентичных последовательностей будут выбраны идентичные наборы шинглов.

Coverage (Покрытие)

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

Extreme Value (Экстремальное значение)

Наибольшее или наименьшее числовое значение (fingerprint) среди токенов внутри одного шингла.

Modulo k (По модулю k)

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

Match Rate (Степень совпадения)

Метрика для оценки сходства двух последовательностей (A и B), часто рассчитываемая как коэффициент Жаккара: (Пересечение шинглов A и B) / (Объединение шинглов A и B).

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

Патент описывает три основных алгоритма выбора шинглов. Все они направлены на создание репрезентативного подмножества шинглов для сравнения.

Алгоритм 1: Выбор на основе экстремальных значений (Claims 1, 29)

Claim 1 (Независимый пункт): Описывает метод выбора шинглов с использованием наибольших значений.

1. Система парсит первую последовательность токенов (документ) в шинглы длины k.
2. Выбирается первое подмножество шинглов. Критерий выбора: в каждом выбранном шингле токен, находящийся на первой позиции ИЛИ на последней позиции, должен иметь НАИБОЛЬШЕЕ числовое значение среди всех токенов в этом шингле.
3. Тот же процесс повторяется для второй последовательности.
4. Полученные подмножества сравниваются.

Claim 29 (Независимый пункт): Аналогичен Claim 1, но использует НАИМЕНЬШЕЕ числовое значение в качестве критерия выбора.

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

Алгоритм 2: Выбор на основе значений по модулю k (Claim 9)

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

1. Система парсит последовательность в шинглы длины k.
2. Для каждого шингла вычисляются значения токенов по модулю k (остаток от деления значения токена на k).
3. Определяются позиции токенов в шингле (например, от 0 до k-1).
4. Выбирается подмножество шинглов. Критерий выбора: в каждом выбранном шингле значение хотя бы одного токена по модулю k должно СОВПАДАТЬ с его позицией в этом шингле.
5. Полученные подмножества для разных последовательностей сравниваются.

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

Алгоритм 3: Выбор на основе групп меньших шинглов (Claim 15)

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

1. Система парсит последовательность в шинглы длины k.
2. Определяется группа S, состоящая из предопределенных шинглов меньшей длины m (m <= k).
3. Выбирается смещение (offset) относительно начала шингла длины k.
4. Выбирается подмножество шинглов длины k. Критерий выбора (должно выполняться одно из двух условий):
   1. Шингл длины m, начинающийся с выбранного смещения внутри шингла длины k, принадлежит к группе S.
   2. ИЛИ Ни один шингл длины m внутри шингла длины k не принадлежит к группе S.
5. Полученные подмножества сравниваются.

Этот алгоритм позволяет более тонко настраивать частоту выбора шинглов в зависимости от их содержимого и предопределенных паттернов (Группа S).

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

Изобретение является частью инфраструктуры обработки и сравнения контента.

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

INDEXING – Индексирование и извлечение признаков
Основное применение патента. В процессе индексации система должна определить, является ли новый или обновленный контент дубликатом уже существующего.

• Извлечение Признаков (Feature Extraction): Алгоритмы шинглирования используются для генерации стабильных и эффективных признаков (отпечатков) документа.
• Обнаружение дубликатов и Каноникализация: Сгенерированные отпечатки сравниваются с отпечатками документов в индексе. Если степень совпадения (Match Rate) высока, документы могут быть признаны почти дубликатами (near-duplicates), что влияет на выбор канонической версии.

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

• Сырой текст документа (последовательность токенов).
• Числовые значения (хеши/fingerprints) для каждого токена.
• Параметр k (длина шингла).

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

• Репрезентативное подмножество шинглов (отпечаток документа).
• Метрики сходства при сравнении с другими документами.

На что влияет

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

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

• Триггеры активации: Применяется каждый раз, когда система обрабатывает текстовый контент во время индексации для генерации его отпечатка.
• Условия работы: Алгоритмы предназначены для сравнения двух или более последовательностей на предмет сходства. Они могут использоваться как для точного (exact matching), так и для приблизительного (approximate matching) сравнения.

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

Описание на примере Алгоритма 1 (Экстремальные значения, Claim 1).

1. Токенизация: Исходный документ преобразуется в последовательность токенов (например, слов).
2. Хеширование: Каждому токену присваивается числовое значение (fingerprint).
3. Шинглирование (Парсинг): Последовательность парсится в перекрывающиеся шинглы длины k. (Например, при k=5, скользящее окно перемещается по документу).
4. Определение Экстремума: Для каждого сгенерированного шингла определяется НАИБОЛЬШЕЕ значение (fingerprint) среди его k токенов.
5. Проверка Условия Выбора: Проверяется, находится ли токен с этим наибольшим значением на ПЕРВОЙ или ПОСЛЕДНЕЙ позиции в данном шингле.
6. Выборка: Если условие выполнено, шингл выбирается и добавляется в первое подмножество (отпечаток документа А).
7. Повторение для Документа Б: Шаги 1-6 повторяются для второго документа, создавая второе подмножество (отпечаток документа Б).
8. Сравнение: Первое и второе подмножества сравниваются для определения количества общих шинглов.
9. Оценка Сходства: Рассчитывается Match Rate (например, Коэффициент Жаккара) на основе количества общих и уникальных шинглов в двух подмножествах.

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

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

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

• Контентные факторы: Текст документа, представленный как последовательность токенов. Важен порядок токенов.
• Системные данные: Числовые значения (хеши, fingerprints), присвоенные токенам.

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

• k (Длина шингла): Ключевой параметр. Определяет гранулярность анализа. Меньшие k (например, 2-3) обнаруживают более мелкие совпадения, большие k (например, 8-10) используются для обнаружения совпадений на уровне предложений или абзацев.
• Экстремальное значение (Max/Min): Используется в Алгоритме 1. Сравнение числовых значений токенов внутри шингла.
• Значение по модулю k: Используется в Алгоритме 2. Вычисляется как остаток от деления значения токена на k.
• Позиция токена: Используется в Алгоритмах 1 и 2. Определяет местоположение токена внутри шингла (например, первый, последний, или позиция от 0 до k-1).
• Match Rate (Степень совпадения): Метрика сходства двух наборов шинглов. В патенте упоминается формула (Коэффициент Жаккара): $\text{Match Rate}(A, B) = \frac{|\text{Shingles}(A) \cap \text{Shingles}(B)|}{|\text{Shingles}(A) \cup \text{Shingles}(B)|}$

1. Фундаментальный механизм обнаружения дубликатов: Патент описывает ключевые алгоритмы для эффективного сравнения контента в масштабах веба. Шинглирование является основой для систем обнаружения почти дубликатов (near-duplicate detection).
2. Чувствительность к порядку слов: Алгоритмы основаны на непрерывных последовательностях (шинглах). Изменение порядка слов или структуры предложения радикально меняет набор генерируемых шинглов и, следовательно, итоговый отпечаток документа.
3. Эффективность за счет выборки: Ключевая инновация заключается не в самом шинглировании, а в методах выбора репрезентативного подмножества шинглов (например, через экстремальные значения). Это позволяет значительно сократить объем данных, необходимых для сравнения, сохраняя точность.
4. Гарантии Consistency и Coverage: Описанные методы гарантируют, что одинаковый контент всегда будет генерировать одинаковый отпечаток (consistency), и что весь контент будет учтен (coverage). Это критически важно для надежной каноникализации.
5. Не семантическое сходство: Шинглирование обнаруживает лексическое сходство (совпадение последовательностей слов), а не семантическое (смысловое) сходство. Два документа с разным содержанием, но использующие похожие стандартные фразы, могут иметь определенный Match Rate, но система не "понимает" смысл через эти алгоритмы.

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

• Фокус на уникальности структуры контента: При создании нового контента или оптимизации существующего уделяйте внимание не только уникальности слов, но и уникальности порядка слов и структуры предложений. Это гарантирует генерацию уникального набора шинглов.
• Мониторинг уникальности контента: Используйте инструменты, основанные на шинглировании (многие инструменты проверки плагиата работают по схожим принципам), для проверки уникальности вашего контента относительно конкурентов и других страниц вашего сайта.
• Управление синдикацией и агрегацией: При синдикации контента или использовании контента из внешних источников (например, описаний товаров от поставщика) осознавайте, что этот контент будет генерировать идентичные шинглы. Убедитесь, что каноникализация настроена правильно, или добавьте достаточно уникальной ценности на страницу, чтобы общий отпечаток отличался.
• Дифференциация шаблонного контента: Хотя патент не фокусируется на удалении шаблонного контента (boilerplate), он подчеркивает, что шаблонный текст генерирует одинаковые шинглы. Убедитесь, что соотношение уникального контента к шаблонному достаточно велико, чтобы страницы не были классифицированы как почти дубликаты друг друга.

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

• Контент-спиннинг (Content Spinning) низкого качества: Простая замена слов на синонимы может быть неэффективной, если структура предложений сохраняется. Многие шинглы могут остаться неизменными или очень похожими, что приведет к высокому Match Rate.
• Плагиат и Склейка (Patchwriting): Копирование целых предложений или абзацев напрямую обнаруживается системами шинглирования, так как они генерируют идентичные последовательности шинглов.
• Чрезмерное внутреннее дублирование: Создание большого количества страниц с минимальными отличиями (например, гео-страницы, отличающиеся только названием города). Если основной контент идентичен, страницы будут иметь почти идентичные отпечатки и могут быть классифицированы как дубликаты.

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

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

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

Сценарий: Оптимизация описания товара в E-commerce

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

Применение знаний из патента:

1. Анализ: Система Google применила шинглирование (например, с k=8) к описанию товара. Поскольку текст идентичен другим сайтам, сгенерированный набор шинглов также идентичен. Google классифицирует контент как дубликат и выбирает другой сайт в качестве канонического.
2. Действие (Неэффективное): SEO-специалист заменяет несколько слов на синонимы, но сохраняет структуру предложений. Результат: Большинство шинглов длины 8 остаются прежними или меняются незначительно. Match Rate остается высоким. Проблема не решена.
3. Действие (Эффективное): SEO-специалист полностью переписывает описание, меняя структуру предложений, порядок изложения характеристик и добавляя уникальные выводы или отзывы. Результат: Новый текст генерирует совершенно другой набор шинглов. Match Rate с оригинальным описанием значительно снижается. Google воспринимает контент как уникальный.