Cómo buscar palabras similares en SQL Server usando la distancia de Levenshtein

En una entrada anterior, vimos cómo implementar y utilizar la distancia de Levenshtein en SQL Server para realizar búsquedas aproximadas. Esta técnica permite contar el número de ediciones necesarias (inserciones, eliminaciones o sustituciones) para transformar una cadena de texto en otra. Gracias a esto, pudimos comparar una cadena específica con los valores de una columna y devolver los registros ordenados según la ”similaritud”. Este enfoque funciona bien cuando la comparación es directa, como en el caso de "Jhon" y "John", donde la distancia de edición es 2. Sin embargo, este enfoque no resulta adecuado cuando se trata de buscar palabras similares en SQL Server dentro de frases o cadenas más largas.

Sin embargo, en escenarios del mundo real, los usuarios no siempre introducen una palabra exacta. A menudo, escriben solo una parte de un nombre, una frase o una descripción. Por ejemplo:

• Entrada del usuario: "Jhon"
• Registro en la base de datos: "John Smith"

Aquí, el nombre "John Smith" contiene una palabra similar a la introducida por el usuario ("Jhon"), pero no coincide con toda la cadena. Si usamos nuestra función edit_distance tal como fue implementada, esta comparará "Jhon" con "John Smith" como una única cadena, lo cual produce una distancia de edición artificialmente alta.

Para solucionar este problema, necesitamos un enfoque más refinado: analizar las palabras individuales dentro del campo de texto y buscar coincidencias aproximadas con la palabra proporcionada. Esta es precisamente la estrategia que exploraremos en esta entrada.

En Analytics Lane

Nuevo test de normalidad interactivo en el laboratorio de Analytics Lane

Enfoque propuesto para buscar palabras similares en SQL Server usando Levenshtein

La solución propuesta consiste en descomponer el contenido de los campos de texto en palabras individuales y comparar cada una con el término introducido por el usuario. Empleando para ello la función que fue implementada anteriormente para obtener la distancia de Levenshtein. Luego, con estos resultados, identificaremos las palabras más parecidas y devolveremos los registros más relevantes, priorizando aquellos con mayor similitud.

En resumen, los pasos a seguir serían:

1. Dividir cada campo de texto en palabras individuales.
2. Calcular la distancia de Levenshtein entre cada palabra y el término de búsqueda.
3. Seleccionar los registros donde al menos una palabra tenga una distancia suficientemente pequeña (es decir, sea similar al término buscado).
4. Finalmente, ordenar los resultados en función de la menor distancia obtenida.

Implementación paso a paso del proceso para buscar palabras similares en SQL Server

Aunque SQL Server no cuenta con una función nativa para dividir cadenas en palabras, podemos utilizar funciones como STRING_SPLIT para lograr este objetivo. A continuación, te muestro cómo construir esta solución paso a paso.

Paso 1: Crear una función para dividir el texto en palabras

Primero, necesitamos una función que divida un campo de texto en palabras individuales. SQL Server 2016 y versiones posteriores incluyen la función STRING_SPLIT, que nos permite dividir una cadena usando un delimitador. Como las palabras suelen estar separadas por espacios, podemos usar esta función directamente.

Aquí tienes un ejemplo básico de cómo dividir una cadena en palabras:

SELECT value AS palabra
FROM STRING_SPLIT('John Smith', ' ');

El resultado de esta consulta será:

Paso 2: Comparar cada palabra con la cadena buscada usando Levenshtein

Ahora que podemos dividir los campos en palabras, el siguiente paso es comparar cada palabra individual con el término introducido por el usuario. Para esto, utilizaremos la función edit_distance que creamos en la entrada anterior.

Asumiendo que se tiene una tabla clientes con los campos id y nombre, la siguiente consulta que realiza esta comparación y devuelve los registros ordenados por distancia:

SELECT DISTINCT 
    c.id, 
    c.nombre, 
    MIN(ed.distancia) AS distancia_minima
FROM clientes AS c
CROSS APPLY STRING_SPLIT(c.nombre, ' ') AS s
CROSS APPLY (
    SELECT dbo.edit_distance(s.value, 'Jhon') AS distancia
) AS ed
WHERE ed.distancia <= 3
GROUP BY c.id, c.nombre
ORDER BY distancia_minima ASC;

Donde cada una de las lineas realiza una operación en el proceso:

