• Saltar al contenido principal
  • Skip to secondary menu
  • Saltar a la barra lateral principal
  • Saltar al pie de página
  • Inicio
  • Secciones
    • Ciencia de datos
    • Criptografía
    • Herramientas
    • Machine Learning
    • Noticias
    • Opinión
    • Productividad
    • Programación
      • JavaScript
      • Julia
      • Matlab
      • Python
      • R
  • Programación
    • JavaScript
    • Julia
    • Matlab
    • Python
    • R
  • Noticias
  • Boletín
  • Contacto
  • Tienda
    • Libros
    • Equipamiento de oficina
    • Equipamiento en movilidad
    • Tiendas afiliadas
      • AliExpress
      • Amazon
      • Banggood
      • GeekBuying
      • Lenovo

Analytics Lane

Ciencia e ingeniería de datos aplicada

  • Ciencia de datos
  • Machine Learning
  • Python
  • Pandas
  • NumPy
  • Matlab
  • Julia
  • JavaScript
  • Excel

La distancia de Levenshtein

junio 17, 2020 Por Daniel Rodríguez Deja un comentario
Tiempo de lectura: 4 minutos

Un problema con el que podemos enfrentarnos de forma relativamente habitual es medir el grado de similitud de dos registros. Cuando los registros con los que trabajamos contienen valores numéricos una de las primeras opciones es la distancia euclídea. Pero cuando trabajamos con cadenas de texto deberemos usar otros algoritmos como puede ser el caso de la distancia de Levenshtein. Una distancia que lleva el nombre de Vladimir Levenshtein, quien definió la distancia en 1965.

La distancia de Levenshtein

En primer podemos definir informalmente la distancia de Levenshtein entre dos cadenas de caracteres como el número mínimo de ediciones (es decir, inserciones, eliminaciones o sustituciones) de un solo carácter que son necesarias para para cambiar una cadena por otra.

Matemáticamente, la distancia de Levenshtein entre dos cadenas de caracteres a y b, cuya longitud son respectivamente |a| y |b|, se puede expresar como lev_{a,b}(|a|,|b|) donde

