Как Google Autocomplete обрезает начало длинных фраз, чтобы показать популярные подсказки

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

Autocompletion Module (Модуль автодополнения)

Компонент поисковой системы, который генерирует список потенциальных завершений для полученного Query Stem.

Completion Verification Module (Модуль верификации дополнений)

Компонент, который определяет меру качества автодополнения в контексте частичного запроса. Использует Language Model или Query Logs.

Compound Word (Составное слово/термин)

Слово или фраза (например, "New York" или "двадцать один"), которая обрабатывается как единое целое при удалении префикса.

Language Model (Языковая модель)

Модель (например, N-gram), которая присваивает вероятность последовательности слов. Может быть основана на корпусе документов или, чаще, на Query Logs.

Prefix (Префикс)

Одно или несколько начальных слов основы запроса, которые система удаляет для создания укороченной версии.

Quality Test (Тест качества)

Процедура оценки автодополнения. В патенте описан тест, основанный на расчете отношения частотности дополнения к частотности основы запроса в Query Logs.

Query Log / Corpus of user queries (Лог запросов / Корпус пользовательских запросов)

База данных, содержащая анонимизированные запросы, ранее отправленные пользователями. Используется для определения частотности и популярности.

Query Stem (Основа запроса)

Текст, отправляемый в Autocompletion Module. Может быть полным вводом пользователя (First Query Stem) или укороченным (Second Query Stem).

Smoothing Factor/Constant (s) (Сглаживающий коэффициент/константа)

Значение, добавляемое в знаменатель при расчете качества для снижения оценки редко отправляемых запросов.

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

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

1. Система получает многословный ввод запроса (query input) до его отправки в поисковую систему.
2. Ввод отправляется как first query stem в Autocompletion Module.
3. Система определяет, что полученные автодополнения не удовлетворяют first quality test.
4. В ответ на это система отправляет second query stem. Это first query stem с удаленным префиксом (начальными словами).
5. Система получает вторые автодополнения, которые удовлетворяют second quality test.
6. Second quality test включает:
   1. Определение отношения (ratio): (Частота потенциального автодополнения в Query Logs) / (Частота любого запроса, включающего second query stem, в Query Logs).
   2. Сравнение этого отношения с пороговым значением.
7. Система предоставляет эти вторые автодополнения для показа в интерфейсе.

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

Claim 2 (Зависимый от 1): Уточняет, что second quality test также включает применение smoothing factor к рассчитанному отношению. Это необходимо для корректной обработки редких запросов.

Claim 3 (Зависимый от 1): Детализирует логику определения префикса для удаления. Если первый термин является частью compound word, то остальные части этого составного термина также включаются в префикс для удаления (составные термины удаляются целиком).

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

1. Система получает ввод и отправляет first query stem.
2. Определяется неудача first quality test.
3. В ответ система отправляет *одну или более* укороченных основ запроса (shortened query stems).
4. Получаются автодополнения, удовлетворяющие second quality test.
5. Система *собирает* (collecting) эти автодополнения и предоставляет их для показа.

Этот пункт описывает возможность одновременной отправки нескольких вариантов укороченных запросов и агрегации результатов.

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

Изобретение применяется на этапе взаимодействия пользователя с интерфейсом поиска, до момента отправки запроса.

INDEXING – Индексирование и извлечение признаков
На этом этапе происходит предварительная обработка Query Logs. Система анализирует исторические данные, подсчитывает частотность различных запросов и строит Language Models. Эти данные необходимы для работы Autocompletion Module.

QUNDERSTANDING – Понимание Запросов
Основное применение патента в рамках функциональности Autocomplete (Google Suggest). Процесс происходит в реальном времени, когда пользователь вводит текст. Система использует описанный механизм для интерпретации частичного ввода и предсказания наиболее вероятного и популярного полного запроса.

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

• Частичный запрос пользователя (Query Stem).
• Данные из Query Logs (частотность запросов).

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

• Список качественных автодополнений (подсказок) для отображения в интерфейсе.

Ключевые технические особенности:

• Итеративное или параллельное удаление префикса: Возможность последовательного укорачивания запроса слева или одновременного запроса подсказок для всех возможных суффиксов.
• Интеллектуальное удаление префикса: Учитываются compound words и стоп-слова при формировании укороченного запроса.
• Верификация качества на основе данных: Использование Query Logs для гарантии популярности и релевантности подсказок.

На что влияет

• Специфические запросы: Наибольшее влияние оказывается на длинные (long-tail) частичные запросы, редкие или сложные формулировки, для которых нет достаточной статистики по точному префиксу.
• Типы контента и Ниши: Не зависит от типа контента или ниши, так как механизм работает на уровне обработки текста запроса и его популярности в логах.

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

• Условия работы: Алгоритм активируется в реальном времени во время ввода текста пользователем в строку поиска.
• Триггеры активации: Механизм удаления префикса запускается, если стандартный метод автодополнения (по полному query stem) не возвращает результатов или возвращает результаты, не удовлетворяющие first quality test (например, имеют низкую оценку популярности).
• Ограничения: Процесс укорачивания может быть ограничен максимальным количеством итераций и минимальным количеством оставшихся слов в запросе.

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

Процесс А: Итеративная обработка (Основной вариант)

1. Получение ввода: Система получает first query stem.
2. Первичный запрос автодополнений: First query stem отправляется в Autocompletion Module.
3. Оценка качества (Тест 1): Анализируется ответ. Определяется, удовлетворяют ли результаты first quality test.
   • Если ДА: Предоставить результаты. Процесс завершен.
   • Если НЕТ: Перейти к шагу 4.
4. Генерация укороченного запроса: Система определяет префикс для удаления, учитывая правила для compound words и стоп-слов. Генерируется second query stem.
5. Вторичный запрос автодополнений: Second query stem отправляется в Autocompletion Module.
6. Оценка качества (Тест 2): Полученные автодополнения проверяются на соответствие second quality test. Это включает расчет метрики качества (относительной частотности) и сравнение с порогом.
7. Принятие решения:
   • Если Тест 2 пройден: Предоставить результаты. Процесс завершен.
   • Если Тест 2 не пройден: Текущий second query stem становится основой для следующей итерации. Вернуться к шагу 4 для дальнейшего укорачивания (если не достигнуты лимиты).

Процесс Б: Параллельная обработка (Альтернативный вариант по Claim 10)

1. Получение ввода и первичная оценка: Шаги 1-3 аналогичны Процессу А.
2. Генерация всех укороченных версий: Если первичная оценка отрицательная, система генерирует все возможные укороченные Query Stems (суффиксы).
3. Параллельный поиск: Все укороченные версии отправляются в Autocompletion Module одновременно.
4. Сбор и валидация: Результаты собираются и проверяются на качество (Тест 2).
5. Выбор лучших результатов: Выбираются наиболее качественные автодополнения из всех наборов и предоставляются пользователю.

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

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

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

• Поведенческие факторы: Критически важные данные. Используется Query Logs (анонимизированные записи о том, какие запросы ранее отправляли пользователи). Эти данные используются для определения частотности (популярности) как частичных запросов, так и потенциальных завершений.
• Контентные факторы (Запроса): Текст самого частичного запроса (query stem) используется для поиска совпадений в логах и для лингвистического анализа (определение слов, compound words, стоп-слов).

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

Система вычисляет метрики качества (Quality Metrics) для оценки потенциальных автодополнений.

1. Quality Metric (Метрика качества на основе относительной частотности)

Это основной метод, указанный в Claims. Рассчитывается как отношение частоты завершения к частоте основы запроса в логах.

В патенте предложено два варианта расчета. Пример варианта расчета: