convert word1 to word2

[jms]

You are given a dictionary of all valid words. You have the following 3 operations permitted on a word: delete a character, insert a character, replace a character. Now given two words - word1 and word2 - find the minimum number of steps required to convert word1 to word2. (one operation counts as 1 step.)

У кого нибудь есть идеи красивого решения? У меня кроме некой реализации перебора нету

[Deynekin]

You are given a dictionary of all valid words. You have the following 3 operations permitted on a word: delete a character, insert a character, replace a character. Now given two words - word1 and word2 - find the minimum number of steps required to convert word1 to word2. (one operation counts as 1 step.)

У кого нибудь есть идеи красивого решения? У меня кроме некой реализации перебора нету

-Лёгко, в одно касание! Применяя операцию replace a character, меняем единицу на двойку: word1 -> word2 - готово!
Даже словарь не понадобился...

[Hamster]

Промежуточные состояния должны быть valid words, или нет?

Если не должны, то зачем нужен словарь?

[Deynekin]

Промежуточные состояния должны быть valid words, или нет?

Если не должны, то зачем нужен словарь?

Ну, разумеется, должны. Иначе и задачи не было бы: удаляй/дописывай буквы - и вся недолга. Так, кстати, мы слова и пишем: по буковке, начиная с "пустого слова".

Но, похоже, в общем случае такую цепочку от одного произвольного слова к другому, прыгая только по словам из словаря, выстроить невозможно. Допустим, наш словарь содержит слово "шшшшш", а все остальные слова - "нормальные". (Возражение, что такого слова нет - несущественное: возьмём обычный словарь и пополним его этим словом, сказав, что оно означает команду замолчать, вести себя тихо - почему нет?) Так вот, стартуя от этого слова и применяя только указанные преобразования, уже после первого шага никак не получить ни одного "нормального" слова из словаря. - Мостик не строится, приэхали!

[Hamster]

Промежуточные состояния должны быть valid words, или нет?

Если не должны, то зачем нужен словарь?

Ну, разумеется, должны. Иначе и задачи не было бы: удаляй/дописывай буквы - и вся недолга. Так, кстати, мы слова и пишем: по буковке, начиная с "пустого слова".

Но, похоже, в общем случае такую цепочку от одного произвольного слова к другому, прыгая только по словам из словаря, выстроить невозможно. Допустим, наш словарь содержит слово "шшшшш", а все остальные слова - "нормальные". (Возражение, что такого слова нет - несущественное: возьмём обычный словарь и пополним его этим словом, сказав, что оно означает команду замолчать, вести себя тихо - почему нет?) Так вот, стартуя от этого слова и применяя только указанные преобразования, уже после первого шага никак не получить ни одного "нормального" слова из словаря. - Мостик не строится, приэхали!

Если не должны, алгоритм нахождения произвольного пути word1->word2 за max(len(word1),len(word2)) операций тривиален, а алгоритм нахождения _кратчайшего_ - отнюдь. Попробуйте привести алгоритм, способный сгенерировать путь от слова "стол" до слова "тополь" за 4 операции, не пользуясь полным перебором. Учтите, что полный перебор в общем случае не канает, потому что пространство всех буквосочетаний, полученных из слова "стол" всего за 4 операции, включает что-то типа 10^8 элементов, а для перебора всех сочетаний, удаленных на 8 шагов, нужен суперкомпьютер.

Если должны, подавляющее большинство слов длиннее ~5 букв в словаре будут находиться в изолированных кластерах в 2-10 слов, и для большинства пар слов задача не будет иметь решения.

[jms]

Я думаю что можно рассматривать две задачи -- с словарем и без.
Давайте остановимся на первой для начала.

Вторая -- что мне приходит в голову, это на этапе предобработки мы строим граф -- вершины слова из словаря, вершины соеденены, если одно слово можно преобразовать в другое. Понятно что граф строится за O(n^2), где n -- количество слов в словаре. Дальше когда нам дают word1 и word2, мы их включаем в граф, и ищем кратчайший путь в нем. Как то так.

А вот для первой, я могу сконструировать достаточно сложный перебор, но хотелось бы элегантное рещение.

[vlad12345]

Имхо формулировка не совсем полная, в частности вопросы:
словарь конечный или необязательно?
для заданных word1 и word2 известно ли нам заранее, что решение существует?
чем плох и перебор и что значит "элегантное" решение? требуется некая скорость алгоритма или некие ограничения на ресурсы?

[vaduz]

Задача ( если без словаря ) - типический sequence alignment.
Для коротких слов решается просто, полным перебором.

[vm__]

Для коротких слов решается просто, полным перебором.

Что такое "короткое слово"? Адна буква? Ни адной? Две-три? Или про терабайты-петабайты речь?!

[AndreyT]

Странно, что до сих пор никто не произнес правильного термина. Это называется Levenshtein distance (http://en.wikipedia.org/wiki/Levenshtein_distance) и именно так - динамическим программированием - решается эта задача без словаря.

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

P.S. Последнее, к сожалению, не даст решения задачи в общем случае, ибо алгоритм Levenshtein distance, например, не пытается удлинить исходное слово, если целевое слово не длиннее. А ограниченный словать может заставлять нас идти и по пути удлинения. Хм...

[vaduz]

Для коротких слов решается просто, полным перебором.

Что такое "короткое слово"? Адна буква? Ни адной? Две-три? Или про терабайты-петабайты речь?!

Короткие слова, это когда самое длинное слово - из книги рекордов Гиннеса.

[Flying Hen]

P.S. Последнее, к сожалению, не даст решения задачи в общем случае, ибо алгоритм Levenshtein distance, например, не пытается удлинить исходное слово, если целевое слово не длиннее. А ограниченный словать может заставлять нас идти и по пути удлинения. Хм...

Есть еще одна проблема. Этот алгоритм проходит оба слова по буквам слева направо, пройденные буквы больше не рассматриваются. Но может найтись такая цепочка, что на последнем шаге меняется начальная буква, например:
муха-мура-тура-тара-кара-каре-кафе-кафр-каюр-крюк-урюк-урок-срок-сток-стон-слон
на последнем шаге меняется вторая буква.

Можно, скажем, построить граф связей между словами, описав все возможные ребра. Потом ходить по нему, запоминая пройденный путь и на каждом шаге проверяя, не проходилось ли уже данное слово. Если мы уже здесь были, возвращаемся назад по рекурсии до ближайшей развилки, где есть еще неисследованные ребра. И так далее, пока случайно не наткнемся на нужное слово. Если вернулись в исходный пункт и нет неисследованных ребер, то цепочка невозможна. Так можно найти какой-то путь, но он не будет кратчайшим. Короче, понятно, что задача нетривиальная.

[Dweller]

Граф связей это правильная идея. Имея граф связей, найти кратчайшее расстояние уже не проблема.
Создаем массив достижимых из Word1 узлов с расстояниями и кратчайшей цепочкой ведущей к ним. На каждой итерации расширяем список, обновляя кратчайшие расстояния и цепочки. Как только найдется Word2, убеждаемся что после очередной итерации все добавленные в список узлы имеют расстояния больше чем расстояние от Word1 до Word2, тогда цепочка от Word1 к Word2 будет оптимальной.
Если слово Word2 так и не появилось в списке достижимых узлов и список стабилизировался, то выдаем ответ что пути от Word1 к Word2 нет.