"bl@nk@"

DISTANCIA DE EDICIÓN

La distancia de Leveinshtein o también conocida como distancia de edición , es un algoritmo tal que dadas dos cadenas, devuelve un entero que da una idea de la distancia (o parecido) entre ellas.
La definición de distancia es el mínimo número de operaciones que hay que realizar para transformar una cadena en la otra.
Debe su nombre al matemático ruso Vladimir levenshtein .

Este entero se calcula contando las transformaciones que es necesario hacer sobre una de estas cadenas para obtener la otra.

Estas posibles transformaciones son:

Borrado de un carácter
Inserción de un carácter
Substitución de un carácter por otro

APLICACIONES

Algunas aplicaciones en la que se puede usar la distancia de edición son:

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.

ALGORITMO CON UNA IMPLEMETACIÓN

1.-Pide la primer palabra y la ingresa a una variable llamada palabra

2.-Pide la segunda palabra y la ingresa a una variable llamada palabra2

3.-calcula la longitud de cada una de las palabras con la función len() y las agrega ala variable correspondiente long y long2

por ejemplo len(palabra)

la longitud de la palabra perro es de 5

4.-crea la matriz donde se realizara las operaciones necesarias para obtener la distancia

matriz= [[0 for x in xrange(long+1)] for y in xrange(long2+1)]

esto crea eje “x” y asigna el valor de 0 con un rango de long + 1 y

crea el eje “y” y asigna el valor de 0 con un rango de long2+1

5.- se enumeraran las letras de cada palabra, para eso se utilizo lo siguiente

i=1

while i<=long:

matriz[0][i]=i

i=i+1

i=1

while i<=long2:

matriz[i][0]=i

i=i+1

6.- Comienza hacer las operaciones necesarias para obtener la distancia, para recorrer toda la tabla se utilizaron 2 ciclos anidados como que fue el while, al entrar al ciclo se compara letra por letra de las 2 palabras, y se van comparando de 1 en 1, esto lo hace con el siguiente

if(palabra[j-1]==palabra2[i-1]): (se pone “-1” ya que como lo mencione anteriormente la palabra empieza desde la posición 0 )

en el cual si las letras son iguales, busca el número menor en la matriz, una posición menos en “x”, una posición menos en “y”, y una posición menos en “x” y “y”, Esto se realiza con una función que es min(), que esta te regresa el valor menor.

matriz[i][j]=min(matriz[i-1][j-1],matriz[i][j-1],matriz[i-1][j])

si las letras no son iguales hace lo mismo que el paso anterior , nada mas que al número menor le suma un 1

matriz[i][j]=min(matriz[i-1][j-1],matriz[i][j-1],matriz[i-1][j]) + 1

7.- Cuando termina de recorrer toda la tabla y de comparar todas las letras el resultado que buscamos se guardara en la última posición de “x” y “y” .

print "distancia: " +str(matriz[long2][long])

Aqui les dejo la imagen del código

Aquí les dejo un ejemplo de la distancia de edición de dos palabras

¿Cómo lo haremos?
Se le asignan costos a cada una de las transacciones.
Al borrado: 1 costo
A la inserción: 1 costo
A la sustitución:1 costo

Pero esto solo aplica si son las letras son diferentes.

Nos basamos a la siguiente figura

Se sabe que tomaremos el menor costo posible entonces mas adelante explico como se realiza esto.

¿Qué pasa si son iguales?

Cuando son iguales lo que hacemos es sumarle cero.

¿Cómo se hace?

Primero tenemos que tener las palabras:

Las palabras que en esta ocasión vamos a utilizar serán

CAMA

CABEZA

Después tenemos que ubicar las palabras en una tipo matriz como se muestra en la manera siguiente.

 Empezamos a calcular la distancia

 Escogemos la primer letra de cada palabra como se muestra en la imagen con las flechas

Entonces checamos si son iguales o diferentes

Como vimos que son diferentes lo que hacemos es agarrar los cuatro cuadros que se encuentran entre M y C los cuales son los siguientes.

Entonces empezamos a realizar los cálculos de los costos, para ver cual cuesta menos la sustitución, la eliminación o la inserción. Entonces lo hacemos de la siguiente manera aumentándole uno de costo.

Como nos damos cuenta en la imagen anterior lo que hacemos es escoger el costo menor de los tres que se encuentran ahí (1,2,2), escogemos el menor que es 1 y lo insertamos en el cuadro en blanco que nos quedo.

En la siguiente imagen ya se encuentra el número en la tabla.

Así seguimos hasta encontrar calcular todos los costos.

Y así nos queda el resultado

Ahora se marca con rojo el camino más optimo.

¿Por qué es el camino optimo?

En la imagen vemos que es mejor tomar las letras que son iguales y sustituir entre las que son diferentes de ellas.

Aquí se ve donde se insertaron las letras, como pueden ver en la imagen cuando hay una inserción marcamos un cuadro arriba de otro. Así que antes de sustituir m hubo 2 inserciones.