Кто-нибудь знает об алгоритме редактирования расстояния, который учитывает только замены и вставки. Таким образом, в основном это был бы алгоритм Левенштейна без удаления.Изменение алгоритма расстояния редактирования, который отслеживает только замещения и вставки
Вы можете использовать почти такое же решение динамического программирования, которое используется для вычисления нормального расстояния Левенштейна, но без переходов, соответствующих удалениям.
Итак, расстояние Левенштейна вычисляется с помощью 'min (Lev [i-1] [j], Lev [i] [j-1], Lev [i-1] [j-1]) + 1' Когда вы говорите пропустить переход, соответствующий делеции, вы говорите, что удалить Lev [i-1] [j] в отношении повторения, которое соответствует удалению? – kchoi
Это зависит от того, могут ли операции выполняться как по строке, так и по первой. В первом случае да. В последнем случае ничего не нужно менять вообще, потому что удаление из одной строки эквивалентно вставке в другую. – kraskevich
Произнесите алгоритм Расстояние Левенштейна является следующее:
For each i= 1...M
For each j = 1...N
//min(deletion, insertion, match/substitution)
D(i,j) = min(D(i-1,j) + 1, D(i,j-1) + 1, D(i-1,j-1) + (X(i)=Y(j) : 0 ? 2))
та часть, которая подсчитывает делеции должны быть удалены. Оставляя вам:
For each i= 1...M
For each j = 1...N
//min(insertion, match/substitution)
D(i,j) = min(D(i,j-1) + 1, D(i-1,j-1) + (X(i)=Y(j) : 0 ? 2))
Примечание: Этот конкретный алгоритм баллов замещения с 2 точками, а две другие операции (удаление, вставка) как 1 балл. Есть много вариантов, которые оцениваются по-разному.
Каков ваш вопрос? –
Полагаю, мне было интересно, есть ли какие-либо алгоритмы, о которых я никогда не слышал, что я точно объяснял выше. или если вы знаете способ отдельно подсчитать удаления, связанные с редактированием на расстоянии Левенштейна, это также было бы полезно. – kchoi