Как определить корректность запроса пользователя

Как проверить, насколько страница сайта соответствует запросу пользователя

Теория и обзор сервиса для анализа соответствия конкретной страницы пользовательскому запросу.

Привет, это PR-CY! Добро пожаловать в наш блог на VC, где мы делимся кейсами, советами и инструментами для продвижения и улучшения ваших сайтов. ��

Быстро о теории: релевантность и что на нее влияет

Вводим в курс дела новичков. Пропустите, если разбираетесь в SEO.

Контентные страницы на сайте обычно создают под конкретные поисковые запросы пользователя. Утрируя, если нужно появиться в выдаче по запросу «зачем кошкам хвост», нужно написать материал, соответствующий этому запросу, то есть релевантный ему. Тексты про хвосты ящериц или кошачьи повадки не ответят на вопрос пользователя «зачем кошкам хвост?». Они появятся в выдаче по другим запросам.

Запрос

Поисковые запросы – это слово или фраза, которые используют пользователи для поиска информации в интернете. Как правило, люди предпочитают максимально краткие (и не всегда корректные с точки зрения синтаксиса) формы выражения своей мысли. Часто запросы включают в себя уточняющие слова, например: «в Москве», «купить», «продать», «обзор», «фото» и прочие варианты.

Чем запросы отличаются от ключевых слов

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

Алгоритмы облегчения ввода запросов и SEO

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

• Подсказки. Когда юзер начинает вводить слово или фразу, система сразу подбирает несколько релевантных запросов, которые уже пользуются популярностью в тематике. При увеличении объема введенного текста растет точность подсказок и, соответственно, выдачи.
• Конвертация раскладки. Если пользователь начинает вводить запросы в поисковую систему, не переключив клавиатуру на корректный язык, то алгоритм автоматически переведет раскладку и выдаст релевантный результат.
• Исправление ошибок. Не все пользователи формируют синтаксически и грамматически правильные запросы. Но это не значит, что нужно оптимизировать страницы с помощью текстов с ошибками. Алгоритмы определяют, что это неверная формулировка, и предлагают посмотреть вариант выдачи с корректным вариантом, но автоматическая подмена не происходит.

Что значат поисковые запросы для SEO

Запрос – что это для SEO? Все просто. Естественно, каждый поисковик стремится выдавать пользователю только целевые запросы. Для этого регулярно вводятся новые алгоритмы для повышения качества ранжирования сайтов, при этом учитывается примерно 200 факторов. Веб-мастер должен уметь грамотно определить ключевые слова сайта на основе поисковых запросов, ведь от корректности семантического ядра зависит вся стратегия продвижения и занимаемая позиция в выдаче.

Какие запросы использовать для продвижения

Каждая целевая страница должна соответствовать интересам целевой аудитории. Поэтому формирование семантического ядра во многом определяет структуру сайта. Сами ключевые слова подбираются с помощью специальных инструментов. Универсальным решением считается «Яндекс.Вордстат», но для расширения и уточнения ядра можно использовать такие сервисы, как Serpstat, SEMRush, «Мутаген» и др. Процесс сбора семантического ядра выглядит следующим образом.

Применение «Яндекс.Вордстата». Здесь можно увидеть частотность, сезонность и географический охват разных поисковых запросов. Сервис предложит похожие варианты для расширения семантики. Этот инструмент считается базовым для всех оптимизаторов, которые занимаются продвижением сайтов в Рунете. В строку поиска достаточно ввести тематическое слово или фразу, чтобы система сформировала таблицу с похожими запросами. Возле каждого варианта будет отображаться месячная частота запросов. Специальные операторы (!, «», + и др.) дают возможность с высокой точностью анализировать спрос на различные семантические формы.

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

Оценка конкурентов. Анализ успешных сайтов других игроков ниши дает возможность сразу двигаться в правильном направлении. Оптимизатор сможет быстро сформировать расширенное семантическое ядро, которое конкуренты, возможно, составляли несколько лет. Для этой цели используются специальные профессиональные инструменты. К проверенным сервисам можно отнести:

• Spy words;
• Megaindex;
• iSpionage;
• SE Ranking.

С их помощью оптимизатор может увидеть, по каким запросам сайты конкурентов находятся в «видимой» зоне выдачи. Это дает возможность максимально расширить поисковый охват аудитории.

