En entradas anteriores hemos hablado de la búsqueda fonética que se puede realizar con las funciones nativas de SQL Server. Usando concretamente con el método SOUNDEX. Otro método que es de interés para buscar cadenas de texto con posibles errores es la distancia de Levenshtein. Un método que mide el número de ediciones necesarias para cambiar una cadena por otra. Por eso en esta entrada vamos a ver como implementar la distancia de Levenshtein en SQL Server.
La distancia de Levenshtein en SQL Server
Entre las funciones de SQL Server no existe una implementación de la distancia de Levenshtein en SQL Server, por lo que es necesaria implementarla. Afortunadamente existe una implementación que se puede encontrar en los foros del blog SQLTeam que reproducimos a continuación:
CREATE FUNCTION edit_distance(@s1 nvarchar(3999), @s2 nvarchar(3999)) RETURNS int AS BEGIN DECLARE @s1_len int, @s2_len int DECLARE @i int, @j int, @s1_char nchar, @c int, @c_temp int DECLARE @cv0 varbinary(8000), @cv1 varbinary(8000) SELECT @s1_len = LEN(@s1), @s2_len = LEN(@s2), @cv1 = 0x0000, @j = 1, @i = 1, @c = 0 WHILE @j <= @s2_len SELECT @cv1 = @cv1 + CAST(@j AS binary(2)), @j = @j + 1 WHILE @i <= @s1_len BEGIN SELECT @s1_char = SUBSTRING(@s1, @i, 1), @c = @i, @cv0 = CAST(@i AS binary(2)), @j = 1 WHILE @j <= @s2_len BEGIN SET @c = @c + 1 SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j-1, 2) AS int) + CASE WHEN @s1_char = SUBSTRING(@s2, @j, 1) THEN 0 ELSE 1 END IF @c > @c_temp SET @c = @c_temp SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j+1, 2) AS int)+1 IF @c > @c_temp SET @c = @c_temp SELECT @cv0 = @cv0 + CAST(@c AS binary(2)), @j = @j + 1 END SELECT @cv1 = @cv0, @i = @i + 1 END RETURN @c END
Código que implementa una nueva función llamada edit_distance
que mide el mínimo número de ediciones necesarias para ir de una cadena a otra. Función que se puede emplear para encontrar registros que son similares e incluso ordenarlos en base al número de ediciones.
Comprobación de los resultados
Una vez creada la función en nuestro SQL Server si se ejecuta el siguiente código se puede comprobar como en el primer caso devuelve 0, es la misma cadena, 1 en el segundo caso, se ha agregado el símbolo de admiración y 2 el último, se ha omitido una letra además de agregar el símbolo de admiración.
SELECT dbo.edit_distance('Hola Mundo', 'Hola Mundo'), dbo.edit_distance('Hola Mundo', 'Hola Mundo!'), dbo.edit_distance('Hola Mundo', 'Hola Mudo!')
Implementación en SQL Server
Ahora que sabemos como funciona el código se puede usar este en consultas de SQL Server para buscar cadenas que son similares, pero no iguales. Lo que nos permite buscar cadenas de texto con la posibilidad de tener errores tipográficos tanto en la cadena de búsqueda como en los registros de la base de datos.
SELECT id, first_name, dbo.edit_distance(first_name, 'Arly') FROM MOCK_DATA WHERE dbo.edit_distance(first_name, 'Arly') < 2 ORDER BY dbo.edit_distance(first_name, 'Arly')
Esta consulta en nuestra base de datos nos devolverá además de Arly nombres de usuarios como Karly o Early, ambos con distancia igual a 1.
Conclusiones
En esta entrada hemos visto una función para aplicar la distancia de Levenshtein en SQL Server, algo que nos puede ayudar a mejorar las búsquedas de registros cuando se cometen errores tipográficos. La solución solamente funciona en SQL Server, pero si alguien conoce una implementación similar para otro motor base de datos puede indicarlo en los comentarios.
Luis Tellez dice
Excelente aporte, yo uso soundex y rank