Здравствуйте, rp80, Вы писали:

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

R>2. Разбивать слова в словаре на подгруппы по 2 или 3 символа, например машина = маш, аши, шин, ина, эти подгруппы будут индексами. Ну и соответственно, когда вводим слово, также бить его на подгруппы и искать далее только в тех подразделах словаря, где есть одинаковые подгруппы. Это решение мне кажется более подходящим, кроме одного но. При первоначальном разбиении многие слова будут дублироваться, например слово "камасутра" будет и в группе "кам" вместе с "камчатка" и в группе "утр" вмсте с "утро" и размер словаря сильно вырастет, возможно в несколько раз.
Ну так хранить нужно не сами слова, а ссылки на них в виде индекса в глобальном массиве слов. Будет тратится [log₂N] бит на каждое вхождение слова. Хотя, конечно, индекс все равно растёт.

R>В общем, прошу совета по алгоритму,
Их простых подходов — хранить все слова в TRIE (или в DAWG для экономии памяти). Тогда процедура поиска слова в trie с k ошибками будет выглядеть так:
Если k == 0, то делается точный поиск (который может завершиться успехом или нет).
Если k > 0, то переходим из текущего узла trie по всем ссылкам, и если переход по ссылке был по несовпадающей букве, уменьшаем k.

Такой рекурсивный алгоритм найдёт все слова с указанным ограничением на расстояние Левенштейна без явного его вычисления для каждого слова с нуля. Собственно trie часто используется для подсчёта расстояния до всех слов — это известный алгоритм. Тут лишь отличие в том, что если для какого-то узла trie уже установлено, что расстояние превысило k, то это означает, что и у всех дочерних узлов оно не меньше, а это отсекает большое число слов, которые уже можно не проверять.

R>ну и может где почитать про это.
Есть отличный обзор "Indexing Methods for Approximate Dictionary Searching: Comparative Analysis".
Либо просто смотреть как работают известные программы проверки орфографии вроде aspell (или даже сразу задействовать их).