Инструменты для сбора запросов. В «Яндекс.Вордстате» собрана информация о пользовательской активности в Рунете. Если нужна глобальная статистика, можно воспользоваться сервисами KWFinder, Keyword Tool или SEMRush. Таких инструментов, платных и бесплатных, очень много. Со временем каждый оптимизатор формирует собственный набор удобных сервисов и программ для работы с ключевыми словами.

Подведем итоги

Теперь вы знаете, что такое запросы в поисковых системах и как они влияют на продвижение сайта. Используйте эти знания для создания качественных семантических ядер и наполнения страниц результативным контентом.

Обзор алгоритмов поисковых систем Яндекс и Google: виды, характеристики и возможности

В основе любой поисковой системы – алгоритмы и индивидуальные принципы функционирования. Они ориентированы на удобство пользователей и правильное ранжирование сайтов: выдача должна быть корректной, полностью удовлетворяя все запросы. Рассмотрим основные алгоритмы, а также принцип функционирования поисковых систем Google и Яндекс, разберем их особенности и предназначение.

Обработка информации: ключевые принципы

При всей простоте системы «запрос-ответ» сервисы вынуждены привлекать массу инструментов, обеспечивающих релевантность поиска. В ранжировании принимают участие миллионы сайтов: какой поднять в ТОП, а какой – пессимезировать, где информация недостоверная, какие ресурсы являются мошенническими? Для решения этих задач используются инструменты, каждый из которых отвечает за узкую ячейку, рассмотрим их.

С английского название переводится как «паук», инструмент осуществляет просмотр доменов с последующим копированием содержимого на выделенные сервера. Формируется «паутина», которая будет анализироваться специальными программами. В поле интересов Spider – исходный код и документы, имеющие формат HTML.

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

Этот алгоритм выполняет суммирование данных, полученных в результате предыдущих исследований. На финише выполняется деление проиндексированных страниц, создается список данных. Деление производится по HTML-тегам.

После выполнения индексации Database делит данные, создавая 2 отдельные базы:

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

Search Engine Results Engine

Инструмент определяет релевантность выдачи при формировании ее под конкретные запросы, а также финальное ранжирование. Помогает сортировать запросы: какие попадут в ТОП-10, какие – в ТОП-100.

Речь идет о сервере, на котором расположен сайт поисковика. С этим ресурсом взаимодействует пользователь во время введения запроса и получения ответа на него.

Читайте также:

Как работает поисковик

Главная цель – предоставление точного ответа на запрос пользователя, для чего поисковые системы Google и Яндекс привлекают методы машинного обучения. Особые схемы обработки и принципы сопоставления разных результатов помогают роботу понять, какая страница из массы будет полезной. Благодаря этому выводятся рейтинг и релевантность, которые появляются у всех сайтов после завершения обхода. Высокие результаты – залог лучших позиций сайта в выдаче, но процесс разделен на несколько этапов.

1. Сбор данных. При потребности в обходе выполняется автоанализ, для которого привлекаются «паук» и Crawler. Они собирают сведения, потом – осуществляют систематизацию.
2. Индексация. Выполняется на регулярной основе в интервальном режиме. После индексации сайт попадает в базу поисковой системы: создается индексный файл, он в перспективе будет использоваться для быстрого поиска нужного материала на странице.
3. Обработка данных. Получив запрос от пользователя, система начинает анализ и выделяет ключевые слова, которые ищет по индексным файлам. На базе процесса выявляются результаты, похожие на изначальный.
4. Ранжирование. Из ранее собранных результатов составляется список, в котором совпадения сортируются от больших к меньшим. Производится определение релевантности, что обеспечивает корректное отображение. Принцип ранжирования зависит от поисковой системы, но основные факторы схожи: соответствие текста интенту запроса, авторитет домена, цитируемость, оптимизация и похожий контент.

Характеристики поисковиков

Приоритет для пользователя – получение ответа на вопрос, однако поисковые системы используют широкий круг критериев для оценки сайтов, в частности контента.

