DISTANCIA DE EDICIÓN

Gerardo Ossio Rodríguez 1454820Yajaira Patricia Ulloa Torres 1464754

DISTANCIA DE EDICIÓN:Es un algoritmo que transforma una cadena dada en

otra.Se basa en tres operaciones, a saber, inserción, borrado

y reemplazamiento.La definición de distancia es el mínimo número de

operaciones que hay que realizar para transformar una cadena en la otra.

Se hace con una técnica informática llamada

PROGRAMACIÓN DINÁMICA.La programación dinámica se usa cuando la solución a

un problema local es parte de la solución global.Esta técnica usa recursividad, aunque se implementa de

manera iterativa por problemas de pila

Algunas aplicaciones en la que se puede usar la distancia de edición 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.

Su nombre se debe al matemático ruso Vladimir

Levenshtein, quien creo este algoritmo en 1965

Este algoritmo utiliza una matriz de tamaño (n + 1) × (m + 1),

donde n y m son las longitudes de los cadenas que se comparan.

EJEMPLO Calcule la distancia de edición de las palabras

algoritmos y computacionales con el algoritmo de programación dinámica, con costo uno para inserción, eliminación y reemplazo (y costo cero para reemplazo con el mismo símbolo). Presente la tabla completa, identifique el costo final

Según las instrucciones el coste para un elemento no igual es de 1.

La tabla quedaría así

Ejemplo

Referencias

http://es.wikipedia.org/wiki/Distancia_de_Levenshtein

ASJP - World Language Tree http://www.fismat.umich.mx/~

karina/tesisMaestria/node40.html