I have two vectors of strings, and each element in one vector matches one or zero elements in the other vector. No one-to-many or many-to-one pairs.

The closest matches are found with a stringdist calculation, see MWE

names.variant.1 <- c("Apple", "Banana", "Citrus", "Orange", "Pear", "Apple Pear")
names.variant.2 <- c("Apples (Fruit)", "Banan", "Citrusfruit", "Some really good oranges", "Pear-fruits", "Pear Apple")
dist.mat <- stringdistmatrix(a=names.variant.1, b=names.variant.2, useNames="strings",method="cosine")
dist.mat[, "Apples (Fruit)"]
# Apple      Banana     Citrus     Orange     Pear       Apple Pear 
# 0.3385622  1.0000000  0.4896896  0.7958759  0.7500000  0.3318469 
dist.mat[, "Pear Apple"]
# Apple      Banana     Citrus     Orange     Pear       Apple Pear 
# 0.1918780  0.7857143  0.8908911  0.5635642  0.3318469  0.0000000 

Here the closest match of "Apples (Fruit)" is "Apple Pear" (should be "Apple"). But the match "Pear Apple" to "Apple Pear" is stronger (and correct).

Is there any method that uses the knowledge that there can only be one-to-one pairs?

In the MWE, the match "Pear Apple" to "Apple Pear" should have disqualified "Apples (Fruit)" to "Apple Pear".

Note: another method than cosine might solve the MWE, but please disregard that. It is how to use the constraint one-to-one or one-to-zero I'm after.

Update: After realising that the problem was how to minimize pairs in the distance matrix, I found this solution:

# Update with solution
solve_LSAP(dist.mat, maximum=FALSE)
# Optimal assignment:
#   1 => 1, 2 => 2, 3 => 3, 4 => 4, 5 => 5, 6 => 6
  • $\begingroup$ I thought questions about solving linear sum assignment problems using the Hungarian method belonged to this site. $\endgroup$ – Chris Feb 15 '19 at 16:09

This constructs a distance matrix, so all pairs have distances relative to each other. What you get is a row / column of the distances to the specified string. I'd say its up to you to order and choose the best fitting / least distance one-to-one pairs.


Not the answer you're looking for? Browse other questions tagged or ask your own question.