¿Cómo saber las operaciones realizadas para calcular la distancia Levenshtein entre cadenas?

string levenshtein-distance

Question

Con la función stringdist , puedo calcular la distancia Levenshtein entre cadenas: cuenta el número de eliminaciones, inserciones y sustituciones necesarias para convertir una cadena en otra. Por ejemplo, stringdist("abc abc","abcd abc") = 1 porque "d" se insertó en la segunda cadena.

¿Es posible conocer las operaciones realizadas para obtener la distancia Levenshtein entre dos cadenas? ¿O también para saber los caracteres que son diferentes entre las 2 cadenas (en este ejemplo, solo "d")? Gracias.

library(stringdist)
stringdist("abc abc","abcde acc") = 3

Me gustaría saber que:

• "d" fue insertada

• "e" fue insertada

• "b" fue sustituido en "c"

O más simplemente, me gustaría tener la lista ("d", "e", "c").

Answer 1

A partir de la respuesta de tmfmnk y la sugerencia de jugar con el atributo "trafos", aquí hay una función que le mostrará una tabla de todos los caracteres insertados o sustituidos, y cuántas veces se insertaron y sustituyeron. Si establece all_actions = T también le mostrará coincidencias.

f <- function(x, y, all_actions = FALSE){
  o <- adist(x, y, count = TRUE)
  cva <- 
    list(char = strsplit(y, '''')[[1]], 
         action = strsplit(attr(o,"trafos"), '''')[[1]])
  if(!all_actions)
    cva <- lapply(cva, ''['', cva$action %in% c(''I'', ''S''))
  do.call(table, cva)
}

f(x = "abc abc", y = "abcde acc")
#     action
# char I S
#    c 0 1
#    d 1 0
#    e 1 0

f(x = "abc abc", y = "abcde acc", all_actions = T)
#     action
# char I M S
#      0 1 0
#    a 0 2 0
#    b 0 1 0
#    c 0 2 1
#    d 1 0 0
#    e 1 0 0

Answer 2

Con adist() , puede recuperar las operaciones:

drop(attr(adist("abc abc","abcde acc", count = TRUE), "counts"))

ins del sub 
  2   0   1 

De ?adist :

Si cuenta es VERDADERO, la transformación se devuelve como el atributo "cuentas" de esta matriz, como una matriz tridimensional con dimensiones correspondientes a los elementos de x, los elementos de y, y el tipo de transformación (inserciones, deleciones y sustituciones), respectivamente.

Answer 3

Esto se conoce como el algoritmo de Needleman-Wunsch . Calcula tanto la distancia entre dos cadenas como el llamado rastreo , que le permite reconstruir la alineación.

Dado que este problema surge principalmente en biología cuando se comparan secuencias biológicas, este algoritmo (y otros relacionados) se implementa en el paquete R {Biostrings} , que es parte de Bioconductor .

Dado que los implementos de este paquete son una solución más general que la simple distancia Levenshtein, el uso es desafortunadamente más complejo y la viñeta de uso es correspondientemente larga. Pero el uso fundamental para sus propósitos es el siguiente:

library(Biostrings)

dist_mat = diag(27L)
colnames(dist_mat) = rownames(dist_mat) = c(letters, '' '')

result = pairwiseAlignment(
    "abc abc", "abcde acc",
    substitutionMatrix = dist_mat,
    gapOpening = 1, gapExtension = 1
)

Sin embargo, esto simplemente no le dará la lista c(''b'', ''c'', ''c'') , porque esa lista no representa completamente lo que realmente sucedió aquí. En su lugar, devolverá una alineación entre las dos cadenas. Esto se puede representar como una secuencia con sustituciones y huecos:

score(result)
# [1] 3
aligned(result)
as.matrix(aligned(result))
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
# [1,] "a"  "b"  "c"  "-"  "-"  " "  "a"  "b"  "c"
aligned(result)

- Para cada carácter en la segunda cadena, proporciona el carácter correspondiente en la cadena original, reemplazando los caracteres insertados por - . Básicamente, esta es una "receta" para transformar la primera cadena en la segunda cadena. Tenga en cuenta que solo contendrá inserciones y sustituciones, no eliminaciones. Para obtener estos, debe realizar la alineación al revés (es decir, intercambiar los argumentos de cadena).