|
Название: Spell checker (проверка орфографии) Отправлено: serg_hd от Июнь 11, 2018, 21:03 Привет всем, такая задача.
Есть текст с неправильными словами, которые надо исправить согласно словам в словаре. Причём: - для изменения слова допускается только 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" действий (именно удалений-вставок, а не замен) будет больше. Может кто сталкивался уже? |