• STRING_SPLIT(c.nombre, ' '): Divide el campo nombre (por ejemplo, “John Smith”) en palabras individuales.
• CROSS APPLY: Permite aplicar la función STRING_SPLIT a cada fila de la tabla clientes.
• dbo.edit_distance(s.value, 'Jhon'): Calcula la distancia de Levenshtein entre cada palabra (s.value) y el término a buscar (“Jhon”).
• WHERE ed.distancia <= 3: Filtra solo las palabras cuya distancia de edición sea menor o igual a 3 (lo que se puede ajustar según la tolerancia deseada).
• GROUP BY y MIN: Agrupa los resultados por id y nombre y devuelve la distancia más pequeña para cada registro.
• ORDER BY distancia_minima ASC: Ordena los resultados para mostrar primero las coincidencias más cercanas.

Ejemplo de uso: Buscar nombres similares**

Supongamos que tenemos la siguiente tabla clientes:

Si el usuario busca “Jhon”, la consulta anterior devolverá:

Mostrandose primero “John Smith” y “Johan Peterson” porque son los registros que tiene palabras con una distancia de 2 respecto a campos buscado “Jhon”.

Consideraciones sobre el rendimiento

Esta solución es muy flexible, pero puede ser costosa en términos de recursos, especialmente si trabajas con tablas muy grandes. Para optimizar las búsquedas se pueden realizar aplicar algunos trucos como:

• Añadir filtros previos: Por ejemplo, limitar la búsqueda a registros recientes o a un subconjunto específico de la tabla.
• Ajustar la distancia máxima: Reducir el valor del filtro (<= 3) para limitar el número de comparaciones.
• Indexar correctamente: Aunque STRING_SPLIT y Levenshtein no se benefician directamente de índices, asegurarse de tener índices en las columnas relevantes puede mejorar el rendimiento general.

Conclusiones

Combinar la distancia de Levenshtein con la función STRING_SPLIT nos permite buscar palabras similares en SQL Server, identificando palabras individuales que son similares al término buscado. Esto soluciona el problema de las búsquedas inexactas en nombres, frases o descripciones más largas, y mejora significativamente la experiencia del usuario.

Con esta técnica, puedes ofrecer un sistema de búsqueda más inteligente y tolerante a errores tipográficos, lo que resulta especialmente útil en aplicaciones como bases de datos de clientes, sistemas de inventario o motores de búsqueda.

Si implementas esta solución, tus usuarios podrán encontrar “John Smith” incluso si escriben “Jhon” o “Johan”, logrando resultados mucho más precisos y relevantes.

Apéndice: Función reutilizable para encontrar la distancia mínima entre palabras

Para facilitar el proceso descrito anteriormente, es útil encapsular la lógica de comparación en una función reutilizable. Esto mejora la claridad de las consultas y permite aplicar el enfoque en múltiples contextos sin tener que repetir la misma lógica una y otra vez.

A continuación, definimos una función llamada dbo.distancia_minima_entre_palabras que recibe un campo de texto (como un nombre completo) y un término de búsqueda (como "Jhon"), y devuelve la menor distancia de Levenshtein entre el término de búsqueda y cada palabra individual del campo.

Una posible implementación de esta función puede ser la que se muestra a continuación:

CREATE FUNCTION dbo.distancia_minima_entre_palabras
(
    @texto NVARCHAR(MAX),        -- El texto completo (por ejemplo, el nombre completo de un cliente)
    @termino NVARCHAR(100)       -- La palabra a buscar (por ejemplo, 'Jhon')
)
RETURNS INT
AS
BEGIN
    DECLARE @distancia_minima INT;

    -- Tabla temporal para almacenar las distancias de cada palabra
    DECLARE @distancias TABLE (valor NVARCHAR(100), distancia INT);

    -- Insertar las distancias de cada palabra comparada con el término de búsqueda
    INSERT INTO @distancias (valor, distancia)
    SELECT 
        valor,
        dbo.edit_distance(valor, @termino)
    FROM 
        STRING_SPLIT(@texto, ' ');

    -- Obtener la menor distancia encontrada
    SELECT 
        @distancia_minima = MIN(distancia)
    FROM 
        @distancias;

    RETURN @distancia_minima;
END;
GO

Ejemplo de uso

Una vez creada la función, podemos aplicarla directamente sobre una tabla de clientes para buscar aquellos cuyos nombres contienen palabras similares a un término dado, por ejemplo, "Jhon":

SELECT 
    c.id,
    c.nombre,
    dbo.distancia_minima_entre_palabras(c.nombre, 'Jhon') AS distancia_minima
FROM 
    clientes AS c
WHERE 
    dbo.distancia_minima_entre_palabras(c.nombre, 'Jhon') <= 2
ORDER BY 
    distancia_minima;

Este enfoque permite encontrar coincidencias como "John Smith", "Jhonny Depp" o "Jon Snow" sin requerir coincidencias exactas, pero priorizando aquellas que son más parecidas según la distancia de Levenshtein.

Nota: La imagen de este artículo fue generada utilizando un modelo de inteligencia artificial.