Approximate string matching in R
In trying to merge some data, I was confronted with a problem of matching up strings where the author had mutilated them. He had done so in two ways: cutting them off at the 8th character or using personal abbreviations. The first one is relatively easy to deal with. The second one is not.
So I looked around a bit and found that there are others who had similar problems:
http://stats.stackexchange.com/questions/3425/how-to-quasi-match-two-vectors-of-strings-in-r
http://stackoverflow.com/questions/2231993/merging-two-data-frames-using-fuzzy-approximate-string-matching-in-r
The large table below shows the matching results. The leftmost column has the strings I need to match. The list to be matched against is the list of country and regional names and their ISO 3 abbreviations here: https://osf.io/59dr7/
It looks like for most cases the shortened version worked fine. 165 of 193 matches were found all of which were correct.
The agrep (with max distance = .1, the default), found a match in 175 cases, so only a little improvement there. But it gets worse, in many cases, it disagrees with the stricter matching method and gets it wrong. There is no case where it is correct over the simpler method. Strangely, in all 10 cases where the simple method failed, agrep got it right. But it got it wrong in the easier cases. In some cases, it is truly bizarre: given the string "United S", it goes for "United Republic of Tanzania" instead of the much easier "United States". Strangely, a common error is preferring a subset/longer version over an exact match. No human would make this error. E.g. given "Moldova", it prefers "Moldova, Republic" of over just "Moldova".
There are a number of different errors it makes. In the comments below I have noted the type of error (my judgment).
For the moment, I would caution the use of this algorithm. Country Genetic_distance_SA to_short_result agrep_result best_match agreement filled_in comments Norway 1455.52 Norway Norway Norway TRUE Norway Netherla 1453.28 Netherlands Netherlands Netherlands TRUE Netherlands Ireland 1940.31 Ireland Iceland Ireland FALSE Ireland prefers substitution over exact Liechste 1511.83 Liechtenstein Liechtenstein FALSE Liechtenstein correct Germany 1484.92 Germany Germany Germany TRUE Germany Sweeden 1453.79 Sweden Sweden FALSE Sweden correct Switzerl 1557.96 Switzerland Switzerland Switzerland TRUE Switzerland Iceland 1932.36 Iceland Iceland Iceland TRUE Iceland Denmark 1472.52 Denmark Denmark Denmark TRUE Denmark Belgium 1940.31 Belgium Belgium Belgium TRUE Belgium Austria 1465.7 Austria Australia Austria FALSE Austria prefers part deleted France 1896.22 France France France TRUE France Slovenia 1292.32 Slovenia Slovenia Slovenia TRUE Slovenia Finland 2420.3 Finland Finland Finland TRUE Finland Spain 1929.44 Spain Saint Barth<U+FFFD>lemy Spain FALSE Spain no idea Italy 1961.9 Italy Italy Italy TRUE Italy Luxembur 1929.98 TRUE Luxembourg Czech Re 1524.73 Czech Republic Czech Republic Czech Republic TRUE Czech Republic U. K. 1916.91 TRUE UK Greece 1283.05 Greece Greece Greece TRUE Greece Cyprus 1288.53 Cyprus Cyprus Cyprus TRUE Cyprus Estonia 2302.86 Estonia Estonia Estonia TRUE Estonia Slovakia 1573.38 Slovakia Slovakia Slovakia TRUE Slovakia Malta 1912.52 Malta Gibraltar Malta FALSE Malta prefers subset + substitution over exact Poland 1905.67 Poland Poland Poland TRUE Poland Lithuani 2389.28 Lithuania Lithuania Lithuania TRUE Lithuania Portugal 1949.34 Portugal Portugal Portugal TRUE Portugal Latvia 2256.69 Latvia Latvia Latvia TRUE Latvia Croatia 1289.64 Croatia Croatia Croatia TRUE Croatia Romania 1928.4 Romania Romania Romania TRUE Romania Bulgaria 1399.01 Bulgaria Bulgaria Bulgaria TRUE Bulgaria Serbia 1421.01 Serbia Serbia Serbia TRUE Serbia Russia 1975.49 Russia Russia Russia TRUE Russia Albania 1301.47 Albania Albania Albania TRUE Albania Macedoni 1334.51 Macedonia Macedonia Macedonia TRUE Macedonia Armenia 1558.32 Armenia Armenia Armenia TRUE Armenia Moldova 1527.95 Moldova Moldova, Republic of Moldova FALSE Moldova prefers longer Botswana 347.18 Botswana Botswana Botswana TRUE Botswana South Af 0 South Africa South Africa South Africa TRUE South Africa Ghana 395.9 Ghana Ghana Ghana TRUE Ghana Eq Guine 373.2 TRUE Equatorial Guinea Congo 452.9 Congo Congo Congo TRUE Congo Kenya 366.78 Kenya Kenya Kenya TRUE Kenya Cameroon 319.62 Cameroon Cameroon Cameroon TRUE Cameroon Tanzania 352.54 Tanzania Tanzania Tanzania TRUE Tanzania Nigeria 342.24 Nigeria Nigeria Nigeria TRUE Nigeria Uganda 358.75 Uganda Uganda Uganda TRUE Uganda Zambia 352.54 Zambia Gambia Zambia FALSE Zambia prefers substitution over exact Sudan 316.95 Sudan Sudan Sudan TRUE Sudan Zimbabwe 352.54 Zimbabwe Zimbabwe Zimbabwe TRUE Zimbabwe Ethiopia 705.3 Ethiopia Ethiopia Ethiopia TRUE Ethiopia Guinea 395.9 Guinea Guinea Guinea TRUE Guinea CentAfrR 469.7 TRUE Central African Republic SierraLe 395.9 TRUE Sierra Leone Mozambiq 355.75 Mozambique Mozambique Mozambique TRUE Mozambique CongoDR 410.17 Congo Republic of Congo Republic of FALSE Congo Republic of wrong but excuseable; Congo Democratic Republic Andorra 1912.83 Andorra Andorra Andorra TRUE Andorra Angola 353.49 Angola Angola Angola TRUE Angola Belarus 1949.85 Belarus Belarus Belarus TRUE Belarus Benin 394.54 Benin Benin Benin TRUE Benin Bosnia 1337.37 Bosnia Bosnia and Herzegovina Bosnia FALSE Bosnia prefers longer BurkinaF 378.36 Burkina Faso Burkina Faso FALSE Burkina Faso correct Burundi 362.98 Burundi Burundi Burundi TRUE Burundi Cape Ver 963.09 Cape Verde Cape Verde Cape Verde TRUE Cape Verde Chad 537.81 Chad Chad Chad TRUE Chad Comoros 352.54 Comoros Comoros Comoros TRUE Comoros IvoryCoa 468.01 TRUE Ivory Coast Djibouti 750.88 Djibouti Djibouti Djibouti TRUE Djibouti Eritrea 665.96 Eritrea Eritrea Eritrea TRUE Eritrea Gabon 360.07 Gabon Gabon Gabon TRUE Gabon Gambia 395.9 Gambia Gambia Gambia TRUE Gambia Georgia 1613.7 Georgia Georgia Georgia TRUE Georgia Guinea-B 395.9 Guinea-Bissau Guinea-Bissau Guinea-Bissau TRUE Guinea-Bissau Lesotho 352.54 Lesotho Lesotho Lesotho TRUE Lesotho Liberia 395.9 Liberia Liberia Liberia TRUE Liberia Malawi 352.54 Malawi Malawi Malawi TRUE Malawi Mali 430.58 Mali Australia Mali FALSE Mali prefers subset + substitution over exact Mauritan 681.23 Mauritania Mauritania Mauritania TRUE Mauritania Namibia 419.32 Namibia Namibia Namibia TRUE Namibia Niger 315.05 Niger Niger Niger TRUE Niger Rwanda 364.26 Rwanda Rwanda Rwanda TRUE Rwanda SaoTomeP 339.89 TRUE Sao Tome and Principe Senegal 395.9 Senegal Senegal Senegal TRUE Senegal Seychell 1709.06 Seychelles Seychelles Seychelles TRUE Seychelles Somalia 500.74 Somalia Somalia Somalia TRUE Somalia Swazilan 400.17 Swaziland Swaziland Swaziland TRUE Swaziland Togo 395.9 Togo Togo Togo TRUE Togo Ukraine 1947.94 Ukraine Ukraine Ukraine TRUE Ukraine Australi 1971.39 Australia Australia Australia TRUE Australia United S 1792.33 United States United Republic of Tanzania United States FALSE United States bizarre New Zeal 2061.12 New Zealand New Zealand New Zealand TRUE New Zealand Canada 1958.73 Canada Canada Canada TRUE Canada Japan 2176.04 Japan Japan Japan TRUE Japan Hong Kon 2674.63 Hong Kong Hong Kong Hong Kong TRUE Hong Kong Korea 2399.11 Korea Korea Democratic People's Republic of Korea FALSE Korea prefers subset + substitution over exact Israel 1539.63 Israel Israel Israel TRUE Israel Singapor 2459.04 Singapore Singapore Singapore TRUE Singapore Qatar 1733.83 Qatar Qatar Qatar TRUE Qatar Hungary 2432.96 Hungary Hungary Hungary TRUE Hungary Bahrain 971.99 Bahrain Bahrain Bahrain TRUE Bahrain Chile 2279.52 Chile Chile Chile TRUE Chile Argentin 1994.59 Argentina Argentina Argentina TRUE Argentina Barbados 468.02 Barbados Barbados Barbados TRUE Barbados Uruguay 1918.61 Uruguay Uruguay Uruguay TRUE Uruguay Cuba 1370.91 Cuba Aruba Cuba FALSE Cuba prefers subset + substitution over exact Saudi Ar 1468.3 Saudi Arabia Saudi Arabia Saudi Arabia TRUE Saudi Arabia Mexico 2024.64 Mexico Mexico Mexico TRUE Mexico Malaysia 1922.77 Malaysia Malaysia Malaysia TRUE Malaysia Trinidad 1024.1 Trinidad and Tobago Trinidad and Tobago Trinidad and Tobago TRUE Trinidad and Tobago Kuwait 1081.15 Kuwait Kuwait Kuwait TRUE Kuwait Lebanon 1543.46 Lebanon Lebanon Lebanon TRUE Lebanon Venezuel 1280.81 Venezuela, Bolivarian Republic of Venezuela, Bolivarian Republic of Venezuela, Bolivarian Republic of TRUE Venezuela, Bolivarian Republic of Mauritiu 1792.48 Mauritius Mauritius Mauritius TRUE Mauritius Jamaica 595.5 Jamaica Jamaica Jamaica TRUE Jamaica Peru 2096.08 Peru Hviderusland Peru FALSE Peru prefers subset + substitution over exact Dominica 521.08 Dominica Dominica Dominica TRUE Dominica SaintLuc 497.7 TRUE Saint Lucia Ecuador 2228.58 Ecuador Ecuador Ecuador TRUE Ecuador Brazil 1875.81 Brazil Brazil Brazil TRUE Brazil SaintVin 395.9 TRUE Saint Vincent Colombia 1973.6 Colombia Colombia Colombia TRUE Colombia Iran 1945.07 Iran France Iran FALSE Iran prefers subset + substitution over exact Tonga 2390.38 Tonga Tonga Tonga TRUE Tonga Turkey 2167.95 Turkey Turkey Turkey TRUE Turkey Belize 1481.26 Belize Belize Belize TRUE Belize Tunisia 203.38 Tunisia Tunisia Tunisia TRUE Tunisia Jordan 1539.63 Jordan Jordan Jordan TRUE Jordan SriLanka 1783.84 TRUE Sri Lanka DomRep 1206.72 TRUE Dominican Republic W. Samoa 2388.58 W. Samoa W. Samoa W. Samoa TRUE W. Samoa Fiji 2534.15 Fiji Fiji Fiji TRUE Fiji China 2646.26 China China China TRUE China Thailand 2068.81 Thailand Thailand Thailand TRUE Thailand Surinam 1562.55 Suriname Suriname Suriname TRUE Suriname Paraguay 2243.61 Paraguay Paraguay Paraguay TRUE Paraguay Bolivia 2410.22 Bolivia Bolivia, Plurinational State of Bolivia FALSE Bolivia prefers longer Philipin 2628.84 Philipines Philipines Philipines TRUE Philipines Egypt 1401.52 Egypt Egypt Egypt TRUE Egypt Syria 1590.05 Syria Syria Syria TRUE Syria Honduras 1979.74 Honduras Honduras Honduras TRUE Honduras Indonesi 2602.63 Indonesia Indonesia Indonesia TRUE Indonesia VietNam 2264.3 Viet Nam Viet Nam FALSE Viet Nam correct, but odd, vs. Vietnam Morocco 191.55 Morocco Morocco Morocco TRUE Morocco Guatemal 2040.41 Guatemala Guatemala Guatemala TRUE Guatemala Irak 1625.4 Irak Iran Irak FALSE Irak prefers substitution over exact India 1888.5 India India India TRUE India Laos 3012.42 Laos Lao People's Democratic Republic Laos FALSE Laos prefers longer Pakistan 1901.47 Pakistan Pakistan Pakistan TRUE Pakistan Madagasc 1678.96 Madagascar Madagascar Madagascar TRUE Madagascar Papua 3115.88 Papua New Guinea Papua New Guinea FALSE Papua New Guinea correct Yemen 1190.13 Yemen Yemen Yemen TRUE Yemen Nepal 2030.11 Nepal Nepal Nepal TRUE Nepal CookIsla 2437.7 TRUE Cook Islands Macau 2660.44 Macau Macao Macau FALSE Macau prefers substitution over exact Marianas 2437.7 Mariana Isl. Mariana Isl. FALSE Mariana Isl. correct Marshall 2437.7 Marshall Islands Marshall Islands Marshall Islands TRUE Marshall Islands NCaledon 2437.7 TRUE New Caledonia Taiwan 2673.71 Taiwan Taiwan, Province of China Taiwan FALSE Taiwan prefers longer PuertoRi 1654.5 TRUE Puerto Rico Afghanis 1962.74 Afghanistan Afghanistan Afghanistan TRUE Afghanistan Algeria 185.65 Algeria Algeria Algeria TRUE Algeria Antigua/ 491.84 Antigua and Barbuda Antigua and Barbuda FALSE Antigua and Barbuda correct Azerbaij 2190.35 Azerbaijan Azerbaijan Azerbaijan TRUE Azerbaijan Bahamas 594.17 Bahamas Bahamas Bahamas TRUE Bahamas Banglade 1897.24 Bangladesh Bangladesh Bangladesh TRUE Bangladesh Bhutan 2082.28 Bhutan Bhutan Bhutan TRUE Bhutan Brunei 1904.48 Brunei Brunei Darussalam Brunei FALSE Brunei prefers longer Burma 2138.54 Burma Burma Burma TRUE Burma Cambodia 2254.37 Cambodia Cambodia Cambodia TRUE Cambodia Costa Ri 1938.1 Costa Rica Costa Rica Costa Rica TRUE Costa Rica El Salva 1016.14 El Salvador El Salvador El Salvador TRUE El Salvador Grenada 537.25 Grenada Grenada Grenada TRUE Grenada Guyana 1379.76 Guyana Guyana Guyana TRUE Guyana Haiti 434.51 Haiti Haiti Haiti TRUE Haiti Kazakhst 2122.18 Kazakhstan Kazakhstan Kazakhstan TRUE Kazakhstan Kiribati 2281.44 Kiribati Kiribati Kiribati TRUE Kiribati Korea (N 2399.11 Korea North Korea North FALSE Korea North correct Kyrgysta 2143.13 TRUE Kyrgyzstan Libya 185.65 Libya Libano Libya FALSE Libya prefers subset, deletion, insertion over exact Maldives 1836.17 Maldives Maldives Maldives TRUE Maldives Micrones 2437.7 Micronesia, Federated States of Micronesia, Federated States of Micronesia, Federated States of TRUE Micronesia, Federated States of Mongolia 2542.15 Mongolia Mongolia Mongolia TRUE Mongolia Nicaragu 1856.28 Nicaragua Nicaragua Nicaragua TRUE Nicaragua Oman 1594.25 Oman Cayman Islands Oman FALSE Oman prefers subset + substitution over exact Panama 1809.12 Panama Panama Panama TRUE Panama SKittsNe 469.61 TRUE Saint Kitts and Nevis Solomon 3050.76 Solomon Islands Solomon Islands FALSE Solomon Islands Tajikist 2000.53 Tajikistan Tajikistan Tajikistan TRUE Tajikistan TimorLes 2602.63 TRUE Timor–Leste Turkmeni 2212.49 Turkmenistan Turkmenistan Turkmenistan TRUE Turkmenistan UArabEm 1286.35 TRUE United Arab Emirates Uzbekist 2193.47 Uzbekistan Uzbekistan Uzbekistan TRUE Uzbekistan Vanuatu 2385.83 Vanuatu Vanuatu Vanuatu TRUE Vanuatu
The R code:
gn = read.csv("genetic_distance.csv", encoding = "UTF-8", stringsAsFactors = F)
gn$abbrev = as_abbrev(gn$Country)
trans = read.csv("countrycodes.csv", sep=";", encoding = "UTF-8", stringsAsFactors = F)
trans$shorter = str_sub(trans$Names, 1, 8)
intersect(trans$shorter, gn$Country)
matches = data.frame(source_names = gn$Country,
to_short = pmatch (gn$Country, trans$shorter)
)
agrep(gn$Country[4], trans$shorter)
best_matches = matrix(nrow = nrow(gn))
for (idx in seq_along(gn$Country)) {
match_idx = agrep(gn$Country[idx], trans$shorter, max.distance = .1, useBytes = T)
#skip on no match
if (length(match_idx) == 0) next
#insert match
best_matches[idx] = match_idx
}
matches$agrep = best_matches
matches$to_short_result = trans[matches$to_short, "Names"]
matches$agrep_result = trans[matches$agrep, "Names"]
for (idx in 1:nrow(matches)) {
if (!is.na(matches[idx, "to_short_result"])) {
matches[idx, "best_match"] = matches[idx, "to_short_result"]
}
if (is.na(matches[idx, "to_short_result"])) {
matches[idx, "best_match"] = matches[idx, "agrep_result"]
}
}
#output
write.table(matches, "clipboard", na = "", sep = "\t")