Similitud entre cadenas y estandarización de direcciones postales
- Resumen
- Medidas de Semejanza entre
Cadenas - Medida de Levenshtein y
Estandarización de Direcciones - Conclusiones
- Bibliografía
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.
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.
- 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.
[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:
