Como quase igualar dois vetores de strings (em R)?

Não sei ao certo como isso deve ser denominado; portanto, corrija-me se souber um termo melhor.

Eu tenho duas listas. Um dos 55 itens (por exemplo: um vetor de strings) e o outro de 92. Os nomes dos itens são semelhantes, mas não idênticos.

Eu gostaria de encontrar o melhor candidato s na lista de 92 para os itens na lista de 55 (Eu, então, passar por isso e escolher o encaixe correto).

Como pode ser feito?

Ideias que eu tinha para onde:

1. Veja todos os que correspondem (usando algo listar? Match)
2. Tente uma matriz de distância entre os vetores das strings, mas não sei como defini-la da melhor maneira (número de letras idênticas, e a ordem das strings?)

Então, que pacote / funções / campo de pesquisa lida com essa tarefa e como?

Atualização: Aqui está um exemplo dos vetores que desejo corresponder

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

Eu tive problemas semelhantes. (visto aqui: https://stackoverflow.com/questions/2231993/merging-two-data-frames-using-fuzzy-approximate-string-matching-in-r )

A maioria das recomendações que recebi caiu em torno de:

pmatch()E agrep(), grep(), grepl()são três funções que se você tomar o tempo para olhar através irá fornecer-lhe algumas dicas sobre strings aproximada quer por corda aproximada ou regex aproximada.

Sem ver as strings, é difícil fornecer um exemplo rígido de como combiná-las. Se você puder nos fornecer alguns dados de exemplo, tenho certeza de que poderíamos chegar a uma solução.

Outra opção que eu achei que funciona bem é achatar as strings tolower(), observando a primeira letra de cada palavra dentro da string e comparando. Às vezes isso funciona sem problemas. Depois, existem coisas mais complicadas, como as distâncias mencionadas em outras respostas. Às vezes, esses trabalhos, às vezes, são horríveis - realmente depende das cordas.

Podemos vê-los?

Atualizar

Parece que concorda () fará o truque para a maioria deles. Note que Agrep () é apenas a implementação de R da distância de Levenshtein.

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

Alguns não calculam, porém, nem tenho certeza se Ferroplasm acidaramus é o mesmo que Ferroglobus placidus DSM 10642, por exemplo:

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

Eu acho que você pode ser um pouco SOL para alguns deles e talvez criar um índice a partir do zero seja a melhor aposta. ou seja, Crie uma tabela com números de identificação para vec55 e, em seguida, crie manualmente uma referência aos IDs na vec55 na vec91. Doloroso, eu sei, mas muito disso pode ser feito com concordância ().

Existem várias maneiras de medir distâncias entre duas cadeias. Duas abordagens importantes (padrão) amplamente implementadas em R são a distância de Levenshtein e Hamming. O primeiro está disponível no pacote 'MiscPsycho' e o segundo no 'e1071'. Usando isso, eu simplesmente calcularia uma matriz de 92 por 55 de distâncias em pares e depois prosseguiria a partir daí (ou seja, a melhor correspondência candidata para a string "1" na lista 1 é a string "x" da lista 2 com a menor distância para a string "1 ").

Como alternativa, existe uma função compare () no pacote RecordLinkage que parece ter sido projetada para fazer o que você deseja e usa a chamada distância Jaro-Winkler que parece mais apropriada para a tarefa em questão, mas eu não tive nenhuma experiência com ela .

EDIT: estou editando minha resposta para incluir o comentário de Brandon e o código de Tal, para encontrar uma correspondência com "Aeropyrum pernix", a primeira entrada do vec55 :

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

Para complementar a resposta útil de Kwak, permita-me adicionar alguns princípios e idéias simples. Uma boa maneira de determinar a métrica é considerando como as seqüências de caracteres podem variar de seu destino. "Editar distância" é útil quando a variação é uma combinação de erros tipográficos, como transpor vizinhos ou digitar incorretamente uma única tecla.

Outra abordagem útil (com uma filosofia um pouco diferente) é mapear cada string em um representante de uma classe de strings relacionadas. O método " Soundex " faz isso: o código Soundex para uma palavra é uma sequência de quatro caracteres que codificam a consoante principal e os grupos de conseqüência interna com som semelhante. É usado quando as palavras são erros de ortografia ou variantes fonéticas uma da outra. No aplicativo de exemplo, você buscaria todas as palavras de destino cujo código Soundex seja igual ao código Soundex para cada palavra do probe. (Pode haver zero ou vários destinos buscados dessa maneira.)

Eu também sugiro que você verifique N-gramas e a distância Damerau – Levenshtein, além das outras sugestões de Kwak.

Este artigo compara a precisão de algumas distâncias de edição diferentes mencionadas aqui (e é altamente citada de acordo com o Google Scholar).

Como você pode ver, existem muitas maneiras diferentes de abordar isso, e você pode até combinar métricas diferentes (o artigo que eu vinculei às conversas sobre esse pequeno pedaço). Eu acho que o Levenshtein e métricas baseadas relacionadas fazem o sentido mais intuitivo, especialmente se ocorrerem erros devido à digitação humana. N-gramas também são simples e fazem sentido para dados que não são nomes ou palavras.

Embora o soundex seja uma opção, o pouco de trabalho que tenho visto (que é reconhecidamente uma quantidade muito pequena) não funciona tão bem quanto Levenshstein ou outras distâncias de edição para nomes correspondentes. E o Soundex é limitado a frases fonéticas provavelmente inseridas por digitadores humanos, onde Levenshtein e N-gramas têm um escopo potencialmente mais amplo (especialmente N-gram, mas eu esperaria que a distância de Levenshtein tivesse melhor desempenho também para não-palavras).

Não posso ajudar no que diz respeito aos pacotes, mas o conceito de N-gramas é bastante simples (fiz uma macro do SPSS para fazer N-gramas recentemente, mas para um projeto tão pequeno, eu iria apenas com os pacotes já feitos em (Os outros pôsteres sugeriram). Aqui está um exemplo de cálculo da distância de Levenshtein em python.

Eu pesquisei alguns pacotes e maneiras de resolver esse problema e acho que o melhor candidato é o fuzzywuzzyRpacote.

O pacote fuzzywuzzyR é uma implementação de correspondência de sequência difusa do pacote python fuzzywuzzy . Ele usa a distância de Levenshtein para calcular as diferenças entre as seqüências. Mais detalhes sobre a funcionalidade do fuzzywuzzyR podem ser encontrados na postagem do blog e no pacote Vignette.

Fiz a solução simples para o seu problema, mas há um pequeno problema. Você precisa instalar o python e, se usar o winodows, também precisará instalar algumas ferramentas de construção para o visual studio . Você tem que escolher estes:

• Windows 10 sdk 10.0.17763.0 e MSVC v140
• Ferramentas de construção do VS 2015 C ++ (v 14v00)

A solução é simples. A função principal ExtractOneretorna uma lista de dois valores. Primeiro é uma correspondência de corda e o segundo é a pontuação correspondente (no intervalo de 0 a 100). O fuzzywuzzyRpacote também oferece outras funções que podem ser úteis. A documentação principal pode ser encontrada aqui . Espero que este código ajude a resolver o 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)   
}

Saída:

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

Com base na função adist

Calcule a distância aproximada da string entre vetores de caracteres. A distância é uma distância generalizada de Levenshtein (editar), fornecendo o número mínimo possivelmente ponderado de inserções, exclusões e substituições necessárias para transformar uma sequência em outra

A função stringdistde um pacote com o mesmo nome possui vários métodos (consulte ?stringdist):

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

Com isso, você pode selecionar a divergência máxima (limite):

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

Esse quadro de dados mostra o primeiro vetor na coluna firstvector, a melhor correspondência do segundo vetor na correspondência da coluna, sua distância na divergência da coluna e todas as correspondências significativas ordenadas nas correspondências classificadas da coluna como no OP.