Distanza di Levenshtein in T-SQL e VB

Home | SQL Server

Calcolo della distanza fra due parole

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

Implementazione T-SQL per SQL Server

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	
	

Codice Visual Basic

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

Torna alla home page di SQL Server

Home