Вправьте мне мозг, please!

Всем привет!
Без излишних предисловий. Немного умею программировать. Прошел собеседование в одну контору. Прислали тестовое задание.Третий день сижу, не могу ничего придумать. Нужно разработать простенький spell checker. Мозг не варит и придумать путевую логику не может. Кто может подсказать сам алгоритм, буду безмерно благодарен! Прошу не код, а помочь именно с логикой. Ссылку на задание выкладываю ниже.
Еще раз уточняю. Я не прошу за меня сделать. Просто дайте "пинка", чтобы понять, куда рыть. Я-то может и не успею (сегодня до 18 часов сдать нужно), но постараться стоит.
Задание - http://dl.dropbox.com/u/46160821/Spell_checker_C%2B%2B.doc .

Lucky_spirit написал:

Всем привет!
Без излишних предисловий. Немного умею программировать. Прошел собеседование в одну контору. Прислали тестовое задание.Третий день сижу, не могу ничего придумать. Нужно разработать простенький spell checker. Мозг не варит и придумать путевую логику не может. Кто может подсказать сам алгоритм, буду безмерно благодарен! Прошу не код, а помочь именно с логикой. Ссылку на задание выкладываю ниже.
Еще раз уточняю. Я не прошу за меня сделать. Просто дайте "пинка", чтобы понять, куда рыть. Я-то может и не успею (сегодня до 18 часов сдать нужно), но постараться стоит.
Задание - http://dl.dropbox.com/u/46160821/Spell_checker_C%2B%2B.doc .

Проверять слова по словарю. В случае несовпадения спрашивать добавть в словарь, или нет.

"CyberDaemon" написал:

. В случае несовпадения спрашивать добавть в словарь, или нет.

не... там надо самому править... ни каких спрашивавший...

как вариант: для каждого слова строим каждую возможную искажённую последовательность. тогда правку будет тривиальной...
[added]
не... не пойдёт... с удалениями ещё можно справится, а вот со вставками на каждое слово будет 26^2 лишних... ещё подумаю...
[added]
а если так: ищем сумму букв. далее слова, которые меньше на 2 буквы должны отличаться в меньшую сторону минимум на 2, максимум на 46.
слова, отличающиеся на 1 букву - 26-1, слова такой же длины +-26 итд... вроде перебор сильно сокращается....
[added]
ещё способ: построить префиксное дерево и при обходе допускать, что там ошибка... тогда проверка, что слово в словаре О(n), худшее время проверка одной ошибки в 26 раз больше, но - тоже О(n) и двух ошибок - O(n^2)...если я не осчитался... но ИРЛ всё должно быть лучше... вообще вроде это лучший.
эх меня попёрло...

"Lucky_spirit" написал:

Еще раз уточняю. Я не прошу за меня сделать. Просто дайте "пинка", чтобы понять, куда рыть.

Lucky_spirit написал:

Немного умею программировать. Прошел собеседование в одну контору. Прислали тестовое задание.Третий день сижу, не могу ничего придумать.

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

CuttingEdge, почему? человек не просил решений. Возможно он вполне подходит для этой работы, просто никогда не работал с текстом на таком уровне. Это же нечёткий поиск - передний край исследований, искусственный интеллект. Вы разве не видите, какие тупые у нас спелчекеры?

Извините, что-то мне уведомлений по почте с этого форума не приходило, поэтому только сейчас увидел ответы на тему. Вопрос решил с помощью вот этого: http://ru.wikibooks.org/wiki/Расстояние_Левенштейна