Math
Odległość edycyjna
Oblicz tablicę Levenshteina i optymalne dopasowanie ciągów znaków.
Co wypróbować
Edytuj dwa napisy o długości do dziesięciu znaków. Tablica Levenshteina wypełnia się wierszami, a potem wyznacza optymalne dopasowanie. Wstawienia i usunięcia kosztują 1; zamiana kosztuje 1 lub 2. Odległość −1 oznacza, że tablica jest niedokończona.
Równania modułu
Równania D(i,0)=i; D(0,j)=j D(i,j)=min(D(i−1,j)+1, D(i,j−1)+1, D(i−1,j−1)+c) c=0 dla równych symboli; w przeciwnym razie koszt zamiany Śledzenie wsteczne daje optymalne dopasowanie złożone z wstawień/usunięć/zamian
