2

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

1

1 ответ 1

0

Когда вы рассчитали расстояние редактирования с помощью алгоритма Дамерау-Левенштейна, то получили матрицу, в последней ячейке которой лежит расстояние редактирования.

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

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

Что касается названия - специального имени, наверное, нет - алгоритмы восстановления пути

3
  • дубликат? ru.stackoverflow.com/a/1276250/179763
    – tym32167
    4 мар 2022 в 5:41
  • @tym32167 Сам по себе вопрос - не дубликат, но ваше решение содержит "бонус"
    – MBo
    4 мар 2022 в 5:54
  • Ну пущай просто ссылка тогда висит - автор захочет - заглянет
    – tym32167
    4 мар 2022 в 5:58

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.