Distancia de Levenshtein

4 08 2011

Hoy hemos tenido que enfrentarnos en el trabajo a un problema, bastante típico hoy en día por lo que creo.

En resumidas cuentas, tenemos una entidad donde alojamos las direcciones fiscales/postales asociadas a cada cliente-contrato.
El problema viene cuando nos percatamos que en numerosas ocasiones se han censado varias direcciones para la misma persona, en momentos diferentes, y mira tu por donde, muchas veces es la misma dirección, aunque no el mismo string.
Por ejemplo: “Avenida Caracol” “Avd. Caracol”, etc….
El foco del problema, la entrada manual de datos y la ausencia de un mecanismo de chequeo y alerta previo a la inserción.

Rebuscando entre mis neuronas alertagadas los residuos de criptografía y codificación, recordaba de la existencia de una distancia de Hamming y unos procedimientos basados en dichas distancias para “medir” la diferencia entre claves, entre un código y otro, o dicho de otro modo, en última instancia debía valer algo parecido para cadenas de chars.

Pues si, lo hay.

 

Se le llama Distancia de Levenshtein o distancia de edición al número mínimo de operaciones requeridas para transformar una cadena de caracteres en otra.

Es útil en programas que determinan cuán similares son dos cadenas de caracteres, como es el caso de los correctores de ortografía, el famoso T9 (supongo), etc…


Según wikipedia, 

En Teoría de la información y Ciencias de la Computación se llama Distancia de Levenshtein, distancia de edición, o distancia entre palabras, al número mínimo de operaciones requeridas para transformar una cadena de caracteres en otra. Se entiende por operación, bien una inserción, eliminación o la sustitución de un carácter. Esta distancia recibe ese nombre en honor al científico ruso Vladimir Levenshtein, quien se ocupara de esta distancia en 1965. Es útil en programas que determinan cuán similares son dos cadenas de caracteres, como es el caso de los correctores de ortografía.
Por ejemplo, la distancia de Levenshtein entre “casa” y “calle” es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro.

  1. casa → cala (sustitución de ‘s’ por ‘l’)
  2. cala → calla (inserción de ‘l’ entre ‘l’ y ‘a’)
  3. calla → calle (sustitución de ‘a’ por ‘e’)

Se le considera una generalización de la distancia de Hamming, que se usa para cadenas de la misma longitud y que solo considera como operación la sustitución. Hay otras generalizaciones de la distancia de Levenshtein, como la distancia de Damerau-Levenshtein, que consideran el intercambio de dos caracteres como una operación

El Algoritmo es de tipo bottom-up, común en programación dinámica. Se apoya en el uso de una matriz (n + 1) × (m + 1), donde n y m son las longitudes de los cadenas. Aquí se indica el algoritmo en pseudocódigo para una función LevenshteinDistance que toma dos cadenas, str1 de longitud lenStr1, y str2 de longitud lenStr2, y calcula la distancia Levenshtein entre ellos:

int LevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
// d is a table with lenStr1+1 rows and lenStr2+1 columns
declare int d[0..lenStr1, 0..lenStr2]
// i and j are used to iterate over str1 and str2
declare int i, j, cost

for i from 0 to lenStr1
d[i, 0] := i
for j from 0 to lenStr2
d[0, j] := j

for i from 1 to lenStr1
for j from 1 to lenStr2
if str1[i] = str2[j] then cost := 0
else cost := 1
d[i, j] := minimum(
d[i-1, j] + 1, // deletion
d[i, j-1] + 1, // insertion
d[i-1, j-1] + cost // substitution
)

return d[lenStr1, lenStr2]
 

El invariante mantenido a través del algorítmo es que pueda 
transformar el segmento inicial str1[1..i] en str2[1..j] 
empleando un mínimo de d[i,j] operaciones. 
Al final, el elemento ubicado en la parte INFERIOR derecha de la matriz 
contiene la respuesta.
 
 


 
 

El Ejercicio

Supóngase que tiene un listado de direcciones postales “sucias” y necesita hacer una limpieza de datos, con un diccionario callejero, para determinar la calidad de sus datos:

Dirección sucia Diccionario
YUNGAY YUNGAY
7 JUNIO SIETE DE JUNIO
R SOTOMAYOR RAFAEL SOTOMAYOR
B ENCALADA BLANCO ENCALADA
GRAL VELASQUEZ GENERAL VELASQUEZ
STA MARIA SANTA MARIA
V MACKENNA VICUÑA MACKENNA
SN ANTONIO SAN ANTONIO
A BELLO ANDRES BELLO

Lo primero que uno podría hacer es separar las cadenas de búsqueda, con un split, e ir comparando palabra por palabra, y devolver la media de los resultados máximos obtenidos. No obstante,  podríamos también usar la distancia de Levenshtein y luego hacer un rankig, desde la menor distancia hasta la más alta. Luego, determinar un punto de corte y poder así determinar cuán buenos son nuestros datos:

Dirección sucia Diccionario DL
YUNGAY YUNGAY 0
SN ANTONIO SAN ANTONIO 1
STA MARIA SANTA MARIA 2
GRAL VELASQUEZ GENERAL VELASQUEZ 3
R SOTOMAYOR RAFAEL SOTOMAYOR 5
V MACKENNA VICUÑA MACKENNA 5
A BELLO ANDRES BELLO 5
B ENCALADA BLANCO ENCALADA 6
7 JUNIO SIETE DE JUNIO 13
 
 
 
Finalmente, sacamos una estadística de las semejanzas en la BBDD y pudimos
establecer el corte para la distancia de levenshtein que determinara si 
teníamos o no que considerar 2 direcciones semejantes. 
Eso si, también hemos puesto en marcha un control de entradas para intentar 
paliar la repetición de direcciones. ;)
 
 
 
 
Anuncios

Acciones

Information

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s




A %d blogueros les gusta esto: