Как Google использует Min-Hashing и Shingling для выявления дубликатов и классификации взаимосвязей между документами в большом корпусе

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

Corpus (Корпус)

Общая коллекция цифровых текстовых томов (документов), подлежащая анализу.

Digital Text Volume (Цифровой текстовый том)

Цифровое представление документа (например, книги), текст которого представлен в машиночитаемом формате (часто результат OCR).

Shingles (Шинглы)

Перекрывающиеся последовательности слов, извлеченные из текста. Например, 5-word shingles. Используются как базовые признаки (features) документа.

Min-Hashing (Мин-хеширование)

Метод снижения размерности. Множество шинглов преобразуется в компактный набор минимальных хеш-значений (Min-Hash values). Этот набор служит «отпечатком» документа или страницы.

Reduced Feature Set (Сокращенный набор признаков)

Компактное представление тома или страницы, полученное после применения Min-Hashing.

Volume Similarity Data (Данные о сходстве томов)

Метрики, описывающие степень сходства между двумя томами, обычно основанные на количестве общих Min-Hash values.

Page Similarity Data (Данные о сходстве страниц)

Метрики, описывающие степень сходства между отдельными страницами двух разных томов.

Signals (Сигналы)

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

Linear page-to-page fit (Линейное соответствие страниц)

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

Relative consecutive page correlation (Относительная корреляция последовательных страниц)

Сигнал, определяющий периодические паттерны совпадения и несовпадения страниц. Указывает на одинаковый контент с разной пагинацией.

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

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

1. Сравнение томов в корпусе для получения данных о сходстве томов (volume similarity data).
2. Идентификация кластера похожих томов на основе этих данных.
3. Сравнение страниц пары томов внутри кластера для определения данных о сходстве страниц (page similarity data).
4. Извлечение сигналов из данных о сходстве томов и страниц. Ключевое требование: извлеченные сигналы должны включать по крайней мере один из следующих:
   • Меру линейного соответствия страниц (linear page-to-page fit).
   • Меру относительной корреляции последовательных страниц (relative consecutive page correlation).
5. Классификация взаимосвязи между парой томов на основе извлеченных сигналов.
6. Сохранение данных классификации.

Ядро изобретения заключается в многоуровневом подходе (том -> страница) и использовании специфических сигналов для классификации типа взаимосвязи, а не просто факта дублирования.

Claim 2 (Зависимый от 1): Детализирует метод сравнения томов (Шаг 1 из Claim 1), подтверждая использование Min-Hashing.

1. Определение набора репрезентативных признаков для тома (например, Shingles).
2. Применение множества хеш-функций к этим признакам.
3. Выбор минимального хеш-значения (minimum hash value) для каждой функции, чтобы создать сокращенный набор признаков (reduced feature set).
4. Сравнение сокращенных наборов признаков разных томов для получения данных о сходстве.

Claim 4 (Зависимый от 1): Детализирует метод сравнения страниц (Шаг 3 из Claim 1). Используется тот же процесс Min-Hashing, что и в Claim 2, но применительно к признакам отдельных страниц.

Claim 7 (Зависимый от 1): Детализирует этап классификации (Шаг 5 из Claim 1).

1. Расчет уровня уверенности (confidence level) для каждого из множества классов. Уровень уверенности указывает на вероятность того, что взаимосвязь описывается данным классом.
2. Присвоение класса взаимосвязи на основе рассчитанных уровней уверенности.

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

Изобретение применяется на этапе обработки и организации корпуса данных.

INDEXING – Индексирование и извлечение признаков
Это основная фаза применения патента. Система анализирует сырой контент (цифровые тома) для извлечения признаков (Shingles, Min-Hash values). Происходит сравнение этих признаков для обнаружения дубликатов, кластеризации похожих документов и классификации взаимосвязей между ними. Это помогает в управлении индексом, выборе канонических версий (canonicalization) и идентификации оригинальных источников контента.

Это преимущественно офлайн-процесс или процесс пакетной обработки для управления качеством корпуса, а не процесс ранжирования в реальном времени.

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

• Цифровые текстовые тома (Digital Text Volumes) — необработанный текст, часто полученный через OCR.

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

• Processing Data: Репрезентативные признаки (Min-Hash values) для томов и страниц.
• Classification Data: Данные, описывающие взаимосвязи между парами томов (например, "Том А идентичен Тому Б", "Том С является подмножеством Тома D").
• Кластеры связанных томов.

На что влияет

