Привет всем!
Есть текст с неправильными словами, которые надо исправить согласно словам в словаре.
Причём:
— для изменения слова допускается только 2 операции: вставка и/или удаление символа;
— если это две вставки или два удаления, то эти два символа не должны находиться рядом;
Если под исправление подходит несколько слов из словаря, то отобразить их в тексте внутри фигурных скобок.

Пример.

Словарь:
rain the his main mainly plain

Текст:
hte mainy lain

В результате должно быть:
the {main mainly} plain

Сначала думал, что достаточно будет использовать алгоритм дистанции Левенштейна. Например, если сравнивать "hte" с "the", то он выдаст длину 2, для "his" тоже. И для самого алгоритма это правильно (т.к. работает заменами), но по заданию подойдёт только "the", т.к. два действия: сначала удаление в начале слова символа "h" и потом добавление "h" между "t" и "e".
"his" не подойдёт, т.к. для приведения слова "hte" к "his" действий (именно удалений-вставок, а не замен) будет больше.
Может кто сталкивался уже, в какую сторону будет правильно думать?

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

S>Привет всем!
S>Может кто сталкивался уже, в какую сторону будет правильно думать?

мне Рабинович по телефону напел у меня приятель работает над spellchecker. Рассказывал, что кроме расстояния Левенштайна они ещё навешивают на каждое изменение весовой коэффициент. Например на опечатку z/x должен быть коэффициент меньше, чем на опечатку q/m. Ну и расстояние Левенштайна не предусматривает простую перестановку двух символов, как в вашем примере hte вместо the. Это должно быть отдельное изменение с довольно низким коэффициентом.

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

S>Может кто сталкивался уже, в какую сторону будет правильно думать?

Лучше всего в сторону смены профессии

А если серьёзно, то в чём проблема? Берёшь у друзей конспект лекций, находишь тему "динамическое программирование" читаешь и делаешь

Если коротко, то заводишь множество троек чисел: (позиция в образце, позиция в слове из словаря, число уже допущенных ошибок).
На первом шагу в множество кладёшь всего одну тройку из трёх 0.
Потом в цикле пока в множестве остаётся хотя бы одна тройка делаешь следующее:

по текущему множеству троек, строишь следующее. Каждую тройку чисел можно "продолжить" несколькими способами.
1) если символы в текущих позиция слова из словаря и образце, совпадают, можно на 1 увеличить обе позиции.
2) если число ошибок меньше лимита и образец ещё не закончился, можно увеличить на 1 позицию в образце и число ошибок
3) если число ошибок меньше лимита и слово из словаря ещё не закончилось, можно увеличить на 1 позицию в слове из словаря и число ошибок
4) если достигнут конец обоих слов ( и образца и слова из словаря), а лимит ошибок ещё не превзойдён, то мы нашли то, что ищем.

Соответственно продолжаешь (кладёшь в множество, соответствующее след. шагу алгоритма) все варианты продолжения.
И крутишь цикл, пока не найдёшь или множество след. шага не будет пустым.

Так как каждый шаг мы как минимум одну из позиций увеличиваем, то шагов будет не больше, чем длина образца и слова из словаря в сумме.
Так как у нас есть лимит на число ошибок, то "ширина" поиска будет ограничена константой, зависящей, как O(лимита). Так что алгоритм линейный по лимиту и длинам.

Да, то, что я описал выше не накладывает ограничение на то, Что вставки не могут идти подряд. Сам придумай, как его туда добавить.

Творческих узбеков и всё такое.

p. s.
Не благодари, в смысле для "спасибо" тут есть кнопки

Здравствуйте, Erop, Вы писали:
E>Лучше всего в сторону смены професии

"Чем отличается размещение вопроса на русском и не русском форумах? В первом случае сначала рассказывают какой ты мудак, а потом, быть может, по сути"

Вы серьёзно или просто наследственное?

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

E>>Лучше всего в сторону смены професии

S>"Чем отличается размещение вопроса на русском и не русском форумах? В первом случае сначала рассказывают какой ты мудак, а потом, быть может, по сути"

Я про то, что кто-то мудак, ничего не писал, в отличии от

S>Вы серьёзно или просто наследственное?
Про смену профессии, да, серьёзно стоит подумать, тем более, что тебя заинтересовал не описанный в моём ответе алгоритм, а совет сменить профессию...

Здравствуйте, Erop, Вы писали:
E>Про смену профессии, да, серьёзно стоит подумать, тем более, что тебя заинтересовал не описанный в моём ответе алгоритм, а совет сменить профессию...
Алгоритм был реализован посредством пересечений возможных вариантов из словаря и текста задолго до Вашего ответа, спасибо.