Comparando cadenas 'no iguales' en SQL: Algoritmo de Levenshtein

Planteando el problema

Como analista de datos (con responsabilidades de un ingeniero de datos), todos los días me encuentro en la necesidad de buscar, comparar, validar y extraer datos provenientes de bases de datos SQL/No-SQL, lo que prácticamente me ha hecho un experto en este lenguaje, sin embargo, siempre me encuentro con un problema más complejo por resolver, como el que trataremos en este pequeño tutorial.

Usualmente, cuando extraemos datos, estos se encontrarán relacionados mediante llaves primarias/foráneas, por lo que relacionarlos entre si es bastante sencillos, por ejemplo: Supongamos una tabla con información de transacciones diarias de una empresa llamada trans_hist, la cual contiene la sucursal de transacción únicamente reflejada con un ID, ya que dicha información (nombre de la sucursal, dirección, información fiscal, etc) se encuentra en otra tabla llamada branches. Si quisiéramos devolver un resumen del total de transacciones por sucursal, bastaría con relacionar ambas tablas y resumirlas mediante una función de agregación, es decir:

SELECT bc.branch_name, COUNT(*) conteo
FROM trans_hist th
LEFT JOIN branches bc on th.branch_id = bc.id
GROUP BY bc.branch_name

En este caso es sumamente sencillo saber a qué sucursal nos referimos cuando resumimos los datos de la tabla de transacciones, ya que hay una relación directa mediante ID’s, pero, ¿Qué pasaría si este no fuera el caso? Imagina que, de pronto, una persona proveniente del equipo de ventas te muestra una lista que hizo en excel con algunos nombres de sucursales, estos con una denominación diferente pero con nombres relativamente parecidos, y quiere obtener exactamente el mismo análisis pero con los nombres que él te proporcionó. ¿Qué podemos hacer en esta situación? Por supuesto, podrías pensar en hacer este ejercicio de forma manual pero, por razones obvias, esta forma de resolver el problema no es para nada escalable. Para este tipo de situaciones, una de las mejores formas que tenemos para comparar cadenas de texto parecidas es mediante el algoritmo de distancia de Levenshtein. La idea tras este algoritmo es bastante sencilla: La distancia de Levenshtein mide la cantidad mínima de operaciones necesarias para transformar la cadena de texto x en la cadena y, esto a partir de las operaciones inserción, eliminación y sustitución. Matemáticamente hablando, la distancia de Levenshtein se puede definir como:

\[ D(i, j) = \begin{cases} \max(i, j) & \text{si } \min(i, j) = 0 \\ D(i-1, j) + 1 & \text{(eliminar un carácter de } s_1 \text{)} \\ D(i, j-1) + 1 & \text{(insertar un carácter en } s_1 \text{)} \\ D(i-1, j-1) + \text{costo} & \text{(sustituir un carácter, si son distintos)} \end{cases} \] Dadas dos cadenas \(s_1\) y \(s_2\), siendo el costo de sustitución:

\[ \text{costo} = \begin{cases} 0 & \text{si } s_1[i] = s_2[j] \\ 1 & \text{si } s_1[i] \neq s_2[j] \end{cases} \]

Lo que, dicho de otra manera, implica que cada operación individual aplicada para poder llegar a la cadena de texto original implicaría sumar una unidad a la distancia de Levenshtein. Lógicamente, un valor de 0 implicaría que ambas cadenas de texto son iguales, siendo que mientras más nos alejemos de ese valor, más diferencias habrá entre ambas cadenas.

Ahora, la pregunta del millón: ¿Cómo aplicamos este algoritmo en SQL? Afortunadamente, en motores como T-SQL de SQL Server o MySQL, podemos aplicar estructuras de control como lo son IF, FOR, WHILE, etc, por lo que podemos utilizar programación funcional para resolver este problema sencillamente. Lo que haremos será declarar una función que, a partir de dos cadenas de texto nos devuelva un valor entero INT. En este caso particular, voy a hacer uso de MySQL para crear esta función, siendo:

CREATE FUNCTION LEVENSHTEIN(s1 VARCHAR(255), s2 VARCHAR(255)) RETURNS INT
DETERMINISTIC
BEGIN
    DECLARE s1_len, s2_len, i, j, cost INT;
    DECLARE v0, v1, temp VARCHAR(256);
    DECLARE c CHAR(1);

    SET s1_len = CHAR_LENGTH(s1);
    SET s2_len = CHAR_LENGTH(s2);

    IF s1_len = 0 THEN RETURN s2_len; END IF;
    IF s2_len = 0 THEN RETURN s1_len; END IF;
    SET v0 = '', v1 = '';
    SET i = 0;
    WHILE i <= s2_len DO
        SET v0 = CONCAT(v0, CHAR(i)); 
        SET i = i + 1;
    END WHILE;

    SET i = 1;
    WHILE i <= s1_len DO
        SET v1 = CONCAT(CHAR(i), REPEAT('0', s2_len));
        SET c = SUBSTRING(s1, i, 1);

        SET j = 1;
        WHILE j <= s2_len DO
            SET cost = IF(c = SUBSTRING(s2, j, 1), 0, 1);
            SET temp = CHAR(
                LEAST(
                    ASCII(SUBSTRING(v0, j + 1, 1)) + 1,
                    ASCII(SUBSTRING(v1, j, 1)) + 1,
                    ASCII(SUBSTRING(v0, j, 1)) + cost
                )
            );

            SET v1 = INSERT(v1, j + 1, 1, temp);
            SET j = j + 1;
        END WHILE;

        SET v0 = v1;
        SET i = i + 1;
    END WHILE;

    RETURN ASCII(SUBSTRING(v1, s2_len + 1, 1));