1. Полнота. Учитывается соотношение количества ресурсов, которые содержат ответ на поставленный вопрос, по отношению ко всем сайтам. Чем выше показатель, тем более полным будет анализ внутренних баз данных.
2. Точность. Показатель конкретизированный, он помогает не просто выводить в ТОП сайты с прямым вхождением запроса, но и понимать, что хочет получить юзер. Если пользователь вводит запрос «купить дом», то он может увидеть не сайты агентств недвижимости, а базы отзывов и информационные порталы, на которых клиенты делятся впечатлениями от заключенных сделок. Параметр точность предупреждает показы сайтов, которые не слишком подходят под поисковые критерии.
3. Актуальность. Показатель определяет актуальность полученных сведений: сроков, которые истекли после размещения. Доминирующее количество поисковых системы берут период за 3 месяца, если домен релевантный – до 3 дней.
4. Скорость выполнения поиска. Временный показатель, необходимый сервису для создания списка выдачи после получения запроса. Определяется мощностью оборудования, привлекаемого для обработки информации. Может изменяться, что зависит от объемов данных. Если поисковик крупный, то скорость обработки достигает 100 миллионов в секунду.
5. Наглядность. Это клиентская оценка, зависящая от точности сведений из ТОП-10. Если пользователь не нашел ответ на первой странице, то может прибегнуть к помощи другого поисковика.

Читайте также:

Как функционируют разные поисковые системы

Google

Поисковая системы при реализации процесса привлекает 3 этапа:

• сканирование. Поисковые роботы собирают сведения, в качестве источников используя файлы и страницы. Каждый этап выполняет конкретный бот, например, сканирование – Googlebot, изображения – Image, а с мобильной версией работает Mobile. Выполняется удаление дублей, для упрощения процесса требуется карта сайта;
• индексирование. Данные собраны, поэтому поисковик переходит к их обработке;
• результаты запроса демонстрируются пользователю: он получает релевантный ответ.

Место домена на странице результатов поиска зависит от дополнительных факторов:

• E-A-T. Предупреждает распространение неправдивой информации из источников, кажущихся авторитетными. Применяется для статей на научные, медицинские и другие тематики, которые оказывают влияние на здоровье/жизнь пользователей. Если контент позиционируется в качестве экспертного, то учитываются авторитет, компетентность и достоверность: статьи должны писать отраслевые специалисты, имеющие диплом или другой документ;
• опыт юзера. Время загрузки страниц, юзабилити, адаптивность – эти и другие параметры формируют либо положительный, либо отрицательный опыт;
• поведенческие факторы. Тесно связаны с опытом: процент отказов, глубина просмотра и т. д.;
• скорость загрузки. Прямой фактор ранжирования, определяющий качество сайта. Лучшее время – до 2 секунд, что не зависит от типа устройства.

Есть дополнительный параметр, он появился недавно, – Core Web Vitals, определяющий не только скорость открытия, но и уровень оптимизации домена для взаимодействия.

Яндекс

Поисковая система Яндекс использует алгоритм YATI, который был запущен в 2020 году. Он основывается на машинном обучение, ориентирован на повышение качества голосового поиска. Алгоритм стал толчком к формированию требований к сайтам, стремящимся занять лучшие позиции в выдаче:

• при оптимизации лучше использовать длинные низкочастотные запросы, синонимичные фразы – все то, что пользователи привлекают при голосовом поиске;
• информативность контента: страницы с низкой долей содержательного текста, а также мусором попадут под удаление;
• естественные поведенческие факторы, в случае накрутки домен может быть заблокирован.

В заключение

Знание принципа работы и алгоритмов поисковых систем – основа успешного продвижения сайта и быстрого попадания в ТОП. В 2022 году во главе угла стоит не только оптимизация, но и экспертность, высокое качество контента, быстрая загрузка страниц, отсутствие теневых схем по накрутке. Для предупреждения проблем и наложения фильтров важно ориентироваться на свою целевую аудиторию, уделяя внимание смысловому наполнению и техническим характеристикам сайта.

Исправляем опечатки в поисковых запросах

Наверное, любой сервис, на котором вообще есть поиск, рано или поздно приходит к потребности научиться исправлять ошибки в пользовательских запросах. Errare humanum est; пользователи постоянно опечатываются и ошибаются, и качество поиска от этого неизбежно страдает — а с ним и пользовательский опыт.

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

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

