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 textocon 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.
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").
Algunas aplicaciones en la que se puede usar la distancia de edicion son:
1.Sistemas para la revisión de faltas ortográficas automatizada en textos.
2.Sistemas de reconocimiento de voz.
3.Sistemas para el análisis de ADN.
4.Sistemas para la detección de plagios.
Aqui esta un pequeño ejemplo: Convertir la palabra gato a perro
Al sustituir, insertar o eliminar vas a agregar un uno a la suma y si es la misma letra en fila y columna no se suma, se queda igual.
Tu al principio en la segunda columna despues de la palabra "gato" donde esta el unico 0 vas a poner hacia abajo la serie del 0 a "n "de uno en uno, n es la cantidad de letras que tiene la palabra, como en la imagen de arriba "gato" tiene 4 letras, se pone en la segunda columna: 0,1,2,3,4.
Despues en la segunda fila abajo de "perro", despues del 0 vas poner otra ves la misma serie empezando de ese cero hasta "n", como "perro" tiene 5 letras se pone 0,1,2,3,4,5.
A continuacion en la columna de la letra "G" y fila "P" como vemos que son letras distintas vamos a tomar el 0 que esta en la celda donde no hay letra en columna y fila y le vamos a sumar un 1, y ponemos en la celda ese 1.
Despues bajamos a la fila "A" pero seguimos en la columna "G", son letras distintas entonces se le va sumar 1 al numero que esta abajo del cero y al lado de la letra "G" que viene siendo 1, entonces lo sumamos y queda 2 que es lo que se pone en la celda.
Despues bajamos a la fila "T" en la misma columna "G", son letras distintas entonces se le va a sumar 1 al numero que esta debajo del 1 que usamos en el paso anterior, es el 2, entonces 2 + 1= 3, el 3 se pone en la interseccion de "T" y "G". Asi sucesivamente sigues estos pasos, hasta que acabes la columna con todas las letras, despues sigue la siguiente columna con todas las letras, pero ahora sumandole los elementos de la columna que acabas de terminar. Por ejemplo estas en la columna "E" y fila "G", son letras distintas entonces le suma 1, tomas el elemento a la derecha del 0 del principio de la tabla, es el 1, entonces 1 + 1= 2, el 2 se pone en la celda "EyG". Asi sigues hasta completar la tabla, pero cuidado cuando tienes la misma letra en fila y columna no se suma nada, se pasa el elemento que esta en la parte superior izquierda de esa intersecion de fila y columna y se pone en esa celda. Por ejemplo en la tabla de arriba tenemos la columna "O" y fila "O", son iguales y por lo tanto no sumas nada, entonces agarras el numero en la parte superior izquierda de esa celda, viene siendo el 4, entonces se pasa ese mismo 4 a la celda que en esta tabla es la celda final. Tomas el valor de esa celda final de la tabla como el numero de la distancia de edicion que hay entre estas cadenas de caracteres, esta marcado en verde.
Necesitas 4 transformaciones para convertir de gato a perro. Entiendase por transformaciones las sustituciones, inserciones y eliminaciones de caracteres.
Bibliografia:
http://es.wikipedia.org/wiki/Distancia_de_Levenshtein
http://www.monografias.com/trabajos34/similitud/similitud.shtml
Nombre: Juan Manuel Casanova Villarreal
Matricula: 1453829
3 comentarios:
El resultado de este problema es 15, bueno almenos es lo que a mi me salio, si si estoy en lo correcto, por que te equivocaste tu, con todo respeto claro, tal ves yo estoy mal, y si lo estoy, cual seria mi error?
Si estas bien, vimos en las asesorias del dia de ayer que el resultado es 15, es que yo habia creido que habia entendido perfectamente el algoritmo pero parece que no, me podrias explicar como corregir la distancia de edicion del algoritmo de la imagen de arriba?, es que todavia no entiendo muy bien como es todo eso del costo de insertar, eliminar caracteres.
Bueno pues decidi eliminar el ejemplo del blog que venia en el examen ordinario de calcular la distancia de edicion de "algoritmos" y "computacionales" porque tenia errores la tabla, busque en muchas paginas de internet pero en ninguna venia un metodo para resolver este problema, y pues como dije en el comentario anterior nose como hacer problemas con palabras muy grandes. Pues como dijo la doctora no es bueno decir mentiras en internet sobre algo, porque todo el mundo va a creer lo que estas publicando solo porque esta en internet y eso no es bueno, por eso decidi eliminarlo.
Publicar un comentario