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

Question

No estoy seguro de cómo debería ser llamado, así que por favor me corrija si usted sabe de un término mejor.

Tengo dos listas. Uno de los 55 ítems (e.g: un vector de cadenas de caracteres), y el otro de 92. Los nombres de los elementos son similares pero no idénticos.

Deseo encontrar el mejor candidato*s* en el 92 lista de los elementos en el 55 de la lista (a continuación, voy a ir a través de él y elegir el correcto montaje).

¿Cómo se puede hacer?

Ideas que tenía dónde:

1. Ver todos los que coinciden (usando algo de la lista ?el partido)
2. Trate de una matriz de distancias entre las cadenas de los vectores, pero no estoy seguro de cómo mejor la definen (número de cartas idénticas, lo que acerca el fin de cuerdas?)

Entonces, ¿qué paquete/funciones/campo-de-trabajo de investigación se aborda esta tarea, y cómo?

Actualización: Aquí está un ejemplo de los vectores deseo partido

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"
)

(Gracias)

Answer 1

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

La mayoría de las recomendaciones que he recibido cayó alrededor de:

pmatch()y agrep(), grep(), grepl() son tres las funciones que si se toma el tiempo para mirar a través de le proporcionará una visión aproximada de la cadena de igualar por aproximada de cadena o aproximado regex.

Sin ver las cadenas, es duro para proporcionarle duro ejemplo de cómo adaptarse a los mismos. Si nos podía proporcionar algunos datos de ejemplo que estoy seguro de que podríamos llegar a una solución.

Otra opción que he encontrado que funciona bien es aplanar las cuerdas, tolower(), mirando a la primera letra de cada palabra dentro de la cadena y, a continuación, comparar. A veces eso funciona sin problemas. Luego hay cosas más complicadas como las distancias mencionado en otras respuestas. A veces funciona, a veces son horribles, realmente depende de las cuerdas.

Podemos verlos?

Actualización

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

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

Algunos no se calcula aunque, no estoy seguro 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 de SOL para algunos de estos y tal vez la creación de un índice de cero es la mejor apuesta. es decir,. Crear una tabla con el número de identificación de vec55 y, a continuación, crear manualmente una referencia a la identificación en vec55 en vec91. Doloroso, lo sé, pero mucho se puede hacer con agrep().

Answer 2

Hay muchas formas de medir las distancias entre dos cadenas. Dos importantes (estándar) enfoques ampliamente implementado en R son las Levenshtein y la distancia de Hamming. El primero está disponible en el paquete 'MiscPsycho" y el segundo en 'e1071'. El uso de estos, yo simplemente calcular un 92 por 55 matriz de pares distancias, a continuación, proceda de allí (es decir, el mejor candidato del partido para la cadena "1" en la lista 1 es la cadena "x" de la lista 2 con menor distancia a la cadena "1").

Alternativamente, hay una función de comparación() en el paquete RecordLinkage que parece estar diseñado para hacer lo que quieras y utiliza el llamado Jaro-Winkler distancia que parece más apropiado para la tarea a mano, pero he tenido ninguna experiencia con ella.

EDIT: estoy editando mi respuesta a incluir en Brandon comentario como Tal del código, para encontrar una coincidencia para "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"

Answer 3

Para complementar Kwak de la respuesta útil, me permite agregar algunos principios simples e ideas. Una buena forma de determinar la métrica es considerar cómo las cadenas de caracteres pueden variar con respecto a su destino. "Distancia de edición" es útil cuando la variación es una combinación de errores tipográficos, como la transposición de los vecinos o mis-escribir una sola tecla.

Otro enfoque útil (con algo un poco diferente de la filosofía) es el mapa de cada cadena en un representante de una clase de las cadenas relacionadas con. El "Soundex" método: el código Soundex para una palabra es una secuencia de cuatro caracteres de la codificación de la directora de consonantes y grupos de similar sonido interno consecuencia. Se utiliza cuando las palabras son fonética faltas de ortografía o variantes de uno a otro. En el ejemplo de aplicación sería buscar todas las palabras de destino cuyo código Soundex es igual al código Soundex para cada sonda palabra. (Podría ser cero o varios objetivos a obtener de esta manera.)

Answer 4

También quisiera sugerir a la salida de N-gramas y el Damerau–Levenshtein distancia y además de otras sugerencias de Kwak.

Este documento compara la precisión de un par de diferentes editar las distancias que se mencionan aquí (y es altamente citados según google scholar).

Como usted puede ver, hay muchas maneras diferentes de acercarse a este, y usted puede incluso combinar diferentes métricas (el papel vinculados a charlas acerca de este alittle bits). Creo que el Levenshtein y relacionados con las métricas basadas en hacer el más intuitivo sentido, especialmente si se producen errores a causa de la humana escribir. N-gramas son también simples y sentido para los datos que no es de nombres o palabras por decir.

Mientras soundex es una opción, el poco trabajo que he visto (que es sin duda una muy pequeña cantidad) soundex no se desempeñan tan bien como Levenshstein u otras editar las distancias para que coincidan con los nombres. Y el Soundex es limitado a la fonética frases probable introducidos por el ser humano typers, donde como Levenshtein y N-gramas tener un potencial más amplio alcance (especialmente N-gram, pero yo esperaría que la distancia de Levenshtein para un mejor desempeño para los no-palabras).

Yo no puedo ayudar en lo de los paquetes, pero el concepto de N-gramas es bastante simple (yo hice una SPSS macro para hacer de N-gramas recientemente, pero para un proyecto pequeño acabo de ir con el hecho ya los paquetes en R los otros carteles han sugerido). Aquí está un ejemplo de cálculo de la distancia de Levenshtein en python.