How to quasi match two vectors of strings (in R)?

Question

I am not sure how this should be termed, so please correct me if you know a better term.

I've got two lists. One of 55 items (e.g: a vector of strings), the other of 92. The item names are similar but not identical.

I wish to find the best candidates in the 92 list to the items in the 55 list (I will then go through it and pick the correct fitting).

How can it be done?

Ideas I had where to:

1. See all the ones that match (using something list ?match)
2. Try a distance matrix between the strings vectors, but I am not sure how to best define it (number of identical letters, what about order of strings?)

So what package/functions/field-of-research deals with such a task, and how?

Update: Here is an example of the vectors I wish to match

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

Answer 1

I've had similar problems. (seen here: https://stackoverflow.com/questions/2231993/merging-two-data-frames-using-fuzzy-approximate-string-matching-in-r)

Most of the recommendations that I received fell around:

pmatch(), and agrep(), grep(), grepl() are three functions that if you take the time to look through will provide you with some insight into approximate string matching either by approximate string or approximate regex.

Without seeing the strings, it's hard to provide you with hard example of how to match them. If you could provide us with some example data I'm sure we could come to a solution.

Another option that I found works well is to flatten the strings, tolower(), looking at the first letter of each word within the string and then comparing. Sometimes that works without a hitch. Then there are more complicated things like the distances mentioned in other answers. Sometimes these work, sometimes they're horrible - it really depends on the strings.

Can we see them?

Update

It looks like agrep() will do the trick for most of these. Note that agrep() is just R's implementation of Levenshtein distance.

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

Some don't compute although, I'm not even sure if Ferroplasm acidaramus is the same as Ferroglobus placidus DSM 10642, for example:

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

I think you may be a bit SOL for some of these and perhaps creating an index from scratch is the best bet. ie,. Create a table with id numbers for vec55, and then manually create a reference to the id's in vec55 in vec91. Painful, I know, but a lot of it can be done with agrep().

Answer 2

There are many ways to measure distances between two strings. Two important (standard) approaches widely implemented in R are the Levenshtein and the Hamming distance. The former is avalaible in package 'MiscPsycho' and the latter in 'e1071'. Using these, i would simply compute a 92 by 55 matrix of pairwise distances, then proceed from there (i.e. the best candidate match for string "1" in list 1 is the string "x" from list 2 with smallest distance to string "1").

Alternatively, there is a function compare() in package RecordLinkage that seems to be designed to do what you want and uses the so called Jaro-Winkler distance which seems more appropriate for the task at hand, but i've had no experience with it.

EDIT: i'm editing my answer to include Brandon's comment as well as Tal's code, to find a match to "Aeropyrum pernix", the first entry of vec55:

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

Answer 3

To supplement Kwak's useful answer, allow me to add some simple principles and ideas. A good way to determine the metric is by considering how the strings might vary from their target. "Edit distance" is useful when the variation is a combination of typographic errors like transposing neighbors or mis-typing a single key.

Another useful approach (with a slightly different philosophy) is to map every string into one representative of a class of related strings. The "Soundex" method does this: the Soundex code for a word is a sequence of four characters encoding the principal consonant and groups of similar-sounding internal consequence. It is used when words are phonetic misspellings or variants of one another. In the example application you would fetch all target words whose Soundex code equals the Soundex code for each probe word. (There could be zero or multiple targets fetched this way.)

Answer 4

I would also suggest you check out N-grams and the Damerau–Levenshtein distance besides the other suggestions of Kwak.

This paper compares the accuracy of a few different edit distances mentioned here (and is highly cited according to google scholar).

As you can see there are many different ways to approach this, and you can even combine different metrics (the paper I linked to talks about this alittle bit). I think the Levenshtein and related based metrics make the most intuitive sense, especially if errors occur because of human typing. N-grams are also simple and make sense for data that is not names or words per say.

While soundex is an option, the little bit of work I have seen (which is admittedly a very small amount) soundex does not perform as well as Levenshstein or other edit distances for matching names. And the Soundex is limited to phonetic phrases likely inputted by human typers, where as Levenshtein and N-grams have a potentially broader scope (especially N-gram, but I would expect the Levenshtein distance to perform better for non-words as well).

I can't help as far as packages, but the concept of N-grams is pretty simple (I did make an SPSS macro to do N-grams recently, but for such a small project I would just go with the already made packages in R the other posters have suggested). Here is an example of calculating the Levenshtein distance in python.

Answer 5

I researched some packages and ways how to solve this problem and I think the best candidate is the fuzzywuzzyR package.

The fuzzywuzzyR package is a fuzzy string matching implemenation of the fuzzywuzzy python package. It uses the Levenshtein Distance to calculate the differences between sequences. More details on the functionality of fuzzywuzzyR can be found in the blog-post and in the package Vignette.

I did the simple solution for your problem, but there is a little catch. You have to install python and if you use winodows also have to install some build tools for visual studio. You have to choose these:

• Windows 10 sdk 10.0.17763.0 and MSVC v140
• VS 2015 C++ build tools (v 14v00)

The solution is simple. The main function ExtractOne returns list of two values. First is one string match and second one is the corresponding score ( in the range 0 - 100 ). The fuzzywuzzyR package provides also other functions which can be useful. Main documentation can found here. I hope this code helps solve the problem.

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

Output:

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

Answer 6

Based on function adist

Compute the approximate string distance between character vectors. The distance is a generalized Levenshtein (edit) distance, giving the minimal possibly weighted number of insertions, deletions and substitutions needed to transform one string into another

Function stringdist from a package of the same name has several methods (see ?stringdist-methods):

method = c("osa", "lv", "dl", "hamming", "lcs", "qgram", "cosine", "jaccard", "jw", "soundex")

With this, you can select maximum divergence (threshold):

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

This dataframe shows the first vector in column firstvector, the bestmatch of the secondvector in column match, its distance in column divergence, and all significant matches ordered in column sortedmatches as in the OP.