Как Google использует анализ самой длинной общей подпоследовательности (LCS) для определения лексических синонимов и вариантов слов

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

Longest Common Subsequence (LCS) (Самая длинная общая подпоследовательность)

Самая длинная последовательность символов, которая присутствует в обоих сравниваемых терминах с сохранением порядка символов, но не обязательно непрерывно. Например, LCS для "architekturwettbewerb" и "architektenwettbewerb" — это "architektwettbewerb".

Edit Distance (Расстояние редактирования)

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

Pseudostemming (Псевдостемминг)

Техника идентификации лексически схожих слов, которая является более инклюзивной (широкой), чем стандартный стемминг. В патенте метод LCS предлагается как улучшение для псевдостемминга.

Lexical Synonyms (Лексические синонимы)

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

Compounding/Decompounding

Процесс объединения нескольких слов в одно составное слово (Compounding) или разделения одного слова на несколько (Decompounding). Например, "wood stock" и "woodstock".

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

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

1. Система получает первый и второй термины.
2. Идентифицируется самая длинная подпоследовательность (LCS), общая для обоих терминов.
3. Определяется, какой из терминов длиннее.
4. Вычисляется отношение (ratio) между длиной LCS и длиной более длинного термина.
5. Определяется, соответствует ли это отношение первому порогу (first threshold).
6. Вычисляется расстояние редактирования (Edit Distance) между терминами.
7. Расстояние редактирования сравнивается со вторым порогом (second threshold).
8. Определяется, соответствует ли расстояние редактирования второму порогу.
9. Термины обозначаются как кандидаты в синонимы на основании того, что и отношение LCS, и расстояние редактирования соответствуют своим порогам.

Ядром изобретения является специфический двухэтапный фильтр для идентификации кандидатов в синонимы, основанный исключительно на лексической структуре. Шаг 1 (LCS Ratio) измеряет общее сходство состава и порядка символов, что эффективнее анализа префиксов для составных слов. Шаг 2 (Edit Distance) измеряет близость различий. Оба условия должны быть выполнены. Это представляет собой точное определение лексического сходства, используемое системой для pseudostemming.

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

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

INDEXING – Индексирование / QUNDERSTANDING – Понимание Запросов (Офлайн-процессы)
Основное применение. Описанные методы (анализ LCS, а также упомянутые в патенте методы для аббревиатур, акронимов, составных слов) используются для генерации списков потенциальных синонимов в офлайн-режиме. Это происходит путем анализа больших корпусов текстов или логов запросов. В результате формируются предопределенные списки lexical synonyms.

QUNDERSTANDING – Понимание Запросов (В реальном времени)
Когда пользователь отправляет запрос, система использует предварительно сгенерированные данные о синонимах для интерпретации интента запроса. Это может включать перезапись (rewriting) или расширение (expansion) запроса для включения этих лексических вариантов.

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

• Два термина (Термин А, Термин Б), оцениваемые на предмет синонимии.

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

• Определение того, являются ли Термин А и Термин Б кандидатами в синонимы (Да/Нет).

На что влияет

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

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

• Условия применения: Алгоритм применяется в процессе генерации синонимов для оценки лексического сходства между двумя терминами.
• Пороговые значения: Для активации необходимо, чтобы LCS Ratio превышал первый порог, а Edit Distance был ниже второго порога. В описании патента упоминаются примеры порогов (например, 0.5 для LCS Ratio), но в Claims они не зафиксированы.

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

Процесс работы системы по методу LCS (согласно FIG. 6):

1. Получение данных: Система получает два термина для сравнения.
2. Вычисление LCS: Вычисляется самая длинная общая подпоследовательность (LCS) двух терминов. (Патент детально описывает использование динамического программирования для этого вычисления).
3. Вычисление коэффициента LCS: Определяется длина LCS и длина более длинного из двух терминов. Вычисляется отношение длины LCS к длине более длинного термина.
4. Первая фильтрация (LCS Ratio): Система проверяет, превышает ли коэффициент LCS первый установленный порог.
   • Если НЕТ: Процесс завершается (термины не считаются лексическими синонимами).
   • Если ДА: Переход к следующему шагу.
5. Вычисление Edit Distance: Система вычисляет расстояние редактирования между двумя терминами.
6. Вторая фильтрация (Edit Distance): Система проверяет, меньше ли расстояние редактирования второго установленного порога.
7. Идентификация: Если оба порога пройдены, термины помечаются как кандидаты в синонимы.

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

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

