Как называются алгоритмы, который показывает пошаговые изменения в слове?

Question

[Soft_touch_plastic]

Здравствуйте, такую задачу решаю, если кратко то нужен путь преобразования одного слова в другое по шагам, например емтто - метто - метро. Интуитивно догадываюсь, что это что-то из области расстояния редактирования (Дамерау-Левенштейна, операции перестановки тоже нужны), но не понимаю как переложить матрицу оттуда на изменения слова. Если кто знает, как такие алгоритмы называются, можете подсказать в какую сторону копать?

Comments

[Василий Дёмин]

Какие изменения слова за шаг разрешены? Просто в вашем примере первое изменение две буквы затронуло, а второе - только одну. Поэтому не очень понятна задача.

[Soft_touch_plastic]

Василий Дёмин, обратите внимание, в первом случае произошла перемена местами двух букв, операция одна. А так операции стандартные для задач расстояния редактирования (удаление, вставка, замена, транспозиция)

[Василий Дёмин]

Мне в голову приходит решение через A*. Соседние вершины графа для любого слова - слова, которые за один шаг можно из него получить. Эвристика - расстояние между словом в вершине и целевым словом.

[Soft_touch_plastic]

Василий Дёмин, ухты, спасибо, можете оформить как ответ и добавить немного подробностей?)

Answer 1

[Wataru]

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

Comments

[Soft_touch_plastic]

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

[Василий Дёмин]

Soft_touch_plastic, Граф можно представить как функцию, которая принимает вершину (в вашем случае слово), а возвращает список соседей. То есть вам нужно применить к слову все возможные трансформации и вернуть результаты этих трансформаций

[Wataru]

Soft_touch_plastic, перебираете все варианты изменений, проверяете, что слово есть в словаре.

Если запустите какой-нибудь A*, то не надо даже граф сначала весь получать, там по ходу алгоритма просто надо обходить всех соседей вершинры - в этот момент генерируете новые слова.

[Soft_touch_plastic]

Wataru, не очень в плане производительности, так необходимо перебрать 100 000 слов, вот таким методом, боюсь это будет в не слишком быстрые сроки выполнятся. Это действительно единственный путь, перебор?

[Wataru]

Soft_touch_plastic, Это не перебор. Это поиск кратчайшего пути в графе. Если слов всего 100 000, то можно сразу весь граф построить и гнать там хоть A*, хоть дейкстру.