Исправление очепяток 2/2.
Для сокращения кол-ва термов, с которыми в итоге можно считать расстояние, также можно использовать n-граммы. Построим n-грамм индекс (отображение из n-граммы во множество термов в документах), а потом пройдёмся по нему и достанем те термы, которые имеют “много” общих n-грамм с запросом. Например у нас есть запрос bord и индекс над биграммами:
bo: aboard about boardroom border
or: border lord morbid sordid
rd: aboard ardent boardroom border
Уже обсуждавшимися методами можно пересечь множества термов для всех биграмм и при выборе кол-ва общих биграмм 2 получить результаты aboard, boardroom и border.
Т.к. выбор количества общих n-грамм сильно зависит от размеров строк, можно оперировать более общими понятиями вроде коэффициента Жаккара, означающим меру сходства множеств (упоминал его в посте про вероятностные сд).
В случае, если после нахождения ближайших термов получается несколько, можно брать более популярный. Например популярным можно назвать терм, который чаще встречается в индексированных документах. А ещё можно смотреть, как сами пользователи исправляют свои ошибки и выбирать ту версию, которую они выбирают чаще. Вот этот подход с популярностями юзается примерно в любом решении: от гугла до небольших самописных штук, которые я видел.
В этом месте кстати есть различные способы использовать это для юзера. Можно просто безусловно попробовать поиск по документам, учитывая исправления (как делаем мы), а можно явно предложить замену, как делают это крупные поисковики.
С точки зрения context-sensitive исправлений самым простым решением может быть попробовать изменить в запросе каждый отдельный терм и поискать результаты по всем подобным запросам, после чего на основании кол-ва результатов/их релевантности выбрать подходящую исправленную версию.
Конечно, количество подобных “исправленных” запросов может быть огромным. Потому тут опять же есть всякие эвристики. Например использовать только самые популярные формы термов (или сочетаний термов) с учётом действий пользователей.
Также важным инструментом является т.н. phonetic correction.
Основная идея – научиться генерировать “фонетический хеш” слов, который будет совпадать, если они произносятся одинаково, даже если пишутся по-разному. Подходы для подобных задач называются soundex алгоритмами. Тут можно вики почитать.