La distancia de Levenshtein es un algoritmo tal que dadas dos cadenas, devuelve un entero que da una idea de la distancia (o parecido) entre ellas. Este entero se calcula contando las transformaciones que es necesario hacer sobre una de estas cadenas para obtener la otra. Estas posibles tranformaciones son:
- Borrado de un carácter.
- Inserción de un carácter.
- Substitución de un carácter por otro.
Por ejemplo, la distancia entre "HOLA" y "TROLA" es 2, ya que hay que hacer 2 operaciones sobre la palabra "HOLA" para obtener "TROLA": substituir la H por una R e insertar una T. Cuanto más corta es la distancia entre las dos cadenas, más parecidas son. Si la distancia es 0, las dos palabras son iguales.
Es útil en programas que determinan cuán similares son dos cadenas de caracteres, como es el caso de los correctores de ortografía. Se le considera una generalización de la distancia de Hamming, que se usa para cadenas de la misma longitud y que solo considera como operación la substitución.
Es útil en programas que determinan cuán similares son dos cadenas de caracteres, como es el caso de los correctores de ortografía. Se le considera una generalización de la distancia de Hamming, que se usa para cadenas de la misma longitud y que solo considera como operación la substitución.
1 comentario:
Si... está buena esta distancia... pero está condicionada por la lógica. Como todo? no, como todo no...
Cristián Antiba
Publicar un comentario