# Loose string matching for words in postal addresses

I'm trying to compare every element in a vector with every other.

From a dataframe of addresses, I extract streets for a zip code. And a vector of these street strings (like "123 main avenue") is the input.

streets <- c ("123 main avenue", "123 main ave", "456 paul st",
"456 paul street", "1 r parkway", "1 r pkwy")


I want to test for similarity of strings (like the one before with "123 main ave"). I could use string distance on the substrings, but preferred grep.

I want to avoid the nested for loop, but cannot think of anything better. Here's what I am trying to do:

compare = function(postal_code)
{
streets <- as.vector(props[props$Zip == postal_code,]["Street"]) cnt <- lengths(streets)[1][1] #Assume two streets "123 main ave" and "123 main avenue" for (i in 1:cnt) { for (j in 1:cnt) { prop1 = streets[[1]][i] prop2 = streets[[1]][j] #split "123 main avenue" into parts prop1_parts = strsplit(trimws(prop1), ' ') prop2_parts = strsplit(trimws(prop2), ' ') prop1_parts_count = length(prop1_parts[[1]]) prop2_parts_count = length(prop2_parts[[1]]) #only if the parts of the two streets are equal if (prop1_parts_count == prop2_parts_count) { #compare apples to apples: 123 with 123, main with main, and ave with avenue for (x in 1:prop1_parts_count) { part1 = prop1_parts[[1]][x] part2 = prop2_parts[[1]][x] if (part1 == part2) { matched = matched & TRUE } else { #ignore number parts like 123 if (any(grep("[[:alpha:]]", part1)) & any(grep("[[:alpha:]]", part2))) { #check if avenue is in ave or ave is in avenue if (any(grep(part1, part2)) | any(grep(part2, part1))) { matched = matched & TRUE print(paste0(prop1, '-', prop2)) } } else { matched = matched & FALSE break #to pass to the next string } } } } } } }  For a vector with 104 streets, the comparisons should be (104*103)/2; but with this code it is 104**2; and for these 10816 comparisons, the benchmark is: I compiled the function as well but no improvement in the execution time. Any elegant/quick way to improve this code is appreciated. ## 1 Answer You'd better use another strategy: 1. Find a table of all usual abbreviations used in postal addresses. 2. Create a new column normalized_street in your original dataframe by replacing all occurrences of abbreviations in column Street by the corresponding full words. 3. Perform an exact self-join on your original dataframe, by Zip and normalized_street. Why I think it's better: • It will allow you to avoid false positives like cat street / catfish street • The exact self-join will be very efficient • Your code will be simpler, cleaner, and entirely vectorized There are lots of things to say about your current code. I'll just point out a few mistakes so that you can avoid them next time: • matched is not initialized • as.vector(props[props$Zip == postal_code,]["Street"]) can be written in a simpler way: props[props\$Zip == postal_code, "Street"]
• Since streets is a vector, you get its length using length(streets)
• For the same reason, you have to use streets[i] instead of streets[[1]][i]
• You should use grepl() instead of any(grep())
• Thanks for the inputs. Will try the lookup-normalized approach and report back. the initialization of matched to TRUE got cut out :(. Fixed the mistakes you pointed out; exec time was down by 1s; may be with the approach above, it should get optimized. – skrubber Jul 21 '17 at 20:55