Как называются алгоритмы, пошагово показывающие изменение слова?
Нужен путь преобразования одного слова в другое по шагам, например: емтто - метто - метро. Интуитивно догадываюсь, что это что-то из области расстояния редактирования (Дамерау-Левенштейна, операции перестановки тоже нужны), но не понимаю как переложить матрицу оттуда на изменения слова. Как такие алгоритмы называются?
Ответы (1 шт):
Когда вы рассчитали расстояние редактирования с помощью алгоритма Дамерау-Левенштейна, то получили матрицу, в последней ячейке которой лежит расстояние редактирования.
Вам нужно получить путь, по которому пришли в данную ячейку, а это проще всего делать, по ходу построения матрицы (при определении минимума в текущей ячейке) записывая дополнительную информацию - из какой ячейки пришли в данную, какую операцию использовали
Имея такую информацию (в той же таблице как дополнительные поля, или в дополнительной таблице), раскручиваете путь из последней ячейки к началу и потом инвертируете его.
Что касается названия - специального имени, наверное, нет - алгоритмы восстановления пути