Связано ли расстояние Левенштейна с наибольшей общей подпоследовательностью? - PullRequest
Новая
       96

Связано ли расстояние Левенштейна с наибольшей общей подпоследовательностью?

1 голос
/ 06 мая 2020

У меня нет доказательств, но я чувствую, что предположим, что s1 - это строка, которую нужно преобразовать в s2, тогда мы можем сохранить наибольшую общую подпоследовательность в s1 как есть, а расстояние редактирования - это количество элементов, которые нам нужно заменить / удалить / вставить. 

For example : s1 = "adjsjvnejnv"
              s2 = "djpppne"

Здесь LCS - это «djne», теперь нам нужно удалить трехэлементную строку «jnv» справа от «djne», мы можем заменить «sjv» на «ppp "в s1, и мы можем удалить" a "из s1. поэтому общее расстояние редактирования составляет 3 + 3 + 1 = 7.

Идея состоит в том, чтобы заменить или удалить элементы между элементами LCS и добавить или удалить элементы из правой и левой части LCS.

Я не могу это доказать. Может ли кто-нибудь предоставить контрпример или доказательство?

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

1 Ответ

0 голосов
/ 18 июня 2020

Да, это так.
И расстояния Левенштейна, и расстояния LCS являются частью группы расстояний, называемых расстояния редактирования .

  • Расстояние LCS позволяет вставлять и удалять строки.
  • Расстояние Левенштейна позволяет вставлять, удалять и заменять строки.

Оба они могут быть вычислены с использованием алгоритма Вагнера-Фишера (первоначально опубликованного Damerau в 1964 году), который представляет собой алгоритм программирования c Dynami, который вычисляет расстояние редактирования между две строки.
Единственная разница между расстоянием LCS и расстоянием Левенштейна будет тогда сводиться к «функции стоимости» для минимизации, используемой в динамическом c программировании. 1015

...