Как Google статистически определяет значимые шаблоны URL (префиксы и суффиксы) для улучшения каноникализации и эффективности сканирования

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

Affix (Аффикс)

Общий термин для префикса (начало строки) или суффикса (конец строки). Подстрока, расположенная на краю (extremity) строки.

Binomial Distribution (Биномиальное распределение)

Статистическая модель, используемая для расчета вероятности определенного числа успехов (в данном случае, совпадений аффикса) в серии независимых экспериментов (N строк).

Character String (Символьная строка)

Последовательность символов. В контексте патента основной пример — URL.

M

Количество строк в наборе, которые имеют определенную уникальную подстроку (аффикс) длины X.

N (или N_x)

Общее количество строк в наборе, длина которых составляет не менее X символов.

Predetermined Model (Предопределенная модель распределения символов)

Модель, определяющая вероятность появления отдельных символов в строках. Может быть равномерной (все символы равновероятны) или неравномерной (на основе эмпирических данных о частоте символов в интернете или в данном наборе строк).

Significant Affix (Значимый аффикс)

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

Test Statistic (T) (Тестовая статистика)

Вычисленное значение, используемое для определения статистической значимости. В данном патенте T — это условная вероятность того, что аффикс встречается M или более раз, при условии, что он встречается хотя бы один раз.

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

Примечание: Патент US8095530B1 содержит описания систем каноникализации на основе релевантности параметров (FIG 1-5), но его формула изобретения (Claims 1-35) сосредоточена исключительно на методе статистического обнаружения аффиксов (FIG 6-7).

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

1. Система получает множество символьных строк.
2. Определяется M: количество строк, имеющих уникальную подстроку длины X на краю (префикс или суффикс).
3. Определяется N: общее количество строк, длина которых не менее X (N>M).
4. Вычисляется вероятность (P) того, что данная подстрока встретится M или более раз из N строк, при условии, что она встречается хотя бы один раз.
5. Эта вероятность P рассчитывается как отношение вероятности того, что подстрока встречается M или более раз, к вероятности того, что она встречается хотя бы один раз.
6. В расчете используется формула биномиального распределения, которая учитывает вероятность появления отдельных символов ($P_{substring[i]}$) согласно Predetermined Model.
7. На основе P, M и N система определяет, является ли подстрока Significant Affix.
8. Значимый аффикс сохраняется.

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

Процесс аналогичен Claim 1, но применяется итеративно для X, изменяющегося от предопределенной минимальной длины до предопределенной максимальной длины. Это позволяет системе идентифицировать как короткие, так и длинные значимые шаблоны в наборе данных.

Claim 15 (Зависимый от 14): Детализирует постобработку результатов.

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

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

Изобретение применяется на этапах, связанных с обработкой и анализом URL-адресов для оптимизации сканирования и индексирования.

CRAWLING – Сканирование и Сбор данных
Система может использовать предварительно вычисленные Significant Affixes для анализа вновь обнаруженных URL. Распознавая общие структуры URL, система может оптимизировать приоритеты сканирования или идентифицировать группы URL, принадлежащие к одному разделу. Это помогает оптимизировать Crawl Budget.

INDEXING – Индексирование (Каноникализация)
Это основная область применения. Система анализирует большие партии уже просканированных URL (часто сгруппированных по хосту) для выявления статистически значимых шаблонов.

1. Анализ структуры URL: Идентификация Significant Affixes помогает понять структуру сайта. Например, система может определить общие префиксы пути (/catalog/product/) или префиксы хоста (www1., m.).
2. Информирование каноникализации: Если определенный префикс является значимым (т.е. структурным), но при этом не влияет на уникальность контента (например, префиксы локализации или сессий, которые не меняют основного содержания), эта информация может быть использована для создания правил каноникализации, которые игнорируют этот префикс при определении канонического URL.

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

• Множество символьных строк (URL-адреса).
• Predetermined Model для распределения символов (вероятности $P_{substring[i]}$).
• Порог статистической значимости (Significance Level).

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

• Список идентифицированных Significant Affixes.

На что влияет

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

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

• Условия применения: Алгоритм применяется к достаточно большому набору строк (URL), чтобы статистический анализ был достоверен. Чаще всего применяется к URL, сгруппированным по хосту или домену.
• Временные рамки: Процесс выполняется офлайн или в пакетном режиме для периодического анализа логов сканирования и обновления понимания структуры сайтов. Он не выполняется в реальном времени при обработке поискового запроса.

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

Процесс итеративного обнаружения значимых аффиксов (на примере префиксов):

1. Инициализация: Определение минимальной и максимальной длины искомых префиксов (X) и установка порога статистической значимости (Significance Level).
2. Получение данных: Получение списка строк (URL) для анализа.
3. Определение модели распределения: Определение вероятности символов ($P_{substring[i]}$) — например, путем анализа частоты символов в полученном списке или использования общей модели для интернета.
4. Итерация по длине (X): Цикл от минимальной до максимальной длины.
5. Фильтрация строк (N): Определение количества строк (N или N_x), длина которых >= X.
6. Извлечение подстрок: Извлечение префиксов длины X из отфильтрованных строк.
7. Итерация по уникальным подстрокам (S): Цикл по каждому уникальному префиксу S.
8. Подсчет совпадений (M): Определение количества строк (M), начинающихся с S.
9. Расчет тестовой статистики (T): Вычисление вероятности того, что S встречается M или более раз, при условии, что он встречается хотя бы один раз. Используется Binomial Distribution.
10. Проверка значимости: Сравнение T с порогом. Если T < Significance Level, префикс S помечается как Significant Affix.
11. Пост-обработка (Фильтрация): После завершения всех итераций список значимых аффиксов фильтруется. Удаляются короткие префиксы, которые являются частью более длинного значимого префикса (например, если найдены "/blog/2025/" и "/blog/", то "/blog/" удаляется).
12. Сохранение: Сохранение итогового списка Significant Affixes.

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

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

• Технические факторы (URL-структура): Основные данные — это сами URL-адреса (или другие строки). Система анализирует структуру URL, включая хост, путь и параметры. В патенте явно упоминается применение этого метода к анализу частей хоста (например, префиксов субдоменов) и компонентов пути.
• Системные данные (Модель распределения): Данные о вероятности появления символов (Predetermined Model), которые могут быть получены эмпирически из большого корпуса URL или из анализируемого набора данных.

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

Система использует несколько ключевых метрик:

• M: Количество строк с конкретным аффиксом длины X.
• N (N_x): Общее количество строк длиной не менее X.
• X: Длина анализируемого аффикса.
• $P_{substring[i]}$: Вероятность появления отдельного символа i (согласно Predetermined Model).

Формулы расчета:

Вероятность того, что конкретная подстрока S длины X появится случайно (P_S):

$P_S = \prod_{i=1}^{X} P_{substring[i]}$

Вероятность того, что подстрока S встретится ровно M раз в N строках (P(M, N, S)) (Биномиальное распределение):

$P(M, N, S) = \frac{N!}{M!(N-M)!} (P_S)^M (1-P_S)^{N-M}$

Тестовая статистика (T) — вероятность того, что S встречается M или более раз, при условии, что он встречается хотя бы один раз (Условная вероятность):