CODEWITHSUNDEEP
rdataframetmlevenshtein-distancestringdist
jvalenti
jvalenti

Reputation: 640

R - return n matches via levenshtein distance

I would like to find the n best matches to a given string via levenshtein distance. I know that the adist function in R gives the minimal distance, but I am attempting to scale the number of results to, say, 10. I have some code below.

name <- c("holiday inn", "geico", "zgf", "morton phillips")
address <- c("400 lafayette pl tupelo ms", "227 geico plaza chevy chase md", 
     "811 quincy st washington dc", "1911 1st st rockville md")

source1 <- data.frame(name, address)

name <- c("williams sonoma", "mamas bbq", "davis polk", "hop a long diner",
  "joes crag shack", "mike lowry place", "holiday inn", "zummer")

name2 <- c(NA, NA, NA, NA, NA, NA, "hi express", "zummer gunsul frasca")
address <- c("2 reads way new castle de", "248 w 4th st newark de",
     "1100 21st st nw washington dc", "1804 w 5th st wilmington de",
     "1208 kenwood parkway holdridge nb", "4203 ocean drive miami fl",
     "400 lafayette pl tupelo ms", "811 quincy st washington dc")
source2 <- data.frame(name, name2, address)

dist.mat.nm <- adist(source1$name, source2$name, partial = T, ignore.case = TRUE)

dist.mat.ad <- adist(source1$address.full, source2$address.full, partial = TRUE, ignore.case = TRUE)
dist.mat <- ifelse(is.na(dist.mat.nm), dist.mat.ad, dist.mat.nm)
dist.mat2 <- ifelse(is.na(dist.mat.ad), dist.mat.nm, dist.mat.ad)
which.match <- function(x, nm) return(nm[which(x == min(x))[1]])
which.index <- function(x, nm) return(which(x == min(x))[1])

source2.matches.name <- apply(dist.mat, 1, which.match, nm = source2$name)
source2.name.index <- apply(dist.mat, 1, which.index, nm = 
source2$names[source2.matches.name])

The desired result is a data frame that contains source1$name, and columns for the best 5 matches based on lev distance using adist, as well as source1$address and its best 5 matches. Perhaps something using top_n from dplyr? If anything is unclear let me know. Any help is much appreciated. Thanks.

Upvotes: 0

Views: 191

Answers (1)

Rui Barradas
Rui Barradas

Reputation: 76402

If I understand the question, the following does what you want.
First I will rerun the code line that creates dist.mat.ad, since your code had an error, it refers to columns address.full when they are named address.

dist.mat.ad <- adist(source1$address, source2$address, partial = TRUE, ignore.case = TRUE)

Now the results you want.

imat <- apply(dist.mat.nm, 1, order)[1:5, ]
top.nm <- data.frame(name = source1$name)
tmp <- apply(imat, 1, function(i) source2$name[i])
colnames(tmp) <- paste("top", 1:5, sep = ".")
top.nm <- cbind(top.nm, tmp)

imat <- apply(dist.mat.ad, 1, order)[1:5, ]
top.ad <- data.frame(address = source1$address)
tmp <- apply(imat, 1, function(i) source2$address[i])
colnames(tmp) <- paste("top", 1:5, sep = ".")
top.ad <- cbind(top.ad, tmp)

The results are in top.nm and top.ad.
Final clean up.

rm(imat, tmp)

Upvotes: 1

Related Questions