Loose string matching for words in postal addresses

Question

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.

Answer 1

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