END

Esta función toma dos cadenas s1 y s2 de hasta 255 caracteres cada una y devuelve un número entero que representa la distancia entre ambas. Las variables a usar son:

s1_len y s2_len: Almacenan la longitud de las cadenas s1 y s2.
i y j: Contadores para los bucles a aplicar sobre las cadenas de texto.
cost para almacenar el costo de sustitución (0 si los caracteres son iguales, 1 si son diferentes).
v0 y v1 como filas de la matriz de distancias utilizadas en el cálculo.
temp como variable temporal para actualizar valores.
c, que almacena un carácter individual de la cadena s1.

A partir de los parámetros anteriores:

Si la longitud de s1 es 0, retorna la longitud de s2 (todas inserciones).
Si la longitud de s2 es 0, retorna la longitud de s1 (todas eliminaciones).
Se llena con valores de 0 a s2_len, representando el costo de convertir una cadena vacía a s2
Se itera sobre los caracteres de s1, creando una nueva fila v1 basada en los valores de v0.
Se calculan los costos de inserción, eliminación y sustitución, eligiendo el mínimo.
La fila v1 reemplaza a v0 para el siguiente cálculo.
Devuelve el último valor de la fila v1, que representa la distancia mínima entre las dos cadenas.

Ya que tenemos creada la función, podemos ponerla en práctica con un ejemplo:

SET @distancia = LEVENSHTEIN('casa', 'caso');
SELECT @distancia

En este caso, la única diferencia entre ambas cadenas es la letra final de esta misma, por lo que únicamente se requiere de un cambio para llegar a la cadena de origen: sustituir el caracter a por o, siendo que el resultado en este caso será 1.

Ahora, regresemos al ejemplo inicial, donde tenemos un resumen de las transacciones por sucursales. Vamos a convertir el query en una CTE para utilizarla más adelante:

WITH resumen as (
  SELECT bc.branch_name, COUNT(*) conteo
  FROM trans_hist th
  LEFT JOIN branches bc on th.branch_id = bc.id
  GROUP BY bc.branch_name
)

Supongamos que la información que nos compartió el equipo de ventas son las siguientes tres sucursales: valle mexico, texcoco, nativitas. Nosotros no sabemos cuál es el equivalente exacto de estas sucursales con el nombre oficial registrado en la base de datos, por lo tanto, para poder relacionar estos nombres podemos hacer uso de un CROSS JOIN que nos una estas tres opciones con todo lo que tengamos en nuestra tabla resumen, utilizando además la función LEVENSHTEIN() para poder saber cuál es la cadena que se aproxima más a cada caso:

WITH resumen as (
  SELECT bc.branch_name, COUNT(*) conteo
  FROM trans_hist th
  LEFT JOIN branches bc on th.branch_id = bc.id
  GROUP BY bc.branch_name
),
  posibles_cadenas AS (
    SELECT 'valle mexico*' AS cadena_nueva
    UNION ALL
    SELECT 'texcoco'
    UNION ALL
    SELECT 'nativitas'
)

SELECT r.branch_name, r.conteo, pc.cadena_nueva, 
       LEVENSHTEIN(r.branch_name,  pc.cadena_nueva) distancia
FROM resumen r
CROSS JOIN posibles_cadenas pc

Ahora que ya hicimos la relación, solamente quedará extraer los nombres no oficiales a partir de los nombres oficiales, haciendo un simple filtrado por grupos:

WITH resumen as (
  SELECT bc.branch_name, COUNT(*) conteo
  FROM trans_hist th
  LEFT JOIN branches bc on th.branch_id = bc.id
  GROUP BY bc.branch_name
),
  posibles_cadenas AS (
    SELECT 'valle mexico*' AS cadena_nueva
    UNION ALL
    SELECT 'texcoco'
    UNION ALL
    SELECT 'nativitas'
),
comparacion as (
  SELECT r.branch_name, r.conteo, pc.cadena_nueva, 
       LEVENSHTEIN(r.branch_name,  pc.cadena_nueva) distancia,
       ROW_NUMBER() OVER (PARTITION BY r.branch_name ORDER BY distancia ASC) min_dist
  FROM resumen r
  CROSS JOIN posibles_cadenas pc
)

SELECT cadena_nueva, conteo
FROM comparacion
WHERE min_dist = 1

¡Y listo! De esta forma obtendremos la cantidad de transacciones de cada sucursal, sin tener que abtener el nombre exacto de cada una de estas sucursales.

Además de este método, podemos encontrar muchos otros algoritmos que nos permitan hacer comparaciones entre cadenas, como lo son: Damerau-Levenshtein, Jaro-Winkler, Hamming, Jaccard, Soundex, N-grams, etc, que pueden variar en cuanto a precisión y velocidad, los cuales cubriré en futuros tutoriales de SQL.

Referencias

[1] Heeringa, W. J. (2004). Measuring dialect pronunciation differences using Levenshtein distance.

[2] Haldar, R., & Mukhopadhyay, D. (2011). Levenshtein distance technique in dictionary lookup methods: An improved approach. arXiv preprint arXiv:1101.1232.

[3] Liu, X., Tao, L., Zhou, Y., Ma, K., & Liu, X. (2014). The Automatic Marking Method of SQL Script Based on Syntax Analysis and Levenshtein, Distance. Software Engineering and Applications, 3, 9-14.

Comparando cadenas ‘no iguales’ en SQL: Algoritmo de Levenshtein

Planteando el problema

Referencias