Cómo definir la distancia de edición entre dos cadenas

El Algoritmo Levenshtein , comúnmente conocida como distancia de edición , es el número mínimo de operaciones de edición necesarias para transformar una cadena de datos , la cadena de origen , en otro, la cadena de destino . Las secuencias de letras o números comprenden cadenas de datos . Operaciones de edición válidos incluyen sustitución, inserción o deleción . Programas como el corrector ortográfico y las herramientas de corrección automática utilizan este algoritmo en su operación. Mientras que el sistema de algoritmo utilizado por las computadoras y teléfonos inteligentes parece desalentador de comprender , el proceso básico de definir una distancia de edición es relativamente simple . Instrucciones
1

escribir o teclear sus dos cadenas en una página lo que la cadena fuentes se alinea directamente encima de la cadena de destino . Por ejemplo :

cat ( cadena de origen ) destino ( cadena de destino )
2

Identificar los puntos de datos en una cadena difiere de la otra. Por ejemplo :

Cat ( cadena de origen ) el destino ( cadena de destino )

Las letras diferentes en el primer punto (C y F ) y la cadena de destino tiene un punto de datos adicional ( E) .
3

Aplicar el menor número de operaciones de edición (inserción , supresión, sustitución) posible cambiar la cadena de origen de la cadena de destino . Cuente las ediciones . Por ejemplo :

Cat - > F sustituto para C y E insert -> Fate

El cambio requiere de dos operaciones de edición , una sustitución y una inserción , y no puede ser completado en menos . Por lo tanto , la distancia de edición entre "cat " y "destino" es dos.