Как Google оптимизирует обработку регулярных выражений и дорогих повторяющихся запросов в специализированных системах

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

Automaton (Автомат)

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

Backward Traversal (Обратный обход)

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

High-Cost Recurring Query (Дорогой повторяющийся запрос)

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

Loop Unrolling (Развертывание цикла)

Техника преобразования автомата для обработки операторов повторения в Regex (например, * или +), которые создают циклы. Цикл разворачивается определенное количество раз (возможно, динамически) для возможности обратного обхода.

Offline Query Processor (Офлайн-процессор запросов)

Компонент, который обновляет Prepared Results во время индексации новых или измененных документов.

Operator Tree (Дерево операторов)

Альтернативный способ представления регулярного выражения, где внутренние узлы представляют операторы (например, конкатенация, повторение), а листья — символы.

Prepared Results (Подготовленные результаты)

Закэшированный набор результатов для идентифицированного High-Cost Recurring Query. В патенте подчеркивается, что эти результаты обновляются во время индексации.

Prepend Operation (Операция prepend)

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

Suffix Array (Суффиксный массив)

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

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

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

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

1. Получение регулярного выражения.
2. Создание представления в виде автомата (automaton representation).
3. Обход автомата от конечных узлов к начальному (traversing... from the termination nodes to the starting node) для определения диапазона суффиксного массива (suffix array range) для начального узла.
4. Использование этого диапазона для идентификации релевантных документов.

Ядром является обратный обход автомата для вычисления диапазона в суффиксном массиве.

Claim 2 и 3 (Зависимые): Уточняют, что обратный обход использует операцию prepend для перемещения между узлами.

Claim 6 и 7 (Зависимые): Описывают обработку операторов повторения, которые создают циклы. Применяется «развертывание цикла» (unrolling the loop), что приводит к созданию нескольких конечных узлов. Развертывание может происходить динамически.

Claim 9 (Независимый пункт, Системный): Описывает систему, объединяющую оба направления.

1. Идентификация дорогих повторяющихся запросов в логах.
2. Хранение их параметров.
3. При получении нового запроса: проверка совпадения с сохраненными дорогими запросами.
4. Если совпадение есть: использование prepared results для генерации выдачи.
5. Одновременно: проверка наличия регулярного выражения в запросе.
6. Если есть: применение механизма из Claim 1 (автомат, обратный обход, суффиксный массив) для идентификации документов.
7. Использование этих документов для генерации выдачи.

Claim 18 (Зависимый от 9): Ключевой аспект обновления кэша. При индексации документа система проверяет, соответствует ли он сохраненным дорогим запросам, и добавляет его в prepared results. Это происходит независимо от выполнения самого запроса (independently from execution of the particular query).

Claim 24 (Независимый пункт): Описывает альтернативный метод для регулярных выражений с использованием operator tree вместо автомата. Метод включает обход дочерних узлов в обратном порядке (traversing the child nodes in reverse order) для определения диапазона суффиксного массива корневого узла.

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

Изобретение затрагивает инфраструктурные компоненты поисковой системы, отвечающие за индексацию и обработку запросов.

INDEXING – Индексирование и извлечение признаков

• На этом этапе генерируется Suffix Array для корпуса документов.
• Offline Query Processor взаимодействует с индексатором. Когда появляется новый или обновленный документ, этот процессор проверяет его на соответствие сохраненным High-Cost Queries и обновляет соответствующие Prepared Results (кэш).

(Офлайн-процессы / Анализ данных)

• Log Analyzer периодически анализирует Log Files для идентификации новых дорогих повторяющихся запросов и обновления списка High-Cost Queries на основе метрик выполнения.

RANKING – Ранжирование (Этап Retrieval/Отбор Кандидатов)

• Если запрос содержит регулярное выражение, активируется Automaton Module.
• Он строит автомат или дерево операторов и выполняет обратный обход, используя Suffix Array.
• Это действует как эффективный префильтр (prefilter) для быстрого определения набора документов-кандидатов.

RERANKING / METASEARCH – Переранжирование и Смешивание

• Query Processor проверяет, соответствует ли входящий запрос одному из High-Cost Queries.
• Если да, он извлекает Prepared Results.
• Система может использовать эти результаты для немедленного показа первой страницы, одновременно выполняя запрос в фоновом режиме. Затем результаты могут быть смешаны (Blend the prepared results with the executed results).

На что влияет

• Типы контента и Ниши: Патент явно указывает на применение для поиска по исходному коду (Source Code Searching). Также упоминаются другие большие корпусы, где поддерживаются регулярные выражения, например, репозитории ДНК или библиотечные коллекции. Влияние на стандартный веб-контент (статьи, товары) отсутствует, так как веб-поиск обычно не поддерживает полный поиск по Regex для пользователей.
• Специфические запросы: Влияет на запросы, содержащие регулярные выражения, и на запросы, которые были классифицированы как High-Cost Recurring Queries.

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

Алгоритмы применяются при выполнении следующих условий:

