Distancia de Levenshtein
número mínimo de operaciones requeridas para transformar una cadena de caracteres en otra / De Wikipedia, la enciclopedia encyclopedia
Estimado Wikiwand AI, Seamos breves simplemente respondiendo estas preguntas clave:
¿Puede enumerar los principales datos y estadísticas sobre Distancia de Levenshtein?
Resumir este artículo para un niño de 10 años
La distancia de Levenshtein, distancia de edición o distancia entre palabras es el número mínimo de operaciones requeridas para transformar una cadena de caracteres en otra, se usa ampliamente en teoría de la información y ciencias de la computación. Se entiende por operación, bien una inserción, eliminación o la sustitución de un carácter. Esta distancia recibe ese nombre en honor al científico ruso Vladimir Levenshtein, quien se ocupó de esta distancia en 1965. Es útil en programas que determinan cuán similares son dos cadenas de caracteres, como es el caso de los correctores ortográficos.
Por ejemplo, la distancia de Levenshtein entre "casa" y "calle" es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro.
- casa → cala (sustitución de 's' por 'l')
- cala → calla (inserción de 'l' entre 'l' y 'a')
- calla → calle (sustitución de 'a' por 'e')
Se le considera una generalización de la distancia de Hamming, que solo compara cadenas de la misma longitud y solo considera como operación la sustitución. Hay otras generalizaciones de la distancia de Levenshtein, como la distancia de Damerau-Levenshtein, que consideran el intercambio de dos caracteres como una operación.
Como buena "distancia", cumple (aunque es complicado demostrarlo formalmente), que:
Dist(A,B) == Dist(B,A)
Dist(A,B) + Dist(B,C) >= Dist(A,C)