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

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 candidate*s* 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?

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


(Thanks)

-
Tal, could you show us some of the data? Or tell us a little bit more about how the strings do or do not match? There are a number of options here most of which are dependent on how you match it up visually. – Brandon Bertelsen Oct 9 '10 at 2:28
Hi Brandon, I will now update my question with some data. Thanks – Tal Galili Oct 9 '10 at 13:12
Hi Tal:> Given that these seems to be typo-free scientific names, i would try the Levenshtein metric first (in the context of a 92-by-55 distance matrix) and see how it comes out. – user603 Oct 9 '10 at 14:31

I've had similar problems. (seen here: http://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().

-
 Hi Brandon - I added a sample of the data. Thanks! – Tal Galili Oct 9 '10 at 13:17 Hi Brandon - your solution worked great - thank you. – Tal Galili Oct 10 '10 at 8:23 +1 for the link to the previous question on the subject in S.E. (thaks for the pointer to agrep()). – user603 Oct 10 '10 at 8:50

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"

-
+1. Also, in case it's helpful, the term to google when comparing strings is "edit distance": en.wikipedia.org/wiki/Edit_distance – ars Oct 8 '10 at 22:05
@ars:> thanks, that's a handy list to feed unto a R search engine and see what comes out! – user603 Oct 8 '10 at 22:09
+1 for RecordLinkage. – mbq Oct 9 '10 at 12:01
Levenshtein edit distance is implemented as part of the base package via agrep() – Brandon Bertelsen Oct 9 '10 at 20:05
@Brandon:> thanks, i couldn't find it.... – user603 Oct 9 '10 at 20:11

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.

-
 Thank you Andy - I will have a look at it in the future. – Tal Galili Oct 10 '10 at 8:23

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

-
 > thanks, first time i've eared of this idea. – user603 Oct 9 '10 at 0:26 Thank you Whuber - I never heard of it. – Tal Galili Oct 10 '10 at 8:23