В чем разница между расстоянием Левенштейна и алгоритмом Вагнера-Фишера

Фактически вы сами отвечаете на вопрос в первом абзаце. Во втором абзаце вы их немного смешиваете.

Расстояние Левенштейна - это метрика расстояния редактирования, названная в честь Владимира Левенштейна, который считал это расстояние в 1965 году и не имел к чему делать с "матрицей" динамического программирования. А алгоритм Вагнера – Фишера - это алгоритм динамического программирования, который вычисляет изменение расстояние между двумя строками символов.

Однако расстояние Левенштейна обычно вычисляется с использованием динамического программирования, если вам нужно вычисление общего назначения, то есть вычисление расстояния редактирования между двумя случайными входными строками. Но расстояние Левенштейна также можно использовать в программе проверки орфографии, когда вы сравниваете одну строку со словарем. В подобных случаях обычно очень медленно использовать вычисления общего назначения и что-то вроде Автомат Левенштейна может предоставить линейное время для получения всех вариантов написания. Кстати, это также используется в нечетком поиске в Lucene начиная с версии 4.

Что касается вашей диссертации, я думаю, это зависит от обстоятельств. Если речь идет о фактической метрике Левенштейна, то я думаю, вам следует начать с нее, а если речь идет о динамическом программировании, вам следует начать с Вагнера-Фишера. Во всяком случае, это мои два цента об этом. И удачи вам с диссертацией.

Действительно, они тесно связаны, но это не одно и то же. Расстояние Левенштейна - это понятие, которое определяется математической формулой. Однако попытка вычислить расстояние Левенштейна путем непосредственной реализации рекурсивной формулы будет ужасно медленной. Вагнера-Фишера - это алгоритм динамического программирования для его эффективного вычисления.