• Конкретные типы контента: В первую очередь влияет на большие объемы текста, подверженные дублированию: книги, длинные документы, новостные статьи (синдикация), описания товаров в e-commerce, техническая документация.
• Управление корпусом: Влияет на то, как Google управляет дублированным контентом и идентифицирует оригинальные источники или наиболее полные версии документа.

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

• Временные рамки: Применяется во время обработки и индексирования корпуса (офлайн-процесс), при добавлении новых документов или периодической переоценке корпуса.
• Триггеры активации: Детальный анализ на уровне страниц активируется только для пар томов, которые были предварительно идентифицированы как похожие на уровне всего тома (т.е. принадлежат одному кластеру).
• Пороговые значения: Используются пороги сходства для кластеризации. Например, тома должны иметь более определенного процента (упоминается 10%) общих Min-Hash values, чтобы считаться похожими.

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

1. Генерация признаков (Уровень тома и страницы): Система обрабатывает каждый цифровой том. Текст всего тома и текст каждой отдельной страницы преобразуется в Shingles (например, перекрывающиеся последовательности из 5 слов).
2. Снижение размерности (Min-Hashing): К наборам шинглов применяются множественные независимые хеш-функции (например, 100 для тома, 34 для страницы). Для каждой функции выбирается минимальное полученное значение. Это формирует компактный набор Min-Hash values для каждого тома и страницы.
3. Сравнение томов и первичная кластеризация: Min-Hash values томов индексируются. Система сравнивает тома и идентифицирует те, которые имеют больше порогового количества общих хеш-значений (например, >10%). При этом могут игнорироваться (дисконтироваться) хеши, которые встречаются слишком часто в корпусе (например, более чем в 300 томах). Эти тома группируются в кластеры похожих документов.
4. Сравнение страниц (Внутри кластера): Для каждой пары томов внутри кластера система сравнивает их страницы, используя Min-Hash values страниц. Генерируются оценки сходства для пар страниц (page similarity data).
5. Извлечение сигналов: Система анализирует page similarity data для извлечения метрик (сигналов), описывающих паттерны сходства. Ключевые сигналы:
   • Связь между общей схожестью тома и средней схожестью страниц.
   • Linear page-to-page fit (оценка смещения и множителя пагинации).
   • Relative consecutive page correlation (выявление периодических паттернов совпадения/несовпадения страниц).
6. Классификация взаимосвязей: Извлеченные сигналы подаются на вход мультиклассового классификатора (multi-class classifier), использующего машинное обучение для определения типа взаимосвязи и расчета уровня уверенности (confidence level):
   • Same pagination (Одинаковый текст и пагинация).
   • Different pagination (Одинаковый текст, разная пагинация).
   • Contiguous subset (Один том содержит текст другого как непрерывное подмножество).
   • Overlapping text (Значительное пересечение текста).
7. Хранение и финальная кластеризация: Данные о классифицированных взаимосвязях сохраняются. Тома могут быть окончательно сгруппированы на основе этих данных (например, кластер всех версий одной и той же книги).

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

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

Патент сосредоточен исключительно на анализе текстового содержания.

• Контентные факторы: Полный текст цифровых томов. Критически важна последовательность слов в тексте.
• Структурные факторы: Используется структурное разделение текста на страницы (пагинация), так как признаки генерируются как для всего тома, так и для отдельных страниц.

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

• Shingles (Шинглы): Базовая единица анализа. Перекрывающиеся последовательности слов (например, 5-word shingles).
• Min-Hash Values: Компактное представление набора шинглов. Вычисляется путем выбора минимального значения, полученного при применении конкретной хеш-функции ко всем шинглам в наборе.
• Similarity Score (Оценка сходства): Оценка сходства между двумя наборами (томами или страницами). Рассчитывается как доля общих Min-Hash values.
• Пороговые значения (Thresholds): Минимальная оценка сходства для включения томов в один кластер (например, 10% общих хешей). Также используется дисконтирование хеш-значений, которые встречаются слишком часто в корпусе, чтобы избежать ложных срабатываний.
• Сигналы (Производные метрики):
  • Measure of volume similarity vs page similarity: Соотношение глобального сходства тома и среднего сходства страниц. Высокое сходство тома при низком сходстве страниц указывает на разную пагинацию.
  • Linear page-to-page fit: Моделирует распределение текста, вычисляя смещение (offset) и множитель (multiplier). Множитель, близкий к 1, указывает на идентичную пагинацию. Большое смещение может указывать на подмножество.
  • Relative consecutive page correlation: Метрика для обнаружения периодических паттернов сходства страниц, что характерно для разной пагинации.