• Контентные (Лексические) факторы: Основными данными являются сами символы, составляющие два сравниваемых термина. В описании упоминаются варианты реализации, где перед сравнением может происходить нормализация: удаление пунктуации и пробелов (для Compounding/Decompounding) или удаление диакритических знаков (Diacriticals).

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

• Length of Term (Длина термина).
• Length of LCS (Длина LCS).
• LCS Ratio (Коэффициент LCS): Рассчитывается по формуле: $\frac{\text{Длина LCS}}{\text{Длина более длинного термина}}$.
• Edit Distance (Расстояние редактирования).
• Пороговые значения: Используются предопределенные пороги (predetermined thresholds) для LCS Ratio и Edit Distance для принятия решения.

1. Лексический анализ как основа: Google активно использует методы лексического анализа (помимо семантического) для определения синонимов, словоформ и вариантов написания. Это фундаментальный слой в Query Understanding.
2. Преимущество LCS над префиксами: Longest Common Subsequence (LCS) является предпочтительным методом по сравнению с простым совпадением префиксов для pseudostemming. Он более устойчив к изменениям в начале или середине слова и лучше обрабатывает составные слова (compounds).
3. Двухфакторная валидация сходства: Идентификация лексических синонимов проходит строгую фильтрацию. Требуется как высокое общее сходство символов и их порядка (высокий LCS Ratio), так и небольшое количество различий (низкий Edit Distance).
4. Учет специфических лексических связей: Система включает механизмы для учета различных типов лексических отношений: стемминг, акронимы, аббревиатуры, различия в пунктуации, пробелах и диакритических знаках.
5. Лексическая связь как сильный сигнал: В патенте отмечается, что для lexical synonyms требования к другим сигналам подтверждения (например, общим результатам поиска или переключению запросов в рамках сессии) могут быть снижены, поскольку сильная лексическая связь сама по себе является надежным индикатором семантической близости.

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

• Естественная вариативность ключевых слов: Не следует чрезмерно беспокоиться о мелких различиях в написании (пунктуация, пробелы, диакритические знаки) или использовании общепринятых аббревиатур и акронимов. Google с высокой вероятностью распознает их как эквиваленты благодаря описанным механизмам (LCS, нормализация).
• Интернационализация (i18n): При работе с языками, где распространены составные слова (например, немецкий, финский, русский), этот патент подтверждает способность Google связывать варианты. Важно использовать естественное и грамматически правильное написание для целевого языка, не опасаясь, что поисковая система не поймет составное слово.
• Фокус на семантике, а не на словоформах: Поскольку Google эффективно группирует лексические варианты (используя pseudostemming с помощью LCS), SEO-стратегия должна фокусироваться на покрытии семантических сущностей и интентов, а не на оптимизации под каждую отдельную словоформу или аббревиатуру.

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

• Keyword Stuffing вариантами написания: Попытки «оптимизировать» текст путем включения всех возможных вариантов написания, пунктуации, аббревиатур и словоформ избыточны. Это ухудшает читаемость и не дает преимуществ, так как система уже умеет связывать эти варианты.
• Создание дублирующего контента под варианты: Создание отдельных страниц для [wood stock] и [woodstock], или [USA] и [U.S.A.] неэффективно. Система нормализует эти различия и считает термины эквивалентными.

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

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

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

Сценарий: Обработка составных слов в немецком языке (Пример из патента)

1. Задача: Определить, являются ли синонимами "Architekturwettbewerb" (конкурс архитектуры) и "Architektenwettbewerb" (конкурс архитекторов).
2. Анализ (Предыдущий метод на основе префиксов): Общий префикс "architekt" (8 символов). Длина слов 21 символ. Отношение 8/21 ≈ 0.38. Если порог 0.5, то слова не считаются синонимами.
3. Анализ (Новый метод LCS):
   • LCS: "architektwettbewerb" (19 символов).
   • LCS Ratio: 19/21 ≈ 0.90. Это значительно выше порога 0.5.
   • Edit Distance: 2 (замена 'ur' на 'en'). Это ниже типичного порога.
4. Результат: Система идентифицирует эти термины как лексические синонимы.
5. SEO Вывод: Страница, оптимизированная под один из этих терминов, будет релевантна запросам по другому, что критически важно для SEO в языках со словосложением.