Когда вы говорите n-граммы, я предполагаю, что вы говорите о буквах в слове, а не о словах в предложении (что, вероятно, является наиболее распространенным использованием). В этом случае я бы согласился с Марком Рушаковым в том, что вы можете сократить список кандидатов до слов, содержащих на 3-5 символов больше или меньше, чем слово, которым вы управляете.
Другой вариант - реализовать алгоритм Левенштейна , чтобы найти расстояние редактирования между двумя словами. Это может быть сделано довольно эффективно: во-первых, только путем проверки вашего сокращенного списка. Во-вторых, через преждевременное завершение вычисления расстояния слова, когда расстояние редактирования превышает некоторый предел (например, 3-5).
В качестве примечания, я не согласен с Марком в том, что вы должны игнорировать короткие слова, так как они не так часто пишутся с ошибками. Большая часть слов с ошибками будет короткими (например, «и» - «над», «-», «ты» - «йо») просто потому, что они встречаются гораздо чаще.
Надеюсь, это поможет!