Нужен путь преобразования одного слова в другое по шагам, например: емтто - метто - метро. Интуитивно догадываюсь, что это что-то из области расстояния редактирования (Дамерау-Левенштейна, операции перестановки тоже нужны), но не понимаю как переложить матрицу оттуда на изменения слова. Как такие алгоритмы называются?
Asked
Active
Viewed 61 times
2
Kromster
- 13,809
Mod diller
- 97
-
https://ru.stackoverflow.com/a/1276250/179763 ? – tym32167 Mar 04 '22 at 05:41
1 Answers
0
Когда вы рассчитали расстояние редактирования с помощью алгоритма Дамерау-Левенштейна, то получили матрицу, в последней ячейке которой лежит расстояние редактирования.
Вам нужно получить путь, по которому пришли в данную ячейку, а это проще всего делать, по ходу построения матрицы (при определении минимума в текущей ячейке) записывая дополнительную информацию - из какой ячейки пришли в данную, какую операцию использовали
Имея такую информацию (в той же таблице как дополнительные поля, или в дополнительной таблице), раскручиваете путь из последней ячейки к началу и потом инвертируете его.
Что касается названия - специального имени, наверное, нет - алгоритмы восстановления пути
MBo
- 53,555
-
-
@tym32167 Сам по себе вопрос - не дубликат, но ваше решение содержит "бонус" – MBo Mar 04 '22 at 05:54
-