Нужен путь преобразования одного слова в другое по шагам, например: емтто - метто - метро
. Интуитивно догадываюсь, что это что-то из области расстояния редактирования (Дамерау-Левенштейна, операции перестановки тоже нужны), но не понимаю как переложить матрицу оттуда на изменения слова. Как такие алгоритмы называются?
-
ru.stackoverflow.com/a/1276250/179763 ?– tym321674 мар 2022 в 5:41
1 ответ
Когда вы рассчитали расстояние редактирования с помощью алгоритма Дамерау-Левенштейна, то получили матрицу, в последней ячейке которой лежит расстояние редактирования.
Вам нужно получить путь, по которому пришли в данную ячейку, а это проще всего делать, по ходу построения матрицы (при определении минимума в текущей ячейке) записывая дополнительную информацию - из какой ячейки пришли в данную, какую операцию использовали
Имея такую информацию (в той же таблице как дополнительные поля, или в дополнительной таблице), раскручиваете путь из последней ячейки к началу и потом инвертируете его.
Что касается названия - специального имени, наверное, нет - алгоритмы восстановления пути
-
-
@tym32167 Сам по себе вопрос - не дубликат, но ваше решение содержит "бонус"– MBo4 мар 2022 в 5:54
-