Алгоритмы. Нахождение расстояния Левенштейна с помощью алгоритма Вагнера-Фишера

Программу данного курса вы можете посмотреть по ссылке - Расстояние Левенштейна (редакционное расстояние, дистанция редактирования) — метрика, измеряющая по модулю разность между двумя строками. Она определяется как минимальное количество односимвольных операций (вставки, удаления, замены), необходимых для превращения одной строки в другую. Находит широкое применение как в редакторской деятельности, так и в геномике. Рекуррентное соотношение для вычисления этой метрики довольно затратно, поэтому на лекции рассмотрим один из более быстрых алгоритмов ее вычисления. Это алгоритм Вагнера — Фишера обладающий простотой реализации и высокой скоростью работы. Реализуем этот алгоритм на Python, Java, Fortran. Ссылка на конспект этой лекции - Ссылка на примеры кода -