• Алгоритмы машинного обучения: Используется мультиклассовый классификатор (multi-class classifier), обученный с использованием машинного обучения на извлеченных сигналах для определения финальной классификации взаимосвязи и расчета confidence level.

1. Масштабируемое обнаружение дубликатов: Google использует вероятностные методы снижения размерности (Min-Hashing) для эффективного обнаружения почти дубликатов в огромных масштабах. Это позволяет избежать вычислительно затратного прямого сравнения текстов.
2. Важность последовательности слов: Использование Shingling означает, что система анализирует последовательность слов для определения сходства. Это делает простые текстовые манипуляции (поверхностный рерайт) малоэффективными, если основная структура фраз сохраняется.
3. Многоуровневый анализ: Система использует иерархический подход. Сначала определяется глобальное сходство (на уровне всего документа), которое служит фильтром перед более детальным анализом гранулярного сходства (на уровне страниц или фрагментов).
4. Классификация взаимосвязей, а не только дублирования: Цель системы — не просто найти дубликаты, а понять природу взаимосвязи. Классификации типа Different Pagination (реформатирование) или Contiguous Subset (синдикация/заимствование) критически важны для управления контентом и определения первоисточников.
5. Фундаментальная технология для каноникализации: Описанные методы являются основой для систем управления любым большим корпусом, включая веб-индекс, и играют ключевую роль в процессах каноникализации и управления дублированным контентом.

Практическое применение в SEO

ВАЖНО: Этот патент описывает внутренние процессы Google для управления корпусом оцифрованных книг (Google Books). Однако лежащие в его основе технологии — Shingling и Min-Hashing — являются стандартными техниками для обнаружения дубликатов и широко используются в веб-поиске. Приведенные ниже выводы основаны на понимании этих технологий и их влияния на SEO.

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

• Обеспечение четкой каноникализации: Наличие таких эффективных технологий обнаружения почти дубликатов подчеркивает необходимость использования тегов rel="canonical". Google может легко идентифицировать страницы с одинаковым или очень похожим контентом, даже если HTML-разметка или URL отличаются.
• Управление синдицированным контентом: Система способна идентифицировать Contiguous Subset — когда один документ полностью содержится в другом. При синдикации контента критически важно обеспечить четкую атрибуцию и ссылку на оригинал (в идеале через rel=canonical), чтобы помочь поисковой системе правильно определить первоисточник и консолидировать сигналы ранжирования.
• Фокус на подлинной уникальности контента: Поскольку система использует Shingling (анализ последовательностей слов) для сравнения, необходимо создавать действительно уникальный контент. Избегайте обширного цитирования, шаблонного текста (boilerplate) или копирования структуры предложений из других источников.

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

• Рерайт и "Спиннинг" контента: Техники поверхностного рерайта, которые сохраняют исходную последовательность многих шинглов, будут эффективно обнаружены Min-Hashing. Система идентифицирует такие тексты как очень похожие на оригинал (почти дубликаты).
• Публикация идентичного контента с минимальными изменениями форматирования: Система специально разработана для обнаружения случаев Different Pagination (разное форматирование/пагинация при одинаковом тексте). Изменение HTML-структуры, дизайна или разбиение текста на страницы не помешает Google распознать дубликат.
• Создание множества страниц с минимальными отличиями (Doorways): Генерация страниц с высоким уровнем сходства приведет к их кластеризации с помощью Min-Hashing и выбору только одной канонической версии, что делает эту тактику неэффективной.

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

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

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

Сценарий: Обнаружение синдицированных статей и каноникализация

1. Контент: Сайт А публикует оригинальную статью. Сайт Б (новостной агрегатор) перепечатывает статью целиком, но использует совершенно другой дизайн, HTML-шаблон, навигацию и рекламу.
2. Анализ Google (Shingling): Google индексирует обе страницы и преобразует основной контент в 5-word shingles. Несмотря на разный HTML, наборы шинглов основного контента идентичны.
3. Анализ Google (Min-Hashing): Система вычисляет Min-Hash values для обеих страниц. Поскольку наборы шинглов идентичны, Min-Hash values также будут идентичны (или почти идентичны).
4. Обнаружение и Классификация: Система фиксирует ~100% сходство и классифицирует взаимосвязь (например, как Different Pagination, если шаблоны сильно отличаются). Страницы помещаются в один кластер дубликатов.
5. Результат (Каноникализация): Google идентифицирует страницы как дубликаты. Система каноникализации затем использует другие сигналы (например, время публикации, авторитетность сайта, наличие rel="canonical" от Сайта Б к Сайту А), чтобы выбрать одну версию (Сайт А) для показа в результатах поиска.