В этой статье мы разберём один из классических подходов к исправлению опечаток, от построения модели до написания кода на Python и Go. И в качестве бонуса — видео с моего доклада «”Очки верткальной реальности”: исправляем опечатки в поисковых запросах» на Highload++.

Постановка задачи

Итак, нам пришёл опечатанный запрос и его надо исправить. Обычно математически задача ставится таким образом:

• дано слово , переданное нам с ошибками;
• есть словарь правильных слов;
• для всех слов w в словаре есть условные вероятности того, что имелось в виду слово , при условии, что получили мы слово ;
• нужно найти слово w из словаря с максимальной вероятностью .

Неясных моментов здесь два — где взять словарь и как посчитать . Первый вопрос считается простым. В 1990 году [1] словарь собирали из базы утилиты spell и доступных в электронном виде словарей; в 2009 году в Google [4] поступили проще и просто взяли топ самых популярных слов в Интернете (вместе с популярными ошибочными написаниями). Этот подход взял и я для построения своего опечаточника.

Второй вопрос сложнее. Хотя бы потому, что его решение обычно начинается с применения формулы Байеса!

Теперь вместо исходной непонятной вероятности нам нужно оценить две новые, чуть более понятные: — вероятность того, что при наборе слова можно опечататься и получить , и — в принципе вероятность использования пользователем слова .

Как оценить ? Очевидно, что пользователь с большей вероятностью путает А с О, чем Ъ с Ы. А если мы исправляем текст, распознанный с отсканированного документа, то велика вероятность путаницы между rn и m. Так или иначе, нам нужна какая-то модель, описывающая ошибки и их вероятности.

Такая модель называется noisy channel model (модель зашумлённого канала; в нашем случае зашумлённый канал начинается где-то в центре Брока пользователя и заканчивается по другую сторону его клавиатуры) или более коротко error model — модель ошибок. Эта модель, которой ниже посвящен отдельный раздел, будет ответственна за учёт как орфографических ошибок, так и, собственно, опечаток.

Оценить вероятность использования слова — — можно по-разному. Самый простой вариант — взять за неё частоту, с которой слово встречается в некотором большом корпусе текстов. Для нашего опечаточника, учитывающего контекст фразы, потребуется, конечно, что-то более сложное — ещё одна модель. Эта модель называется language model, модель языка.

Модель ошибок

Первые модели ошибок считали , подсчитывая вероятности элементарных замен в обучающей выборке: сколько раз вместо Е писали И, сколько раз вместо ТЬ писали Т, вместо Т — ТЬ и так далее [1]. Получалась модель с небольшим числом параметров, способная выучить какие-то локальные эффекты (например, что люди часто путают Е и И).

В наших изысканиях мы остановились на более развитой модели ошибок, предложенной в 2000 году Бриллом и Муром [2] и многократно использованной впоследствии (например, специалистами Google [4]). Представим, что пользователи мыслят не отдельными символами (спутать Е и И, нажать К вместо У, пропустить мягкий знак), а могут изменять произвольные куски слова на любые другие — например, заменять ТСЯ на ТЬСЯ, У на К, ЩА на ЩЯ, СС на С и так далее. Вероятность того, что пользователь опечатался и вместо ТСЯ написал ТЬСЯ, обозначим — это параметр нашей модели. Если для всех возможных фрагментов мы можем посчитать , то искомую вероятность набора слова s при попытке набрать слово w в модели Брилла и Мура можно получить следующим образом: разобьем всеми возможными способами слова w и s на более короткие фрагменты так, чтобы фрагментов в двух словах было одинаковое количество. Для каждого разбиения посчитаем произведение вероятностей всех фрагментов w превратиться в соответствующие фрагменты s. Максимум по всем таким разбиениям и примем за значение величины :

Давайте посмотрим на пример разбиения, возникающего при вычислении вероятности напечатать «аксесуар» вместо «аксессуар»:

Как вы наверняка заметили, это пример не очень удачного разбиения: видно, что части слов легли друг под другом не так удачно, как могли бы. Если величины и ещё не так плохи, то и , скорее всего, сделают итоговый «счёт» этого разбиения совсем печальным. Более удачное разбиение выглядит как-то так:

