Forum programmazione

Qualcuno mi saprebbe dire perchè uno degli algoritmi più conosciuti di calcolo della distanza di levensthein tra due stringhe considera solo inserimenti in coda alla stringa di partenza.

Ad Esempio mi aspetterei che la distanza tra 'Giulo' e Giulio' sia 1 mentre invece l'algoritmo mi da come risultato 2.

Ringrazio in anticipo

Hai implementato male l'algoritmo, in che linguaggio lo hai sviluppato?
Ho fatto in test in php passando le tue stringhe(Giulo,Giulio) e restituisce 1.
Se conosci PHP e vuoi fare altre prove non devi neanche reimplementarti la funzione visto che c'è già , levenshtein.

L' algoritmo l'ho sviluppato in Visual Basic.
Questa è una versione in pseudocodice , mi puoi dire quella che hai tu è la stessa di quella che ho io ?


L’algoritmo per calcolare la distanza di Levensthein `e descritto in figura 2.1.
Prende in input le due stringhe e costruisce una matrice d di (n+1)×(m+1)
interi, dove n `e la lunghezza della stringa s ed m `e la lunghezza della stringa
t, nella posizione d[n+1][m+1] sar`a presente a conclusione dell’algoritmo il
valore della distanza tra le due stringhe.


Levensthein-Distance(s,t)
1 for i à 1 to length(s) + 1
2 do d[i][1] Ã i
3 for j à 1 to length(t) + 1
4 do d[1][j] Ã j
5 for i à 2 to length(s) + 1
6 do for j à 2 to length(t) + 1
7 do if s[i] = t[j]
8 then cost à 0
9 else cost à 1
10 d[i][j] Ã min(d[i − 1][j] + 1, d[i][j − 1] + 1,
d[i − 1][j − 1] + cost)
11 return d[length(s) + 1][length(t) + 1]