La distanza tra due parole, secondo l'algoritmo di Levenshtein non è altro che il grado di similitudine tra queste due parole, viene di fatto calcolata la somiglianza tra parole. A volte si ha a che fare con dati sporchi digitati non correttamente su diverse tabelle proveniente da diversi ambiente ed è difficile riconciliare le informazioni usando solo query con la condizione LIKE.
La funzione che segue, scritta in TSQL per SQL server, ci viene incontro, basandosi sull'algoritmo di Levenshtein, restituisce un numero intero che rappresenta la distanza, ovvero la differenza, tra le due parole. Più il risultato è basso più le parole sono simili, nel caso di due parole uguali l'algortimo restituisce 0.
L'algoritmo di Levenshtein di fatto restituisce il numero minimo di modifiche da applicare alla parola A per trasformarla in un altra B, dove per modifica si intende: la cancellazione di un carattere, la sostituzione di un carattere con un altro, o l'inserimento di un carattere.
Ad esempio il confronto tra i termini casa e cassa o case retituisce valore 1 in quanto c'è un solo carattere di differenza, le parole si somigliano.
Può essere usata nel seguente modo:
select *
from miatabella
where dbo.Levenshtein ('paroladaconfrontare', miatabella.miocampo) < 3
o addirittura
select * from tabella1 join tabella2 on dbo.Levenshtein (tabella1.campo1, tabella2.campo2)
E' evidente che le query vanno fatte con attenzione perchè come si può immaginare la funzione richiede molte risorse. Ho impostato il limite a 30 caratteri, se avete bisogno di confronti con stringhe più lunghe basta modificare leggermente la funzione T-SQL
Il codice che segue è pronto per essere copiato ed incollato nel Query Analyzer ed essere eseguito, crea direttamente la funzione del calcolo della somiglianza dei termini.
create function dbo.Levenshtein (@parola1 varchar(30), @parola2 varchar(30)) returns int as begin declare @distanza int -- La variabile che viene restituita declare @lenparola1 int -- La lunghezza della prima parola declare @lenparola2 int -- la lunghezza della seconda parola -- Calcolo la lunghezza delle due parole set @lenparola1 = len(@parola1) set @lenparola2 = len(@parola2) -- Se la lunghezza di una delle due parole è 0 allora viene restituita la lunghezza dell'altra if @lenparola1 = 0 set @distanza = @lenparola2 else if @lenparola2 = 0 set @distanza = @lenparola1 else begin declare @array_temp table (riga int,colonna int,valore int) -- Creo una tabella temporanea per simulare un array bidimensionale declare @i int declare @j int -- inizializzo la cella (0,0) con il valore 0 insert @array_temp values (0, 0, 0) -- importo i valori della prima riga e della prima colonna a 0 set @i = 1 while @i <= @lenparola1 begin insert @array_temp values (@i, 0, @i) set @i = @i + 1 end set @j = 1 while @j <= @lenparola2 begin insert @array_temp values (0, @j, @j) set @j = @j + 1 end -- Ciclo sulle due parole calcolando la distanza declare @cost int declare @min1 int declare @min2 int declare @min3 int set @i = 1 while @i <= @lenparola1 begin set @j = 1 while @j <= @lenparola2 begin -- Compare the letters and determine @cost -- If they are the same, @cost is 0. If different, -- @cost is 1 if (substring(@parola1, @i, 1) = substring(@parola2, @j, 1)) set @cost = 0 else set @cost = 1 -- Calcolo il minimo tra: -- La cella a sinistra -- Quella in alto -- E quella in alto a sinistra in diagonale select @min1 = [valore] + 1 from @array_temp where riga = @i - 1 and colonna = @j select @min2 = [valore] + 1 from @array_temp where riga = @i and colonna = @j - 1 select @min3 = [valore] + @cost from @array_temp where riga = @i - 1 and colonna = @j - 1 if @min2 < @min1 set @min1 = @min2 if @min3 < @min1 set @min1 = @min3 insert into @array_temp values (@i, @j, @min1) set @j = @j + 1 end set @i = @i + 1 end -- La distanza finale è la cella in basso a destra select @distanza = [valore] from @array_temp where riga = @lenparola1 and colonna = @lenparola2 end -- Restituisco la distanza return @distanza end
Per completare la pagina inserisco anche la codifica Visual Basic della funzione. Prima della vera e propria funzione c'è una procedura che calcola il minimo fra tre elementi.
Function Min3(a As Integer, b As Integer, c As Integer) As Integer
Dim temp As Integer
temp = a
If b < temp Then temp = b
If c < temp Then temp = c
Min3 = temp
End Function
Public Function LevenshteinVB(a As String, b As String) As Integer
Dim d() As Integer
Dim i As Integer, j As Integer
Dim c As Integer
If Len(a) = 0 Then
LevenshteinVB = Len(b)
Exit Function
End If
If Len(b) = 0 Then
LevenshteinVB = Len(a)
Exit Function
End If
ReDim d(0 To Len(a), 0 To Len(b)) As Integer
For i = 0 To Len(a)
d(i, 0) = i
Next i
For j = 0 To Len(b)
d(0, j) = j
Next j
For i = 1 To Len(a)
For j = 1 To Len(b)
If Mid$(a, i, 1) = Mid$(b, j, 1) Then
c = 0
Else
c = 1
End If
d(i, j) = Min3(d(i - 1, j) + 1, d(i, j - 1) + 1, d(i - 1, j - 1) + c)
Next j
Next i
LevenshteinVB = d(Len(a), Len(b))
End Function