Здесь всё сразу стало на свои места, и видно, что итоговая вероятность будет определяться преимущественно величиной .

Как вычислить

Несмотря на то, что возможных разбиений для двух слов имеется порядка , с помощью динамического программирования алгоритм вычисления можно сделать довольно быстрым — за . Сам алгоритм при этом будет очень сильно напоминать алгоритм Вагнера-Фишера для вычисления расстояния Левенштейна.

Мы заведём прямоугольную таблицу, строки которой будут соответствовать буквам правильного слова, а столбцы — опечатанного. В ячейке на пересечении строки i и столбца j к концу алгоритма будет лежать в точности вероятность получить s[:j] при попытке напечатать w[:i] . Для того, чтобы её вычислить, достаточно вычислить значения всех ячеек в предыдущих строках и столбцах и пробежаться по ним, домножая на соответствующие . Например, если у нас заполнена таблица

, то для заполнения ячейки в четвёртой строке и третьем столбце (серая) нужно взять максимум из величин и . При этом мы пробежались по всем ячейкам, подсвеченным на картинке зелёным. Если также рассматривать модификации вида и , то придётся пробежаться и по ячейкам, подсвеченным жёлтым.

Сложность этого алгоритма, как я уже упомянул выше, составляет : мы заполняем таблицу , и для заполнения ячейки (i, j) нужно операций. Впрочем, если мы ограничим рассмотрение фрагментами не больше какой-то ограниченной длины (например, не больше двух букв, как в [4]), сложность уменьшится до . Для русского языка в своих экспериментах я брал .

Как максимизировать

Мы научились находить за полиномиальное время — это хорошо. Но нам нужно научиться быстро находить наилучшие слова во всём словаре. Причём наилучшие не по , а по ! На деле нам достаточно получить какой-то разумный топ (например, лучшие 20) слов по , который мы потом отправим в модель языка для выбора наиболее подходящих исправлений (об этом ниже).

Чтобы научиться быстро проходить по всему словарю, заметим, что таблица, представленная выше, будет иметь много общего для двух слов с общими префиксами. Действительно, если мы, исправляя слово «аксесуар», попробуем заполнить её для двух словарных слов «аксессуар» и «аксессуары», мы заметим, что первые девять строк в них вообще не отличаются! Если мы сможем организовать проход по словарю так, что у двух последующих слов будут достаточно длинные общие префиксы, мы сможем круто сэкономить вычисления.

И мы сможем. Давайте возьмём словарные слова и составим из них trie. Идя по нему поиском в глубину, мы получим желаемое свойство: большинство шагов — это шаги от узла к его потомку, когда у таблицы достаточно дозаполнить несколько последних строк.

Этот алгоритм, при некоторых дополнительных оптимизациях, позволяет нам перебирать словарь типичного европейского языка в 50-100 тысяч слов в пределах сотни миллисекунд [2]. А кэширование результатов сделает процесс ещё быстрее.

Как получить

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

Подход, использованный в [2, 4], сравнительно прост. Давайте найдём много пар , где — правильное слово из словаря, а — его опечатанный вариант. (Как именно их находить — чуть ниже.) Теперь нужно извлечь из этих пар вероятности конкретных опечаток (замен одних фрагментов на другие).

Для каждой пары возьмём составляющие её и и построим соответствие между их буквами, минимизирующее расстояние Левенштейна:

Теперь мы сразу видим замены: а → а, е → и, с → с, с → пустая строка и так далее. Также мы видим замены двух и более символов: ак → ак, се → си, ес → ис, сс → с, сес → сис, есс → ис и прочая, и прочая. Все эти замены необходимо посчитать, причём каждую столько раз, сколько слово s встречается в корпусе (если мы брали слова из корпуса, что очень вероятно).

После прохода по всем парам за вероятность принимается количество замен α → β, встретившихся в наших парах (с учётом встречаемости соответствующих слов), делённое на количество повторений фрагмента α.

