Как Google использует Топ-N терминов и URL-паттерны для быстрой кластеризации похожих страниц на сайте

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

Document Cluster (Кластер документов)

Финальная группа документов, которые удовлетворяют определенному Pattern String.

Document Group (Группа документов)

Предварительная группа документов, которые имеют идентичные Top N Terms. Используется как основа для поиска Pattern String.

Fingerprint (Отпечаток)

Хеш или компактное представление конкатенации Top N Terms документа. Используется для быстрого сравнения документов при реализации алгоритма.

Minimum Description Length (MDL) (Принцип минимальной длины описания)

Принцип, используемый для выбора наилучшего Pattern String. Он балансирует точность шаблона (меньше подстановочных знаков) с его охватом (больше совпадений URL).

Modified TF-IDF (Модифицированный TF-IDF)

Специфическая метрика оценки терминов, используемая в патенте. Она смещает вес в сторону терминов, часто встречающихся в анализируемом наборе документов (например, шаблонный текст сайта), за счет компонента S в формуле.

Pattern String (Строка шаблона / Шаблон URL)

Шаблон, основанный на URL с использованием подстановочных знаков (например, * или <>), который идентифицируется как общий для подмножества документов.

Term Frequency Score (Оценка частотности термина)

Метрика, оценивающая важность термина в документе (в данном случае, Modified TF-IDF).

Top N Terms (Топ-N терминов)

N терминов с наивысшими оценками Term Frequency Score в документе.

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

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

1. Система идентифицирует множество документов из набора, у которых Top N Terms (по оценке частоты термина) одинаковы.
2. Идентифицируется подмножество этих документов, которые удовлетворяют определенной строке шаблона (Pattern String).
3. Формируется кластер документов (Document Cluster) как минимум из этого подмножества.

Claim 2 и 3 (Зависимые): Уточняют процесс идентификации схожести.

1. Система определяет оценки частоты терминов и упорядочивает их (Claim 2).
2. Критическое уточнение (Claim 3): Идентифицируются документы, у которых не только одинаковые Top N Terms, но и одинаковый порядок этих терминов (по их оценкам). Это строгий критерий структурной схожести.

Claim 7 (Зависимый от 1): Уточняет область применения. Набор документов — это документы, принадлежащие одному и тому же веб-сайту.

Claim 8 (Зависимый от 1): Уточняет природу Pattern String. Строка шаблона — это строка, которой удовлетворяют URL (Universal Resource Locators) документов.

Claim 13 (Независимый пункт): Описывает систему, реализующую метод, аналогичный Claim 1, с акцентом на этапы (расчет оценок, идентификация первого подмножества по Top N и порядку, идентификация второго подмножества по Pattern String, формирование кластера).

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

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

INDEXING – Индексирование и извлечение признаков
Основное применение патента. После сканивания система анализирует документы для вычисления Term Frequency Scores и определения Top N Terms. Этот процесс является частью структурного анализа сайта и обнаружения шаблонного контента (boilerplate detection). Цель — сгруппировать похожие страницы до того, как они будут полностью обработаны, что позволяет применять дальнейшую обработку к выборке из кластера или обрабатывать кластер как единое целое.

CRAWLING – Сканирование и Сбор данных
Результаты кластеризации могут влиять на планирование сканирования (Crawl Scheduling). Если система идентифицирует Document Cluster через шаблон URL (Pattern String), она может оптимизировать краулинговый бюджет, например, адаптируя частоту сканирования для всего кластера на основе анализа выборки документов (sampling).

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

• Набор документов (обычно с одного веб-сайта, согласно Claim 7).
• URL этих документов.
• Предварительно рассчитанная статистика корпуса (для компонента IDF).

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

• Кластеры документов (Document Clusters), каждый из которых связан с определенным Pattern String.

На что влияет

• Конкретные типы контента и ниши: Особенно эффективно на крупных веб-сайтах с шаблонной структурой и предсказуемыми шаблонами URL. Примеры: страницы товаров в E-commerce, новостные статьи, ветки форумов, профили пользователей. Менее эффективно для сайтов с хаотичной структурой или уникальным дизайном каждой страницы.

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

• При каких условиях работает алгоритм: При обработке набора документов, принадлежащих одному веб-сайту, для выявления структурных сходств.
• Триггеры активации и пороговые значения: Процесс группирования активируется, если достаточное количество документов (превышающее пороговый минимальный размер группы, threshold minimum size, например, 4) имеют идентичные Top N Terms. Итерации ограничены максимальным значением N (параметр M, например, 100) для гарантии эффективности O(n).

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

Процесс А: Группировка документов (Поиск оптимального N)

1. Расчет оценок: Для всех терминов в наборе документов рассчитываются Modified TF-IDF. Термины в каждом документе сортируются по убыванию оценки.
2. Инициализация N: Устанавливается значение $N=1$.
3. Группировка по Топ-N: Вычисляются отпечатки (Fingerprint) конкатенации Top N Terms (с учетом порядка). Документы с одинаковыми отпечатками объединяются в Document Groups.
4. Проверка размера групп: Проверяется, есть ли хотя бы одна группа, размер которой равен или превышает пороговое значение (threshold minimum size).
5. Условие итерации:
   • Если размер достаточен И N меньше максимального порога M: N увеличивается на 1, процесс возвращается к шагу 3.
   • Если размер недостаточен: процесс останавливается, используются группы, полученные для $N-1$.
   • Если $N=M$: процесс останавливается, используются группы для N.

Процесс Б: Кластеризация на основе групп

1. Выбор группы: Выбирается Document Group (например, самая большая), сгенерированная в Процессе А.
2. Идентификация паттерна: Анализируются URL документов в группе для поиска общего Pattern String. Используется принцип MDL для выбора наилучшего шаблона (баланс точности и охвата).
3. Формирование кластера: Идентифицируются ВСЕ документы в исходном наборе (не только в текущей группе), которые удовлетворяют найденному Pattern String. Они формируют Document Cluster.
4. Итерация: Процесс повторяется для оставшихся некластеризованных документов до тех пор, пока возможно формирование групп достаточного размера.

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

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

• Контентные факторы: Текст документов. Система анализирует частоту терминов внутри каждого документа (n) и в пределах всего набора документов/сайта (S).
• Технические факторы: URL-адреса документов. Они используются на этапе Pattern Matching для формирования финальных кластеров. URL сегментируются по разделителям (например, "/" и "?").
• Статистические данные корпуса: Общее количество документов в корпусе (D) и количество документов в корпусе, содержащих термин (d), необходимые для расчета IDF-компоненты.

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

• Modified TF-IDF: Ключевая метрика для определения важности термина. Формула, приведенная в патенте: $((n+S)\cdot\log(D/d))$