R: subcadena común más larga

Question

¿Alguien sabe de un paquete R que resuelva el problema de subcadena común más largo ? Estoy buscando algo rápido que pueda funcionar en vectores.

Answer 1

Mira el " Rlibstree " paquete en omegahat: http://www.omegahat.org/Rlibstree/ .

Esto utiliza http://www.icir.org/christian/libstree/ .

Answer 2

Debe mirar la función LCS del paquete qualV . Está implementado en C, por lo tanto, es bastante eficiente.

Answer 3

La pregunta aquí no es totalmente clara sobre la aplicación prevista de la solución al problema de subcadena común más largo. Una aplicación común que encuentro es la coincidencia entre nombres en diferentes conjuntos de datos. El paquete stringdist tiene una función útil amatch () que considero adecuada para esta tarea.

En resumen , amatch () tomará como entrada dos vectores, el primero es x el vector de cadenas que desea encontrar coincidencias (esto también puede ser una sola cadena), la segunda es table , que es el vector de cadenas con las que desea hacer comparaciones y elegir la coincidencia con la subcadena común más larga. amatch () devolverá un vector cuya longitud es igual a la de x : cada elemento de este resultado será un índice en la tabla que contiene el mejor partido.

Detalles : amatch () toma un argumento method , que debe especificar como lcs si lo desea coincidencia en la subcadena común más larga. Hay muchas otras opciones para diferentes técnicas de coincidencia de cadenas (por ejemplo, distancia de Levenshtein). También hay un argumento obligatorio maxDist . Si todas las cadenas en table son mayores " distancia " desde una cadena dada en x , luego amatch () devolverá NA para ese elemento de su salida. " distancia " se define de manera diferente según el algoritmo de coincidencia de cadenas que elija. Para lcs, (más o menos) solo significa cuántos caracteres diferentes (no coincidentes) hay. Consulte la documentación para más detalles.

Paralelización : otra buena característica de amatch () es que paralelizará automáticamente la operación para usted, haciendo suposiciones razonables sobre los recursos del sistema a utilizar. Si desea tener más control sobre esto, puede alternar el argumento nthread .

Ejemplo de aplicación :

library(stringdist)

Names1 = c(
"SILVER EAGLE REFINING, INC. (SW)",
"ANTELOPE REFINING",
"ANTELOPE REFINING (DOUGLAS FACILITY)"
)

Names2 = c(
"Mobile Concrete, Inc.",
"Antelope Refining, LLC. ",
"Silver Eagle Refining Inc."
)

Match_Idx = amatch(tolower(Names1), tolower(Names2), method = 'lcs', maxDist = Inf)
Match_Idx
# [1] 3 2 2

Matches = data.frame(Names1, Names2[Match_Idx])
Matches

#                                 Names1          Names2.Match_Idx.
# 1     silver eagle refining, inc. (sw) silver eagle refining inc.
# 2                    antelope refining   antelope refining, llc. 
# 3 antelope refining (douglas facility)   antelope refining, llc. 

### Compare Matches:

Matches$Distance = stringdist(Matches$Names1, Matches$Match, method = 'lcs')

Además, a diferencia de funciones como LCS de qualV , esto no considerará " subsecuencia " coincidencias que implican ignorar caracteres intermedios para formar una coincidencia (como se discutió aquí ). Por ejemplo, mira esto:

Names1 = c(
"hello"
)

Names2 = c(
"hel123l5678o",
"hell"
)

Match_Idx = amatch(tolower(Names1), tolower(Names2), method = 'lcs', maxDist = Inf)

Matches = data.frame(Names1, Match = Names2[Match_Idx])
Matches

# 1  hello  hell

Answer 4

No sé R, pero solía implementar el algoritmo de Hirschberg, que es rápido y no consume demasiado espacio.

Como recuerdo, solo se llaman recursivamente 2 o 3 funciones cortas.

Aquí hay un enlace: http://wordaligned.org/articles/longest-common-subsequence

Así que no dudes en implementarlo en R, vale la pena el esfuerzo ya que es un algoritmo muy interesante.