¿Cómo combinar cuasi dos vectores de cadenas (en R)?

No estoy seguro de cómo debería llamarse esto, así que corríjame si conoce un término mejor.

Tengo dos listas. Uno de los 55 elementos (por ejemplo, un vector de cadenas), el otro de 92. Los nombres de los elementos son similares pero no idénticos.

Deseo encontrar los mejores candidatos s en la lista 92 de los elementos de la lista 55 (entonces voy a pasar por ella y elegir el correcto montaje).

¿Cómo puede hacerse esto?

Ideas que tenía donde:

1. Ver todos los que coinciden (¿usando algo de la lista? Coinciden)
2. Pruebe una matriz de distancia entre los vectores de cadenas, pero no estoy seguro de cómo definirla mejor (número de letras idénticas, ¿qué pasa con el orden de las cadenas?)

Entonces, ¿qué paquete / funciones / campo de investigación se ocupa de tal tarea, y cómo?

Actualización: Aquí hay un ejemplo de los vectores que deseo hacer coincidir

vec55 <- c("Aeropyrum pernix", "Archaeoglobus fulgidus", "Candidatus_Korarchaeum_cryptofilum", 
"Candidatus_Methanoregula_boonei_6A8", "Cenarchaeum_symbiosum", 
"Desulfurococcus_kamchatkensis", "Ferroplasma acidarmanus", "Haloarcula_marismortui_ATCC_43049", 
"Halobacterium sp.", "Halobacterium_salinarum_R1", "Haloferax volcanii", 
"Haloquadratum_walsbyi", "Hyperthermus_butylicus", "Ignicoccus_hospitalis_KIN4", 
"Metallosphaera_sedula_DSM_5348", "Methanobacterium thermautotrophicus", 
"Methanobrevibacter_smithii_ATCC_35061", "Methanococcoides_burtonii_DSM_6242"
)
vec91 <- c("Acidilobus saccharovorans 345-15", "Aciduliprofundum boonei T469", 
"Aeropyrum pernix K1", "Archaeoglobus fulgidus DSM 4304", "Archaeoglobus profundus DSM 5631", 
"Caldivirga maquilingensis IC-167", "Candidatus Korarchaeum cryptofilum OPF8", 
"Candidatus Methanoregula boonei 6A8", "Cenarchaeum symbiosum A", 
"Desulfurococcus kamchatkensis 1221n", "Ferroglobus placidus DSM 10642", 
"Halalkalicoccus jeotgali B3", "Haloarcula marismortui ATCC 43049", 
"Halobacterium salinarum R1", "Halobacterium sp. NRC-1", "Haloferax volcanii DS2", 
"Halomicrobium mukohataei DSM 12286", "Haloquadratum walsbyi DSM 16790", 
"Halorhabdus utahensis DSM 12940", "Halorubrum lacusprofundi ATCC 49239", 
"Haloterrigena turkmenica DSM 5511", "Hyperthermus butylicus DSM 5456", 
"Ignicoccus hospitalis KIN4/I", "Ignisphaera aggregans DSM 17230", 
"Metallosphaera sedula DSM 5348", "Methanobrevibacter ruminantium M1", 
"Methanobrevibacter smithii ATCC 35061", "Methanocaldococcus fervens AG86", 
"Methanocaldococcus infernus ME", "Methanocaldococcus jannaschii DSM 2661", 
"Methanocaldococcus sp. FS406-22", "Methanocaldococcus vulcanius M7", 
"Methanocella paludicola SANAE", "Methanococcoides burtonii DSM 6242", 
"Methanococcus aeolicus Nankai-3", "Methanococcus maripaludis C5", 
"Methanococcus maripaludis C6", "Methanococcus maripaludis C7", 
"Methanococcus maripaludis S2", "Methanococcus vannielii SB", 
"Methanococcus voltae A3", "Methanocorpusculum labreanum Z", 
"Methanoculleus marisnigri JR1", "Methanohalobium evestigatum Z-7303", 
"Methanohalophilus mahii DSM 5219", "Methanoplanus petrolearius DSM 11571", 
"Methanopyrus kandleri AV19", "Methanosaeta thermophila PT", 
"Methanosarcina acetivorans C2A", "Methanosarcina barkeri str. Fusaro", 
"Methanosarcina mazei Go1", "Methanosphaera stadtmanae DSM 3091", 
"Methanosphaerula palustris E1-9c", "Methanospirillum hungatei JF-1", 
"Methanothermobacter marburgensis str. Marburg", "Methanothermobacter thermautotrophicus str. Delta H", 
"Nanoarchaeum equitans Kin4-M", "Natrialba magadii ATCC 43099", 
"Natronomonas pharaonis DSM 2160", "Nitrosopumilus maritimus SCM1", 
"Picrophilus torridus DSM 9790", "Pyrobaculum aerophilum str. IM2", 
"Pyrobaculum arsenaticum DSM 13514", "Pyrobaculum calidifontis JCM 11548", 
"Pyrobaculum islandicum DSM 4184", "Pyrococcus abyssi GE5", "Pyrococcus furiosus DSM 3638", 
"Pyrococcus horikoshii OT3", "Staphylothermus hellenicus DSM 12710", 
"Staphylothermus marinus F1", "Sulfolobus acidocaldarius DSM 639", 
"Sulfolobus islandicus L.D.8.5", "Sulfolobus islandicus L.S.2.15", 
"Sulfolobus islandicus M.14.25", "Sulfolobus islandicus M.16.27", 
"Sulfolobus islandicus M.16.4", "Sulfolobus islandicus Y.G.57.14", 
"Sulfolobus islandicus Y.N.15.51", "Sulfolobus solfataricus P2", 
"Sulfolobus tokodaii str. 7", "Thermococcus gammatolerans EJ3", 
"Thermococcus kodakarensis KOD1", "Thermococcus onnurineus NA1", 
"Thermococcus sibiricus MM 739", "Thermofilum pendens Hrk 5", 
"Thermoplasma acidophilum DSM 1728", "Thermoplasma volcanium GSS1", 
"Thermoproteus neutrophilus V24Sta", "Thermosphaera aggregans DSM 11486", 
"Vulcanisaeta distributa DSM 14429", "uncultured methanogenic archaeon RC-I"
) 