Как найти пары ? В [4] предлагается такой подход. Возьмём большой корпус сгенерированного пользователями контента (UGC). В случае Google это были просто тексты сотен миллионов веб-страниц; в нашем — миллионы пользовательских поисковых запросов и отзывов. Предполагается, что обычно правильное слово встречается в корпусе чаще, чем любой из ошибочных вариантов. Так вот, давайте для каждого слова находить близкие к нему по Левенштейну слова из корпуса, которые значительно менее популярны (например, в десять раз). Популярное возьмём за , менее популярное — за . Так мы получим пусть и шумный, но зато достаточно большой набор пар, на котором можно будет провести обучение.

Этот алгоритм подбора пар оставляет большое пространство для улучшений. В [4] предлагается только фильтр по встречаемости ( в десять раз популярнее, чем ), но авторы этой статьи пытаются делать опечаточник, не используя какие-либо априорные знания о языке. Если мы рассматриваем только русский язык, мы можем, например, взять набор словарей русских словоформ и оставлять только пары со словом , найденном в словаре (не лучшая идея, потому что в словаре, скорее всего, не будет специфичной для сервиса лексики) или, наоборот, отбрасывать пары со словом s, найденном в словаре (то есть почти гарантированно не являющимся опечатанным).

Чтобы повысить качество получаемых пар, я написал несложную функцию, определяющую, используют ли пользователи два слова как синонимы. Логика простая: если слова w и s часто встречаются в окружении одних и тех же слов, то они, вероятно, синонимы — что в свете их близости по Левенштейну значит, что менее популярное слово с большой вероятностью является ошибочной версией более популярного. Для этих расчётов я использовал построенную для модели языка ниже статистику встречаемости триграмм (фраз из трёх слов).

Модель языка

Итак, теперь для заданного словарного слова w нам нужно вычислить — вероятность его использования пользователем. Простейшее решение — взять встречаемость слова в каком-то большом корпусе. Вообще, наверное, любая модель языка начинается с собирания большого корпуса текстов и подсчёта встречаемости слов в нём. Но ограничиваться этим не стоит: на самом деле при вычислении P(w) мы можем учесть также и фразу, слово в которой мы пытаемся исправить, и любой другой внешний контекст. Задача превращается в задачу вычисления , где одно из — слово, в котором мы исправили опечатку и для которого мы теперь рассчитываем , а остальные — слова, окружающие исправляемое слово в пользовательском запросе.

Чтобы научиться учитывать их, стоит пройтись по корпусу ещё раз и составить статистику n-грамм, последовательностей слов. Обычно берут последовательности ограниченной длины; я ограничился триграммами, чтобы не раздувать индекс, но тут всё зависит от вашей силы духа (и размера корпуса — на маленьком корпусе даже статистика по триграммам будет слишком шумной).

Традиционная модель языка на основе n-грамм выглядит так. Для фразы её вероятность вычисляется по формуле

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

Иными словами, если мы захотим вычислить , обозначив частоту произвольной n-граммы за , мы получим формулу

Логично? Логично. Однако трудности начинаются, когда фразы становятся длиннее. Что, если пользователь ввёл впечатляющий своей подробностью поисковый запрос в десять слов? Мы не хотим держать статистику по всем 10-граммам — это дорого, а данные, скорее всего, будут шумными и не показательными. Мы хотим обойтись n-граммами какой-то ограниченной длины — например, уже предложенной выше длины 3.

Здесь-то и пригождается формула выше. Давайте предположим, что на вероятность слова появиться в конце фразы значительно влияют только несколько слов непосредственно перед ним, то есть что

Положив , для более длинной фразы получим формулу

Обратите внимание: фраза состоит из пяти слов, но в формуле фигурируют n-граммы не длиннее трёх. Это как раз то, чего мы добивались.

Остался один тонкий момент. Что, если пользователь ввёл совсем странную фразу и соответствующих n-грамм у нас в статистике и нет вовсе? Было бы легко для незнакомых n-грамм положить , если бы на эту величину не надо было делить. Здесь на помощь приходит сглаживание (smoothing), которое можно делать разными способами; однако подробное обсуждение серьёзных подходов к сглаживанию вроде Kneser-Ney smoothing выходит далеко за рамки этой статьи.

Как исправлять фразы

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

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

Можно рассматривать слова по отдельности и применять некий классификатор, чтобы понимать, опечатано данное слово или нет, как это предложено в [4]. Классификатор обучается на вероятностях, которые мы уже умеем считать, и ряде других фичей. Если классификатор говорит, что нужно исправлять — исправляем, учитывая имеющийся контекст. Опять-таки, если несколько слов написаны с ошибкой, принимать решение насчёт первого из них придётся, опираясь на контекст с ошибками, что может приводить к проблемам с качеством.

