Similitud entre cadenas y estandarización de direcciones postales

Resumen

Existen diversas métricas para medir la distancia o similitud entre dos cadenas. De ellas son muy conocidas la "Distancia de Hamming" y la "Distancia Levenshtein". Esta última tiene múltiples aplicaciones sobre todo en los últimos años, debido al auge que han tomado los problemas de procesamiento de textos y del lenguaje natural. Como subconjunto de este problema y en el cual también existe aplicación de las medidas de semejanza entre cadenas, se encuentra el procesamiento de direcciones postales, el cual tiene vital importancia para las empresas cuya credibilidad y profesionalidad dependen altamente de la información de sus clientes.

Palabras Clave: Distancia Levenshtein, Distancia Hamming, Semejanza entre cadenas, Estandarización de Direcciones.

Introducción

La distancia o medida de similitud entre dos cadenas es ampliamente utilizada para solucionar diversos problemas. Existen diferentes métricas de este tipo ya definidas como son la "Distancia de Hamming" [1] y la "Distancia Levenshtein" [1]. Esta última es usada frecuentemente en correctores ortográficos para sugerir palabras, almacenadas en un fichero o diccionario del sistema, que se asemejan a la detectada con problemas ortográficos según una medida de similitud entre cadenas.

Esta misma idea puede ser útil en el procesamiento de direcciones postales que se quieren etiquetar o estandarizar para una mejor explotación de la información que en sí llevan.

En este trabajo se ofrece una breve descripción de las medidas antes mencionadas a través de ejemplos, se mencionan sus posibles aplicaciones y más puntualmente la utilización de la distancia de Levenshtein durante el proceso de estandarización de direcciones postales que serán llevadas a un almacén de datos.

Medidas de Semejanza entre Cadenas

Es usual hablar de distancia o diferencias entre objetos, es por ello que no resulta extraño el término distancia o medida de similitud entre dos cadenas.

Al hablar de distancia entre cadenas se estaría hablando de medir las diferencias que hay entre estas. Algunas de las diferencias interesantes podrían ser encontradas en las longitudes de las cadenas que se están comparando, o, en palabras de una misma longitud los cambios de unas letras por otras.

Esta métrica ha sido utilizada en la solución de diversos problemas, sobre todo en los de procesamiento de textos o del lenguaje natural.

Los procesadores de textos de última generación son capaces de sugerir posibles palabras que pueden servir de reemplazo para una palabra encontrada en un texto con errores ortográficos. Estos procesadores saben cómo evaluar la distancia entre una palabra mal escrita y palabras que ya se encuentran almacenadas en sus ficheros o diccionarios; aquellas palabras cuyas distancias evaluadas son la más pequeñas, son ofrecidas como candidatas para el reemplazo.

Existen diferentes medidas de distancia entre dos cadenas ya definidas. Una de ellas es la "Distancia de Hamming" (DH) [1], la cual es definida solo para cadenas que tengan la misma longitud. Esto quiere decir que para dos cadenas de igual longitud "x" y "z", DH(x, z) es el número de lugares en los cuales dos cadenas se diferencian.

Por ejemplo:

Si x="casa" y z="caza", entonces DH (x, y) = 1, porque la palabra "z"se diferencia en un carácter ( s/z ) de la palabra "x".

Otra medida de distancia o de similitud entre dos cadenas ampliamente utilizada es la "Distancia Levenshtein" (DL) [2]. Esta es un poco más elaborada que la de Hamming, pues no solo es aplicable a cadenas de la misma longitud, sino que toma en cuenta otros factores.

La "Distancia Levenshtein" o "Distancia de Edición", como también se le conoce a esta métrica, es el número de eliminaciones, inserciones o sustituciones requeridas para transformar una cadena fuente "x" en una cadena objetivo "z".

Por ejemplo:

Si x = "mesa" y z = "mesa", entonces DL (x,z) = 0, porque no es necesario hacer ninguna transformación. Las cadenas fuente y objetivo son idénticas.
Si x = "enojo" y z = "enajo", entonces DL (x,z) = 1, porque es necesaria una transformación para que la cadena fuente y objetivo sean iguales (cambiar la "o" por la "a").
Si x = "enojo" y z = "enojar", entonces DL (x,z) = 2, porque son necesarias dos transformaciones para que la cadena fuente y objetivo sean iguales (insertar la "r" al final de la palabra fuente y cambiar la "o" por la "a").

De lo expuesto anteriormente tenemos que, mientras mayor es el valor de la DL, mayor diferencia hay entre las cadenas analizadas.

La Distancia Levenshtein toma este nombre del científico ruso Vladimir Levenshtein, quien ideó el algoritmo en 1965 [4]. Desde entonces y mayormente en la actualidad, este algoritmo ha sido utilizado en el desarrollo de varias aplicaciones, tales como:

Sistemas para la revisión de faltas ortográficas automatizada en textos.
Sistemas de reconocimiento de voz.
Sistemas para el análisis de ADN.
Sistemas para la detección de plagios.

En los sistemas para la revisión de faltas ortográficas automatizada si el texto contiene una palabra "p", que no está en el diccionario, una palabra semejante o cercana (alguna con una distancia de edición pequeña), puede ser sugerida como la corrección de la palabra "p".

Los errores de transposición son comunes en la escritura de textos. Una transposición puede ser tratada como una eliminación, una inserción o un cambio de letra. [2]

En los sistemas de reconocimiento de voz se emplea, por ejemplo, para encontrar la pareja más cercana entre una expresión y otra que se encuentra en una biblioteca de expresiones ya clasificadas. [2]

