Исправление очепяток 1/2.
Я думаю, понятно, зачем нужно уметь исправлять запросы, но вот хороший пример от Google про то, как люди ищут Britney Spears: link. Тут и brittiny spears, и drittney spears, и buttney spears, и много всего другого.
Исправления обычно делят на два вида: isolated-term correction (когда пытаемся исправить каждый отдельный терм запроса отдельно) и context-sensitive (когда каждый отдельный терм корректен, но при этом они не согласуются друг с другом). Сначала про первое.
Есть два основных, применяющихся вместе, алгоритмических метода исправлять опечатки: по расстоянию между строками (edit distance) и по пересечению n-грамм.
Когда говорят про расстояние между строками, обычно имеют в виду, что есть некоторое множество операций (например, добавление, удаление и замена символа), и тогда расстоянием между s1 и s2 будет кол-во операций, нужное, чтобы превратить одну строку в другую (в данном случае это расстояние Левенштейна). В общем случае различным операциям может назначаться разный вес (например изменить гласную на другую гласную это семантически “дешевле”, чем гласную на согласную; или пользователи часто промахиваются по клавиатуре, что означает, что некоторые ошибки в буквах возникают чаще).
Нахождение расстояния Левенштейна между двумя строками это известная таска на динамическое программирование. Однако в рамках больших поисковых индексов подобная операция для всех пар (терм запроса, терм в индексе) будет занимать огромное время. Потому это не прям хорошее решение, однако на него в более простых случаях можно наворачивать разные эвристики. Например одной из простых может быть предположение, что пользователь не ошибся в первом символе слова (в общем случае в первых k символах), что означает сужение поиска по индексу лишь среди термов, которые начинаются на тот же префикс.
Или можно например использовать улучшение метрики Левенштейна под названием Дамерау-Левенштейн, где разрешено переставлять символы.
Иногда (даже всегда) работают не с расстояниями, а с вероятностями. Например можно посчитать
p(w|s) – вероятность того, что имели в виду терм w, при условии, что получили терм s (эту величину мы пытаемся максимизировать). Тут применяем формулу Байеса:p(w|s) = C * p(s|w) * p(w),где
p(s|w) – вероятность того, что при наборе w можно получить s, а p(w) – вероятность того, что пользователь мог использовать терм w (тут уже речь идёт про модель конкретного языка). Не будем уходить глубже в этом месте и пойдём дальше (хотя тут много интересных моментов есть, вроде того, что в языке постоянно появляются новые слова; что можно строить модели того, как пользователи ошибаются).