В реализации нашего опечаточника мы использовали такой подход. Давайте для каждого слова в нашей фразе найдём с помощью модели ошибок топ-N словарных слов, которые могли иметься в виду, сконкатенируем их во фразы всевозможными способами и для каждой из получившихся фраз, где — количество слов в исходной фразе, посчитаем честно величину

Здесь — слова, введённые пользователем, — подобранные для них исправления (которые мы сейчас перебираем), а — коэффициент, определяемый сравнительным качеством модели ошибок и модели языка (большой коэффициент — больше доверяем модели языка, маленький коэффициент — больше доверяем модели ошибок), предложенный в [4]. Итого для каждой фразы мы перемножаем вероятности отдельных слов исправиться в соответствующие словарные варианты и ещё домножаем это на вероятность всей фразы в нашем языке. Результат работы алгоритма — фраза из словарных слов, максимизирующая эту величину.

Так, стоп, что? Перебор фраз?

К счастью, за счёт того, что мы ограничили длину n-грамм, найти максимум по всем фразам можно гораздо быстрее. Вспомните: выше мы упростили формулу для так, что она стала зависеть только от частот n-грамм длины не выше трёх:

Если мы домножим эту величину на и попытаемся максимизировать по , мы увидим, что достаточно перебрать всевозможные и и решить задачу для них — то есть для фраз . Итого задача решается динамическим программированием за .

Реализация

Собираем корпус и считаем n-граммы

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

В качестве словарных я брал топ слов по частотности так, чтобы получалось порядка ста тысяч слов. Исключались слишком длинные слова (больше 20 символов) и слишком короткие (меньше трёх символов, кроме захардкоженных известных русских слов). Отдельно пощадил слова по регулярке r»^[a-z0-9]$» — чтобы уцелели версии айфонов и другие интересные идентификаторы длины 2.

При подсчёте биграмм и триграмм во фразе может встретиться несловарное слово. В этом случае это слово я выбрасывал и бил всю фразу на две части (до и после этого слова), с которыми работал отдельно. Так, для фразы «А вы знаете, что такое «абырвалг»? Это… ГЛАВРЫБА, коллега» учтутся триграммы “а вы знаете”, “вы знаете что”, “знаете что такое” и “это главрыба коллега” (если, конечно, слово “главрыба” попадёт в словарь. ).

Обучаем модель ошибок

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

Код на Python

def generate_modifications(intended_word, misspelled_word, max_l=2): # Выстраиваем буквы слов оптимальным по Левенштейну образом и # извлекаем модификации ограниченной длины. Чтобы после подсчёта # расстояния восстановить оптимальное расположение букв, будем # хранить в таблице помимо расстояний указатели на предыдущие # ячейки: memo будет хранить соответствие # i -> j -> (distance, prev i, prev j). # Дальше немного непривычно страшного Python кода - вот что # бывает, когда язык используется не по назначению! m, n = len(intended_word), len(misspelled_word) memo = [[None] * (n+1) for _ in range(m+1)] memo[0] = [(j, (0 if j > 0 else -1), j-1) for j in range(n+1)] for i in range(m + 1): memo[i][0] = i, i-1, (0 if i > 0 else -1) for j in range(1, n + 1): for i in range(1, m + 1): if intended_word[i-1] == misspelled_word[j-1]: memo[i][j] = memo[i-1][j-1][0], i-1, j-1 else: best = min( (memo[i-1][j][0], i-1, j), (memo[i][j-1][0], i, j-1), (memo[i-1][j-1][0], i-1, j-1), ) # Отдельная обработка для перепутанных местами # соседних букв (распространённая ошибка при # печати). if (i > 1 and j > 1 and intended_word[i-1] == misspelled_word[j-2] and intended_word[i-2] == misspelled_word[j-1] ): best = min(best, (memo[i-2][j-2][0], i-2, j-2)) memo[i][j] = 1 + best[0], best[1], best[2] # К концу цикла расстояние по Левенштейну между исходными словами # хранится в memo[m][n][0]. # Теперь восстанавливаем оптимальное расположение букв. s, t = [], [] i, j = m, n while i >= 1 or j >= 1: _, pi, pj = memo[i][j] di, dj = i - pi, j - pj if di == dj == 1: s.append(intended_word[i-1]) t.append(misspelled_word[j-1]) if di == dj == 2: s.append(intended_word[i-1]) s.append(intended_word[i-2]) t.append(misspelled_word[j-1]) t.append(misspelled_word[j-2]) if 1 == di > dj == 0: s.append(intended_word[i-1]) t.append("") if 1 == dj > di == 0: s.append("") t.append(misspelled_word[j-1]) i, j = pi, pj s.reverse() t.reverse() # Генерируем модификации длины не выше заданной. for i, _ in enumerate(s): ss = ts = "" while len(ss) < max_l and i < len(s): ss += s[i] ts += t[i] yield ss, ts i += 1

