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

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

Document (Документ)

Любой машиночитаемый продукт, сканируемый краулером (веб-страница, файл и т.д.).

Features / Tokens (Признаки / Токены)

Элементы, извлекаемые из документа для генерации отпечатка (слова, числа, основы слов, синонимы). Стоп-слова могут исключаться.

Fingerprint / Hash Value (Отпечаток / Хеш-значение)

Компактное значение (например, 64-битное), генерируемое для документа. Ключевое свойство: у схожих документов отпечатки также схожи.

k / Hamming distance (Расстояние Хэмминга)

Количество битов, в которых отличаются два отпечатка. Используется как мера схожести. Порог k — максимально допустимое различие для признания документов дубликатами (например, k=3).

Near-duplicate document (Почти дубликат документа)

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

Permutation (Перестановка, $x_i$)

Процесс изменения порядка битов в отпечатке по заранее определенному правилу.

Permuted Fingerprint (Переставленный отпечаток)

Отпечаток после применения к нему перестановки.

Sequence of bit positions / Prefix (Последовательность битовых позиций / Префикс, $p_i$)

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

Simhash

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

Tables (Таблицы, $T_i$)

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

Weights (Веса)

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

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

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

1. Система сканирует документ и определяет его fingerprint.
2. Система ищет кандидатов среди сохраненных отпечатков. Ключевой механизм: поиск осуществляется путем сравнения только части отпечатка (sequence of bit positions), а не всего отпечатка.
3. Для найденных кандидатов система определяет, являются ли они substantially similar к новому отпечатку. Схожесть определяется как отличие не более чем на k битов (где k > 0).
4. Если найден схожий отпечаток, новый документ идентифицируется как near-duplicate.

Claim 2 (Зависимый от 1): Детализирует генерацию отпечатка.

Отпечаток генерируется путем извлечения признаков (set of features), присвоения им весов (weight) и вычисления отпечатка на основе этих взвешенных признаков.

Claim 7 (Зависимый от 6 и 1): Описывает механизм эффективного хранения.

Система применяет несколько перестановок (plurality of permutations) к каждому отпечатку. В каждой из нескольких таблиц хранятся отпечатки, обработанные соответствующей перестановкой. Это позволяет реализовать быстрый поиск по части битов (Claim 1).

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

Исходящие ссылки (outgoing links) в документе игнорируются, если он идентифицирован как near-duplicate.

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

1. Координатор получает новые документы, определяет их отпечатки и рассылает их группе устройств.
2. Устройства поддерживают основную таблицу (First table) существующих отпечатков и создают временную таблицу (Second table) для нового пакета.
3. Устройства определяют схожесть между отпечатками в таблицах, используя тот же механизм: совпадение по последовательности битов и проверка отличия не более чем на k битов.
4. При обнаружении схожести новый отпечаток помечается как дубликат.

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

Изобретение применяется исключительно на этапе сканирования для оптимизации ресурсов.

CRAWLING – Сканирование и Сбор данных
Это основная область применения патента. Система (Web Crawler Engine) использует этот механизм сразу после загрузки документа (fetched) для принятия решения о его дальнейшей обработке.

• Взаимодействие компонентов: Fetch Bots загружают документ и передают его в Duplicate Document Detector. Детектор использует Set of Tables (базу отпечатков) для проверки. Результат передается в Content Manager.
• Принятие решений: Если документ — дубликат, Content Manager игнорирует его исходящие ссылки. Если нет — извлекает ссылки и добавляет их в очередь сканирования (Address List).

INDEXING – Индексирование и извлечение признаков
Патент косвенно влияет на этот этап. Если документ отброшен на этапе CRAWLING как дубликат, он не передается на индексацию. Процесс извлечения признаков (Feature Extraction) и расчет весов, необходимые для генерации fingerprint, также происходят на ранних этапах обработки.

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

• Содержимое только что загруженного документа.
• База данных отпечатков ранее просканированных документов (Set of Tables).
• Параметры конфигурации (k, f, $p_i$, перестановки $x_i$).

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

• Решение: является ли документ near-duplicate.
• Список исходящих ссылок (если документ не дубликат).
• Обновленная база данных отпечатков (если документ не дубликат).

На что влияет

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

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

• Условия работы: Алгоритм применяется к каждому документу, загруженному Fetch Bot в процессе сканирования (в реальном времени или пакетном режиме).
• Триггеры активации: Факт загрузки документа является триггером для запуска процесса.
• Пороговые значения: Ключевым порогом является значение k (расстояние Хэмминга). Если отпечатки отличаются на k битов или меньше, система считает документы дубликатами. В примере патента используется k=3 для 64-битного отпечатка.

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

Процесс обработки нового документа

1. Идентификация и загрузка: Система идентифицирует адрес (URL) и загружает документ.
2. Генерация отпечатка (Fingerprint Generation):
   1. Из документа извлекается набор признаков (features).
   2. Каждому признаку присваивается вес (weight) в зависимости от его важности (например, заголовок важнее рекламы).
   3. На основе признаков и весов генерируется f-битный отпечаток (F) с использованием хеширующей функции (например, Simhash).
3. Генерация переставленных отпечатков: К отпечатку F применяется набор заранее определенных перестановок (