• Триггер 1 (Кэширование): Когда параметры входящего запроса точно совпадают с параметрами запроса, ранее сохраненного в базе High-Cost Queries.
• Триггер 2 (Regex): Когда входящий запрос содержит регулярное выражение.
• Триггер 3 (Обновление кэша): Когда в индекс добавляется новый документ или обновляется существующий.
• Пороги (для идентификации High-Cost): Запрос должен превышать пороги частоты (например, >3 раз за период) И стоимости (например, поиск по >75% документов, превышение порога времени выполнения, или запрос «всех результатов»).

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

Процесс А: Обработка запроса в реальном времени

1. Получение запроса: Система получает запрос от пользователя.
2. Проверка на High-Cost Query: Система определяет, является ли запрос дорогим повторяющимся запросом путем сравнения с базой сохраненных запросов.
3. Обработка High-Cost Query (Если ДА):
   • Система извлекает Prepared Results из хранилища.
   • Система может немедленно вернуть первую страницу результатов из кэша.
   • Параллельно может быть запущен процесс выполнения запроса в реальном времени (опционально).
4. Обработка Стандартного Запроса (Если НЕТ) или фоновое выполнение:
   • Система проверяет наличие регулярного выражения в запросе.
   • Если Regex ЕСТЬ:
     1. Создается автомат или дерево операторов для Regex.
     2. Развертываются повторяющиеся термины (unrolling loops) для устранения обратных ребер (оптимизация).
     3. Выполняется обратный обход структуры (от конечных узлов к начальному).
     4. На каждом шаге используется операция prepend для вычисления диапазонов в Suffix Array.
     5. Определяется финальный диапазон Suffix Array для начального узла (префильтрация).
   • Если Regex НЕТ: Стандартный поиск по индексу.
5. Выполнение поиска: Поиск выполняется по отобранным кандидатам.
6. Смешивание результатов (Если применимо): Prepared Results смешиваются с результатами выполнения в реальном времени.
7. Возврат результатов: Результаты возвращаются пользователю.

Процесс Б: Управление кэшем (Офлайн и Индексация)

1. Анализ логов (Периодически): Log Analyzer анализирует логи, идентифицирует новые High-Cost Recurring Queries по порогам частоты и стоимости, и удаляет неактуальные. Инициализирует Prepared Results для новых запросов.
2. Обновление при индексации (Постоянно): При индексации нового или обновленного документа Offline Query Processor проверяет его на соответствие всем сохраненным High-Cost Queries. При наличии совпадений соответствующие Prepared Results обновляются.

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

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

• Параметры запроса: Текст запроса, включая регулярные выражения, если они присутствуют.
• Системные данные:
  • Log Files: Журналы выполнения запросов. Используются для идентификации дорогих повторяющихся запросов. Содержат данные о времени выполнения, количестве обработанных документов, запросах на показ всех результатов.
  • Document Corpus: Исходные данные для индексации.
  • Suffix Array: Предварительно рассчитанная структура данных корпуса, используемая для оптимизации Regex.
  • High Cost Queries: База данных параметров дорогих запросов.
  • Prepared Results: Кэш результатов.

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

Патент фокусируется на метриках производительности и эффективности:

• Критерии High-Cost Query:
  • Количество обработанных документов: Сравнивается с порогом (например, 75% корпуса или фиксированное число).
  • Запрос всех результатов: Фиксация факта, что пользователь запросил все результаты, а не только лучшие совпадения.
  • Время выполнения запроса: Сравнивается с предустановленным порогом времени для определения всех релевантных документов.
• Suffix Array Range (Диапазон суффиксного массива): Основная метрика при обработке Regex. Вычисляется путем обратного обхода автомата с использованием операции prepend.
• Dynamic Unrolling Threshold (Порог динамического развертывания): При обработке циклов в Regex система сравнивает размер диапазона Suffix Array между итерациями развертывания. Если уменьшение диапазона незначительно (например, менее 10% за несколько итераций), процесс останавливается для экономии ресурсов.
• Оптимизация интервалов: Если диапазон Suffix Array состоит из слишком большого числа маленьких интервалов, система может объединять соседние интервалы, включая промежутки между ними (merging neighboring intervals), чтобы сократить общее число интервалов и ускорить обработку.

1. Фокус на инфраструктуре и эффективности: Патент полностью посвящен оптимизации производительности и снижению вычислительных затрат в специализированных поисковых системах. Он не предлагает новых методов оценки релевантности, качества контента или сигналов ранжирования.
2. Эффективная обработка Regex: Google разработал высокооптимизированный метод для поиска по регулярным выражениям, использующий суффиксные массивы и обратный обход автоматов. Этот метод превосходит традиционные подходы (например, prefilter trees) по эффективности и точности префильтрации.
3. «Умное» кэширование (Live Caching): Внедрение механизма обновления кэша (Prepared Results) непосредственно в процесс индексации является ключевой оптимизацией. Это позволяет поддерживать актуальность результатов для дорогих повторяющихся запросов без необходимости их повторного выполнения.
4. Ограниченное применение в веб-поиске: Описанные механизмы предназначены для систем (поиск по исходному коду), где поддерживается поиск по регулярным выражениям и часто требуется получение полного набора результатов. В стандартном веб-поиске Google эти методы напрямую не применяются в том же виде.
5. Отсутствие практической ценности для SEO: Для SEO-специалистов этот патент не несет практической ценности в плане разработки стратегий продвижения.

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

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

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

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

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

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

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

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