Сам подсчёт правок выглядит элементарно, хотя длиться может долго.

Применяем модель ошибок

Эта часть реализована в виде микросервиса на Go, связанного с основным бэкендом через gRPC. Реализован алгоритм, описанный самими Бриллом и Муром [2], с небольшими оптимизациями. Работает он у меня в итоге примерно вдвое медленнее, чем заявляли авторы; не берусь судить, дело в Go или во мне. Но по ходу профилировки я узнал о Go немного нового.

Не используйте math.Max , чтобы считать максимум. Это примерно в три раза медленнее, чем if a > b < b = a >! Только взгляните на реализацию этой функции:

// Max returns the larger of x or y. // // Special cases are: // Max(x, +Inf) = Max(+Inf, x) = +Inf // Max(x, NaN) = Max(NaN, x) = NaN // Max(+0, ±0) = Max(±0, +0) = +0 // Max(-0, -0) = -0 func Max(x, y float64) float64 func max(x, y float64) float64 < // special cases switch < case IsInf(x, 1) || IsInf(y, 1): return Inf(1) case IsNaN(x) || IsNaN(y): return NaN() case x == 0 && x == y: if Signbit(x) < return y >return x > if x > y < return x >return y >

Применяем модель языка

Здесь без особых сюрпризов был реализован алгоритм динамического программирования, описанный в разделе выше. На этот компонент пришлось меньше всего работы — самой медленной частью остаётся применение модели ошибок. Поэтому между этими двумя слоями было дополнительно прикручено кэширование результатов модели ошибок в Redis.

Результаты

По итогам этой работы (занявшей примерно человекомесяц) мы провели A/B тест опечаточника на наших пользователях. Вместо 10% пустых выдач среди всех поисковых запросов, которые мы имели до внедрения опечаточника, их стало 5%; в основном оставшиеся запросы приходятся на товары, которых просто нет у нас на платформе. Также увеличилось количество сессий без второго поискового запроса (и ещё несколько метрик такого рода, связанных с UX). Метрики, связанные с деньгами, впрочем, значимо не изменились — это было неожиданно и сподвигло нас к тщательному анализу и перепроверке других метрик.

Заключение

Стивену Хокингу как-то сказали, что каждая включенная им в книгу формула вдвое уменьшит число читателей. Что ж, в этой статье их порядка полусотни — поздравляю тебя, один из примерно читателей, добравшихся до этого места!

Бонус

Ссылки

[1] M. D. Kernighan, K. W. Church, W. A. Gale. A Spelling Correction Program Based on a Noisy Channel Model. Proceedings of the 13th conference on Computational linguistics — Volume 2, 1990.

[2] E.Brill, R. C. Moore. An Improved Error Model for Noisy Channel Spelling Correction. Proceedings of the 38th Annual Meeting on Association for Computational Linguistics, 2000.

[3] T. Brants, A. C. Popat, P. Xu, F. J. Och, J. Dean. Large Language Models in Machine Translation. Proceedings of the 2007 Conference on Empirical Methods in Natural Language Processing.

[4] C. Whitelaw, B. Hutchinson, G. Y. Chung, G. Ellis. Using the Web for Language Independent Spellchecking and Autocorrection. Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 2.

• Блог компании Joom
• Поисковые технологии
• Программирование
• Алгоритмы
• Математика