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.

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.

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