Búsqueda de direcciones duplicadas mediante la métrica de distancia Levenshtein en SQL

Cuando el operador LIKE de SQL es insuficiente o carece de la capacidad de encontrar cadenas que son similares, pero no exactamente iguales, el algoritmo de la distancia Levenshtein es útil.

La métrica de la distancia Levenshtein mide la diferencia entre dos cadenas. Es el número mínimo de ediciones de un solo carácter que se requieren para cambiar una cadena por otra. Las ediciones de un solo carácter pueden ser inserciones, eliminaciones y sustituciones. Por ejemplo, la diferencia entre “books” y “back” es de tres.

• books -> baoks (sustitución de “o”por “a”)
• baoks -> backs (sustituyendo “o” por “c”)
• backs -> back (supresión de la “s”)

Phil Factor escribe sobre la distancia de edición y da una implementación en T-SQL de MS SQL Server para este algoritmo en su post String Comparisons in SQL: Distancia de edición y el algoritmo de Levenshtein.

Otros SGBD ya vienen con una implementación. Por ejemplo, la función LEVENSHTEIN en PostgreSQL, la función EDIT_DISTANCE_SIMILARITY en Oracle, y la EDITDIST3 en SQLite.

La distancia de Levenshtein es útil cuando se trata de identificar una cadena como 931 Main St que es la “misma” que 931 Main Street. Este es un problema común en los sistemas que trabajan con información de los clientes, como los CRM. En este caso, el cálculo de la distancia de Levenshtein y su posterior transformación en un ratio basado en la longitud de la cadena más grande puede dar el porcentaje de similitud entre las dos cadenas. Cada uno debe decidir qué porcentaje es suficiente para determinar que dos direcciones son lo suficientemente similares como para ser consideradas iguales.

Una proporción inferior al 50 % de diferencia ha dado buenos resultados en el pasado.

Obviamente, esta técnica no es solo para las direcciones. Se puede utilizar para encontrar cadenas similares según sea necesario. Los correctores ortográficos utilizan la distancia de Levenshtein para encontrar palabras que sugerir cuando una persona comete una errata. Ispell sugiere palabras con una distancia de edición de 1, por ejemplo.

Un ejemplo en PostgreSQL

Aquí hay una tabla con dos columnas de texto. Cada columna contiene una dirección.

CREATE TABLE Addresses(
	LINE1 text,
    LINE2 text
);

Estos son los registros de muestra. La mayoría de las direcciones de cada fila son iguales para un humano, pero no son iguales al operador LIKE .

INSERT INTO Addresses (LINE1, LINE2)
VALUES ('9128 LEEWARD CIR, INDIANAPOLIS, IN', '9128 Leeward Circle, Indianapolis, IN');

INSERT INTO Addresses (LINE1, LINE2)
VALUES ('101 OCEAN LANE DRIVE, KEY BISCAYNE, FL','101 Ocean Lane Drive Unit 1010, Key Biscayne, FL');

INSERT INTO Addresses (LINE1, LINE2)
VALUES ('9301 EVERGREEN DRIVE, PARMA, OH', '9301 Evergreen Dr, Parma, OH');

INSERT INTO Addresses (LINE1, LINE2)
VALUES ('1817 BERTRAND DR, LAFAYETTE, LA', '2924 Polo Ridge Ct, Charlotte, NC');

INSERT INTO Addresses (LINE1, LINE2)
VALUES ('201 E 87TH ST, NEW YORK, NY', '201 E 87th Street 3E, New York, NY');

INSERT INTO Addresses (LINE1, LINE2)
VALUES ('799 CARRIGAN AVE, OVIEDO, FL', '799 Carrigan Avenue, Oviedo, FL');

INSERT INTO Addresses (LINE1, LINE2
VALUES ('4014 CADDIE DRIVE, ACWORTH, GA', '10617 WEYBRIDGE DR, TAMPA, FL');

Aquí se puede utilizar la función LEVENSHTEIN para calcular un ratio de diferencia y determinar qué direcciones son iguales.

SELECT
	Line1,
	Line2,
	LEVENSHTEIN(UPPER(line1),UPPER(line2)) as distance,
	LEVENSHTEIN(UPPER(line1),UPPER(line2))::decimal / GREATEST(length(line1), length(line2)) AS ratio
FROM Addresses

Por último, se puede utilizar una cláusula “where” (donde) que compruebe un ratio de igualdad inferior a 0,5 para identificar las direcciones que son iguales.

SELECT
	Line1,
	Line2,
	LEVENSHTEIN(UPPER(line1),UPPER(line2)) as distance,
	LEVENSHTEIN(UPPER(line1),UPPER(line2))::decimal / GREATEST(length(line1), length(line2)) AS ratio
FROM Addresses
WHERE LEVENSHTEIN(UPPER(line1),UPPER(line2))::decimal / GREATEST(length(line1), length(line2)) < .5

Este código filtra las dos columnas “where”. 1 y 2 no son iguales (demasiado lejos, según el algoritmo). Arriba, están las filas con una ración superior a 0,5 (es decir, filas 4 y 7).

Vea el ejemplo anterior en este SqlFiddle.

La utilidad del algoritmo de la distancia de Levenshtein queda patente en los ejemplos anteriores como herramienta significativa para discernir las similitudes en los datos. 

Si quiere saber más sobre nuestros servicios en Encora, 

Puntos clave para tener en cuenta 

• Cuando el operador LIKE de SQL es insuficiente o carece de la capacidad de encontrar cadenas que son similares, pero no exactamente iguales, el algoritmo de la distancia Levenshtein es útil.
• La métrica de la distancia Levenshtein mide la diferencia entre dos cadenas. Es el número mínimo de ediciones de un solo carácter que se requieren para cambiar una cadena por otra.
• La distancia de Levenshtein es útil cuando se trata de identificar una cadena como 931 Main St que es la “misma” que 931 Main Street. Este es un problema común en los sistemas que trabajan con información de los clientes, como los CRM.
• Si se calcula la distancia de Levenshtein y se transforma en un cociente basado en la longitud de la cadena más larga, se puede obtener el porcentaje de similitud entre las dos cadenas. Esto permite identificar los duplicados.

Acerca de Encora

En Encora, creamos ventajas competitivas para los clientes asociados a través de la innovación tecnológica acelerada. Estaremos encantados de acompañarlo en su viaje.

Por qué Encora 

• Somos globales: Con más de 20 oficinas y laboratorios de innovación en 12 países, Encora está dispersa por todo el mundo. Como operamos en diferentes zonas horarias, siempre hay alguien dispuesto a ayudarlo.
• Somos un servicio completo: La innovación tecnológica abarca un enorme rango de temas, habilidades y estrategias. Ofrecemos un concepto de servicio completo, cada componente adaptado según sus necesidades, para presentar una solución completa. 
• Nos dedicamos a ello: Nuestro creciente equipo de más de 4.000 programadores, desarrolladores, ingenieros y pensadores estratégicos cualificados y dedicados es la razón por la que Encora se ha convertido en una empresa tecnológica galardonada con una reputación envidiable.
• Tenemos experiencia: Nos asociamos principalmente con empresas tecnológicas de rápido crecimiento que impulsan la innovación y el crecimiento en sus sectores. Nuestro modelo de entrega único, nuestra metodología ágil y nuestra calidad inigualable han contribuido a nuestro crecimiento constante.