TSQL: Funzione di Levenshtein per analizzare la similitudine fra stringhe

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.

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
    -- Compara i caratteri e determina il @cost
    -- Se sono uguali @cost = 0.

-- Se diversi @cost = 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 

Possiamo ad esempio utilizzarla:

select * 
from miatabella 
where dbo.Levenshtein ('paroladaconfrontare', miatabella.miocampo) < 3

N.B.: Questa funzione è stata presa in rete e non scritta da me 

P.S. la versione Enterprise di SQL Server 2008 R2 comprende i

 Master Data services

che includono questa ed altre funzioni di Fuzzy lookup.