Truco SQL: La distancia de Levenshtein en SQL Server

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.

En Analytics Lane

Nuevo simulador FIRE en el laboratorio de aplicaciones de Analytics Lane

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.