Есть Большой словарь правильных слов. Пользователь вводит свое слово и может ошибиться, но так что длина слова будет не более чем на 2 символа больше или на 2 меньше , чем правильное написание. Нужно быстро пройтись по словарю и, если точного совпадения нет выдать слова такие что, расстояние Левенштейна между ними и введенным словом не более некоторой константы.

Алгоритм поиска расстояния Левенштейна реализован и вроде более менее оптимизирован. И, собственно, остается организовать быстрый поиск поиск по словарю. А конкретнее задача в том как сузить область поиска, чтобы не пришлось перебирать все слова в словаре.
Словарь грузится в std::unordered_set.
Пока в голову пришли 2 варианта.

1. При загрузке словаря разбить все слова на непересекающиеся группы по длине слова. А так как введенное слово не может быть более чем на 2 символа меньше или больше правильного, то нужно искать не во всем словаре а только в группах с таким же кол-вом слов, а также в -1 -2 и в +1 +2.

2. Разбивать слова в словаре на подгруппы по 2 или 3 символа, например машина = маш, аши, шин, ина, эти подгруппы будут индексами. Ну и соответственно, когда вводим слово, также бить его на подгруппы и искать далее только в тех подразделах словаря, где есть одинаковые подгруппы. Это решение мне кажется более подходящим, кроме одного но. При первоначальном разбиении многие слова будут дублироваться, например слово "камасутра" будет и в группе "кам" вместе с "камчатка" и в группе "утр" вмсте с "утро" и размер словаря сильно вырастет, возможно в несколько раз.

В общем, прошу совета по алгоритму, ну и может где почитать про это. Спасибо.