Categorías
Techies

La distancia de Levenshtein

La distancia de Levenshtein nos dice cuál es la similaridad entre dos cadenas de texto, es decir, ¿cuánto se parece la cadena A a la cadena B? Básicamente lo que mide es el numero mínimo de operaciones necesarias para transformar la cadena A en la cadena B. Estas operaciones se limitan a tres: destrucción, inserción y substitución. Cuanto más cerca a cero sea la distancia, más parecidas son las cadenas. Un concepto tan simple y tan potente a su vez. Aliado perfecto en minería de datos o en cualquier sistema de Big Data.

Levenshtein – algoritmo

Pongamos un ejemplo clásico.

Supongamos que recibimos en nuestro sistema un listado de ciudades que debemos validar en nuestra capa de extracción y normalización de datos.

Un usuario puede escribir de forma errónea la ciudad de Barcelna. Nuestro sistema comparará la cadena Barcelna con nuestra base de datos y no la encontrará. Pero sabemos perfectamente que el usuario quería decir Barcelona, ¿verdad?. Entonces, ¿cómo hacemos que nuestro sistema “piense” como nosotros? ¿cómo podemos hacer que sugiera un resultado similar? Aquí podemos hacer uso del algoritmo que calcula la distancia de Levenshtein.

No voy a explicar el algoritmo porque ya está explicado en mil sitios. En sistemas como Oracle (desde la versión 10g) tienen disponibles, de forma predeterminada, una función que calcula esta distancia y que podéis consultar en este enlace. La idea es sencilla, si nuestra ETL no es capaz de encontrar valores exactos, podríamos hacer que al menos seleccione aquel valor que más se le parezca. En nuestra decisión queda indicarlo de alguna manera con un campo indicador

Para MySql podemos crear las siguientes funciones:

DROP FUNCTION IF EXISTS levenshtein;
DELIMITER $$
CREATE FUNCTION levenshtein( s1 text, s2 text) RETURNS int(11)
DETERMINISTIC
BEGIN
DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
DECLARE s1_char CHAR;
DECLARE cv0, cv1 text;
SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0;
IF s1 = s2 THEN
RETURN 0;
ELSEIF s1_len = 0 THEN
RETURN s2_len;
ELSEIF s2_len = 0 THEN
RETURN s1_len;
ELSE
WHILE j <= s2_len DO
SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1;
END WHILE;
WHILE i <= s1_len DO
SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1;
WHILE j <= s2_len DO
SET c = c + 1;
IF s1_char = SUBSTRING(s2, j, 1) THEN
SET cost = 0; ELSE SET cost = 1;
END IF;
SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost;
IF c > c_temp THEN SET c = c_temp; END IF;
SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1;
IF c > c_temp THEN
SET c = c_temp;
END IF;
SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
END WHILE;
SET cv1 = cv0, i = i + 1;
END WHILE;
END IF;
RETURN c;
END;
$$
CREATE FUNCTION levenshtein_ratio( s1 text, s2 text ) RETURNS int(11)
DETERMINISTIC
BEGIN
DECLARE s1_len, s2_len, max_len INT;
SET s1_len = LENGTH(s1), s2_len = LENGTH(s2);
IF s1_len > s2_len THEN
SET max_len = s1_len;
ELSE
SET max_len = s2_len;
END IF;
RETURN ROUND((1 - LEVENSHTEIN(s1, s2) / max_len) * 100);
END;
$$
DELIMITER;

Para nuestro ejemplo contamos con una tabla Ciudades con una sola columna llamada Nombre. En la tabla se han insertado todas las ciudades de España (bien escritas claro). Por otro lado tenemos la palabra a buscar, Barcelna. Si lanzamos la siguiente SELECT tendremos como resultado la palabra más similar. Barcelona.

SELECT Nombre, levenshtein_ratio('Barcelna',Nombre) ratio 
FROM Ciudades
ORDER BY 2 DESC
LIMIT 1

El uso de este algoritmo puede aplicarse en muchas situaciones. Si quereis ver su implementación en otros lenguajes, podéis echar un vistazo a este enlace.

Hala, a dormir.

Hasta pronto.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *