Después de una pequeña ausencia y downtime por exceso de pago, continuare con la serie de mini-tutorías de data mining, en esta ocasión veremos el algoritmo jaro-winkler (aplausos por favor).
Este algoritmo es parecido al anterior (distancia Levenshtein), solo que este es mas preciso, con el anterior podíamos tener 3 palabras:
1) Rene
2) Ale
3) Alejandra
Y nos diría que ’rene’ y ‘ale’ son mas parecidas pues a ‘ale’ le faltan menos letras para ser ‘rene’ que para ser ‘alejandra’, con el jaro-winkler no tendremos ese problema, sin mas preámbulo veamos lo que nos interesa, tiene una formula medio rara pero ahí les va, consiste en los siguientes pasos:
1) Calcular cantidad de caracteres en común y guardarlos en ‘m’.
2) Calcular longitud de cadena 1 y 2 y almacenarlas en ‘s1’ y ‘s2’ respectivamente.
3) Calcular el número de transposiciones almacenarlo en ‘t’ y dividirlo entre 2. Las transposiciones son los caracteres que son iguales pero están en diferente orden, ejemplo: paco y paoc, la ‘c’ y la ‘o’ están en las dos palabras solo q en diferente orden ;).
4) Sumar m/s1 + m/s2 + (m-t/m) y el resultado de esto multiplicarlo por 1 / 3 ( uno sobre tres, nada de que .3 ).
5) Y esa será nuestra distancia jaro-winkler.
Veamos una primer implementación (algo ruda) del algoritmo, en la cual se realizara en 2 pasos, el primero para limpiar las cadenas de caracteres extraños y el segundo para realizar el algoritmo.
-- funcion que elimina caracteres no comunes
CREATE FUNCTION [dbo].ufnNormalizarCadena
(
@cadena VARCHAR(MAX)
)
RETURNS VARCHAR(MAX)
AS BEGIN
DECLARE @cadenaNormalizada VARCHAR(MAX)
SET @cadenaNormalizada = @cadena
SET @cadenaNormalizada = REPLACE(@cadenaNormalizada, '.', '')
SET @cadenaNormalizada = REPLACE(@cadenaNormalizada, ',', '')
SET @cadenaNormalizada = REPLACE(@cadenaNormalizada, '-', '')
SET @cadenaNormalizada = REPLACE(@cadenaNormalizada, ';', '')
SET @cadenaNormalizada = REPLACE(@cadenaNormalizada, ':', '')
RETURN @cadenaNormalizada
END
Y ahora lo bueno:
-- funcion que nos regresa la distancia jaro-winkler
CREATE FUNCTION [dbo].[ufnJaroWinkler]
(
@Cadena1 varchar(max),
@Cadena2 varchar(max)
)
RETURNS float
AS BEGIN
Declare @Cadena1Normalizada varchar(max), -- cadena 1 normalizada
@Cadena2Normalizada varchar(max), -- cadena 2 normalizada
@LongitudCadena1 int, -- longitud cadena 1 normalizada
@LongitudCadena2 int -- longitud cadena 2 normalizada
Declare @LongitudTemporal int, -- temporal usado para invertir longitudes de cadenas normalizadas
@LongitudMayor int, -- longitud de la cadena normalizada mas grande
@m int, -- distancia :: (max/2) -1
@i int -- usado para recorrer la primer cadena
Declare @f int,
@z int,
@tr int, -- transposiciones
@a1 varchar(max), -- usado para determinar si el caracter en i es igual en cadena 1 y cadena 2
@a2 varchar(max) -- usado para determinar si el caracter en i es igual en cadena 1 y cadena 2
Declare @CadenasTemporal varchar(max), -- temporal usado para invertir cadenas normalizadas
@wcd float -- .3333 usado para multiplicar al final
Declare @CantidadCaracteresComun float, -- cantidad de caracteres en comun
@DistanciaJaro float -- resultado final
Declare @TablaTemporal1 Table
(
[FID] [int],
[FStatus] [bit] NOT NULL
)
Declare @TablaTemporal2 Table
(
[FID] [int],
[FStatus] [bit] NOT NULL
)
set @tr = 0
Set @CantidadCaracteresComun = 0
Set @DistanciaJaro = 0
-- normalizar cadenas
Set @Cadena1Normalizada = [dbo].ufnNormalizarCadena(@Cadena1)
Set @Cadena2Normalizada = [dbo].ufnNormalizarCadena(@Cadena2)
Set @LongitudCadena1 = LEN(@Cadena1Normalizada)
Set @LongitudCadena2 = LEN(@Cadena2Normalizada)
Set @wcd = 1.0 / 3.0
-- cadena 2 debera ser la mas grande
if @LongitudCadena1 > @LongitudCadena2
begin
set @LongitudTemporal = @LongitudCadena2
set @LongitudCadena2 = @LongitudCadena1
set @LongitudCadena1 = @LongitudTemporal
set @CadenasTemporal = @Cadena1Normalizada
set @Cadena1Normalizada = @Cadena2Normalizada
set @Cadena2Normalizada = @CadenasTemporal
end
set @LongitudMayor = @LongitudCadena2
-- inserta en tabla temporal de la cadena 1 el numero de caracter y un 0
Declare @ContadorI int
Set @ContadorI = 1
while( @ContadorI <= @LongitudCadena1 )
Begin
insert into @TablaTemporal1
values ( @ContadorI, 0 )
Set @ContadorI = @ContadorI + 1
End
-- inserta en tabla temporal de la cadena 2 el numero de caracter y un 0
Set @ContadorI = 1
while( @ContadorI <= @LongitudCadena2 )
Begin
insert into @TablaTemporal2
values ( @ContadorI, 0 )
Set @ContadorI = @ContadorI + 1
End
-- calcula M
Set @ContadorI = 1
Set @m = ROUND(( @LongitudMayor / 2 ) - 1, 1)
set @i = 1
while( @i <= @LongitudCadena1 )
Begin
-- Lee el caracter
Set @a1 = SubString(@Cadena1Normalizada, @i, 1)
-- # iteraciones
if @m >= @i
Begin
set @f = 1
set @z = @i + @m
End
else
Begin
set @f = @i - @m
set @z = @i + @m
End
if @z > @LongitudMayor
Begin
set @z = @LongitudMayor
End
-- si el caracter esta en las dos tablas pone el bit en 1
while( @f <= @z )
Begin
Set @a2 = SubString(@Cadena2Normalizada, @f, 1)
Declare @valStatus bit
Select @valStatus = [FStatus]
from @TablaTemporal2
Where [FID] = @f
if ( ( @a2 = @a1 )
and ( @valStatus = 0 )
)
Begin
Set @CantidadCaracteresComun = @CantidadCaracteresComun + 1 -- incrementamos la cantidad de caracteres en comun
Update @TablaTemporal1
set [FStatus] = 1
Where [FID] = @i
Update @TablaTemporal2
set [FStatus] = 1
Where [FID] = @f
Goto saltar_linea
End
set @f = @f + 1
end
saltar_linea:
set @i = @i + 1
End
set @i = 1
set @z = 1
-- recorremos X y Y hasta encontrar en Y un bit con 1 y luego nos saltamos de renglon,
while( @i <= @LongitudCadena1 )
Begin
Declare @v1Status bit
set @v1Status = 0
Select @v1Status = [FStatus]
from @TablaTemporal1
Where [FID] = @i
if ( @v1Status = 1 )
Begin
while( @z <= @LongitudCadena2 )
Begin
Declare @v2Status bit
set @v2Status = 0
Select @v2Status = [FStatus]
from @TablaTemporal2
Where [FID] = @z
if ( @v2Status = 1 )
Begin
set @z = 1
Set @a1 = SubString(@Cadena1Normalizada, @i, 1)
Set @a2 = SubString(@Cadena2Normalizada, @z, 1)
-- si los caracteres en el ciclo son diferentes sumamos las transposiciones
if ( @a1 <> @a2 )
Begin
set @tr = @tr + 0.5
End
Goto j_loop
End
set @z = @z + 1
End
j_loop:
End
set @i = @i + 1
End
-- calculamos la distancia jaro
if @CantidadCaracteresComun <> 0
begin
Set @DistanciaJaro = @wcd * ( @CantidadCaracteresComun / @LongitudCadena1 + @CantidadCaracteresComun
/ @LongitudCadena2 + ( @CantidadCaracteresComun - @tr )
/ @CantidadCaracteresComun )
end
return @DistanciaJaro
end
Ahora veamos un ejemplo de esto:
-- creamos tablas de prueba
CREATE TABLE #tmp1
(
nombre NVARCHAR(50)
)
CREATE TABLE #tmp2
(
nombre NVARCHAR(50)
)
-- Insertamos valores de ejemplo
INSERT INTO [#tmp1] SELECT ('ale')
INSERT INTO [#tmp1] SELECT ('pancho')
INSERT INTO [#tmp2] SELECT ('rene')
INSERT INTO [#tmp2] SELECT ('alejandra')
INSERT INTO [#tmp2] SELECT ('poncho')
-- ejecutamos la consulta
SELECT * FROM (
SELECT a.nombre NombreA,b.nombre NombreB,dbo.ufnJaroWinkler(a.nombre,b.nombre) AS Distancia
FROM [#tmp1] a CROSS JOIN [#tmp2] b
) cte
ORDER BY Distancia DESC
-- eliminamos evidencia
DROP TABLE #tmp1
DROP TABLE #tmp2
Esto nos regresara lo siguiente:
NombreA NombreB Distancia
pancho poncho 0.888888
ale alejandra 0.777777
ale rene 0.52777725
pancho alejandra 0.518518
pancho rene 0.47222175
ale poncho 0
Si se fijan los 2 mejores resultados son los que si tienen sentido, analizando nuestra fuente de datos podríamos establecer un margen y decir (por ejemplo) superior a .7 es un valor valido, cambiemos un poco nuestra consulta final:
-- ejecutamos la consulta mejorada
SELECT * FROM (
SELECT a.nombre NombreA,b.nombre NombreB,dbo.ufnJaroWinkler(a.nombre,b.nombre) AS Distancia
FROM [#tmp1] a CROSS JOIN [#tmp2] b
) cte
WHERE [Distancia] > 0.7
ORDER BY Distancia DESC
Y ahora solo tendremos los 2 mas parecidos, esto concluye este gran post, espero les guste y les sirva, en el siguiente vamos a hacer un reader de RSS usando SQL Server 2005, hasta la próxima.