• 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 similitud de Jaro–Winkler

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

La similitud de Jaro–Winkler

La semana pasada hemos se ha visto cómo medir la diferencia entre dos cadenas de texto con la distancia de Levenshtein. Una distancia que mide el número de operaciones necesarias para convertir una cadena de caracteres en otra. Otra distancia que se puede utilizar para medir la similitud entre dos cadenas de texto es la de Jaro–Winkler. Una modificación propuesta por Winkler en 1990 de la distancia que Jaro había propuesto un año antes en la que se le da un mayor peso las cadenas que comparten prefijos. Además de esto, a diferencia de la distancia de Levenshtein el algoritmo de Jaro–Winkler ya ofrece directamente el grado de similitud, es decir, un valor entre 0 y 1, sin necesidad de normalizar posteriormente.

La similitud de Jaro

Antes de ver la forma de calcular la similitud de Jaro–Winkler se puede estudiar la similitud de Jaro. Una métrica en la que la única operación de edición que utiliza es la transposición de caracteres. Por lo que solamente es necesario contar el número de caracteres iguales entre dos cadenas y el número de transposiciones que son necesarias para llegar de una a otra. Así, se puede definir matemáticamente la distancia de Jaro entre las cadenas de texto a y b mediante la expresión.

j_{a,b}=\left\{\begin{matrix} 0 & si \, m = 0, \\ \frac{1}{2} \left( \frac{m}{|a|} + \frac{m}{|b|} + \frac{m-t}{m} \right) & si \, m \ne 0 \end{matrix}\right.

en donde |a| es la longitud de la cadena a, |b| es la longitud de la cadena b, m es el número de caracteres coincidentes en ambas cadenas y t es la mitad de número de transposiciones necesarios para convertir una cadena en otra.

Para asumir que un carácter de la cadena a coincide con uno de la cadena b este ha de ser el mismo y no estar separado más de una distancia igual a la mitad de la cadena más larga menos uno. Esto es, no pueden estar separados más de la distancia.

Publicidad


Por otro lado, las transposiciones son el número de caracteres que son iguales en ambas cadenas, pero se encuentran en diferente orden. Este valor dividido por dos es el valor que toma t en la expresión anterior.

La similitud de Jaro–Winkler

Winkler propuso modificar la similitud de Jaro para dar un peso mayor a las cadenas de texto que tiene prefijos comunes. Ya que en la mayoría de los casos los prefijos tienen más valor que los sufijos de las cadenas para identificar texto que son similares. Así en la similitud de Jaro–Winkler se introduce una escala que otorga calificaciones más favorables a las cadenas que coinciden desde el principio. Siendo la longitud de prefijo establecida un hiperparámetro que es necesario fijar. Esto es, la métrica se modifica mediante la expresión

jk_{a,b} = j_{a,b} + l p (1-j_{a,b})

donde l es la longitud del prefijo común al comienzo de las cadenas y p es un factor de escala constante con el que se ajusta la puntuación hacia arriba por tener prefijos comunes.

Implementación

La similitud de Jaro–Winkler se puede implementar mediante el siguiente algoritmo en R.

Publicidad


jaroWinkler <- function(str_1, str_2,
                        weight_threshold = 0.7,
                        num_chars        = 4) {
  str_1 <- tolower(str_1)
  str_2 <- tolower(str_2)
  len_1 <- str_length(str_1)
  len_2 <- str_length(str_2)

  if (len_1 == 0 || len_2 == 0) {
    if (len_1 == 0 && len_2 == 0) {
      return(1)
    } else {
      return(0)
    }
  }

  search_range <- max(len_1, len_2) / 2
  search_range <- floor(max(1, search_range))

  match_1 <- rep(FALSE, len_1)
  match_2 <- rep(FALSE, len_2)

  num_common <- 0

  for (i in 1:len_1) {
    ini <- max(1, i - search_range)
    end <- min(i + search_range, len_2)

    for (j in ini:end) {
      if (match_2[j]) {
        next
      }

      if (str_sub(str_1, i, i) != str_sub(str_2, j, j)) {
        next
      }

      match_1[i] <- TRUE
      match_2[j] <- TRUE
      num_common <- num_common + 1
      break;
    }
  }

  if (num_common == 0) {
    return(0)
  }

  num_half_transposed <- 0
  k                   <- 1

  for (i in 1:len_1) {
    if (!match_1[i]) {
      next
    }

    while (!match_2[k]) {
      k <- k + 1
    }

    if (str_sub(str_1, i, i) != str_sub(str_2, k, k)) {
      num_half_transposed <- num_half_transposed + 1
    }

    k <- k + 1
  }

  num_transposed <- floor(num_half_transposed / 2)
  weight         <- (num_common / len_1 + num_common / len_2 +
                       (num_common - num_transposed) / num_common) / 3

  if (weight <= weight_threshold) {
    return(weight)
  }

  num_max <- min(num_chars, min(len_1, len_2));
  pos     <- 1
  while (pos <= num_max && str_sub(str_1, pos, pos) == str_sub(str_2, pos, pos)) {
    pos <- pos + 1
  }

  if (pos == 1) {
    return(weight)
  }

  return(weight + 0.1 * (pos - 1) * (1 - weight))
}

En este código se han fijado por defecto el número de los caracteres de los prefijos a 4 (num_chars) y el peso que se le ha asignado es de 0,7 (weight_threshold). Posteriormente se comprueba si las cadenas son vacías o no, en caso afirmativo si son ambas vacías se devuelve 1 y cero en caso contrario.

Posteriormente se procede con el algoritmo en sí. Obteniéndose el número de caracteres que son similares dentro del rango permitido. Para inmediatamente después obtener el número de transposiciones. Finalmente se usa los pesos para obtener el resultado deseado.

Conclusiones

En la entrada de hoy hemos visto la similitud de Jaro–Winkler, una métrica con la que se puede ver si dos cadenas son similares y medir este grado. Al igual que la distancia de Levenshtein esta es una función que se puede utilizar en diferentes aplicaciones como correctores ortográficos u OCR.

Imagen de PDPics en Pixabay

¿Te ha parecido de utilidad el contenido?

¡Puntúalo entre una y cinco estrellas!

Puntuación promedio 5 / 5. Votos emitidos: 1

Publicidad


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

  • Distancias
    Distancias y métricas en aprendizaje automático
  • mountains
    Matrices dispersas (“Sparse Matrix”)
  • space
    Cómo funciona k-modes e implementación en Python
  • time
    Diferentes modelos de aprendizaje no supervisado
  • vote
    El método D'Hondt y su implementación en Python
  • luggage
    El archivo DESCRIPTION (Creación de paquetes en R 2ª parte)

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

Mantener un sistema de alta disponibilidad con PostgreSQL y repmgr

diciembre 1, 2023 Por Daniel Rodríguez

Diferencias entre los errores 401 y 403 del estándar HTTP

noviembre 29, 2023 Por Daniel Rodríguez

Ver el código de cualquier función en Python

noviembre 27, 2023 Por Daniel Rodríguez

Publicidad

Es tendencia

  • Operaciones de filtrado de DataFrame con Pandas en base a los valores de las columnas publicado el mayo 10, 2019 | en Python
  • Diferentes formas de ordenar dataframes en pandas publicado el abril 29, 2019 | en Python
  • Seleccionar filas y columnas en Pandas con iloc y loc publicado el junio 21, 2019 | en Python
  • Codificación JSON Archivos JSON con Python: lectura y escritura publicado el julio 16, 2018 | en Python
  • pandas Pandas: Cómo crear un DataFrame vacío y agregar datos publicado el noviembre 16, 2020 | 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.4 (13)

Ordenación de diccionarios en Python mediante clave o valor

Publicidad

Comentarios recientes

  • Anto en Rendimiento al iterar en JavaScript sobre un vector
  • Daniel Rodríguez en Creación de un certificado Let’s Encrypt en Windows con Win-Acme
  • Guillermo en Creación de un certificado Let’s Encrypt en Windows con Win-Acme
  • 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?

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