Distancia de Levenshtein

Carta Común · N.º 207848

La distancia de Levenshtein es una métrica que cuantifica la diferencia entre dos cadenas de caracteres o, de forma más general, entre dos secuencias finitas de símbolos. En su definición clásica, corresponde al número mínimo de operaciones de inserción, eliminación y sustitución de un único símbolo necesarias para transformar una secuencia en la otra, asignando coste 1 a cada operación.​ Recibe su nombre del matemático soviético Vladimir Levenshtein, que introdujo esta distancia en 1965 en el contexto de los códigos capaces de corregir errores de inserción y eliminación.​ La distancia de Levenshtein es una forma clásica de distancia de edición. Este último término también se emplea en sentido más amplio para modelos en los que cambia el conjunto de operaciones permitidas o el coste asignado a cada una de ellas.​ Se utiliza, entre otros ámbitos, en la corrección ortográfica, la búsqueda aproximada, el análisis lingüístico, el reconocimiento del habla, el cotejo de registros y la comparación…

Leer en Wikipedia