Por otra parte, en los sistemas de análisis de ADN la distancia de edición da una indicación de cuán cercanas están dos cadenas. Medidas semejantes son usadas para calcular la distancia entre secuencias de ADN (cadenas sobre el alfabeto {A, C, G, T}, o secuencia de proteínas sobre el alfabeto de 20 aminoácidos), para varios propósitos:

para encontrar genes o proteínas que puedan tener funciones o propiedades compartidas.
para inferir relaciones de familia y árboles evolutivos sobre diferentes organismos.

Medida de Levenshtein y Estandarización de Direcciones

Ya se vio que era posible utilizar la Distancia de Levenshtein para sugerir posibles palabras que pueden servir de reemplazo para una palabra encontrada con errores ortográficos. En un final lo que ocurre es que, el corrector ortográfico al detectar la palabra con error hace una búsqueda automática en los diccionarios asociados a este donde busca las palabras con mayor similitud para luego ser mostradas como posibles candidatas de reemplazo.

Esta misma idea puede ser utilizada dentro del proceso de limpieza de datos de un almacén de datos al cual se quiere llevar un conjunto de direcciones de forma estandarizada para hacer un uso más efectivo de estas [3].

Para lograr estandarizar direcciones lo primero es separarlas en las partes que la conforman. Una de las formas posibles de separar una dirección en sus partes es analizándola palabra a palabra y determinando a qué parte de dirección pertenece cada una de ellas.

Por ejemplo, dada la siguiente dirección:

Esta dirección podría ser separada en los siguientes elementos:

Este proceso, en otras palabras, sería el de etiquetar cada palabra o conjunto de palabras de la dirección dada con la parte de dirección o etiqueta correcta. Una forma de llevar a cabo esta tarea de forma automatizada es definiendo un autómata para analizar las direcciones, de forma que los nodos de dicho autómata son las partes ya definidas en las que se desea separar la dirección (Calle, Entre Calle, Número de Casa, Reparto, etc.), y los arcos de un estado a otro están asociados a una probabilidad de transición [5] (Ver Fig.1)

Fig. 1 Ejemplo de posible autómata para analizar direcciones

Si además se tiene asociado a cada nodo un diccionario, formado por palabras de ejemplo del tipo del nodo al que está asociado, del cual se seleccionan elementos para comprobar la pertenencia o no al nodo en cuestión, se necesitaría entonces una medida de similitud para poder reducir las posibles fallas de selección por causa de errores ortográficos en las palabras que conforman la dirección.

Utilizando, por ejemplo, como medida de semejanza entre dos cadenas la Distancia de Levenshtein con valor de selección igual a "1", si se tiene en el diccionario asociado al nodo "Calle Principal" el nombre de calle "Porvenir", se seleccionaría correctamente en el nodo "Calle Principal" la palabra "Porveniw" que aparece escrita en la dirección con errores ortográficos, ya que la DL (Porveniw, Porvenir)=1 debido a que solo hay que hacer una transformación para convertir la palabra fuente en la palabra objetivo.

Por supuesto que este proceso podría tener variaciones tales como, la medida de distancia para llevar a cabo la selección, que podría ser definida por el usuario que estuviera llevando a cabo el proceso de etiquetar las direcciones en sus partes; así como la decisión de corregir o no la palabra escrita con errores en la dirección.

El modelo anteriormente mostrado sin muchos detalles es una de las aplicaciones de los modelos ocultos de Markov [5], los cuales se han hecho muy populares en el campo del procesamiento del lenguaje natural. Su simplicidad hace que los procesadores obtenidos sean bastante eficientes, y su carácter probabilístico permite que los modelos aprendan de manera automática a partir de conjuntos de ejemplos.

De modo que utilizando este modelo unido a una buena medida de semejanza entre cadenas, como la distancia de Levenshtein, se obtiene una herramienta útil y de gran ayuda para el proceso de estandarizar y etiquetar direcciones postales.

Conclusiones

La distancia o medida de similitud entre dos cadenas es ampliamente utilizada para solucionar diversos problemas.
Existen varias medidas de similitud entre cadenas ya definidas, tales como la "Distancia de Hamming" y la "Distancia Levenshtein", esta última muy utilizada para resolver problemas en el campo del procesamiento de textos y del lenguaje natural.
La distancia de Levenshtein en unión con los modelos ocultos de Markov pueden ser usados durante el proceso de estandarización de direcciones postales.

Bibliografía

[1] A. Bogomolny (Feb/2006) – Distance between strings, http://www.cut-the-knot.org/do_you_know/Strings

[2] L. Allison (Feb/2006) – Dynamic Programming Algorithm (DPA) for Edit-Distance,

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/

[3] L. Padrón (Feb/2006) – Almacenes de Datos: Importancia de la estandarización de las direcciones para las empresas de hoy en día, http://www.ilustrados.com/publicaciones/EEFAAVpAEAMsuJmGDv.php

[4] M. Gilleland (Feb/2006) – Levenshtein Distance, in Three Flavors, http://www.merriampark.com/ld.htm#WHATIS

[5] V. Borkar, K. Deshmukhy, S. Sarawagiz – Automatic segmentation of text into structured records, http://www.cs.washington.edu/homes/kd/papers/sigmod01.pdf

DATOS DE LA AUTORA

Liudmila Padrón Torres

Profesión: Especialista Informática. Graduada en Licenciatura en Ciencias de la Computación. Actualmente cursando Maestría en Ciencias de la Computación.

Entidad donde trabaja: Empresa de Telecomunicaciones de Cuba S.A (ETECSA V.C.)

Fecha de realización del trabajo: 04/03/2006

Categorías del Trabajo: ComputaciónGeneral

Foto: