Comparar (distancia) de dos palabras con T-SQL.

Post: By Marcos Ezquerra, CEO de Fx2

Desde hace alg煤n tiempo se nos ha vuelto bastante necesario comparar que tan cercanos son dos strings (textos o cadenas de caracteres).

En algunos casos es bastante simple, por ej. MARCOS y MARCO se parecen mucho, solo una letra de diferencia. El problema es mas complejo cuando comparamos MARCOS vs MACROS, son las mismas letras, pero dos de ellas cambiadas de lugar.

En realidad, lo que se necesita resolver es que tan cercanas son dos palabras. El caso concreto es la comparaci贸n de matriculas para el producto ViewParking.

  • Distancia聽 (鈥淢ARCOS鈥 , 鈥淢ARCOS鈥) = 0
  • Distancia聽 (鈥淢ARCOS鈥 , 鈥淢ACROS鈥) = 2
  • Distancia (鈥淣CP1940鈥 , 鈥淣CB1940鈥) = 1
  • Distancia (鈥淎AJ779鈥 , 鈥淎AJ7792鈥) = 1
  • Distancia (鈥淎AR8486鈥 , 鈥淎AR886鈥) = 1

En T-SQL exsite la funci贸n SOUNDEX, que ayuda a definir que tan similares suenan dos palabras. Si bien es un modelo de aproximaci贸n no es una soluci贸n buena cuando se trata de cadenas de caracteres alfanum茅ricos.

Lo que se quiere medir es: 鈥渕edir la distancia de una cadena de caracteres en cuantos caracteres necesitamos mover o adicionar para que ambas cadenas sean iguales”.

En el CLR estas funciones est谩n provistas por terceros, pero en T-SQL esto no es tan sencillo.

Un algoritmo que permite definir una medida de distancia es el 鈥Algoritmo de Levenshtein鈥 o 鈥淒istancia de Levenshtein鈥

Desarrollado por Vladimir Levenshtein en 1965, este algoritmo, que algunos vimos durante el pasaje por la Universidad, permite medir la diferencia de edici贸n o distancia entre dos palabras.

Una versi贸n m谩s elaborada es la del algoritmo Damerau-Levenshtein que tiene consideraciones en cuanto a dos caracteres en posiciones invertidas, por ejemplo.

Comparto una implementaci贸n de Levenshtein, que entre otras cosas fue revisada y publicada por el blog de RedGate.

Importante: en esta versi贸n he restringido he restringido el largo del string (cadena) para mejorar el rendimiento, en la versi贸n original soporte NVARCHAR (MAX), pero es bastante m谩s lenta.


CREATE function LEVENSHTEIN ( @SourceString nvarchar(100), @TargetString nvarchar(100) )
–Returns the Levenshtein Distance between @SourceString string and @TargetString
–Translated to TSQL by Joseph Gama
–Updated slightly by Phil Factor
returns int
as
BEGIN
DECLARE @Matrix Nvarchar(4000), @LD int, @TargetStringLength int, @SourceStringLength int,
@ii int, @jj int, @CurrentSourceChar nchar(1), @CurrentTargetChar nchar(1),@Cost int,
@Above int,@AboveAndToLeft int,@ToTheLeft int, @MinimumValueOfCells int
— Step 1: Set n to be the length of s. Set m to be the length of t.
— If n = 0, return m and exit.
— If m = 0, return n and exit.
— Construct a matrix containing 0..m rows and 0..n columns.
if @SourceString is null or @TargetString is null return null
Select @SourceStringLength=LEN(@SourceString),
@TargetStringLength=LEN(@TargetString),
@Matrix=replicate(nchar(0),(@SourceStringLength+1)*(@TargetStringLength+1))
If @SourceStringLength = 0 return @TargetStringLength
If @TargetStringLength = 0 return @SourceStringLength
if (@TargetStringLength+1)*(@SourceStringLength+1)> 4000 return -1
–Step 2: Initialize the first row to 0..n.
— Initialize the first column to 0..m.
SET @ii=0
WHILE @ii<=@SourceStringLength
BEGIN
SET @Matrix=STUFF(@Matrix,@ii+1,1,nchar(@ii))–d(i, 0) = i
SET @ii=@ii+1
END
SET @ii=0
WHILE @ii<=@TargetStringLength
BEGIN
SET @Matrix=STUFF(@Matrix,@ii*(@SourceStringLength+1)+1,1,nchar(@ii))–d(0, j) = j
SET @ii=@ii+1
END
–Step 3 Examine each character of s (i from 1 to n).
SET @ii=1
WHILE @ii<=@SourceStringLength
BEGIN

–Step 4 Examine each character of t (j from 1 to m).
SET @jj=1
WHILE @jj<=@TargetStringLength
BEGIN
–Step 5 and 6
Select
–Set cell d[i,j] of the matrix equal to the minimum of:
–a. The cell immediately above plus 1: d[i-1,j] + 1.
–b. The cell immediately to the left plus 1: d[i,j-1] + 1.
–c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost
@Above=unicode(substring(@Matrix,@jj*(@SourceStringLength+1)+@ii-1+1,1))+1,
@ToTheLeft=unicode(substring(@Matrix,(@jj-1)*(@SourceStringLength+1)+@ii+1,1))+1,
@AboveAndToLeft=unicode(substring(@Matrix,(@jj-1)*(@SourceStringLength+1)+@ii-1+1,1))
+ case when (substring(@SourceString,@ii,1)) = (substring(@TargetString,@jj,1))
then 0 else 1 end–the cost
— If s[i] equals t[j], the cost is 0.
— If s[i] doesn’t equal t[j], the cost is 1.
— now calculate the minimum value of the three
if (@Above < @ToTheLeft) AND (@Above < @AboveAndToLeft)
select @MinimumValueOfCells=@Above
else if (@ToTheLeft < @Above) AND (@ToTheLeft < @AboveAndToLeft)
select @MinimumValueOfCells=@ToTheLeft
else
select @MinimumValueOfCells=@AboveAndToLeft
Select @Matrix=STUFF(@Matrix,
@jj*(@SourceStringLength+1)+@ii+1,1,
nchar(@MinimumValueOfCells)),
@jj=@jj+1
END
SET @ii=@ii+1
END
–Step 7 After iteration steps (3, 4, 5, 6) are complete, distance is found in cell d[n,m]
return unicode(substring(
@Matrix,@SourceStringLength*(@TargetStringLength+1)+@TargetStringLength+1,1
))
END
go