Math
Distanza di modifica
Calcola la tabella di Levenshtein e un allineamento ottimale di stringhe.
Da provare
Modifica due stringhe di al massimo dieci caratteri. La tabella di Levenshtein si riempie riga per riga, poi traccia un allineamento ottimo. Inserimenti e cancellazioni costano 1; la sostituzione costa 1 o 2. Distanza −1 significa che la tabella non è finita.
Equazioni del modulo
Equazioni 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 per simboli uguali; altrimenti costo di sostituzione La ricostruzione all'indietro fornisce un allineamento ottimo di inserimento/cancellazione/sostituzione
