Distancia de edición de Python

Hoy aprenderemos sobre la distancia de edición en Python. También exploraremos la inserción, eliminación, sustitución e implementación recursiva de la cadena de caracteres.

Editar distancia en Python

La distancia de edición es la cantidad requerida para la transposición de una Cadena a otra Cadena. Esta transposición se realiza por recursión, sustitución, inserción y borrado de los caracteres de una cadena.

El número de eliminaciones, inserciones y reemplazos de caracteres necesarios para convertir una palabra en otra depende de qué tan cerca se hayan editado las dos palabras.

También se trata como la distancia Levenshtein en Python porque no necesita que dos cadenas tengan la misma longitud para comparar; la distancia Levenshtein tiene una influencia significativa.

La distancia Levenshtein es sencilla de comprender intuitivamente. El número total de modificaciones de un solo carácter determina la distancia entre los dos.

La distancia de salida indica cuántas modificaciones se requirieron para que las dos palabras fueran idénticas. Cuanto menor sea la distancia de salida, menos cambios serán necesarios.

Entendamos la distancia de edición utilizando el siguiente código de ejemplo para la implementación de inserción, eliminación, sustitución y recursividad de la cadena de caracteres.

Inserción de la cadena de caracteres

En el siguiente código, se inserta t entre i y n en la máquina de palabras.

Código de ejemplo:

w = "Machine"
w = w[:5] + "t" + w[5:]
print(w)

Producción :

Machitne

Eliminación de la cadena de caracteres

En el siguiente código, la c se elimina entre a y h en la máquina de palabras.

Código de ejemplo:

w = "Machine"
w = w[:2] + w[3:]
print(w)

Producción :

Mahine

Sustitución de la cadena de caracteres

En el siguiente código, c se reemplaza por a entre a y h en la máquina de palabras.

Código de ejemplo:

w = "Machine"
w = w[:2] + "a" + w[3:]
print(w)

Producción :

Maahine

Implementación recursiva de la cadena de caracteres

La distancia de edición entre máquina y aprendizaje es cinco, como se muestra en el resultado a continuación.

Podemos tomar cualquier entrada de cadena del usuario, y la distancia Levenshtein se implementa recursivamente en el siguiente método de Python.

Esta técnica recursiva es ineficiente ya que las distancias de Levenshtein de las subcadenas idénticas se calculan repetidamente.

Código de ejemplo:

w1 = input("Type here for word 1: ")
w2 = input("Type here for word 2: ")

len1 = len(w1)
len2 = len(w2)

a = [[0] * (len2 + 1) for _ in range(len1 + 1)]

for m in range(0, len1 + 1):
    a[m][0] = m

for n in range(0, len2 + 1):
    a[0][n] = n

for m in range(1, len1 + 1):
    for n in range(1, len2 + 1):
        if w1[m - 1] == w2[n - 1]:
            a[m][n] = a[m - 1][n - 1]
        else:
            a[m][n] = min(a[m][n - 1], a[m - 1][n], a[m - 1][n - 1]) + 1
print(a[m][n])

Producción :

Type here for word 1: machine
Type here for word 2: learning
5