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

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



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

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

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


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

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

Эта постановка — самая элементарная — предполагает, что если нам пришёл запрос из нескольких слов, то мы исправляем каждое слово по отдельности. В реальности, конечно, мы захотим исправлять всю фразу целиком, учитывая сочетаемость соседних слов; об этом я расскажу ниже, в разделе “Как исправлять фразы”.

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

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

$P(w|s) = \mathrm{const} \cdot P(s|w) \cdot P(w)$


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

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

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

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

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


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

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

$P(s|w) = \max_{s=\alpha_1\alpha_2\ldots\alpha_k, w=\beta_1\beta_2\ldots\beta_k}P(\alpha_1\rightarrow\beta_1)\cdot P(\alpha_2\rightarrow\beta_2)\cdot \ldots \cdot P(\alpha_k\rightarrow\beta_k)\,.$


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

$\begin{matrix} \text{ак} & \text{сес} & \text{су} & \text{а} & \text{р} \\ \downarrow & \downarrow & \downarrow & \downarrow & \downarrow \\ \text{а} & \text{кс} & \text{е} & \text{суа} & \text{р} \end{matrix}$

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

$\begin{matrix} \text{ак} & \text{се} & \text{сс} & \text{у} & \text{ар} \\ \downarrow & \downarrow & \downarrow & \downarrow & \downarrow \\ \text{ак} & \text{се} & \text{с} & \text{у} & \text{ар} \end{matrix}$


Здесь всё сразу стало на свои места, и видно, что итоговая вероятность будет определяться преимущественно величиной $P(\text{сс} \rightarrow \text{с})$.

 

Как вычислить $P(s|w)$


Несмотря на то, что возможных разбиений для двух слов имеется порядка $O(2^{|s|+|w|})$, с помощью динамического программирования алгоритм вычисления $P(s|w)$ можно сделать довольно быстрым — за $O(|s|^2|w|^2)$. Сам алгоритм при этом будет очень сильно напоминать алгоритм Вагнера-Фишера для вычисления расстояния Левенштейна.

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


, то для заполнения ячейки в четвёртой строке и третьем столбце (серая) нужно взять максимум из величин $0.8 \cdot P(\text{кс} \rightarrow \text{к})$ и $0.16 \cdot P(\text{с} \rightarrow \text{к})$. При этом мы пробежались по всем ячейкам, подсвеченным на картинке зелёным. Если также рассматривать модификации вида $P(\alpha \rightarrow \text{пустая строка})$ и $P(\text{пустая строка} \rightarrow \beta)$, то придётся пробежаться и по ячейкам, подсвеченным жёлтым.

Сложность этого алгоритма, как я уже упомянул выше, составляет $O(|s|^2|w|^2)$: мы заполняем таблицу $|s|\times|w|$, и для заполнения ячейки (i, j) нужно $O(i\cdot j)$ операций. Впрочем, если мы ограничим рассмотрение фрагментами не больше какой-то ограниченной длины $L$ (например, не больше двух букв, как в [4]), сложность уменьшится до $O(|s|\cdot|w|\cdot L^2)$. Для русского языка в своих экспериментах я брал $L = 3$.

 

Как максимизировать $P(s|w)$


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

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

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

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

 

Как получить $P(\alpha\rightarrow\beta)$


Вычисление $P(\alpha\rightarrow\beta)$ для всех рассматриваемых фрагментов — самая интересная и нетривиальная часть построения модели ошибок. Именно от этих величин будет зависеть её качество.

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

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

$\begin{matrix} \text{а} & \text{к} & \text{с} & \text{е} & \text{с} & \text{с} & \text{у} & \text{а} & \text{р} \\ \text{а} & \text{к} & \text{с} & \text{е} & \text{с} & \text{} & \text{у} & \text{а} & \text{р} \end{matrix}$

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

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

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

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

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

Модель языка


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

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

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

$ P(w_1w_2\ldots w_k) =P(w_1) \cdot P(w_2|w_1) \cdot P(w_3|w_1w_2) P(w_k|w_1w_2w_{k-1})\,, $


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

Иными словами, если мы захотим вычислить $P(\text{мама мыла раму})$, обозначив частоту произвольной n-граммы за $f$, мы получим формулу

$ P(\text{мама мыла раму}) = f(\text{мама}) \cdot \frac{f(\text{мама мыла})}{f(\text{мама})} \cdot \frac{f(\text{мама мыла раму})}{f(\text{мама мыла})} = f(\text{мама мыла раму})\,. $


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

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

$ P(w_k|w_1w_2\ldots w_{k-1}) \approx P(w_k|w_{k-L+1}\ldots w_{k-1})\,. $


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

 
$ P(\text{карл у клары украл кораллы}) \approx f(\text{карл}) \cdot \frac{f(\text{карл у})}{f(\text{карл})}\cdot \frac{f(\text{карл у клары})}{f(\text{карл у})} \cdot \frac{f(\text{у клары украл})}{f(\text{у клары})} \cdot \frac{f(\text{клары украл кораллы})}{f(\text{клары украл})}\,. $
 

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

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

 

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


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

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

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

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

$ P(s_1|w_1) \cdot P(s_2|w_2) \cdot \ldots \cdot P(s_K|w_K) \cdot P(w_1w_2\ldots w_K)^{\lambda}\,. $



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

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

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

$ P(w_1w_2\ldots w_K) =P(w_1) \cdot P(w_2|w_1) \cdot P(w_3|w_1w_2) \cdot \ldots \cdot P(w_K|w_{K-2}w_{K-1})\,. $


Если мы домножим эту величину на $P(s_i|w_i)$ и попытаемся максимизировать по $w_K$, мы увидим, что достаточно перебрать всевозможные $w_{K-2}$ и $w_{K-1}$ и решить задачу для них — то есть для фраз $w_1w_2\ldots w_{K-2}w_{K-1}$. Итого задача решается динамическим программированием за $O(KN^3)$.

Реализация


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


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

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

    Если только вам ВДРУГ не нужно, чтобы +0 обязательно был больше -0, не используйте math.Max.
  • Не используйте хэш-таблицу, если можете использовать массив. Это, конечно, довольно очевидный совет. Мне пришлось перенумеровывать символы юникода в числа в начале программы так, чтобы использовать их как индексы в массиве потомков узла trie (такой lookup был очень частой операцией).
  • Коллбеки в Go недёшевы. В ходе рефакторинга во время код ревью некоторые мои потуги сделать decoupling ощутимо замедлили программу при том, что формально алгоритм не изменился. С тех пор я остаюсь при мнении, что оптимизирующему компилятору Go есть, куда расти.

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


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

Результаты


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

Заключение


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

Бонус



Ссылки


[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.