lev_{a,b}(i,j)=\left\{\begin{matrix} max(i,j) & si \, \min(i,j)= 0, \\ \min \left\{\begin{matrix} lev_{a,b}(i-1,j) + 1 \\ lev_{a,b}(i,j-1) + 1 \\ lev_{a,b}(i-1,j-1) + 1_{a_i \ne b_j} \end{matrix}\right.& si \, min(i,j) \ne 0 \end{matrix}\right.

En esta expresión 1_{a_i \ne b_j} denota una función que devuelve 0 cuando las los cadenas de caracteres, a_i y b_i, son iguales y 1 en caso contrario, es decir son diferentes. Por otro lado, nótese que la función lev_{a,b}(i, j) es la distancia entre los primeros i caracteres de la cadena a y los j primeros de la cadena b.

En la función mínimo de la expresión cada una de las líneas miden una de las tres posibles transformaciones. La primera fila representa la eliminación de un carácter en la cadena a, la segunda fila corresponde a la inhesión de un carácter y la tercera fila corresponde a la sustitución.

Publicidad


Ejemplo

Posiblemente como mejor se puede entender la distancia de Levenshtein es mediante un ejemplo. Para lo que se puede usar la definición informal: el número mínimo de ediciones de un solo carácter requeridas para cambiar una cadena de caracteres por la otra. A sí se puede ver fácilmente que la distancia entre las cadenas “cama” y “cana” es 1, ya que solamente se tiene que reemplazar un carácter por otro el “m” por un “n”.

Otro ejemplo fácil de calcular es la distancia entre “cama” y “calle”, la que es de 3. En este caso solamente es necesario realizar tres ediciones para convertir una cadena en otra. Esto es cambiar “m” por “l” (“cala”), insertar una “l” (“calla”) y, finalmente, cambiar la segunda “a” por una “e”.

Nótese que en caso cambiar un carácter por el mismo en mayúscula es una sustitución. Por lo que habitualmente se suele convertir las cadenas a minúsculas (o mayúsculas) antes de aplicar el algoritmo.

Aplicaciones

Las aplicaciones de este algoritmo, al igual que otras métricas para cadenas de texto, son amplias. Por ejemplo, los correctores ortográficos o el reconocimiento óptico de caracteres. Ya que permite identificar la palabra de un diccionario que más se aproxima a la que se ha escrito o identificado, permitiendo así sustituir una por otra.

Generalmente la distancia de Levenshtein se utiliza para medir la distancia entre cadenas cortas, ya que el coste computacional crece rápidamente con la longitud de estas.

Publicidad


Implementación de la distancia de Levenshtein

A continuación, se muestra cómo se puede implementar en R este algoritmo.

levenshtein_distance <- function(str_1, str_2) {
  str_1 <- tolower(str_1)
  str_2 <- tolower(str_2)

  if (str_length(str_1) == 0 || str_length(str_2) == 0) {
    return(max(str_length(str_1), str_length(str_2)))
  }

  previous_row <- 0:str_length(str_2);

  for (i in 1:str_length(str_1)) {
    current_row    <- rep(0, str_length(str_2))
    current_row[1] <- i

    for (j in 1:str_length(str_2)) {
      insertions         <- previous_row[j + 1] + 1
      deletions          <- current_row[j] + 1
      substitutions      <- previous_row[j] + (str_sub(str_1, i, i) != str_sub(str_2, j, j))
      current_row[j + 1] <- min(insertions, deletions, substitutions)
    }

    previous_row <- current_row
  }

  return(current_row[length(current_row)])
}

En el código en primer lugar, se comprueba si alguna cadena es vacía, lo que nos indica que la distancia es igual a la longitud de la cadena más larga. Esto es, el coste de escribir la cadena o borrarla. Posteriormente se itera sobre las dos cadenas comprobando cuales son las transformaciones necesarias para convertir una cadena en otra.

Similitud

Levenshtein cuenta el número de ediciones (inserciones, eliminaciones o sustituciones) necesarias para convertir una cadena en otra. Siendo el resultado un número entero. Lo que representa un problema, ya que el número de errores que se pueden esperar en una cadena es proporcional a la longitud de esta. Un problema que se puede solucionar normalizando la distancia para obtener el grado de similitud

1 - (lev_{a,b}(|a|,|b|) / max(|a|,|b|))

Un valor que se encuentra entre 1, las cadenas son iguales, y 0, las cadenas son completamente diferentes. Independientemente de la longitud de las cadenas comparadas.

La fórmula de la similitud de levenshtein se puede implementar fácilmente una vez tenemos ya implementada la distancia.

Publicidad


levenshtein <- function(str_1, str_2) {
  distance   <- levenshtein_distance(str_1, str_2)
  similarity <- 1 - distance / max(str_length(str_1), str_length(str_2))
  return(similarity)
}

Conclusiones

En esta entrada se ha visto una distancia para medir la distancia entre dos cadenas de caracteres. Algo que es útil ya que cada vez es más habitual trabajar con tipos de datos no solamente numéricos.

Imagen de Markus Spiske en Pixabay

¿Te ha parecido de utilidad el contenido?

¡Puntúalo entre una y cinco estrellas!

Puntuación promedio 4.7 / 5. Votos emitidos: 3

Ya que has encontrado útil este contenido...

¡Síguenos en redes sociales!

¡Siento que este contenido no te haya sido útil!

¡Déjame mejorar este contenido!

Dime, ¿cómo puedo mejorar este contenido?

Publicaciones relacionadas

  • KL-UCB para un problema Bandido Multibrazo (Multi-Armed Bandit)
    KL-UCB para un problema Bandido Multibrazo (Multi-Armed…
  • Cuatro aplicaciones de la Inteligencia Artificial en Transporte y Logística
    Cuatro aplicaciones de la Inteligencia Artificial en…
  • Aprendizaje Automático
    ¿Qué es el Aprendizaje Automático?
  • Diferentes modelos de aprendizaje no supervisado
    Diferentes modelos de aprendizaje no supervisado
  • Distancias
    Distancias y métricas en aprendizaje automático
  • Cómo funciona k-modes e implementación en Python
    Cómo funciona k-modes e implementación en Python

Publicado en: Ciencia de datos, R

Interacciones con los lectores

Deja una respuesta Cancelar la respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

I accept the Terms and Conditions and the Privacy Policy

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

Publicidad




Barra lateral principal

Suscríbete a nuestro boletín

Suscríbete al boletín semanal para estar al día de todas las publicaciones.

Política de Privacidad

Analytics Lane en redes sociales

  • Amazon
  • Facebook
  • GitHub
  • Instagram
  • Pinterest
  • RSS
  • Twitter
  • Tumblr
  • YouTube

Publicidad

Entradas recientes

El método de Hare-Niemeyer y su implementación en Python

septiembre 29, 2023 Por Daniel Rodríguez

Redimensionar una partición de disco LVM con espacio no asignado en Linux

septiembre 27, 2023 Por Daniel Rodríguez

¿Cómo saber la versión de Pandas o cualquier otra librería en Python?

septiembre 25, 2023 Por Daniel Rodríguez

Publicidad

Es tendencia

  • ¿Cómo cambiar el nombre de las columnas en Pandas? publicado el mayo 6, 2019 | en Python
  • Seleccionar filas y columnas en Pandas con iloc y loc publicado el junio 21, 2019 | en Python
  • pandas Pandas: Cambiar los tipos de datos en los DataFrames publicado el julio 15, 2021 | en Python
  • Numpy básico: valores mínimos y máximos en arrays Numpy publicado el octubre 23, 2019 | en Python
  • Unir y combinar dataframes con pandas en Python publicado el septiembre 10, 2018 | en Python

Publicidad

Lo mejor valorado

4.9 (22)

Seleccionar filas y columnas en Pandas con iloc y loc

4.7 (12)

Operaciones de filtrado de DataFrame con Pandas en base a los valores de las columnas

4.6 (15)

Archivos JSON con Python: lectura y escritura

4.5 (10)

Diferencias entre var y let en JavaScript

4.3 (12)

Ordenación de diccionarios en Python mediante clave o valor

Publicidad

Comentarios recientes

  • Daniel Rodríguez en ¿Cómo eliminar columnas y filas en un dataframe pandas?
  • Miguel en ¿Cómo eliminar columnas y filas en un dataframe pandas?
  • alberto en Resolver problema de credenciales en Bitbucket
  • Pablo en Aplicar el método D’Hondt en Excel
  • Agapito en Creación de un EXE desde un archivo Python en Windows

Publicidad

Footer

Analytics Lane

  • Acerca de Analytics Lane
  • Boletín de noticias
  • Contacto
  • Libros
  • Lo más popular
  • Noticias
  • Tienda
  • Tiendas afiliadas

Secciones

  • Ciencia de datos
  • Criptografía
  • Herramientas
  • Machine Learning
  • Opinión
  • Productividad
  • Programación
  • Reseñas

Sobre de Analytics Lane

En Analytics Lane tratamos de explicar los principales conceptos de la ciencia e ingeniería de datos con un enfoque práctico. Los principales temas tratados son ciencia de datos, ingeniería de datos, inteligencia artificial, machine learning, deep learning y criptografía. Además, también se habla de los principales lenguajes de programación y herramientas utilizadas por los científicos e ingenieros de datos.

Copyright © 2018-2023 Analytics Lane ·Términos y condiciones ·Política de Cookies ·Política de Privacidad ·Herramientas de privacidad ·Contacto