He tenido problemas similares (visto aquí: https://stackoverflow.com/questions/2231993/merging-two-data-frames-using-fuzzy-approximate-string-matching-in-r )

La mayoría de las recomendaciones que recibí cayeron en torno a:

pmatch()Y agrep(), grep(),grepl() son tres funciones que si se toma el tiempo para mirar a través de le proporcionará una idea de la coincidencia de cadenas aproximada, ya sea por la cadena aproximada de expresiones regulares o aproximada.

Sin ver las cadenas, es difícil proporcionarle un buen ejemplo de cómo combinarlas. Si pudiera proporcionarnos algunos datos de ejemplo, estoy seguro de que podríamos llegar a una solución.

Otra opción que encontré que funciona bien es aplanar las cadenas, tolower() mirando la primera letra de cada palabra dentro de la cadena y luego comparando. A veces eso funciona sin problemas. Luego hay cosas más complicadas como las distancias mencionadas en otras respuestas. A veces estos funcionan, a veces son horribles, realmente depende de los hilos.

¿Podemos verlos?

Actualizar

Parece que agrep () hará el truco para la mayoría de estos. Tenga en cuenta que agrep () es solo la implementación de R de la distancia de Levenshtein.

agrep(vec55[1],vec91,value=T)

Sin embargo, algunos no computan, ni siquiera estoy seguro de si Ferroplasm acidaramus es el mismo que Ferroglobus placidus DSM 10642, por ejemplo:

agrep(vec55[7],vec91,value=T) 

Creo que puede ser un poco SOL para algunos de estos y tal vez crear un índice desde cero es la mejor opción. es decir,. Cree una tabla con números de identificación para vec55, y luego cree manualmente una referencia a la identificación en vec55 en vec91. Doloroso, lo sé, pero se puede hacer mucho con agrep ().

Hay muchas formas de medir distancias entre dos cadenas. Dos enfoques (estándar) importantes ampliamente implementados en R son la distancia de Levenshtein y Hamming. El primero está disponible en el paquete 'MiscPsycho' y el segundo en 'e1071'. Utilizando estos, simplemente calcularía una matriz de 92 por 55 de distancias por pares, luego procedería desde allí (es decir, la mejor coincidencia candidata para la cadena "1" en la lista 1 es la cadena "x" de la lista 2 con la menor distancia a la cadena "1 ").

Alternativamente, hay una función compare () en el paquete RecordLinkage que parece estar diseñada para hacer lo que desea y utiliza la llamada distancia Jaro-Winkler, que parece más apropiada para la tarea en cuestión, pero no tengo experiencia con ella .

EDITAR: estoy editando mi respuesta para incluir el comentario de Brandon, así como el código de Tal, para encontrar una coincidencia con "Aeropyrum pernix", la primera entrada de vec55 :

agrep(vec55[1],vec91,ignore.case=T,value=T,max.distance = 0.1, useBytes = FALSE)
[1] "Aeropyrum pernix K1"

Para complementar la útil respuesta de Kwak, permítame agregar algunos principios e ideas simples. Una buena manera de determinar la métrica es considerar cómo las cadenas pueden variar de su objetivo. "Editar distancia" es útil cuando la variación es una combinación de errores tipográficos como transponer vecinos o escribir mal una sola tecla.

Otro enfoque útil (con una filosofía ligeramente diferente) es mapear cada cadena en un representante de una clase de cadenas relacionadas. El método " Soundex " hace esto: el código Soundex para una palabra es una secuencia de cuatro caracteres que codifica la consonante principal y grupos de consecuencia interna de sonido similar. Se utiliza cuando las palabras son faltas de ortografía fonéticas o variantes entre sí. En la aplicación de ejemplo, buscará todas las palabras de destino cuyo código Soundex sea igual al código Soundex para cada palabra de la sonda. (Podría haber cero o múltiples objetivos obtenidos de esta manera).

También te sugiero que revises N-gramos y la distancia Damerau-Levenshtein además de las otras sugerencias de Kwak.

Este documento compara la precisión de algunas distancias de edición diferentes mencionadas aquí (y es muy citado según Google Scholar).

Como puede ver, hay muchas formas diferentes de abordar esto, e incluso puede combinar diferentes métricas (el documento que vinculé a este tema habla un poco). Creo que el Levenshtein y las métricas relacionadas tienen el sentido más intuitivo, especialmente si se producen errores debido a la tipificación humana. Los N-gramos también son simples y tienen sentido para los datos que no son nombres o palabras por decir.

Si bien soundex es una opción, el poco trabajo que he visto (que es una cantidad muy pequeña) soundex no funciona tan bien como Levenshstein u otras distancias de edición para nombres coincidentes. Y el Soundex se limita a las frases fonéticas probablemente introducidas por los mecanografiadores humanos, donde, como Levenshtein y N-gramos tienen un alcance potencialmente más amplio (especialmente N-gram, pero esperaría que la distancia de Levenshtein también se desempeñe mejor para las no palabras).

No puedo ayudar en lo que respecta a los paquetes, pero el concepto de N-gramos es bastante simple (hice una macro SPSS para hacer N-gramos recientemente, pero para un proyecto tan pequeño simplemente iría con los paquetes ya hechos en R los otros carteles han sugerido). Aquí hay un ejemplo de cálculo de la distancia de Levenshtein en python.

Investigué algunos paquetes y formas de resolver este problema y creo que el mejor candidato es el fuzzywuzzyRpaquete.

El paquete fuzzywuzzyR es una implementación de coincidencia de cadenas difusas del paquete fuzzywuzzy python. Utiliza la distancia de Levenshtein para calcular las diferencias entre secuencias. Se pueden encontrar más detalles sobre la funcionalidad de fuzzywuzzyR en la publicación del blog y en el paquete Vignette.

Hice la solución simple para su problema, pero hay una pequeña trampa. Debe instalar Python y, si utiliza winodows, también debe instalar algunas herramientas de compilación para Visual Studio . Tienes que elegir estos:

• Windows 10 sdk 10.0.17763.0 y MSVC v140
• Herramientas de compilación VS 2015 C ++ (v 14v00)

La solución es simple. La función principal ExtractOnedevuelve la lista de dos valores. El primero es una coincidencia de cadena y el segundo es el puntaje correspondiente (en el rango de 0 a 100). El fuzzywuzzyRpaquete también proporciona otras funciones que pueden ser útiles. La documentación principal se puede encontrar aquí . Espero que este código ayude a resolver el problema.

library(fuzzywuzzyR)

# The Fuzzy initialization
init_proc = FuzzUtils$new()
PROC = init_proc$Full_process # class process-method
PROC1 = tolower # base R function
init_scor = FuzzMatcher$new()
SCOR = init_scor$WRATIO    
init <- FuzzExtract$new()

match_strings <- function(vector_to_process, base_vector){  
  new_vec = c()
  for(i in 1:length(vector_to_process)){      
    new_word <- init$ExtractOne(string = vector_to_process[i], sequence_strings = base_vector, processor = PROC1, scorer = SCOR, score_cutoff = 0L)
    new_vec[i] <- new_word[[1]]
  }     
  return(new_vec)
}

# Check if all python modules are available
if (check_availability()){    
  new_vec <- match_strings(vec55, vec91)
  print(new_vec)   
}

Salida:

[1] "Aeropyrum pernix K1"                                 "Archaeoglobus fulgidus DSM 4304"                    
[3] "Candidatus Korarchaeum cryptofilum OPF8"             "Candidatus Methanoregula boonei 6A8"                
[5] "Cenarchaeum symbiosum A"                             "Desulfurococcus kamchatkensis 1221n"                
[7] "Thermoplasma volcanium GSS1"                         "Haloarcula marismortui ATCC 43049"                  
[9] "Halobacterium sp. NRC-1"                             "Halobacterium salinarum R1"                         
[11] "Haloferax volcanii DS2"                              "Haloquadratum walsbyi DSM 16790"                    
[13] "Hyperthermus butylicus DSM 5456"                     "Ignicoccus hospitalis KIN4/I"                       
[15] "Metallosphaera sedula DSM 5348"                      "Methanothermobacter thermautotrophicus str. Delta H"
[17] "Methanobrevibacter smithii ATCC 35061"               "Methanococcoides burtonii DSM 6242"       

Basado en la función adist

Calcule la distancia aproximada de la cadena entre los vectores de caracteres. La distancia es una distancia de Levenshtein (edición) generalizada, que proporciona el número mínimo posiblemente ponderado de inserciones, eliminaciones y sustituciones necesarias para transformar una cadena en otra

La función stringdistde un paquete del mismo nombre tiene varios métodos (ver ?stringdist):

método = c ("osa", "lv", "dl", "hamming", "lcs", "qgram", "coseno", "jaccard", "jw", "soundex")

Con esto, puede seleccionar la divergencia máxima (umbral):

firstvector<-vec55
secondvector<-vec91

match<-character()
threshold<-14 # max 14 characters of divergence
mindist<-integer()
sortedmatches<-character()

for (i in 1:length(firstvector) ) {
  matchdist<-adist(firstvector[i],secondvector)[1,]
  # matchdist<-stringdist(firstvector[i],secondvector) # several methods available

  matchdist<-ifelse(matchdist>threshold,NA,matchdist)
  sortedmatches[i]<-paste(secondvector[order(matchdist, na.last=NA)], collapse = ", ")
  mindist[i]<- tryCatch(ifelse(is.integer(which.min(matchdist)),matchdist[which.min(matchdist)],NA), error = function(e){NA})
  match[i]<-ifelse(length(secondvector[which.min(matchdist)])==0,NA,
                  secondvector[which.min(matchdist)] )
}
res<-data.frame(firstvector=firstvector,match=match,divergence=mindist, sortedmatches=sortedmatches, stringsAsFactors = F)
res

Este marco de datos muestra el primer vector en el primer vector de columna, la mejor coincidencia del segundo vector en la coincidencia de columna, su distancia en la divergencia de columna y todas las coincidencias significativas ordenadas en coincidencias ordenadas por columna como en el OP.