#algorithm #distance #proof #edit-distance #string-algorithm
Вопрос:
(от: https://math.mit.edu/classes/18.417/Slides/alignment.pdf)
На слайде на 11 — й странице рассказывается о том, как Расстояние редактирования и Расстояние выравнивания эквивалентны.
Я понимаю, как доказать, что Расстояние редактирования всегда будет меньше или равно соответствующему расстоянию выравнивания. Мы всегда можем построить последовательность изменений из заданных выравниваний, которая даст тот же результат. Поскольку последовательность изменения расстояния является максимально короткой, соответствующая последовательность по крайней мере такая же длинная.
Я не понимаю, как доказать обратное неравенство. Может ли кто-нибудь предоставить доказательства? Очевидно, для доказательства этого нужно использовать неравенство треугольника.
На аналогичной ноте, есть ли какие-либо ресурсы, которые строго относятся к этой теме? Например, мне нужны доказательства того, почему эти два расстояния удовлетворяют аксиомам метрических пространств.
Комментарии:
1. Их подход заключается в том, что если вы выполняете последовательность операций редактирования, вы получаете правильное выравнивание. И это выравнивание лучше (или то же самое), чем другое выравнивание.
2. Одним из подходов было бы следовать слайду 17 — в нем говорится о традиционном повторении, которое определяет/вычисляет расстояние выравнивания как теорему. Вы можете доказать, что то же самое повторение справедливо и для расстояния редактирования.